2005-2006  Complementi di Calcolo Parallelo e Distribuito

Annunci    Informazioni    Calendario delle lezioni    Seminari e Progetti    Link utili

Calendario delle lezioni 

Febbraio    Marzo    Aprile    Maggio — future —    Maggio   

20/02/06 
Introduzione: descrizione delle finalità del corso e delle modalità d'esame. Panoramica dei modelli di programmazione parallela: strutturata e non strutturata; approcci a linguaggio dedicato, a direttive, a librerie; message passing e memoria condivisa. Esemplificazione dei concetti con MPI, Assist, Open MP, HPF. Cenni sulle gerarchie di memoria sequenziali e parallele (shared memory, DVSM) ed impatto sulla programmazione parallela.
Riferimenti: Per questa lezione non ci sono riferimenti precisi. Consiglio di leggere [1] cap. 1 ed inizio cap. 2, e rivedere i concetti di Architetture Parallele (ASE) richiamati: forme di parallelismo di base, implementazione delle reti di interconnessione dedicate.
23/02/06
MPI, modello di programmazione e primitive fondamentali.
Modello SPMD, programmi “piatti” (master-slave o master-worker) e programmi strutturati. Versioni dello standard MPI (faremo riferimento principalmente a MPI 1.1). Comunicazione diretta punto a punto, comunicazione collettiva. Concetto di comunicatore e rank di un processo. Schema di esecuzione di un programma MPI (caricatore, handshake dei processi, esecuzione). Primitive MPI_* : Init, Finalize, Comm_size, Comm_rank. Primitive Send e Recv generali, descrizione dei parametri e significato nel modello di comunicazione: tag, source, comunicatore, rank; tipi di dato base in MPI. Cenni ai tipi di dato strutturati, alla creazione di comunicatori. Differenza tra comunicazione MPI e comunicazione nel formalismo con canali usato ad ASE (esempio: comunicazione asimmetrica e canali asimmetrici).
Riferimenti: Parte dei concetti spiegati sono riportati nellle sezioni 2.1–2.2 del testo [1]. La sezione 2.3 e seguenti non sono necessarie. La descrizione dettagliata delle primitive si trova sullo standard MPI [3], nel capitolo 3 fino alla sezione 3.3 (pagg 16–26). Leggere le sezioni 2.4, 2.6. Attenzione: alcuni esempi seguono la sintassi FORTRAN, trovate la sintassi C nell'appendice A (A.1–A.8, pagg. 210–220).
Attenzione! Come spiegato a lezione molti testi, incluso quello di riferimento [1], trascurano l'aspetto strutturale dei programmi e fanno l'ipotesi implicita che tutti i programmi siano master-worker o data parallel. Fate attenzione e riflettete sempre su come scrivere un programma ed usare i comunicatori per ottenere moduli di codice riutilizzabili.
27/02/06
Differenti modalità di send e receive in MPI: standard, buffered, sincrona, ready; concetto di Envelope e utilizzo dei buffer nei vari casi, corrispondenze e differenze con i canali sincroni/asincroni del formalismo usato ad ASE; comunicazioni bloccanti e non bloccanti, strutture request, MPI_WAIT ed MPI_TEST; concetti di gruppo e (intra-)comunicatore; primitive per la creazione e manipolazione dei gruppi e dei comunicatori. Uso dei comunicatori per realizzare librerie parallele e per strutturare programmi.
Riferimenti: [3] capitolo 3, sezioni 3.2.3–3.2.5, 3.4–3.5, 3.7–3.7.4, leggere 3.7.5
02/03/06 
Tipi di dati strutturati in MPI: strutture opache datatype, concetto di typemap, size ed extent di una typemap; località della dichiarazione dei datatype (MPI_TYPE_COMMIT, _FREE); compatibilità di datatype diversi; costruttori di tipo (_CONTIGUOUS, _VECTOR, _INDEXED, _HVECTOR, _HINDEXED, STRUCT), controllo dell'extent (MPI_LB, MPI_UB); concetto di packing e unpacking associato alle comunicazioni, overlapping e semantica dei datatype rispetto alla comunicazione punto a punto; funzioni accessorie (_TYPE_EXTENT, _TYPE_SIZE, _GET_COUNT, _GET_ELEMENTS). Comunicazioni collettive: utilizzo e semantica (bloccante e non necessariamente sincrona); BARRIER, BCAST, GATHER, SCATTER, ALLGATHER, e versioni a count variabile: GATERV, SCATTERV, ALLGATHERV.
Riferimenti: [3] capitolo 3 : 3.12, 3.12.1, 3.12.2 (parte), 3.12.3–5. Capitolo 4 fino a 4.7 compreso.
06/03/06
Operatori MPI, comunicazioni collettive che li utilizzano (REDUCE, ALLREDUCE, SCAN). Programma MPI elementare. Mandelbrot come esempio di calcolo non bilanciabile staticamente, analisi del problema. Applicazioni strutturate realizzate con comunicatori. Il farm bilanciante con terminazione (inizio).
Riferimenti: [3] capitolo 4 : 4.9, 4.11. [1] pag. 60, 86–92. [5] Implementazione del farm con terminazione nel formalismo a canali.
09/03/06
Implementazione del paradigma farm con terminazione in MPI; strutturazione ricorsiva tramite comunicatori del programma; implementazione dell'emettitore, terminazione tramite uso di TAG e/o comunicazioni separate; uso di comunicazioni asincrone (MPI_BSend, MPI_Buffer_attach). Breve introduzione al Data Mining.
13/03/06
Il giorno 13/03 non si terrà lezione.
16/03/06
Introduzione al KDD: concetto di processo di KDD (iterativo/interattivo) e motivazione al data mining parallelo; spazio dei dati, e dimensione fisica dei dati, spazio dei modelli (bias descrittivo) e sua esplorazione (bias di ricerca); concetto di tecnica di data mining e differenza rispetto al concetto di algoritmo di DM; elementi caratterizzanti un algoritmo di DM sequenziale; elementi caratterizzanti un alg. di DM parallelo (decomposizione in parallelo dei dati, del modello, dello spazio di ricerca).
Concetto di clustering, clustering geometrico, K-means, una particolare implementazione del k-means; caratteristiche del metodo (ricerca greedy, proprietà di convergenza), definizione dell'algoritmo e analisi dei problemi di implementazione parallela.
Meta ricerca; possibili condizioni di terminazione; parallelizzazione del calcolo sui cluster e partizionamento dei dati, conseguenze sulle sincronizzazioni e sul bilanciamento del carico ad ogni iterazione.
Riferimenti: Vedi link
23/03/06
24/03/06
Classificazione per induzione di alberi (C4.5) come problema Divide et Impera irregolare e data-intensive. Schema dell'algoritmo, operazioni base, possibili scelte di parallelizzazione.
03/04/06 
Analisi delle possibili parallelizzazioni di K-means : in memoria, out of memory, in parallelo su piu' thread, in parallelo su piu' set di centri.
Possibili parallelizzazioni di C4.5: rispetto alle colonne (data parallel verticale), alle istanze (data parallel orizzontale), alla struttura dell'algoritmo (task parallel sulla creazione dell'albero). Soluzioni miste.
20/04/06
— Assist 1 —
Introduzione ai concetti base; programmazione a skeleton, origini (Cole), concetto di skeleton parallelo, cenni a linguaggi derivati (funzionali e imperativi); implementazione come librerie, compilatori stand-alone, estensione di linguaggi funzionali; mapping su motori macro-dataflow. Confronto con parallelismo non strutturato (MPI e simili) e con strutture limitate (HPF per data parallel).
Implementazione degli skeleton (template vs data-flow); passaggio da skeleton "rigidi" a skeleton estensibili.
Assist: caratteristiche (modularità, riuso del codice seq e parallelo, espressività, efficienza, scalabilità). Riferimenti (ambienti di programmazione): Ocaml-p3l, eSkel, muSkel, P3l, Skie, Assist
Approfondimenti: muSkel, eSkel.
21/04/06
— Assist 2 —
Descrizione di esempi di codice Assist (generic ed implementazione di forme di parallelismo); problemi di implementazione nell'integrazione tra linguaggi, confronto con soluzioni Java-based (Proactive, Ibis).
sintassi in/out, input_stream/output_stream, creazione/consumo esplicito di elementi dello stream; disuso di assist_in(); uso di static per gestire lo stato sequenziale.
Esempi di codice Assist: pipeline_C.ast, pipeline.ast, grafo.ast, parmod.ast
Approfondimenti: Proactive, Ibis.
24/04/06
— Assist 3 —
Parmod: attributi (variabili condivise e di controllo); distribuzione di stream sugli attributi; attr. replicati, scattered; uso nelle operation.
Parmod data parallel
Descrizione della compilazione Assist: generazione del codice, lancio del programma, operazioni a basso livello (manuale) e via GEA (automatizzazione); parametrizzazione del lancio. Cenni al supporto dinamico: riallocazione dinamica dei VP e dei VPM (2 casi distinti: parmod none, parmod con topology array).
Esempi di codice Assist
27/04/06
Assist – parmod : esempi.
Esempi di codice Assist
28/04/06
—Memorie secondarie 1—
Implementazione di algoritmi in memoria secondaria: motivi, e problemi legati (dimensione del problema, necessità di parallelizzare, trashing, inadeguatezza delle politiche generali al particolare problema); motivazioni architetturali e pratiche per modelli di costo algoritmici; gerarchie di memoria (livelli, ordini di grandezza di latenza e banda); evoluzione dei modelli e scelte semplificatrici; differenza tra modelli algoritmici e modelli di performance (livello di astrazione, complessità accettabile, precisione nell'uso pratico o semplicità nel calcolo di upper/lower bound e complessità media).
Cenni ai modelli oblivious e ai modelli con costo ridotto per accessi lineari; il modello PDM: ipotesi realistiche in passato e ad oggi sul numero di dischi e processori, esempi di effetti della gerarchia di memoria al livello di microarchitettura (fault cache, prefetching ottimizzato con stride, fault TLB).
Classi di operazioni elementari (scan, sort, output, search), complessita' associata; conseguenza del logaritmo in base elevata nella complessita del search e del sort; il costo generico delle permutazioni.
Riferimenti:
Jeff Vitter, External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA, ACM Computing Survey 33(2) Jun 2001, pp.209-271
ACM Computing survey 28 (4es) Dec 1996,
(panoramica: è importante leggere il position paper di T. Cormen, M. Goodrich, A bridging model for parallel computation, communication, and I/O)
04/05/06 
—Memorie secondarie 2—
Permutazioni in memoria interna ed esterna; complessità, permutazioni BMMC (cenni); trasposizione, complessità generica, relazione con la dimensione del blocco; caso particolare B²<M; descrizione delle matrici a blocchi, uso della descrizione a blocchi ricorsiva per ottimizzare gerarchie di memoria a più livelli (vedi Algoritmi Cache Oblivious); confronto con decomposizione parallela (accesso a memoria esterna ←→ accesso a memoria remota); complessità 
 FFT(N) == sort(N)
(la complessità del sort ritorna continuamente nel modello PDM per memoria esterna).
Framework per scrivere algoritmi in memoria esterna: analisi comparativa rispetto ai modelli per parallelismo a skeleton; struttura di TPIE, cenni a Vic*;
il framework FG: modello di grafo pipeline/dag, computazione data flow rispetto ai blocchi, rappresentazione mediante thumbnail che riferiscono i blocchi dati, interazione con il motore di prefetch. Confronto con ASSIST, meccanismo dei reference e struttura del parmod.
Riferimenti: articoli su FG, survey Vitter; eventualmente, articoli su TPIE (pagina web di J.S.Vitter) e ViC* (pagina web di T.S.Cormen).
Approfondimenti: test di FG, analisi dell'algoritmo Slabpose (come seminario) o implementazione in ASSIST ed FG (come progetto).
08/05/06
Algoritmo DBSCAN sequenziale e parallelo. Concetto di clustering geometrico in spazi a dimensione elevata, clustering per densità; algoritmo astratto in termini di quesry spaziali; elementi di strutture indice spaziali (R-tree, R*-tree, X-tree) e descrizione dello R*-tree, costo medio delle query. Costo sequenziale, possibili parallelizzazioni (partizionamento spaziale, replicazione) e svantaggi. Analisi della parallelizzazione con replicazione e degli overhead, meccanismo di filtraggio.
Riferimenti:
11/05/06
Programmazione a memoria condivisa: Distributed Virtual Shared Memory.
Riferimenti: Testo [1] Cap 9; M. Aldinucci, Dynamic shared data in structured parallel programming frameworks, TD 09/03 (dal sito del dipartimento), Cap. 3: 3.1, 3.2, 3.3 fino a pag. 100; 3.3.3, 3.4.
12/05/06
Programmazione con memoria condivisa in Assist. Uso di un supporto DVSM, meccanismo dei reference, primitive di inizializzazione (REF_init, REF_end, REF_new, REF_delete), di trasferimento dati (REF_Read, REF_Write, REF_D_Read, REF_D_Write, REF_D_ReadV, REF_D_WriteV) e di sincronizzazione (REF_Lock, REF_Unlock).
Semantica dell'allocazione in memoria condivisa, semantica dell'accesso a segmenti dati (approssimativamente una DSM object-based) e parti di esso.
Uso di un modello di consistenza definito dall'utente, possibile implementazione. Cenni a strutture dati dinamiche in memoria condivisa per programmi paralleli (Shared_Tree).
Esempi di codice Assist con uso di reference
15/05/06
Bucket sort e Sample sort sequenziale e parallelo, algoritmo ed analisi della complessità in numero di comunicazioni, quantità di comunicazioni, complessità delle operazioni in locale. N-body: definizione del problema ed algoritmo sequenziale elementare.
Riferimenti: Testo [1] par. 4.2.1, testo [2] par. 9.5 (della seconda edizione), testo [1] par. 4.2.3.
Approfondimenti:Implementazione di algoritmi di sort out-of-core in ASSIST.
18/05/06 
N-body parallelo, schema dell'algoritmo elementare, complessità e accorpamento delle comunicazioni; metodo Barnes-Hut, approssimazione con centri di massa, struttura dati quad-tre (oct-tree), complessità ricostruzione dell'albero, aggiornamento, distribuzione dell'albero e dell'array dei corpi (parte dell'albero condivisa/replicata, partizionamento dell'array), bilanciamento del calcolo tra i processori, space-filling curves; cenni a metodi avanzati (metodi PP e PM, potenziale, algoritmi ibridi tipo Fast MultiPole); problemi multibody non gravitazionali (forza elettrostatica, simulazione strutturale di molecole).
Riferimenti: Testo [1] par. 4.2.3.
19/05/06
Aula D1 Ottimizzazione tramite algoritmi genetici. Algoritmo base, crossover, mutazione, selezione, criterio di fitness. Parallelizzazione degli step. Parallelizzazione sulle popolazioni: modelli di migrazione (topologie a isole, stepping stones, anelli, griglie), criteri di scelta per la migrazione, frequenza, quantità di individui. Analisi delle anomalie di speedup.
Riferimenti: Testo [1] Cap. 13 (Par. 13.3 tutto). Articolo
22/05/06
Problemi di ottimizzazione combinatoria. Cenni al simulated annealing, carattersitiche comuni con gli algoritmi genetici. Ricerca combinatoria: N-Queen. Implementazione sequenziale, albero delle scelte, backtrack. Generalità delle implementazioni e riuso del codice, lavoro di Knuth sui problemi di copertura. Parallelizzazione: strategie di espansione in parallelo, ordinamento dei nodi da espandere, bilanciamento del carico statico (previsione del costo) e dinamico (espansione parziale). Ottimizzazione combinatoria: Branch and Bound. Algoritmo sequenziale, implementazione in parallelo; espansione depth/breadth firsth, ordinamento in base alla funzione di valutazione, costo dell'euristica di bound. Sincronizzazione immediata o periodica dei bound, bilanciamento tra overhead e accelerazione parallela. Necessità pratica di bilanciamento del carico e supporto alla fault tolerance.
Riferimenti: Testo [1] Cap 13, par 13.1, 13.2; Articolo di D.E. Knuth; documentazione del Grids@Work contest
25/05/06
Implementazione del sample sort in Assist; problemi legati all'utilizzo di risorse non locali nei VP; concetto di stato dei VP ed implementazione della dinamicità; integrazione tra linguaggi compilati (C, C++) e basati su bytecode (Java, C#).
Turn back to the home page Ultimo aggiornamento: 18 Maggio 2006