Prima di acquistare dell'hardware, è sempre una buona idea prendere in considerazione il progetto del sistema che si intende realizzare. Fondamentalmente ci sono due questioni relative al progetto di un sistema Beowulf: il tipo di nodi (cioè di computer) da usare e il modo in cui tali nodi sono connessi. C'è una questione relativa al software, che può influire sulle decisioni che riguardano l'hardware: la libreria di comunicazione (API). Nel seguito di questo documento verrà fatta una discussione più dettagliata riguardo all'hardware e al software di comunicazione.
Anche se il numero di possibilità non è elevato, quando si costruisce un Beowulf, ci sono comunque alcune importanti decisioni di progetto da prendere. Poiché la scienza (o l'arte) della "computazione parallela" ha molte interpretazioni differenti, qui di seguito ne viene data un'introduzione. Se non ti piace leggere materiale di rassegna, puoi saltare questa sezione, ma sei vivamente invitato a leggere la sezione Fattibilità prima di prendere le decisioni finali relative all'hardware.
Questa sezione fornisce una rassegna sui concetti della computazione parallela. NON è una descrizione completa né esauriente della scienza e tecnologia della computazione parallela. È una breve descrizione delle questioni che possono essere importanti per un progettista o per un utente Beowulf.
Mentre progetti e costruisci il tuo Beowulf, molte delle questioni che vengono descritte sotto diventeranno importanti nel processo delle tue decisioni. A causa della natura dei suoi componenti, un supercomputer Beowulf richiede che si prendano attentamente in considerazione molti fattori che adesso vengono a essere sotto il nostro controllo. In generale, non è così difficile comprendere le questioni relative alla computazione parallela. In realtà, una volta che le questioni sono comprese, le tue aspettative saranno più realistiche e avrai una maggiore probabilità di successo. A differenza del "mondo sequenziale", in cui la velocità del processore è considerato il solo fattore che ha la massima importanza, la velocità dei processori nel "mondo parallelo" è solo uno dei vari fattori che determineranno le prestazioni e l'efficienza del sistema complessivo.
La computazione parallela può assumere molte forme. Dal punto di vista dell'utente è importante considerare vantaggi e svantaggi di ciascuna metodologia. La sezione seguente tenta di dare diverse prospettive sui metodi della computazione parallela e indica dove va a cadere una macchina Beowulf all'interno di questo continuum.
È importante rispondere a questa domanda. Usare 8 CPU per eseguire un word processor suona un po' "over-kill" -- e in effetti lo è. Ma cosa dire di un server web, una base di dati, un programma di rendering o uno schedulatore di progetti? Forse più CPU potrebbero essere d'aiuto. E cosa dire di una simulazione complessa, un codice che studia la dinamica dei fluidi, o un'applicazione di estrazione di dati? In queste situazioni, più CPU sono sicuramente d'aiuto. In effetti, sistemi con CPU multiple vengono usati per risolvere sempre più problemi.
Generalmente la successiva domanda è: "Perché ho bisogno di due o quattro CPU? Aspetterò semplicemente il chip iper-turbo 986." Ci sono varie ragioni:
Se hai bisogno di velocità - sia a causa di un problema di limiti della computazione che di un problema di limiti nell'I/O, vale la pena considerare il parallelismo. Poiché la computazione parallela è implementata in vari modi, per risolvere il tuo problema con il parallelismo dovranno essere prese alcune decisioni molto importanti. Queste decisioni possono avere effetti decisivi sulla portabilità, la performance e il costo della tua applicazione.
Prima di entrare nei dettagli tecnici, diamo uno sguardo a un "problema di computazione parallela" reale, usando un esempio con il quale abbiamo familiarità: l'attesa in lunghe code a un negozio.
Immaginiamo un grande negozio con 8 registratori di cassa raggruppati insieme nella parte anteriore del negozio. Assumiamo che ogni cassiere/registratore corrisponda a una CPU e ogni cliente a un programma di computer. La dimensione del programma di computer (il carico di lavoro) corrisponde alla dimensione della spesa del cliente. Per illustrare i concetti della computazione parallela possono essere usate le seguenti analogie.
Un solo registratore di cassa è aperto (in uso) e deve servire ogni cliente, uno alla volta.
Esempio relativo ai computer: MS DOS
Un solo registratore di cassa è aperto, ma adesso viene servita solo una parte di una spesa per volta, si passa al prossimo cliente e si serve una parte della sua spesa. I clienti "sembrano" muoversi lungo la coda insieme, ma se oltre a te non ci sono altri clienti, verrai servito più velocemente.
Esempio relativo ai computer: UNIX, NT utilizzante una singola CPU
Adesso apriamo più registratori di cassa nel negozio. Ogni cliente può essere servito da un registratore di cassa separato e la coda può muoversi più velocemente. Questa viene chiamata SMP - Multi-elaborazione simmetrica (Symmetric Multi-processing). Sebbene ci siano più registratori di cassa aperti, continuerai a non muoverti lungo la coda più velocemente del caso in cui ci sei solo tu e un solo registratore di cassa.
Esempio relativo ai computer: UNIX e NT con più CPU
Se "spezzi" gli articoli della tua spesa, puoi muoverti più velocemente sulla coda usando più registratori di cassa allo stesso tempo. Innanzitutto, dobbiamo ipotizzare un gran guadagno, perché il tempo investito nello "spezzare la spesa" deve essere riguadagnato usando più registratori di cassa. In teoria, dovresti muoverti lungo la coda "n" volte più veloce di prima, dove "n" è il numero di registratori di cassa. Quando i cassieri hanno bisogno dei totali parziali, possono scambiarsi velocemente informazioni guardando e parlando a ogni altro registratore di cassa "locale". Possono anche curiosare ai registratori di cassa vicini per cercare informazioni di cui hanno bisogno per lavorare più velocemente. Comunque, c'è un limite al numero di registratori di cassa che possono trovarsi in un punto del negozio.
La legge di Amdal, inoltre, limiterà la velocità dell'applicazione alla porzione sequenziale del programma più lenta.
Esempio relativo ai computer: UNIX oppure NT con extra CPU sulla stessa scheda madre che eseguono programmi multi-threaded.
Al fine di migliorare la performance, il negozio aggiunge 8 registratori di cassa sul retro del negozio. Poiché i nuovi registratori di cassa sono lontani da quelli che si trovano sul davanti, i cassieri devono chiamare questi al telefono per comunicare i loro totali parziali. Tale distanza aggiunge un sovraccarico (di tempo) alla comunicazione tra cassieri, ma se le comunicazioni sono minimizzate, ciò non costituisce un problema. Se fai una spesa davvero molto grande, tale da richiedere tutti i registratori di cassa, allora, come avveniva prima, la velocità può essere aumentata usando tutti i registratori di cassa allo stesso tempo, e il sovraccarico va riconsiderato. In qualche caso, il negozio può avere singoli registratori di cassa (o gruppi isolati di registratori di cassa) sparsi per il negozio: ogni registratore di cassa (o isola) deve comunicare via telefono. Poiché tutti i cassieri possono comunicare l'un l'altro attraverso il telefono, non è molto importante dove si trovano.
Esempio relativo ai computer: una o più copie di UNIX o NT con più CPU sulla stessa o su differenti schede madri, che comunicano attraverso messaggi.
Gli scenari descritti sopra, sebbene non esatti, sono una buona rappresentazione dei vincoli posti sui sistemi paralleli. A differenza di sistemi con singola CPU (o registratore di cassa), qui va presa in considerazione la possibilità di comunicazione tra diverse CPU.
Di seguito vengono presentati i metodi e le architetture comuni della computazione parallela. Sebbene la presente trattazione non sia sicuramente esauriente, è sufficiente per comprendere le questioni fondamentali relative a un progetto Beowulf.
Ci sono fondamentalmente due modi in cui viene messo insieme l'hardware dei computer paralleli:
Un tipico Beowulf è un insieme di macchine con singola CPU, connesse usando fast Ethernet ed è, pertanto, una macchina a memoria locale. Una macchina SMP a 4 vie è una macchina a memoria condivisa e può essere usata per fare computazioni parallele - applicazioni parallele che comunicano usando la memoria condivisa. Proprio come nell'esempio dell'analogia negozio-computer, le macchine a memoria locale (registratori di cassa individuali) possono essere scalati a grandi numeri di CPU, mentre il numero di CPU in macchine a memoria condivisa (il numero di registratori di cassa che si possono mettere in un punto) può essere limitato a causa di conflitti nell'accesso alla memoria.
È possibile, comunque, connettere molte macchine a memoria condivisa per creare una macchina a memoria condivisa "ibrida". Queste macchine ibride "appaiono" all'utente come una grande macchina SMP singola e sono spesso chiamate macchine NUMA (accesso in memoria non uniforme), perché la memoria globale vista dal programmatore e condivisa da tutte le CPU può avere differenti ritardi. A qualche livello, comunque, una macchina NUMA deve "inviare messaggi" tra gruppi di memorie localmente condivise.
È anche possibile connettere macchine SMP come nodi di computazione a memoria locale. Le tipiche schede madri della CLASSE I hanno 2 o 4 CPU e sono usate spesso come un mezzo per ridurre il costo del sistema complessivo. Lo schedulatore interno di Linux determina come queste CPU ottengono le risorse condivise. L'utente non può (a questo punto) assegnare uno specifico task a uno specifico processore SMP. L'utente può, comunque, iniziare due processi indipendenti oppure un processo multithreaded e aspettarsi un aumento di performance rispetto a un sistema avente una singola CPU.
Ci sono fondamentalmente due modi per "esprimere" la concorrenza in un programma:
Esistono altri metodi, ma questi due sono quelli più largamente usati. È importante ricordare che l'espressione della concorrenza non è necessariamente controllata dall'hardware sottostante. Sia lo scambio di messaggi che i thread possono essere implementati su SMP, NUMA-SMP e cluster - sebbene, come spiegato sotto, l'efficienza e la portabilità sono questioni importanti.
Storicamente, la tecnologia dello scambio di messaggi rifletteva il modello dei primi computer paralleli a memoria locale. I messaggi richiedono un'operazione di copia dei dati, mentre i thread, corrispondentemente, usano dati. I ritardi e le velocità alle quali i messaggi possono essere copiati sono i fattori limitanti dei modelli a scambio di messaggi. Un messaggio è piuttosto semplice: qualche dato e un processore destinatario. Le API comuni per lo scambio di messaggi sono PVM oppure MPI. Lo scambio di messaggi può essere implementato efficientemente usando i thread, quindi i messaggi funzionano bene sia su macchine SMP che tra cluster di macchine. Il vantaggio nell'uso dei messaggi su una macchina SMP, invece del normale uso dei thread, è che se decidi in futuro di usare cluster, è facile aggiungere macchine o scalare le tue applicazioni.
I thread del sistema operativo sono stati sviluppati poiché i progetti di SMP (multi-elaborazione simmetrica) a memoria condivisa consentivano una comunicazione e sincronizzazione molto veloci, tra parti concorrenti di un programma. I thread funzionano bene su sistemi SMP perché la comunicazione avviene attraverso la memoria condivisa. Per questa ragione l'utente deve isolare i dati locali da quelli globali, altrimenti i programmi non gireranno nel modo corretto. A differenza dei messaggi, con i thread una buona parte di copiatura può essere evitata, perché i dati sono condivisi dai processi (thread). Linux supporta i thread POSIX. Il problema con i thread è che è difficile estenderli oltre una macchina SMP e poiché i dati sono condivisi dalle CPU, le questioni relative alla coerenza delle cache può contribuire al sovraccarico. Estendere i thread oltre i limiti della SMP in modo efficiente richiede la tecnologia NUMA che è costosa e non supportata da Linux in forma nativa. I thread sono stati implementati sopra i messaggi ( (http://syntron.com/ptools/ptools_pg.htm)), ma i thread implementati usando i messaggi sono spesso inefficienti.
Riguardo alla performance si può affermare quanto segue:
performance di performance di un scalabilità
una macchina SMP cluster di macchine
---------------- ------------------- -----------
messaggi buona ottima ottima
thread ottima scarsa* scarsa*
* richiede una tecnologia NUMA costosa.
Per poter eseguire un'applicazione in parallelo su più CPU, occorre suddividerla in parti concorrenti. Un'applicazione progettata per una singola CPU, non verrà eseguita più velocemente di un'applicazione per singola CPU su una macchina multiprocessore.
Ci sono alcuni strumenti e compilatori che possono suddividere i programmi, ma parallelizzare il codice, non è un'operazione "plug'n'play". A seconda del tipo di applicazione, parallelizzare il codice può essere facile, estremamente difficile o addirittura impossibile, in base alle dipendenze dell'algoritmo.
Prima di affrontare la questione del software, occorre introdurre il concetto di Fattibilità.
Molte domande relative all'elaborazione parallela, hanno la stessa risposta:
"Dipende dall'applicazione"
Prima di addentrarsi nel problema, c'è un'importante distinzione da fare - la differenza tra CONCORRENTE e PARALLELO. Per il gusto della discussione definiremo così questi due concetti:
CONCORRENTI: parti di un programma che possono essere eseguite indipendentemente.
PARALLELE: parti CONCORRENTI di un programma eseguite da processori diversi nello stesso momento.
La distinzione è molto importante, poiché la CONCORRENZA è una proprietà del programma, mentre il PARALLELISMO è una proprietà della macchina. Idealmente un'esecuzione parallela dovrebbe risultare in prestazioni più veloci. Il fattore limitante nelle prestazioni parallele è la velocità di comunicazione e la latenza fra i nodi (la latenza esiste anche con applicazioni i cui thread sono eseguiti su CPU diverse, a causa della necessità di controllare la coerenza della cache - cache coherency). Molti dei comuni benchmark paralleli sono altamente paralleli, quindi latenza e comunicazione non costituiscono colli di bottiglia. Questo tipo di problema può essere chiamato "ovviamente parallelo". Altre applicazioni non sono così semplici ed eseguire parti CONCORRENTI del programma in PARALLELO potrebbe causare un rallentamento del programma, vanificando così ogni miglioramento di prestazioni ottenuto nelle parti CONCORRENTI del programma. In altre parole, il tempo di comunicazione impiegato deve essere proporzionato con quello impiegato nell'elaborazione, altrimenti l'esecuzione PARALLELA di parti CONCORRENTI è inefficiente.
È compito del programmatore determinare quali parti CONCORRENTI del programma devono essere eseguite in PARALLELO e quali NO. La risposta a ciò determinerà l'EFFICIENZA dell'applicazione. Il grafico che segue, riassume la situazione per il programmatore:
| *
| *
| *
% di | *
appli- | *
cazione | *
| *
| *
| *
| *
| *
| ****
| ****
| ********************
+-----------------------------------
tempo di comunicazione/tempo di elaborazione
In un perfetto computer parallelo, il rapporto fra comunicazione e elaborazione sarebbe uguale, e tutto ciò che fosse CONCORRENTE potrebbe essere implementato in PARALLELO. Sfortunatamente computer paralleli reali, incluse macchine con memoria condivisa, sono soggette agli effetti descritti nel grafico. Chi progetta un Beowulf, tenga in mente questo grafico, perché l'efficienza dell'elaborazione parallela dipende dal rapporto fra tempo di comunicazione e tempo di elaborazione per UNO SPECIFICO COMPUTER PARALLELO. Le applicazioni possono essere portabili fra computer paralleli, ma non c'è garanzia che saranno efficienti su una piattaforma differente.
IN GENERALE, NON ESISTE UN PROGRAMMA PARALLELO PORTABILE ED EFFICIENTE.
C'è ancora un'altra conseguenza del grafico di cui sopra. Poiché l'efficienza dipende dal rapporto comunic./elab., cambiare un solo componente del rapporto non significa, necessariamente, che un'applicazione sarà più veloce. Un processore più veloce, mantenendo la stessa velocità di comunicazione, potrebbe non avere effetti visibili sul programma. Per esempio, raddoppiando o triplicando la velocità della CPU, mantenendo la stessa velocità di comunicazione, potrebbe far sì che alcune porzioni che prima erano eseguite in PARALLELO, adesso siano più efficienti se eseguite SEQUENZIALMENTE. Quindi, adesso potrebbe essere più veloce eseguire le parti che prima erano PARALLELE, come SEQUENZIALI. Inoltre, una inefficiente esecuzione di porzioni parallele, impedirà all'applicazione di raggiungere la sua massima velocità. Quindi l'aggiunta di un processore più veloce potrebbe rallentare l'applicazione (impedendo alla nuova CPU di raggiungere la sua massima velocità, per quell'applicazione).
SOSTITUIRE LA CPU CON UNA PIÙ VELOCE, POTREBBE RALLENTARE L'APPLICAZIONE.
In conclusione, quindi, per sapere se usare o no un'architettura parallela, occorre avere un po' di intuito circa l'adeguatezza di una particolare macchina per un'applicazione. Occorre tener presente svariati fattori, incluso la velocità della CPU, il compilatore, le "message passing API", la rete, ecc. Inoltre occorre tener presente che l'aver tracciato lo schema di un'applicazione non è tutto.
È possibile identificare una porzione del programma in cui è richiesta una pesante elaborazione, ma non è possibile conoscerne il costo in termini di comunicazione. Potrebbe essere che, per un certo sistema, i costi di comunicazione rendano inefficiente l'esecuzione in parallelo del codice.
Una nota finale su un malinteso comune. Spesso viene detto che un programma è PARALLELIZZATO, ma in realtà solo le parti CONCORRENTI lo sono. Per tutte le ragioni dette sopra, il programma non è PARALLELIZZATO. Un'efficiente PARALLELIZZAZIONE è una proprietà della macchina.
Una volta stabilita la necessità della computazione parallela e quindi di costruire un Beowulf, potrebbe essere una buona idea ripensare all'applicazione in base a quanto detto precedentemente.
In generale ci sono due cose che possono essere fatte:
In altri casi, in qualche momento, occorrerà prendere in considerazione i fattori relativi all'efficienza.
In generale possono essere fatte tre cose:
Esaminiamole una per una
Questo passo è spesso considerato come "parallelizzazione del programma". Le decisioni sulle parallelizzazioni, verranno prese nel passo 2. In questo passo occorre determinare le data dependencies.
Da un punto di vista pratico, le applicazioni possono esporre due tipi di concorrenza: pesanti elaborazioni (macina numeri, "number crunching") e I/O (database). Sebbene in molti casi la concorrenza di elaborazione e I/O sono ortogonali, ci sono applicazioni che li richiedono entrambi. Esistono alcuni strumenti che possono effettuare una analisi di concorrenza sulle applicazioni esistenti. La maggior parte di questi strumenti sono progettati per il FORTRAN. Due sono le ragioni per cui viene utilizzato il FORTRAN: storicamente la maggior parte di applicazioni che effettuano numerosi calcoli sono state scritte in FORTRAN ed è più facile da analizzare. Se non ci sono strumenti disponibili, questo passo può essere complicato, per le applicazioni esistenti.
Senza l'aiuto di strumenti, questo passo può richiedere prove ed errori, o solo provare formulare delle ipotesi. Per ogni specifica applicazione occorre provare a determinare se ha dei limiti di CPU (legati all'elaborazione) o di hard disk (legati all'I/O). Le esigenze di Beowulf possono differire in base alle necessità. Per esempio un problema legato all'elaborazione può aver bisogno di poche CPU molto veloci e una rete molto veloce, mentre un problema legato all'I/O può funzionare meglio con più CPU più lente e una fast Ethernet.
Questa raccomandazione, in genere, è una sorpresa per molte persone, perché è un luogo comune che i processori più veloci sono sempre meglio. Questo è vero se si dispone di un budget illimitato, i sistemi reali possono avere vincoli di costo che occorre valutare. Per i problemi legati all'I/O, c'è una regola poco conosciuta (chiamata Legge Eadline-Dedkov) che è abbastanza utile:
Poiché due computer paralleli con lo stesso indice di prestazioni per la somma delle CPU, quello che ha i processori più lenti (e probabilmente una corrispondente rete di comunicazione più lenta fra i processori) avrà prestazioni migliori per quelle applicazioni che fanno largo uso di I/O.
Mentre la profondità di questa regola va oltre lo scopo di questo documento, potrebbe essere interessante scaricare il documento Performance Considerations for I/O-Dominant Applications on Parallel Computers (Postscript format 109K) (ftp://www.plogic.com/pub/papers/exs-pap6.ps)
Una volta determinato il tipo di concorrenza dell'applicazione, occorre stimare quanto possa essere efficiente in parallelo. Vedere la sezione Software per una descrizione degli strumenti Software.
In assenza di strumenti, occorre provare ad ipotizzare la propria strada, in questa fase. Se un'elaborazione che richiede molta cpu può essere misurata in minuti e i dati possono essere trasferiti in secondi, allora potrebbe essere una buona candidata per la parallelizzazione. Occorre ricordare, però, che se un loop di 16 minuti viene suddiviso in 32 parti, il trasferimento dei dati richiede diversi secondi per parte, allora le cose potranno essere difficili. Si raggiungerà un punto in cui i ritorni sono ridotti.
Ci sono diversi modi per descrivere le parti concorrenti di un programma:
La maggiore differenza fra le due è che l'esplicita è determinata dall'utente, mentre l'implicita è determinata dal compilatore.
PVM o MPI o aggiungere thread usando i thread POSIX (occorre ricordare, però, che i thread non si possono muovere fra piastre madri SMP).
I metodi espliciti sono i più difficili da implementare e da mettere sotto debug. Gli utenti, in genere, includono chiamate a funzioni esplicite in sorgenti standard FORTRAN 77 o C/C++. Alla libreria MPI sono state aggiunte alcune funzioni per rendere più facili da implementare alcuni metodi paralleli standard (ad es. le funzioni scatter/gather). Inoltre è possibile usare librerie standard scritte per computer paralleli. Occorre considerare sempre, però il rapporto fra portabilità ed efficienza).
Per ragioni storiche, la maggior parte dei sorgenti di programmi che effettuano pesanti calcoli ("number crunching") sono scritti in FORTRAN. Per questo motivo, il FORTRAN ha il supporto maggiore (strumenti, librerie, ecc.) per l'elaborazione parallela. Molti programmatori, adesso, utilizzano il C o riscrivono in C vecchie applicazioni scritte in FORTRAN con l'idea che il C permetterà un'esecuzione più veloce. Questo è vero, dal momento che il C è quanto di più vicino ad un linguaggio macchina universale, ma ha anche alcuni svantaggi. L'utilizzo di puntatori, in C, rende estremamente difficile determinare le dipendenze fra i dati. Se avete un programma FORTRAN e pensate di parallelizzarlo, NON CONVERTITELO IN C!
Sono quelli in cui l'utente lascia alcune (o tutte) decisioni di parallelizzazione al compilatore. Esempi sono FORTRAN 90, High Performance FORTRAN (HPF), Bulk Synchronous Parallel (BSP) e un'intera collezione di altri metodi che sono sotto sviluppo.
I metodi impliciti richiedono che l'utente fornisca alcune informazioni circa la natura concorrente dell'applicazione, ma il compilatore, poi, prenderà la decisione di come eseguire, questa concorrenza, in parallelo. Questi metodi forniscono alcuni livelli di portabilità ed efficienza, ma non c'è ancora alcun "modo perfetto" per descrivere un problema concorrente per un'elaborazione parallela.