Teoria dei Numeri con Raspberry PI

Factor5 on PI

Il grande, il piccolo e la mente umana

Impariamo la teoria dei numeri utilizzando il nostro fido Raspberry PI. Con un pizzico di buona volontà scopriremo le ottimizzazioni più spinte.

Tradizionalmente, la teoria dei numeri è quel ramo della matematica pura che si occupa delle proprietà dei numeri interi e contiene molti problemi aperti che possono essere facilmente compresi anche da chi non è un matematico. Capire se un numero sia divisibile o primo, conoscerne i fattori, capire quale sia il legame tra un numero ed un suo divisore sono classici problemi di teoria dei numeri elementare.

Lavorando soprattutto sulle proprietà dei numeri interi, poi, è possibile sfruttare le capacità di elaborazione di un computer, che con i numeri interi ci parla. L’unica accortezza nel manipolare le cifre dei nostri fattori consiste nell’evitare il cosiddetto overflow, ovvero l’utilizzo di un numero più grande di quanto il computer possa rappresentare.

Ma qual è questo limite?

Sistemi operativi a 32 o 64 bit

Quando si parla di sistemi 32-bit o 64-bit, si considerano in genere due fattori chiave: la larghezza dei registri ed il bus di comunicazione. Un registro misura la capacità in bit dei dati che può essere manipolata nella CPU in una singola operazione, mentre il bus indica quante celle di memoria differenti possono essere indirizzate attraverso una singola richiesta di dati.

Ovviamente, a complicare le cose abbiamo avuto sistemi operativi con registri 8 bit di dati e 16 bit di indirizzi (il DOS del processore 8086), 16 bit di dati e 32 bit di indirizzi (i processori 80386SX), abbiamo assistito a scempi come l’indirizzamento segmentato attraverso registri, e registri da 32 bit acceduti unicamente nella loro sezione a 8 bit. Sotto questo punto di vista lo Zilog Z80 ed il Motorola 68000 erano molto più coerenti ed eleganti… ma magari ne parleremo in un altro articolo. Ciò che qui conta è capire che un sistema operativo a 64 bit consente di indirizzare una maggior quantità di memoria e di lavorare con numeri interi più grandi.Teoria dei Numeri - Tipi interi

Quanto esattamente più grandi è presto detto: nella tabella possiamo osservare le estensioni caratteristiche di ciascun formato. Con 32 bit possiamo lavorare al massimo con numeri interi sino al miliardo, mentre con 64-bit si arriva al miliardo di miliardi.

Quando 64 è meglio di 32?

Raramente. Un sistema a 32 bit risulta molto più compatto di un sistema a 64 bit, in quanto tutte le operazioni di caricamento e salvataggio di dati in memoria richiedono solo 4 byte per l’indirizzamento (4 x 8 = 32 bit) anziché 8. Ma le strutture statiche sono più limitate: un database ad esempio potrebbe indicizzare solo 2/4 miliardi di record in modo nativo, richiedendo routine complesse (e time-consuming) per superare tale limitazione.

Anche nell’ambito della teoria dei numeri vale la stessa limitazione, e interi a 64 bit, anche se leggermente più lenti da gestire, sono in genere da preferirsi agli interi a 32 bit.

Forse qualcuno tra i miei lettori ha conosciuto il gioco del Tetris originale di Vadim Gerasimov e Alexey Pajitnov.

Teoria dei numeri e Tetris

Il gioco aveva un limite di punteggio pari a 32767. Superando quel limite si passava direttamente a -32768, -32767, -32766 e così via: il programma, codificato in Pascal a 16 bit, aveva il tipo intero pari a 15 bit + 1 bit di segno, e 2^15 – 1 = 32767. Allo stesso modo gli array statici non potevano eccedere i 65535 elementi, o 2^16 – 1. Oggi nessuno più si sognerebbe di programmare a 16 bit, ma il concetto di limitazione dovuta al sistema operativo è sempre presente, ed è comunque opportuno, quando possibile, tenersi un margine di manovra per ogni evenienza. O si rischia di fare la fine del Volo 501 di Ariane 5, abortito pochi secondi dopo la partenza perché i valori di conversione da floating point a 64 bit hanno provocato un overflow appena convertiti in interi a 16 bit.

Hybrid PI e teoria dei numeri

Il nostro amico Raspy ha un processore ARM (il Cortex) a 64 bit, ed è quindi perfettamente in grado di funzionare per i nostri scopi specifici. Purtroppo il SBC viene fornito con Raspbian, un sistema operativo leggerissimo a 32 bit originante da una distro Linux, per rendere il nostro PI più veloce ed efficiente. E no, con 32 bit non possiamo inventarci le ottimizzazioni consentite con 64: anche se il processore potrà lavorare 64 bit, il sistema operativo si rifiuterà di farlo. E allora?

Allora prendiamo i nostri attrezzi da lavoro e carichiamo un sistema operativo a 64 bit ottimizzato per il Raspberry. Nella vastissima community di sviluppatori, c’è anche chi ha pensato a noi matematici, producendo una distro di Gentoo appositamente per il PI. Ovviamente sono presenti installer sia per il nuovo PI 4 che per il PI3, quello in mio possesso sul quale eseguiremo i nostri test. Non ci dilungheremo qui sull’installazione, dal momento che la guida sul link è completa. Inseriamo la nostra schedina e lanciamo il sistema, quindi controlliamo il risultato del comando uname -a.

Teoria dei Numeri con Raspberry PI

Ecco a voi il Linux PI 64 4.10, con supporto Multi-Processing, e GNU-compliant!

Ottimo. E adesso che abbiamo un PI a 64 bit, come lo sfruttiamo?

Ricerca di fattori con multi-threading

Ora che abbiamo un ambiente Linux totalmente compatibile, dobbiamo scegliere quale software utilizzare per i nostri lavori.

Il Raspberry PI ha una ricchissima serie di librerie Python utili per il prototyping di applicazioni, per la creazione di test-case e in linea di massima per tutto ciò che potrebbe servire ad un possessore di SBC per realizzare le proprie applicazioni di controllo IoT. Ma noi vogliamo di più. E’ infatti risaputo che il Python non sia un fulmine di guerra nell’esecuzione di programmi complessi. Un codice non efficientissimo su un sistema di per sé lento non è la scelta migliore per un’applicazione di calcolo matematico. Molto meglio il linguaggio C.

Ma la maggior parte dei programmi scritti in C sono appannaggio di processori Intel, per ARM non c’è nulla, si tende a pensare. Invece il C è stato sviluppato con un occhio di riguardo alla portabilità: se si utilizza una sintassi standard nel codice e nelle chiamate di sistema, il programma scritto per un Pentium compilerà e funzionerà al primo colpo anche sul PI. Anche se utilizza la libreria esterna GMP (Gnu Multi Precision library). E anche se  fa uso di threads attraverso la libreria di sistema pthreads.

Teoria dei Numeri con Raspberry PI

Nell’immagine vediamo il mio programma per la ricerca di fattori dei numeri di Mersenne, Factor5. Viene richiesto al programma di cercare tutti i possibili fattori di 2^3321928097 – 1 compresi tra 3 e 1.152.921.504.606.846.975 (2^60 – 1).   La finestra in alto a sinistra utilizza un solo thread, quella in alto a destra utilizza due threads, quella in basso a sinistra utilizza quattro threads del mio Raspy 3. La finestra in basso a destra utilizza invece 4 threads del mio Intel 9800X a 4.5 GHz e memoria quad-channel.I tempi di esecuzione sono esposti di seguito:

Si tenga presente che il povero Cortex-A53 non aveva alcun sistema di raffrreddamento, e che il nuovo PI 4 risuta di circa 2-3 volte più veloce del PI 3.

Quanto mi costi?

Si tenga presente che in questo test non vogliamo paragonare la potenza elaborativa di un Intel della famiglia X con un processore ARM: è evidente che Intel è più veloce, e tuttavia, è il caso di presentare un paio di considerazioni sul confronto.

Il numero di operazioni (costo) rispetto al consumo ad esempio. Il PI a pieno carico, con un alimentatore da 2.5A consuma circa 7W per ora, o 7 x 24 x 30 = 5 kW al mese. Se 1 kW costa 20 centesimi di euro, un PI 3 a piena potenza ci costerà 1 euro di corrente elettrica al mese. Il processore Intel 9800X, invece, con tutto il sistema che si porta dietro (alimentatore, scheda video, dissipatori, LED, motherboard, RAM, disco, USB…) consuma almeno 400W per ora, anche se io utilizzerei come minimo un alimentatore Gold da 500W. 500W per ora significa 500 x 24 x 30 = 360 kW per complessivi 72 euro al mese.

Quindi se volessimo avere il medesimo consumo con il nostro Raspy, potremmo utilizzare 72 SBC. Ora attenzione: dai test effettuati il processore Intel 9800X risulta 8 volte più veloce del singolo PI, ma questo significa che a parità di potenza erogata il nostro Raspberry PI risulta 9 volte più efficiente a livello di singola istruzione!

Quanto ci costerebbero 72 PI? Ad un prezzo di mercato di 30 euro a scheda, con sconto per numero di pezzi, spenderemmo 2.160 euro più il sistema di alimentazione, che rappresenta il prezzo dell’altro sistema con processore Intel 9800X. E’ vero, l’Intel ha 8 cores. Ma se noi acquistassimo 30/35 PI avremmo comunque un sistema distribuito con un rapporto costo/consumo/prestazioni pari alla workstation Intel.

La prima puntata relativa alla Teoria dei Numeri con Raspberry PI termina qui. In una prossima puntata tratteremo l’argomento clustering per i SBC, e vedremo come non sempre l’aumento delle schede corrisponde all’aumento delle prestazioni: occorre tener conto anche della dissipazione del calore, dei carichi transienti, della latenza nelle trasmissioni dei dati in rete e così via. Ma per applicazioni a parallelismo massiccio (embarassingly parallel) in cui la comunicazione inter-processo è minima. queste soluzioni possono tranquillamente lottare ad armi pari con sistemi ben più blasonati.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.