|
admin
Webmaster
Regione: Italy
Prov.: Pisa
Città: Capannoli
24662 Messaggi |
 Inserito il - 09/09/2003 : 10:38:27
|
Sistemi di calcolo parallelo
di: Oscar Bettelli
Negli ultimi anni sono state delineate le principali caratteristiche architetturali delle macchine parallele conformemente ai modelli teorici di calcolo parallelo e alle metriche usate per misurarne le prestazioni.
Sebbene attualmente vi siano macchine parallele che vengono impiegate come macchine dedicate per supportare applicazioni specifiche (trattamento di immagini, robotica, visione, ecc.), è sempre più diffusa la necessità di avere a disposizione sistemi di tipo general-purpose. Per soddisfare questa richiesta è necessario un modello di macchina astratta standard che svolga il ruolo che il modello di Von Neumann ha svolto per gli elaboratori sequenziali.
La più famosa e accettata classificazione delle architetture per i sistemi paralleli è quella proposta da M.J.Flynn. Secondo questa classificazione, le due più importanti caratteristiche di un elaboratore sono: il numero di flussi di istruzioni che esso può processare ad ogni istante, e il numero di flussi di dati su cui esso può operare simultaneamente. Combinando queste due caratteristiche è possibile ottenere le seguenti quattro classi architetturali:
SISD (Single Instruction stream – Single Data stream)
SIMD (Single Instruction stream – Multiple Data stream)
MISD (Multiple Instruction stream – Single Data stream)
MIMD (Multiple Instruction stream – Multiple Data stream)
La classe SISD comprende l’architettura tradizionale di Von Neumann che è quella usata da tutti i calcolatori convenzionali, in cui il singolo processore obbedisce ad un singolo flusso di istruzioni (programma sequenziale) ed esegue queste istruzioni ogni volta su un singolo flusso di dati.
Alla classe SIMD appartengono le architetture composte da molte unità di elaborazione che eseguono contemporaneamente la stessa istruzione ma lavorano su insiemi di dati diversi. Generalmente, il modo di implementare le architetture SIMD è quello di avere un processore principale che invia le istruzioni da eseguire contemporaneamente ad un insieme di elementi di elaborazione che provvedono ad eseguirle. Il processore principale spesso è ospitato all’interno di un calcolatore convenzionale che provvede a supportare anche l’ambiente di sviluppo. I sistemi SIMD sono utilizzati principalmente per supportare computazioni specializzate in parallelo.
La classe MISD, in cui più flussi di istruzioni (processi) lavorano contemporaneamente su un unico flusso di dati, non è stata finora utilizzata praticamente. È da notare che, mentre nella classe SIMD la granularità, ovvero la dimensione delle attività eseguibili in parallelo, è quella delle istruzioni, nella classe MISD e in quella MIMD la granularità è quella dei processi, programmi composti da più istruzioni.
Il modello rappresentato dalla classe MIMD, in cui più processi, eventualmente creati dinamicamente, sono in esecuzione contemporaneamente su più processori ed utilizzano dati propri o condivisi, rappresenta una evoluzione della classe SISD. Infatti, la realizzazione di queste architetture avviene attraverso l’interconnessione di un numero elevato di elaboratori di tipo convenzionale. I sistemi con architettura MIMD sono oggi fra quelli più studiati e si può presumere che essi rappresentino il punto di partenza per la costruzione di macchine parallele di tipo general-purpose.
Sebbene la tassonomia di Flynn sia in grado di rappresentare alcuni aspetti fondamentali nella maggior parte delle architetture parallele, essa non è in grado di esplicitare pienamente tutte le caratteristiche interessanti per un programmatore. Infatti, essa non è in grado di distinguere fra architetture a memoria condivisa e architetture a memoria distribuita. Inoltre, in essa non trovano adeguata collocazione i calcolatori vettoriali, le macchine data-flow e quelle a riduzione che sono utilizzate come architetture parallele per la implementazione di linguaggi funzionali.
In particolare è possibile introdurre una ulteriore sottoclassificazione:
SIMD
Processori vettoriali
Array processor
Array sistolici
MIMD
Sistemi a memoria distribuita
Sistemi a memoria condivisa
Macchine Data-Flow
Macchine a riduzione
Le architetture SIMD utilizzano un modello di computazione in parallelo di tipo sincrono. Questo modello permette di coordinare l’esecuzione di più operazioni concorrenti attraverso intervalli di tempo che hanno una durata fissa, pari al tempo necessario per eseguire una operazione.
Il modello prevede che una computazione sia suddivisa in più fasi e che all’interno di ogni fase le computazioni possano essere partizionate per esplicitare parallelismo di tipo temporale o spaziale. Nel caso di parallelismo temporale differenti parti di una singola istruzione sono eseguite in parallelo in moduli diversi connessi in cascata (pipeline). Nel caso spaziale gli stessi passi vengono eseguiti simultaneamente su un array di processori identici sincronizzati da un unico controllore.
Il parallelismo temporale è stato utilizzato nella costruzione di processori vettoriali con caratteristiche pipeline. Mentre il parallelismo spaziale è stato utilizzato nella realizzazione degli array processor. Entrambe le forme di parallelismo sono state usate nella progettazione degli array sistolici.
I processori vettoriali sono in grado di raggiungere elevate prestazioni nell’elaborazione di applicazioni di calcolo scientifico. Le elevate prestazioni sono dovute principalmente alla presenza di computazioni vettoriali e matriciali, che possono essere elaborate attraverso unità hardware specializzate in grado di effettuare operazioni su vettori in pipeline.
Il parallelismo è esplicitato all’interno di un singolo processore a livello firmware e non è visibile a livello del programmatore.
L’architettura è generalmente costituita da una memoria principale, una unità di controllo scalare ed una vettoriale, registri scalari e vettoriali e da multiple unità funzionali connesse in pipeline che implementano operazioni aritmetiche e booleane sia su grandezze scalari che vettoriali e che sono in grado di funzionare concorrentemente. Le operazioni vettoriali sono inviate all’unità di controllo vettoriale che le esegue in pipeline attraverso le unità vettoriali. Il flusso di dati vettoriali fra la memoria principale e le unità vettoriali è controllato dall’unità di controllo vettoriale.
Per sfruttare appieno la velocità delle unità funzionali è necessario disporre di una elevata banda di memoria. A tale scopo le informazioni aventi indirizzi contigui sono memorizzate in moduli contigui. È possibile quindi che gli elementi di un vettore, memorizzati in indirizzi consecutivi, possano essere letti e scritti contemporaneamente. Una importante tecnica che i processori vettoriali utilizzano consiste nel permettere a più unità funzionali vettoriali strutturate in pipeline di evolvere in parallelo utilizzando il flusso dei risultati che provengono da un’unità funzionale come ingresso per un’altra unità funzionale.
Il grande successo dei processori vettoriali è dovuto alla loro facilità di programmazione. Essa può avvenire o attraverso l’estensione di linguaggi sequenziali con istruzioni vettoriali o attraverso compilatori. In quest’ultimo caso il compilatore provvede ad individuare le relazioni di dipendenza fra le istruzioni vettoriali e ad effettuare la traduzione di istruzioni iterative in istruzioni vettoriali.
A differenza dei processori vettoriali che sono in grado di trattare sia istruzioni scalari che vettoriali, un array processor è una architettura in grado di fornire elevate prestazioni solo per programmi che contengano un numero elevato di istruzioni vettoriali.
La classica struttura di un array processor è costituita da una unità di controllo (UC), una memoria programma, e da un array di elementi di elaborazione (PE). La memoria contiene il programma che deve essere eseguito. L’unità di controllo ha il compito di prelevare le istruzioni dalla memoria e di separare le istruzioni scalari da quelle vettoriali. Quelle scalari sono eseguite direttamente dalla UC mentre quelle vettoriali sono inviate a tutti i PE dell’array in parallelo.
La UC attende che il processore più lento abbia terminato di eseguire l’istruzione prima di inviarne una nuova, implementando così il sincronismo della computazione.
Ogni elemento dell’array è dotato di un meccanismo di controllo locale che, basandosi sul proprio stato, è in grado di decidere se eseguire o ignorare le istruzioni che riceve dalla UC. Attraverso un meccanismo di controllo globale, la UC è in grado di determinare correttamente la sequenza delle istruzioni da eseguire.
Una caratteristica importante di un array processor è rappresentata dallo schema di interconnessione che supporta le comunicazioni processore-processore e processore-memoria. Le principali strutture di interconnessione processore-processore, nel caso di memoria distribuita, sono di tipo matrice o ipercubo.
La Connection Machine rappresenta una evoluzione di questo modello architetturale.
Ogni elemento dell’array è una cella composta da un processore e da una memoria locale. Questa strutturazione rimuove la classica suddivisione fra processore e memoria. Le celle possono essere raggruppate per formare strutture dati attive. Su queste strutture possono essere eseguite parallelamente istruzioni di basso livello attraverso i vari processori che agiscono sulle parti locali della struttura dati.
La Connection Machine è composta da celle connesse secondo una topologia ad ipercubo.
Il paradigma che trae maggior vantaggio da queste architetture è quello data-parallel. Questa forma di parallelismo prevede che i dati vengano suddivisi spazialmente ed ogni PE esegua, ad intervalli regolari, su una porzione di dati, la stessa computazione.
Gli array sistolici sono architetture utilizzate nell’elaborazione di segnali e nell’analisi numerica. Un array sistolico è costituito da un insieme di moduli uguali, ognuno con una memoria locale, connessi attraverso semplici strutture regolari (matrici, alberi,…) corrispondenti al grafo della computazione, in modo da mantenere la località nelle comunicazioni.
Negli array sistolici i dati viaggiano in maniera ritmica dalla memoria del computer ospite ai nodi della rete per ritornare nuovamente alla memoria.
Le comunicazioni con l’esterno possono avvenire solo attraverso i nodi che sono distribuiti lungo i bordi. Questo permette di avere un buon bilanciamento fra l’elaborazione parallela, l’accesso alla memoria e le richieste di ingresso-uscita.
Ogni nodo esegue una computazione utilizzando i dati di input e il proprio stato interno e invia il risultato ai nodi vicini sui link di uscita. Tutte le operazioni sono sincronizzate attraverso un clock globale esterno. Gli algoritmi eseguiti su questa architettura sono detti sistolici in analogia col funzionamento della circolazione del sangue che viene pompato dal cuore.
Le architetture MIMD sono caratterizzate da una grande flessibilità che permette a questi sistemi di supportare su una stessa piattaforma hardware diversi modelli computazionali.
Il modello architetturale MIMD può essere suddiviso in sistemi a memoria condivisa detti multiprocessor e sistemi a memoria distribuita conosciuti come multicomputer.
A livello architetturale, i processori del sistema (nodi) cooperano secondo un modello asincrono. Secondo questo modello i vari nodi possono eseguire, in maniera autonoma, più flussi di istruzioni (processi) che usano dati locali o condivisi. I processi su ogni nodo vengono eseguiti facendo riferimento al tempo locale del processore. L’assenza di un tempo globale fa sì che, a differenza del modello sincrono, sia necessario disporre di meccanismi di comunicazione e sincronizzazione per consentire ai vari processi di scambiarsi informazioni sullo stato del sistema.
Se si intende realizzare un modello computazionale asincrono la comunicazione fra processi dovrà avere una semantica non bloccante sia per le primitive di output sia per quelle in input. Un messaggio inviato da un processo è depositato in un buffer, se la primitiva corrispondente non è pronta a ricevere il dato. Il processo che ha inviato il messaggio continua l’elaborazione e successivamente gli verrà segnalato che il messaggio è stato ricevuto. Questi meccanismi di comunicazione riducono la sincronizzazione e favoriscono una esecuzione più parallela dei processi e una loro maggiore indipendenza.
Nel caso di architetture MIMD a memoria condivisa è possibile emulare un modello sincrono o asincrono utilizzando un linguaggio concorrente che utilizzi un modello di cooperazione a memoria globale e disponga di costrutti di sincronizzazione del tipo semafori o monitor.
Questi modelli per la cooperazione fra processi permettono di utilizzare macchine MIMD sia come paradigmi di programmazione a parallelismo esplicito che implicito. Nel caso esplicito, le attività concorrenti sono espresse direttamente come processi del linguaggio concorrente. Nel caso implicito, il programma sorgente è trasformato, mediante compilatori, in una rete di processi cooperanti.
I multicomputer sono programmati attraverso il paradigma di scambio messaggi, attraverso una rete di interconnessione, mentre i multiprocessori usano il modello a memoria condivisa.
Uno dei limiti principali delle architetture di tipo multiprocessor è quello di non poter essere costituite, a causa dei problemi di accesso in memoria e dei ritardi introdotti dalla rete, da molti processori, mostrando così una bassa scalabilità.
I multicomputer sono sistemi caratterizzati da un numero elevato (dalle centinaia alle migliaia) di elaboratori (processore e memoria) ad altissima scala di integrazione, interconnessi da strutture regolari. Ogni elaboratore è dotato di un insieme di elementi di connessione (link) che gli permettono di collegarsi ad altri elaboratori secondo strutture statiche o dinamiche di tipo punto-a-punto. La struttura di interconnessione è scelta con l’obiettivo di mantenere piccola la distanza fra due nodi qualsiasi e di avere un basso numero di link per processore.
Se gli algoritmi utilizzati impongono che la maggior parte degli accessi avvenga su dati locali e i processi hanno un comportamento indipendente, allora il carico sulla rete è notevolmente ridotto e le performance del sistema diventano elevate.
Non sempre gli algoritmi sono caratterizzati da una elevata località. In questi casi, il sistema utilizza pesantemente la rete di comunicazione e necessita di algoritmi di instradamento (routing) dei messaggi per garantire una completa connettività logica fra i nodi. Gli algoritmi di routing utilizzati sono generalmente dinamici, cioè decidono il percorso a tempo di esecuzione e consentono di bilanciare il carico sui vari link in modo da evitare fenomeni di saturazione.
Per ottenere elevate prestazioni in termini di efficienza e scalabilità è necessario che gli algoritmi da eseguire su un multicomputer siano progettati effettuando un adeguato bilanciamento fra il tempo di elaborazione e il tempo per la consegna dei messaggi (granularità dei processi) e definendo opportune strategie per l’allocazione delle attività ai vari nodi di elaborazione mantenendone bilanciato il carico di elaborazione.
Le macchine data-flow e a riduzione sono sistemi caratterizzati da un nuovo approccio alla programmazione parallela. Il modello architetturale usato è sostanzialmente il modello MIMD (cooperazione asincrona fra i nodi ed esecuzione di attività concorrenti), ma il nuovo paradigma computazionale che esse usano è in grado di fornire una visione più astratta dell’architettura.
Diversamente dalla macchina di Von Neumann, in cui le istruzioni sono eseguite sequenzialmente controllate da un program counter, queste architetture basano il loro funzionamento su due modelli computazionali: data-driven e demand-driven.
Il modello data-driven prevede che una istruzione possa essere eseguita solo se tutti gli operandi che essa usa sono disponibili.
Nel modello demand-driven è la richiesta del risultato che fa partire l’esecuzione dell’istruzione che lo deve calcolare.
Entrambi i modelli non utilizzano un program counter e l’esecuzione di una istruzione avviene solo in base alla disponibilità dei dati.
Le macchine data-flow utilizzano un modello data-driven e le macchine a riduzione un modello demand-driven.
Nelle architetture data-flow i meccanismi di controllo della sequenza delle istruzioni tipici della programmazione imperativa non sono presenti. Esse vengono utilizzate per l’esecuzione di programmi funzionali o logici in cui il modello astratto è espresso attraverso un modello data-driven. Questo modello computazionale può essere assimilato ad un modello di computazione concorrente asincrona a scambio messaggi in cui i nodi possono avere granularità pari a quella dei processi o a quella di una singola istruzione. Ogni istruzione può essere implementata come un template, che è composto da un campo operatore, una memoria per ricevere gli operandi, e un campo con l’indicazione dei destinatari a cui spedire il risultato. Per far partire l’esecuzione tutti i valori degli operandi devono essere ricevuti nelle posizioni ad esse riservate nel template. I grafi data-flow sono in grado di esplicitare due forme di parallelismo. La prima forma permette a due nodi di essere eseguiti in parallelo se non vi è dipendenza fra i dati (parallelismo spaziale). La seconda forma è ottenuta dalle computazioni pipeline indipendenti che sono presenti nel grafo (parallelismo temporale).
Le macchine a riduzione utilizzano un modello demand-driven per controllare il flusso della computazione. Il modello prevede che una istruzione venga abilitata per l’esecuzione se i risultati che essa produce sono necessari come operandi per un’altra istruzione che è già abilitata.
Nel caso di elaborazione di istruzioni letterali (applicazioni di funzioni su argomenti) o espressioni, l’esecuzione di un programma consiste nel riconoscimento delle espressioni riducibili e nella sostituzione dei loro valori calcolati.
Il modello di esecuzione può essere visto come un grafo in cui ogni nodo è rappresentato da una sottoespressione che deve essere ridotta.
Gli elementi di elaborazione (PE) elaborano i task (singole elaborazioni) utilizzando un pool di task selezionati e un pool di task in attesa.
Lo schema di elaborazione è il seguente: un PE estrae un task dal pool dei processi selezionati, se vi sono sottoespressioni da valutare, i task relativi sono aggiunti al pool dei selezionati e il task originale va nel pool di attesa, quando un task può essere valutato, i suoi risultati saranno utilizzati per attivare un task nel pool di attesa che passa nel pool dei selezionati.
Uno dei principali requisiti da soddisfare affinché l’elaborazione parallela diventi una tecnologia su cui basare le applicazioni del futuro, è quello di disporre di un modello standard di macchina astratta, simile al modello di Von Neumann per l’elaborazione sequenziale, in modo da separare gli aspetti implementativi software da quelli hardware. Quello che serve è un modello astratto su cui compilare efficientemente i linguaggi di alto livello e che possa essere implementato efficientemente in hardware, in modo che sia possibile eseguire un programma con la stessa efficienza su macchine parallele diverse. Un modello teorico consente di valutare i limiti teorici delle prestazioni delle macchine parallele e di effettuare un’analisi della scalabilità e dell’efficienza degli algoritmi paralleli.
I modelli teorici più conosciuti sono:
Il modello PRAM (Parallel Random Access Machine)
Il modello Spatial Machines basato sugli automi cellulari
Il modello BSP (Bulk Synchronous Parallel)
Il modello LogP
La PRAM è una macchina composta da un insieme di processori sequenziali (RAM), ognuno con una propria memoria locale (ML), che comunicano attraverso una memoria condivisa (MC), una unità di switching (SW) che connette i processori con la memoria condivisa. In una unità di tempo, ogni processore può effettuare operazioni di lettura o scrittura, sia in memoria locale che in quella comune o eseguire operazioni RAM.
Da questo si deduce che il tempo di esecuzione di ogni istruzione è costante, e quindi il modello computazionale può essere considerato di tipo sincrono. In esso il costo dovuto alle comunicazioni è trascurato. Il modello PRAM può essere considerato come una astrazione di un multiprocessor a memoria condivisa.
Gli algoritmi che vengono eseguiti su una PRAM seguono il modello data-parallel: tutti i processori possono eseguire la stessa istruzione su dati diversi.
Purtroppo attraverso una PRAM non è possibile modellare computazioni a scambio messaggi su architetture a memoria distribuita.
La Spatial Machine utilizza un particolare tipo di automa cellulare come modello di computazione parallela che ha la potenza computazionale di una macchina di Turing.
Il modello è più realistico di un automa cellulare poiché il numero di processori è finito sebbene i processori possano muoversi e inviare messaggi in uno spazio infinito. Il modello computazionale della Spatial Machine è definito su una griglia cartesiana tridimensionale di dimensioni infinite. Nel modello tutte le computazioni avvengono in un numero finito di passi ed in ogni passo tutte le computazioni sono eseguite simultaneamente. La Spatial Machine è composta da un numero finito di celle ognuna con le stesse funzionalità di un processore. Ogni processore ha un controllo finito simile a quello della macchina di Turing con un numero finito di stati e una funzione di transizione. Nella macchina, una cella è individuata come cella terminazione. La computazione termina quando un processore raggiunge il suo stato finale nella cella terminazione.
La Spatial Machine può essere definita come un riconoscitore di un linguaggio limitando l’output ai due valori "accept" e "reject".
Il modello BSP è stato proposto con l’obiettivo di definire un modello più pratico del modello PRAM che sia un efficiente bridge fra software e harware.
Il modello BSP è basato su tre elementi:
Un insieme di componenti (processori e memorie)
Un router che è in grado di consegnare messaggi fra coppie di processi attraverso una rete di comunicazione di tipo punto-a-punto
Un dispositivo di sincronizzazione per la temporizzazione dei componenti.
Una computazione BSP consiste in una sequenza di superstep (computazioni globali) in ognuno dei quali ogni componente può eseguire computazioni locali, trasmissione di messaggi verso il router o trattamento dei messaggi ricevuti da altri processori. Un superstep è considerato concluso una volta che tutte le computazioni di tutti i componenti sono completati e il router non ha richieste da soddisfare. I superstep sono separati da barriere globali e tutti i messaggi di un superstep sono ricevuti prima che il successivo superstep inizi.
Il modello LogP presenta una parametrizzazione più evoluta rispetto al modello BSP ma è anch’esso un modello intermedio che caratterizza una macchina parallela attraverso la latenza e la banda.
Il modello LogP caratterizza una macchina parallela attraverso i seguenti parametri:
L: rappresenta la latenza e indica il ritardo che è introdotto dalla rete di interconnessione quando viene trasferito un messaggio avente le dimensioni di una word da un processore sorgente ad uno destinatario.
O: è l’overhead, ovvero il tempo necessario per processare il messaggio nel nodo che lo riceve o in quello che lo invia.
G: è il gap e indica il minimo intervallo di tempo fra la trasmissione o la ricezione di messaggi consecutivi ad un processore. Il reciproco di G corrisponde alla banda di comunicazione disponibile per processore.
P: il numero dei moduli processori/memoria.
Il modello LogP assume che la rete abbia una capacità finita.
Se un processore tenta di inviare un messaggio e la rete è satura allora il processore si blocca finché la rete non è in grado di accettare nuovi messaggi.
Le computazioni locali non sono modellate.
Il modello LogP non prende in considerazione alcuno stile di programmazione o protocollo di comunicazione ed è ugualmente applicabile a paradigmi a memoria condivisa, a scambio di messaggi o data parallel.
Le prestazioni di uno o più moduli che costituiscono un programma parallelo possono essere migliorate aumentando il grado di parallelismo, ovvero il numero di processori che mediamente sono usati durante l’esecuzione del programma. Il grado di parallelismo può essere incrementato sostituendo un modulo con un insieme di moduli operanti in parallelo e caratterizzati da una granularità più fine a quella del modulo di partenza.
Tuttavia la scelta di avere moduli con granularità fine non sempre consente di ottenere miglioramenti poiché spesso si ha un aumento del grado di accoppiamento che è una misura del grado di congestione dei moduli che nel programma hanno la funzione di servire richieste effettuate da parte di più moduli utilizzatori.
Inoltre è importante curare la ripartizione dei dati fra i vari processori in modo da favorire una località nelle richieste di accesso ai dati.
Negli ultimi anni sono stati sviluppati dei linguaggi per la programmazione parallela (detti linguaggi concorrenti) che permettono la scrittura di algoritmi paralleli come un insieme di azioni concorrenti eseguite su differenti processori o nodi di elaborazione.
La realizzazione di programmi paralleli richiede di affrontare e risolvere problemi che non sono presenti nella programmazione sequenziale. Problemi tipici sono la creazione di processi, la loro sincronizzazione, la gestione delle comunicazioni tra processi, la prevenzione dello stallo (deadlock) e la terminazione dei processi che compongono il programma parallelo.
|
|
![[AmadeuX BiblioForum]](https://www.amadeux.it/forum/immagini/amadeuxcomm1.jpg "[AmadeuX BiblioForum]")
Discussione Bloccata
