Progetto e implementazione di una interfaccia grafica per lo sviluppo di applicazioni parallele eseguibili su piattaforme di calcolo eterogenee

INTRODUZIONE 2ping), non sono disponibili a tutt'oggi strumenti che li risolvono in modosoddisfacente.Le prospettive future del metacomputing sono alquanto incoraggianti esi prevede che a brevesara possibile raggiungere una piena integrazione tra icomponenti hardware e gli strumenti software che permetta di coprire tuttele fasi di gestione e utilizzo del metacomputer.La presente tesi, dopo una introduzione al metacomputing e agli aspettidella programmazione parallela, presenta una rassegna dei principali ambien-ti visuali per la programmazione parallela, dandone una valutazione in basealle loro caratteristiche piu signicative. In base all'analisi fatta, e stato pro-gettato ed implemenatato un nuovo strumento per lo sviluppo di applicazioniparallele.Nel primo capitolo vengono brevemente trattate le potenzialitaele pro-blematiche del metacomputing e viene descritto il problema dell'aÆnita frai moduli del programma e gli elaboratori del metacomputer.Il capitolo 2 descrive le principali forme di parallelismo e i linguaggi diprogrammazione per la scrittura dei programmi paralleli. In particolare vieneesaminata la classe dei linguaggi paralleli nativi e i costrutti da essi messia disposizione del programmatore.Nel capitolo 3 vengono presentati gli strumenti di sviluppo HeNCE, CO-DE2, VPE e Enterprise; questi sono ambienti visuali che permettono laprogettazione, il debugging e il monitoraggio delle applicazioni sviluppate.Il capitolo 4, dopo una breve analisi della facilita e generalita d'usodegli strumenti esaminati nel capitolo precedente, espone sia gli obiettivida raggiungere che la metodologia di sviluppo adottata per la denizio-ne di un nuovo strumento, denominato THetA (Tool for HeterogeneousApplications).Il capitolo 5 descrive l'interfaccia utente di THetA e i principali aspettiimplementativi. In particolare sono illustrati tutti i costrutti paralleli e leroutine di libreria implementate.
INTRODUZIONE 3Nel capitolo 6, inne, viene mostrato un esempio di uso dello strumentoTHetA per lo sviluppo di una semplice applicazione parallela. L'obiettivoe quello di illustrare l'intera fase di sviluppo con particolare attenzione aicostrutti utilizzati. Vengono inoltre riportati i codici prodotti da THetArelativamente all'esempio considerato.Nelle appendici A e B sono, rispettivamente, riportate le descrizioni delleroutine delle librerie PVM e libtheta usate da THetA per la produzionedel codice parallelo.
Capitolo 1Calcolo eterogeneo:potenzialita e problemiL'uso di un insieme, omogeneo o no, di risorse computazionali interconnesseper mezzo di una rete e viste come un singolo elaboratore parallelo a memoriadistribuita e oggi una via praticabile per la soluzione di alcune classi di proble-mi numerici richiedenti un costo computazionale elevato. Poichee possibile,generalmente, scomporre questi problemi in piu sottoproblemi, la metodolo-gia seguita nella programmazione consiste nel partizionare le applicazioni inpiu moduli da assegnare all'insieme dei calcolatori usati.Allo stato attuale molti dei problemi relativi all'integrazione di macchi-ne dierenti sono risolti grazie alla disponibilita sul mercato di pacchettisoftware in grado di fornire primitive per la cooperazione tra processi resi-denti su macchine diverse. Comunque, il partizionamento delle applicazioni,e ancora demandato al programmatore che deve inoltre preoccuparsi dellesincronizzazioni e dello scambio di dati tra i moduli.Le prospettive future prevedono di costituire grandi macchine virtualicomprendenti diverse organizzazioni ed estese su vaste aree geograche. Sulversante software si prevede di realizzare una serie di strumenti in grado disemplicare o addirittura automatizzare il partizionamento di applicazioni ela distribuzione dei processi sui vari nodi di un metacomputer. L'obiettivo4
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.1. Sistemi di calcolo eterogenei 5e quello di rendere le varie strutture hardware e software completamentetrasparenti all'utente.1.1 Sistemi di calcolo eterogeneiFino a pochi anni fa i sistemi di calcolo parallelo omogenei, che utilizzanouna o piumacchine compatibili dal punto di vista del codice eseguibile, col-legate in rete, hanno assicurato prestazioni adeguate nell'esecuzione di molteapplicazioni. Allo stato attuale, la necessita di disporre di maggiore potenzacomputazionale per soddisfare, ad un costo ragionevole, le esigenze di unasempre piu ampia classe di applicazioni ha fatto chiaramente comprendere,agli sviluppatori di software parallelo, le limitazioni di cui sorono tali si-stemi. Si supponga di voler eseguire un'applicazione parallela costituita daporzioni di codice di tipo diverso, intendendo, per tipo del codice di un modu-lo, la classe architetturale che meglio si presta ad eseguirlo. Tale applicazionecomprende moduli aventi tipo MIMD, SIMD, vettoriale e special-purpose (inquesto caso FFT). Si supponga inoltre di eseguire l'applicazione prima su diun'architettura MIMD, poi su di un supercalcolatore vettoriale ed inne sudi una rete di elaboratori ognuno dei quali aventi una delle architetture corri-spondenti ai tipi di codice presenti (avreno percio un'architettura MIMD, unsupercalcolatore vettoriale, un'architettura SIMD ed una special-purpose).Ogni elaboratore della rete esegue il codice del tipo a lui \aÆne".La Figura 1.1 mostra i tempi di esecuzione, espressi in percentuale ri-spetto al tempo di esecuzione impiegato da un elaboratore sequenziale nel-l'esecuzione dell'applicazione in oggetto; tempo preso a riferimento e quindiconsiderato pari al 100%.Si supponga pari a T il tempo impiegato dall'elaboratore sequenziale (uni-processor) come mostra il caso a) della Figura. Quando il programma vieneeseguito su un elaboratore MIMD il tempo di esecuzione e pari al 48% deltempo T. Il supercalcolatore vettoriale impiega invece un tempo pari al 35%
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.1. Sistemi di calcolo eterogenei 6
20%10% 4%1%
MIMD SIMD FFT
MIMD
Elaboratore
Architettura
Supercalcolatore
vettoriale
Metacomputer
11
1
1%
Vettoriale
25% 15% 7%
1
100%
c)
a)
d)
b)
SISD
Figura 1.1: Esecuzione di un codice campione su una macchina MIMD, unsupercalcolatore vettoriale e su un metacomputer [KPSW93].del tempo T. Il caso d) inne, mostra che il tempo necessario per eseguire ilprogramma sulla rete dei quattro elaboratori risulta essere il 4% del tempoimpiegato dall'uniprocessor.Come si puo facilmente notare da un esame della Figura, le prestazioniottenute nel caso d) sono signicativamente piu elevate di quelle ottenutenegli altri casi. Questo perche i sistemi di calcolo omogenei (gli elaboratoriusati in b) e c) sono due esempi di sistemi omogenei costituiti da un solo no-do) raggiungono la loro performance di picco solo nell'esecuzione dei modulidel tipo corrispondente alla loro classe architetturale; la maggior parte deltempo di elaborazione e speso nell'esecuzione dei moduli di tipo diverso. Seaggiungessimo, per aumentare le prestazioni, un elaboratore MIMD ed unsupercalcolatore vettoriale rispettivamente nei casi b) e c), avremmo solo unlieve miglioramento delle prestazioni in quanto la maggior parte del tempodi elaborazione sarebbe spesa ancora nell'esecuzione di codici non aÆni. Il
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.1. Sistemi di calcolo eterogenei 7
caso d) mostra, invece, che le migliori prestazioni sono ottenute eseguendol'applicazione sulla rete di elaboratori (il quale costituisce un esempio di si-stema di calcolo eterogeneo); questo perche ogni modulo del programma eeseguito dall'elaboratore a lui piu aÆne.Occorre pero osservare che la composizione della rete e naturalmente quel-la ideale: non sempre infatti potremo disporre, per ogni applicazione, dellemacchine piu adatte. In genere ne avremo a disposizione solo alcune e saracompito della fase di mapping assegnare i moduli alle macchine rispettandoil piu possibile le aÆnita.Le piattaforme di calcolo eterogenee sono divenute oggetto di interessesempre crescente a causa dei vantaggi, in termini di performance, che il lorouso consente di raggiungere nell'esecuzione di applicazioni composte da mo-duli caratterizzati da tipi di codice diversi. Di esse daremo ora una denizionee mostreremo, nel paragrafo seguente, un altro esempio di loro utilizzo.Denizione 1.1 Un sistema di calcolo parallelo eterogeneo (metacom-puter) e un insieme di nodi di elaborazione autonomi, collegati in rete, noncompatibili fra loro dal punto di vista dei codici eseguibili e considerati comeun'unico ambiente di calcolo integrato [GWWJ94].Denizione 1.2 Una applicazione distribuita eun'applicazione parallelacomposta da piu moduli cooperanti, in esecuzione sui nodi di un metacompu-ter [GY93].
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.1. Sistemi di calcolo eterogenei 81.1.1 Componenti di un metacomputerIn un metacomputer si possono individuare i seguenti componenti: rete di collegamento e relativeinterfacce nodi-rete; protocolli di comunicazione; sistemi operativi; ambienti di sviluppo delle applicazioni.L'eterogeneita, oltre a quella dovuta ai diversi modelli architetturali deglielaboratori del metacomputer, puo presentarsi anche in ciascuna di questecomponenti; ad esempio in un metacomputer avremo una molteplicita di pro-tocolli di comunicazione, di sistemi operativi, ecc. I problemi presenti in unsistema eterogeneo sono dovuti alla diÆcile integrazione di detti componenti.Un tipico problema si presenta quando due macchine del metacomputer usa-no formati diversi per la rappresentazione di dati dello stesso tipo. In questocaso ogniqualvolta sia necessario eettuare uno scambio di dati tra processiin esecuzione su queste due macchine occorre disporre di meccanismi per latrasformazione di formato per far si che il processo destinatario interpreticorrettamente i dati inviatigli dal processo mittente.Nel seguito di questa trattazione il termine metacomputing si riferiraalla tecnica avente per scopo l'utilizzo eÆciente di un sistema di calcolo etero-geneo per raggiungere la massima performance possibile nell'esecuzione delleapplicazioni che richiedono una elevata potenza computazionale e contengonotipi di codice diversi.
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.1. Sistemi di calcolo eterogenei 91.1.2 Una applicazione pratica del metacomputingSi consideri il problema del monitoraggio sismico illustrato in [Hwa93], essoprevede tre fasi principali :1. Ricezione, in tempo reale, dei segnali provenienti da un insieme di puntidi rilevamento situati nelle zone da controllare.2. Analisi dei segnali ricevuti e produzione del modello descrittivo delfenomeno.3. Interpretazione dei risultati ottenuti al passo precedente.La Figura 1.2 mostra l'insieme delle tre fasi unitamente alle azioni in-traprese per il loro svolgimento. Nell'ipotesi di progettare un modulo perla soluzione di ciascuna fase si otterranno tipi di codice diverso per ognunodi essi. Come si puo intuire, un metacomputer potrebbe raggiungere unaperformance soddisfacente nell'esecuzione dell'applicazione che risolve il pro-blema. In particolare il modulo che svolge la prima fase si presta ad essereeseguito su processori aventi capacita di calcolo vettoriale. Per l'esecuzionedel secondo modulo sono particolarmente adatte macchine neurali, proces-sori Lisp o qualsiasi altra macchina con capacita di elaborazione simbolicaper il riconoscimento dei segnali in ingresso. Per lo svolgimento della terzafase, inne, e necessaria una decomposizione del dominio dei dati, per indi-viduare le informazioni relative a ciascuna zona osservata, e la conseguenteelaborazione in parallelo di tali informazioni da parte di un insieme di moduliuguali. La tecnica del metacomputing puo allora essere adottata per risol-vere eÆcientemente questo problema, facendo in modo che sia garantita lamigliore aÆnita possibile nell'assegnamento dei moduli agli elaboratori delmetacomputer.
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.1. Sistemi di calcolo eterogenei 10
Segnali real-time
ricevuti dai siti
di osservazione
Analisi dei segnali
Analisi simbolica
Interprete
real-time
Evento
sismico ?
SI
NO
Archiviazione
dei dati
Insieme 1 Insieme n
Insieme 2
Reti neurali
Processori Lisp
Interpretazione AI
Figura 1.2: Procedimento di rilevamento sismico distinto in tre fasi principali.
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.2. Granularita delle computazioni 111.1.3 Ulteriori impieghi del metacomputerUn sistema di calcolo eterogeneo puo essere usato anche per lo sviluppo el'esecuzione di applicazioni fault-tolerant in quanto un sistema distribuitoe piu tollerante ai guasti di uno centralizzato. I sistemi distribuiti infattigodono della proprieta di fallimento parziale (partial failure [BST89]): poichei nodi della rete sono autonomi, il fallimento che si verica in uno di essi noncausa il fallimento degli altri. Questa caratteristica puo essere sfruttata peraumentare l'aÆdabilitadiuna applicazione in due diversi modi:1. replicando preventivamente funzioni e dati su piu nodi di elaborazione.In questo modo aumentano le possibilita, nel caso uno o piu di essifallisca, che l'applicazione venga comunque portata a termine.2. Suddividendo, a runtime, il lavoro di un nodo soggetto ad un malfun-zionamento fra tutti gli altri.1.2 Granularita delle computazioniSi denisce granularita di un programma la misura della \quantita" dicomputazione associata [Hwa93]. Tipicamente tale misura e il numero diistruzioni contenute in esso.Si distinguono, in letteratura, tre tipi di granularita: ne (ne-grain),media (medium-grain) e larga/grossa (coarse-grain). Il parallelismo ne-grain e espresso a livello delle istruzioni, quello medium-grain a livello diprocedure (o subroutine) e quello coarse-grain a livello delle applicazioni.Una granularita minore implica un maggior parallelismo potenziale per-che il programma e costituito da un maggior numero di moduli, aumentandocos la possibilita di parallelismo. D'altra parte, generalmente, maggiore eilgrado di parallelismo maggiore e la necessita di comunicazione tra i modulistessi. I costi dovuti atalicomunicazioni, che farebbero crescere il tempo di
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.3. Problematiche del metacomputing 12
elaborazione anche se il programma fosse eseguito su una singola architet-tura parallela, si rivelano ancor piu penalizzanti nel caso di esecuzione sulmetacomputer. Infatti, i tempi richiesti per lo scambio dei dati tra processiin esecuzione su elaboratori diversi del metacalcolatore costituiscono la partepreponderante del tempo di esecuzione complessivo. Una scelta opportuna,in fase di sviluppo, della granularita dei moduli del programma assume lamassima importanza perche permette di diminuire la necessita di comuni-cazione tra di essi. Le applicazioni coarse-grain, essendo composte da unnumero limitato di moduli, risultano le piu adatte per essere eseguite sulmetacomputer in quanto, solitamente, i costi di comunicazione sono piubas-si rispetto alle applicazioni di altro tipo. D'altra parte occorre notare chela rilevazione e lo sfruttamento di forme di parallelismo a grana ne e oggiun problema in parte risolto grazie all'esistenza di strumenti automatici. Lostesso non si puo dire per quel che concerne il parallelismo coarse-grain perla cui individuazione in un programma non esiste ancora alcuno strumentoautomatico (x2.2).1.3 Problematiche del metacomputingLo sfruttamento delle risorse di un sistema di calcolo eterogeneo rappresentail problema principale per la realizzazione del metacomputing [FF95].Per poter gestire al meglio le risorse a disposizione e necessaria sia un'a-nalisi dettagliata dei tipi di parallelismo presenti nel codice delle applicazioni,che la conoscenza delle prestazioni delle macchine del metacomputer nell'ese-cuzione dei vari tipi di codice. Questo puo essere conseguito, rispettivamen-te, con le fasi di determinazione del tipo di codice (code type proling)ebenchmarking (analytical benchmarking). Ulteriori diÆcoltasonodovutealla realizzazione della fase di mapping per l'assegnazione dei processi delprogramma agli elaboratori del metacomputer.Esamineremo ora i principali aspetti relativi alla conoscenza delle risorse
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.3. Problematiche del metacomputing 13
ed i vincoli che tali informazioni impongono nella loro gestione trattandoinnanzitutto il problema del partizionamento.1.3.1 PartizionamentoIl partizionamento del codice di un'applicazione parallela consiste nel sud-dividerne il codice in un insieme di moduli cooperanti per la soluzione delproblema originario. Puo essere eettuato a vari livelli in funzione dellagranularita voluta. Come esempi di partizionamento si possono considerarequello fatto da un compilatore parallelizzante (x2.2.1) che tipicamente per-mette di sfruttare parallelismo a grana ne e quello fatto dal programmatoreche suddivide un'applicazione distribuita in pochi moduli per ottenere unparallelismo a grana grossa.Il processo di partizionamento puo essere suddiviso in due fasi: rilevamen-to del parallelismo presente nell'applicazione e clustering [KPSW93]. Questepossono essere eseguite sia manualmente dal programmatore sia da uno stru-mento automatico a tempo di compilazione [KPSW93]. C'e pero da osservarecome il problema della rilevazione del parallelismo sia estremamente diÆcileda risolvere con uno di questi strumenti, in quanto coinvolge aspetti di seman-tica del programma. In [BST89] e mostrato come una semplicazione possaessere introdotta adottando linguaggi dichiarativi (funzionali e logici). Inol-tre, recentemente, sono stati sviluppati alcuni linguaggi paralleli nativi chesemplicano ulteriormente la fase di rilevamento e dei quali ci occuperemoin x2.2.3.1.3.2 Code type prolingSi denisce code type proling [KPSW93, GY93] il procedimento che permet-te di caratterizzare i moduli di un programma secondo il tipo di parallelismoe di fornire una stima del loro tempo di esecuzione su ciascuna macchinadel metacomputer. Dietro questa semplice denizione si cela, in realta, un
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.3. Problematiche del metacomputing 14problema estremamente complesso in quanto coinvolge la semantica di unprogramma. Un esempio che mette in evidenza tale complessitae costituitodal frammento di codice mostrato in Figura 1.3 che permette il calcolo delprodotto scalare tra due vettori.Prod scalare(Vect a,b,c; int n)f inti;for (i=0; i<n; i++)c[i]=a[i]*b[i];gFigura 1.3: Procedura per il calcolo del prodotto scalare tra due vettori.L'attribuzione del tipo di codice a questo frammento non puo prescinderedal valore assunto dalla variabile n a tempo di esecuzione. Se la variabilen avesse un valore dell'ordine di poche decine, il tipo piu appropriato perquesto codice sarebbe infatti \sequenziale" e non \parallelo SIMD" come sipotrebbe dedurre a prima vista. Questo perche l'esecuzione del frammentosu di un elaboratore SIMD comporterebbe l'utilizzazione solamente di unapiccola parte delle migliaia di unita di calcolo presenti, con grave pregiudiziodell'eÆcienza complessiva.Questo esempio mette in evidenza le diÆcoltache uno strumento di pro-ling (proler) incontrerebbe nell'eettuare un'analisi del codice. Soluzionipossibili per questo problema sono: Delegare il compito di determinare i tipi di codice al programmatore,per mezzo di annotazioni (direttive) inserite nel codice sorgente. Que-sta e la soluzione che si rende necessaria per programmi espressi conlinguaggi sequenziali in quanto si presentano frequentemente problemi
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.3. Problematiche del metacomputing 15analoghi a quello mostrato nell'esempio. Utilizzare uno strumento semiautomatico che richieda l'intervento delprogrammatore solo in presenza di ambiguitacomesivericava nell'e-sempio. Programmare usando linguaggi di programmazione paralleli dotati dicostrutti per esprimere le diverse forme di parallelismo (x2.1). Questorenderebbe piu agevole dedurre automaticamente il tipo di codice.1.3.3 Analytical benchmarkingCon analitycal benchmarking [KPSW93, GY93] si intende una metodologiadi valutazione delle prestazioni che permette di misurare la performance rag-giunta da una macchina nell'esecuzione di un certo tipo di codice. Mentre ilcode type proling identica il tipo di un codice, l'analytical benchmarkingconsente di stabilire quale fra le macchine del sistema e la migliore per uncerto tipo di codice. Osservazioni sperimentali [GY93] hanno dimostrato chele macchine SIMD sono adatte per computazioni matriciali (che presentanoun parallelismo SIMD), mentre le macchine MIMD sono eÆcienti quando imoduli di un programma hanno una limitata intercomunicazione.1.3.4 MappingIl mapping consiste nell'assegnazione dei processi dell'applicazione agli elabo-ratori usati in modo da ottimizzare una certa funzione obiettivo ( ad esempiominimo tempo di completamento del programma oppure bilanciamento delcarico di lavoro tra gli elaboratori). Tutte le informazioni disponibili raccol-te nelle precedenti fasi (tipi di codice, tempi di esecuzione stimati, aÆnita,costi di comunicazione fra i nodi) possono essere sfruttate per ricavare l'as-segnamento ottimale dei processi alle macchine. Il mapping ha grande im-portanza ai ni dell'ottenimento della miglior performance possibile in fasedi esecuzione.
CAPITOLO 1. CALCOLO ETEROGENEO: POTENZIALITA EPROBLEMI1.3. Problematiche del metacomputing 16E stato mostrato [Bok81] che nei sistemi omogenei il problema del map-ping e NP-completo quando lo schema delle interazioni tra i processi delprogramma non e in alcun modo vincolato, ma puo assumere una qualunqueforma che l'utente reputi opportuna. Questa \generalita", se da un lato nonimpone alcuna restrizione durante la fase di progetto del programma, da unaltro impedisce ad uno strumento automatico di risolvere in maniera ottimaleil problema del mapping.Nei sistemi eterogenei occorre considerare ulteriori aspetti (aÆnita, irre-golarita della topologia della rete di interconnessione) che rendono piu diÆcileil problema. In particolare ricordiamo la necessita di tenere conto delle dif-ferenti aÆnita tra le architetture e i tipi di codice: la scelta di assegnareciascun modulo alla macchina piu aÆne puo contrastare sia con l'obietti-vo di bilanciamento del carico che con quello di minimizzazione dei costi dicomunicazione.Data la complessita del problema del mapping, sia nella sua formulazionepiu generale che in molte altre piu particolari (ottenute da quella generaleimponendo vincoli sulla struttura d'interconnessione dei processi [Ahm95]),sono state sviluppate numerose euristiche aventi lo scopo di ottenere soluzioniapprossimate. La bonta di tali soluzioni dipende fortemente da una molte-plicita di fattori quali, ad esempio, la granularita, la topologia sica dellarete di interconnessione, l'ampiezza della banda e la struttura d'interazionedei moduli del programma.Su quest'ultimo aspetto ci soermeremo nel capitolo 4, quando classi-cheremo alcuni strumenti di programmazione per metacomputer in basealle restrizioni che impongono alla struttura di interazione dei moduli deiprogrammi paralleli. Gli altri fattori, pur rivestendo anch'essi molta impor-tanza, non verranno trattati ulteriormente in quanto collegati ad aspetti aldi la degli scopi di questa tesi.