Il Jetson Nano è un SBC nato per risolvere problemi legati al Machine Learning (ML) ed alla AI, ma il suo cuore CUDA soddisferà appassionati di grafica e calcolo.

Un numero si dice primo quando è divisibile per 1 e per se stesso.

I numeri di Mersenne sono descritti come potenze di due meno 1, con esponente primo (2^P-1).

I primi numeri primi di Mersenne sono rappresentati nella tabella seguente:

P	2P-1	Scoperto da	Anno
2	22-1	Matematici greci	c. 500 a.C
3	23-1	Matematici greci	c. 500 a.C.
5	25-1	Matematici greci	c. 275 a.C.
7	27-1	Matematici greci	c. 275 a.C.
13	213-1	Anonimo	1456
17	217-1	Pietro Cataldi	1588
19	219-1	Pietro Cataldi	1588
31	231-1	Leonhard Euler	1772
61	2P-1	Ivan Mikheevich Pervushin	1883
89	2P-1	R. E. Powers	Giugno 1911

Ovviamente esistono diversi esponenti che, pur essendo primi, non rendono primo il relativo numero di Mersenne. Un esempio per tutti:

2¹¹-1 = 2047 = 23 x 89

In realtà i numeri primi di Mersenne sono una eccezione, non la regola: a tutt’oggi se ne conoscono solo 51, compresi tra 3 e 2^82.589.933-1.

Il problema con questi numeri è la crescita delle cifre che li compongono, esponenziale per definizione. Crescita che rende difficile il trovare possibili divisori.

Fattori dei numeri di Mersenne

Non ci addentreremo in profondità nei meandri della teoria dei numeri. Il margine di questo blog è troppo ristretto per riuscirci correttamente. Vale però la pena ricordarne alcune caratteristiche che li rendono più facilmente “avvicinabili” dalle attuali tecniche di calcolo.

Il fattore di un numero di Mersenne ha sempre la forma seguente: f = 2 * k * P + 1, dove P è l’esponente del numero e k è un numero intero che parte da 1. Tuttavia, anche se diventa semplice creare un vettore composto di tutti i fattori possibili, la loro quantità è talmente elevata (2^P-1) da risultare inavvicinabile. Per P = 1.000 avremmo un milione di fattori diversi da testare. Per P = 1.000.000 i candidati diverrebbero mille miliardi.

E allora?

Caratteristiche della ricerca dei fattori di numeri di Mersenne

Allora abbiamo dalla nostra parte altre euristiche. Ad esempio è possibile dimostrare che un fattore primo di un numero di Mersenne, diviso per 8, dà un resto pari a 1 o 7. Questo significa che possiamo eliminare tutti i fattori potenziali divisibili per 2, ovvero un buon 50%. Inoltre un fattore f, per essere un divisore del numero di Mersenne originale, diviso per 8 non può dare resto 3 o 5. Il che ci permette di eliminare un altro 25% dei fattori. Con una semplice operazione di estrazione del modulo (resto) riusciamo ad eliminare il 75% dei potenziali fattori. Niente male!

Purtroppo però il 75% di mille miliardi è ancora superiore a 12 miliardi. Rimane una cifra difficilmente avvicinabile con un approccio a forza bruta.

Possiamo applicare il seguente algoritmo.

1. Creiamo tre vettori di interi, A, B e C nei quali porre il nostro k. A = {0, 3, 6, 9, 12, 15, 18, 21, 24…}. B = {1, 4, 7 ,10, 13, 16, 19, 22, 25…}. C = {2, 5, 8, 11, 14, 17, 20, 23, 26…}.
2. Uno di questi tre vettori (poniamo sia C) conterrà tutti i valori di k per cui f = 2*k*P+1 è divisibile per 3 (e quindi non divide il numero di Mersenne). Possiamo eliminarlo.
3. Sugli altri due vettori A e B, cerchiamo il primo valore di k per cui f = 2*k*P+1 è divisibile per 5, e lo cancelliamo.
4. Cancelliamo poi tutti i valori posti a distanza di multipli di 5 dal k originario. Se ad esempio f = 2*k*P+1 è divisibile per 5 per k = 3, cancelleremo da A il 3, il 18, il 33 e così via.
5. Agiremo nello stesso modo sul vettore di interi B.
6. Sugli stessi vettori potremo operare eliminando i multipli del 7 e dell’11.
7. A questo punto, giocando con l’aritmetica modulare vista in precedenza, ci ritroviamo con 4 * 3 * 5 * 7 * 11 = 4620 classi resto.
8. Ne utilizzeremo solamente 960 (quelle che ci daranno k per cui f = 2*k*P+1 non è divisibile).
9. In pratica resteremo con poco più del 20% dei candidati iniziali, dopo aver effettuato meno di 20 operazioni.
10. Utilizziamo un vettore di bit sufficientemente ampio per mantenere i valori di k da utilizzare. Così minimizzeremo tempi e spazi di spostamento nella memoria locale della GPU.
11. I vettori determinati in tal modo vengono quindi sottoposti ad un ulteriore sieving con i successivi numeri primi. In genere con meno di 100.000 primi si elimina il 95% dei candidati.
12. Utilizziamo 2 o 3 stream per parallelizzare ulteriormente il flusso di operazioni da effettuare.
13. Ogni computing unit della nostra GPU calcolerà il fattore f = 2*k*P+1 su ciascuno dei k rimanenti, e controllerà se f divide il numero di Mersenne.
14. In caso positivo il fattore f verrà restituito alla routine chiamante. Il numero esaminato ha un  fattore, e non è quindi primo.

Performance dell’algoritmo

L’algoritmo di base si presta bene alla parallelizzazione, ma possiamo utilizzare qualche altro trucco di programmazione per ottimizzarlo ulteriormente. Ad esempio è possibile utilizzare interi a 24 bit anziché i classici interi a 32 bit. A causa della particolare circuitazione delle schede Nvidia, alcune operaazioni sugli interi vengono eseguite più velocemente con questo formato.

Ma 24 bit sono pochi, specialmente se contiamo di utilizzaremolte cifre significative. Occorre quindi mettere mano al codice e creare una routine di moltiplicazione in multipla precisione. Una routine che utilizzi ove possibile chunks da 24 bit. Con 3 chunks abbiamo un intero a 71 bit, con 4 chunks arriviamo a 95 bit (più lo spazio per eventuali errori di overflow).

Per le moltiplicazioni potremmo scegliere l’algoritmo della moltiplicazione/esponenziazione modulare di Montgomery, ma risulta di non facile parallelizzazione: meglio optare per la Barret Reduction. Si tratta di un algoritmo progettato per ottimizzare l’operazione di estrazione del modulo c = a mod n, partendo dal presupposto che n sia costante, ed a sia minore di n², rimpiazzando le operazioni di divisione computazionalmente più costose con moltiplicazioni. Per la cronaca, la principale motivazione di Barrett nel considerare questo metodo fu l’implementazione dell’algoritmo RSA. In esso i valori in questione eccedono sicuramentela misura di una machine word.

Dalla teoria alla pratica

Il nostro amico Oliver Weihe, che scrive su www.mersenneforum.org ,  ha messo in pratica i dettami appena esposti. Ne è uscito mfaktc, un programma di calcolo parallelo per la ricerca di fattori dei numeri di Mersenne basato su CUDA. Il programma è estremamente ottimizzato e potente. Di seguito riportiamo la classica tabella dei tempi. Avremo un’idea dell’ordine di efficienza che l’architettura CUDA presente anche in Jetson Nano può garantire.

Testeremo il numero di Mersenne 2^189.503.747-1 alla ricerca di fattori compresi tra 2⁷³ e 2⁷⁴ (ovvero 24.919.647.009.180 < k < 49.839.294.025.881) utilizzando il programma mfaktc per CUDA ed il programma di George Woltman mprime, ottimizzato in assembler su Intel per sfruttare memoria quad-channel, multithreading e istruzioni vettoriali AVX-512.

Sistema	cores	Frequency	timing
Intel 9800X (single core)	1	4200	6h 15'
Intel 9800X (8 cores)	8	3800	43'
Nvidia GT 710	192	954	8h 20'
Nvidia Jetson Nano	128	921	8h 43'
Nvidia RTX 2060	1920	1710	7' 52"

È evidente come l’efficienza del calcolo parallelo sotto CUDA non è in discussione. Una workstation professionale, spinta al massimo della propria velocità con tutti i cores attivi, è ancora almeno una cinquantina di volte più lenta di una scheda GPU di categoria medio-alta. Almeno rispetto ai calcoli con numeri interi. Vedremo infatti in un prossimo articolo come con il passare ad operazioni in virgola mobile, l’architettura CUDA tenderà a diminuire le proprie prestazioni di un fattore 32.

Come si comporta l’architettura CUDA del Jetson Nano in questo frangente?

Intanto ricordiamo che non abbiamo tenuto in conto parametri come clock rate e bus width della memoria nelle schede CUDA. La GT 710 ed il Jetson Nano non sono stati progettati per muovere quantitativi di dati particolarmente rilevanti in memoria. DI conseguenza tali parametri  sono stati tenuti sufficientemente bassi per miglirare l’eficienza energetica ed i costi. Ovviamente in questo caso particolare la limitata banda passante e la velocità di accesso penalizzano le prestazioni del Jetson Nano. Esse risultano tuttavia allineate a quelle di un discreto Core i3 di classe 8300.

Come si evince dall’immagine, il nostro Jetson Nano riesce a completare ciascuna delle 960 classi resto da controllare in circa 32 secondi. La ricerca di fattori di un numero di 60 milioni di cifre è effettuata in un delta di circa 24 trilioni di candidati. Richiede meno di nove ore. Il tutto per un costo inferiore ai 100 euro, ed un consumo di circa 10W per ora a pieno carico.

La dicitura GHz-d/day è una misura derivante dalle metriche utilizzate dagli appassionati di calcolo. Nasce dalla necessità di avere un valore non legato al microcodice utilizzato, al sistema operativo, alla lunghezza in bit dei registri o dell’ampiezza del bus. Si è voluto definire 1 GHz-d il lavoro (di fattorizzazione o calcolo di primalità) di un Pentium con clock a 1 GHz in un giorno. In tale ambito, il Jetson Nano effettua lo stesso carico di calcoli effettuato da14 vecchi pentium a 2 GHz.

Considerazioni finali

Il Jetson Nano ha un piccolo cuore CUDA in grado di offrire non poche soddisfazioni agli appassionati di grafica e calcolo numerico. Anche se progettato specificamente per risolvere problemi legati al Machine Learning ed alla AI. Lo vedremo meglio nei prossimi articoli.

Maggiori informazioni sui numeri di Mersenne potrete trovarle su www.mersenneforum.org, un forum di appassionati di matematica e informatica.

Se invece vi interessa il calcolo distribuito in ambito matematico, seguite il link tutto italiano dedicato al Team_Italia.

Link utili:

• Jetson Nano development kit