La struttura del corso e' abbastanza naturalmente suddivisa in piu' moduli, ma i rimandi ed i collegamenti tra di essi sono essenziali. Gli esempi di problemi da parallelizzare sono suddivisi tra i vari moduli del corso.

• 19/02 Panorama del corso. Introduzione ad MPI.
  Panoramica del corso, obiettivi, tecnologie principali (MPI, ASSIST).
  Forme di parallelismo e implementazione nei diversi modelli/linguaggi di programmazione parallela. Esempi di problemi che verranno esaminati del corso: algoritmi di Data Mining, ricerca combinatoria ed ottimizzazione, algoritmi in memoria esterna. Modalità di superamento dell'esame. MPI: modello a scambio di messagi, motivazioni dello sviluppo, descrizione ad alto livello dello standard e del modello di programmazione SPMD.
• 22/02 MPI: concetti essenziali e comunicazione punto a punto.
  MPMD (multiple program multiple data) e SPMD in MPI. Master slave e data parallel come casi particolari di programmi SPMD, utilizzo strutturato di MPI e realizzazione di librerie parallele. Primitive punto a punto di MPI: send e receive sincrona e asincrona, receive asimmetrica. Primitive collettive elementari. Standard di riferimento: MPI 1.1 (cap.3) con integrazione MPI 2 (cap.3).
  Caratteristiche di ordinamento relativo, (non) fairness e uso delle risorse delle primitive MPI. Concetti base di MPI:
  • tipi di dato (tipi base, definiti dall'utente, tipi opachi e handle)
  • comunicatori (rank, inter/intra-comunicatori, gruppi)
  • primitive punto a punto (envelope, completamento locale e globale, primitive bloccanti e non bloccanti, modalità della send)
  • operazioni collettive.
• 26/02 MPI: datatype e comunicatori.
  Tipi di dato generali, concetto di typemap (sequenza di tipi base e displacement). Rappresentazione interna alla libreria MPI come tipi opachi e uso dei costruttori forniti da MPI, MPI_TYPE_COMMIT e MPI_TYPE_FREE. MPI_TYPE_ (contiguous, vector, hvector, indexed, hindexed, struct). Concetti di size ed extent. Modificatori di extent (_LB ed _UB). Matrici a blocchi, triangolari, diagonali.
  Comunicatori in MPI: gruppi di processi, concetto di universo di comunicazione, attributi.
  Funzioni di gestione dei gruppi (estrazione dal comunicatore, creazione, operazioni booleane, creazione di gruppi arbitrari). Localita' delle operazioni sui gruppi.
  Intercomunicatori e intracomunicatori. Intra-comunicatori di default (MPI_COMM_WORLD e _SELF), operazioni locali (MPI_COMM_SIZE, _RANK, _COMPARE) e collettive ( _CREATE, _DUP, _SPLIT, _FREE).
  Intercomunicatori, gruppo locale e remoto (MPI_COMM_TEST_INTER, _REMOTE_SIZE, _REMOTE_GROUP, _INTERCOM_CREATE, _INTERCOM_MERGE).
• 05/03 MPI: comunicazioni collettive.
  Primitive di comunicazione collettive, località al comunicatore, non sincronizzazione e non interferenza. Uso di typemap distinte sui processi, disambiguità in scrittura sul singolo processo e su più processi (il risultato della scrittura non deve dipendere dall'ordine della typemap). Sincronizzazione collettiva: Barrier. Primitive di comunicazione collettiva: broadcast; gather e gatherv, scatter e scatterv; allgather e allgatherv, alltoall e allto allv.
  Primitive che coinvolgono operazioni sui dati: definizione degli operatori (op_create e op_free), implementazione concreta; reduce, scan (parallel prefix).
• 06/03 Mandelbrot
  Descrizione matematica del problema, caratteristiche essenziali: approssimazione numerica di un insieme frattale definito dalla divergenza della successione z=z²+c; variabilità del carico (dipendenza dalle condizioni iniziali) e non predicibilità. utilità come benchmark sbilanciato con carico massimo variabile associato al limite delle iterazioni. Soluzioni a bilanciamento statico e dinamico.
  Introduzione al KDD ed all'estrazione di informazioni da DBMS.
• 12/03 KDD e Data Mining
  Il KDD come sorgente di problemi interessanti per la parallelizzazione. Definizione, caratterizzazione (iterativa, interattiva) e passi base del processo di KDD (data cleaning, integration, selection, transformation, mining; result evaluation, presentation). Definizione di algoritmo di data mining (mining task, pattern/modello di conoscenza, funzione di valutazione, strategia di ricerca, meccanismi di gestione dei dati). Motivazione ed esempi di uso: 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 parallela del k-means; caratteristiche del metodo (ricerca greedy, proprietà di convergenza), definizione dell'algoritmo e analisi dei problemi di implementazione parallela. Meta ricerca (cenni), possibili condizioni di terminazione; parallelizzazione del calcolo sui cluster e partizionamento dei dati.

• 13/03 Data Mining, K-means; introduzione ad ASSIST da completare
• 19/03 Programmazione Parallela Strutturata e ASSIST
  Evoluzione dei modelli di programmazione parallela: approccio a linguaggio sequenziale + direttive, approccio a librerie di comunicazione message passing, approcci a parallelismo strutturato.
  Fortran e HPF, parallelizzazione del data parallel tramite direttive e owner-computes rule.
  Skeleton paralleli : definizione di Murray Cole, utilizzo in linguaggi imperativi e funzionali, possibilità di implementazione (librerie, linguaggi specializzati, linguaggi di coordinamento). Skeleton e template, corrispondenza 1-1 e 1-molti con modelli di costo, skeleton come programmi macro-dataflow parametrici. Esempi rispetto a P3L, SkIE, ASSIST.
  ASSIST: approccio modulare con linguaggio di coordinamento a skeleton. Uso di skeleton paralleli flessibili e tradeoff tra espressività e semplicita di implementazione.
  Il linguaggio: moduli sequenziali, incapsulamento, interazione a stream, generazione degli stub (comunicazioni, gestione del parallelismo); coordinamento e linguaggi ospiti, compilazione a due fasi, inclusione di codice e macroespansione, direttive di compilazione (inc, lib, path).
• 21/03 ASSIST: il parmod
  semantica di base: più forme di parallelismo in alternativa e controllo del non determinismo, maggiore potenza espressiva rispetto a scheleton semplici, compromesso tra espressività e semplicità di implementazione; schema generale (input section, output section, processori virtuali), distribuzioni (on_demand, broadcast) e collezioni (from any, from all), topologie (none, one, array); attributi, attributi replicati e partizionati.
• 28/03 ASSIST: il parmod
  concetto di guardia e controllo del nondeterminismo (priorità, variabili di condizione, espressioni di input); stream interni; distribuzione scheduled; topologie e condizioni di bordo, descrizione di insiemi di parmod non omogenei; compatibilità tra topologie e distribuzioni; analisi di esempi tratti dal tutorial.
• 11/04 ASSIST: esecuzione delle applicazioni
  Struttura dell'applicazione multi architettura come albero di directory; metadati di descrizione dell'applicazione, elementi del linguaggio ALDL; processi, attributi dei processi (vincoli hardware e software), vincoli collettivi (coallocazione), esistenza di vincoli specifici di ASSIST. Server di deployment: GEA, accenni alle versioni precedenti, confronto con i caricatori MPI; obiettivi (generalità, portabilità, eterogeneità dei supporti) e schema base (parse/query/filter/map/deploy); cenni di deployment tramite middleware di griglia;
• 16/04 ASSIST: supporto alla memoria virtuale condivisa
  libreria smReference e suo uso da ASSIST.

Questa parte del programma e' dedicata all'analisi di strumenti teorici, problemi specifici e ambienti di programmazione parallela. Il programma e' suscettibile di modifiche.

• 18/04
• 23/04 Modelli algoritmici paralleli \\Modelli astratti di calcolo parallelo. Il modello PRAM, caratteristiche fondamentali (programma comune, meoria a registri + memoria comune, sincronia dell'esecuzione). Operazioni elementari, HALT, FORK. Modelli di conflitto in lettura e scrittura (EREW, cenni a CREW, CRCW e sottovarianti). Esempio di programma elementare (somma parallela), concetto di complessità parallela in tempo e numero di processori, concetto di Work, work-optimality e relazione con l'efficienza. Esempio di riduzione (logaritmica) del numero di processori tramite utilizzo dell'algoritmo sequenziale su sottoinsiemi, che porta all'algoritmo work-optimal generale per riduzioni con operazioni associative. Cenni alla complessità e work-optimality di alcuni algoritmi comuni. Implementabilità del modello (assunzioni non realistiche, cenni all'emulazione su architetture reali), validità dei risultati di non work-optimality, impossibilità di superlinearità sul modello teorico. Cenni ad altri modelli paralleli (modelli circuitali, modelli con topologia di comunicazione assegnata).
  Modelli a parallelismo discreto: cenni ai coarse grain models [Valiant] e cenni ai parallel bridging models [Cormen]. Modello BSP, schema e parametri, valutazione del costo algoritmico. Realisticità del modello, cenni alle estensioni. Cenni a CGM e LogP. Implementabilità, cenni a BSPlib.
• 2/05
• 7/05
• 9/05
• 14/05
• 16/05
• 21/05
• 23/05