CCP 06-07: elenco delle lezioni

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. Diversamente da quanto pianificato all'inizio del corso, per anticipare la descrizione dell'ambiente di programmazione ASSIST gli spunti di ricerca ed i problemi obiettivo di parallelizzazione sono stati concentrati, per la maggior parte, nel terzo modulo 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
  Concetto di distributed virtual shared memory (DVSM) [capitolo 9 del libro]. Vantaggi e svantaggi (protabilità, prestazioni, scalabilità). Modelli di consistenza (weak, strict / sequential), unità di coerenza (pagine, variabili, oggetti), livello dei meccanismi di implementazione (hardware, sistema operativo, libreria, linguaggio di programmazione). Eager and lazy release consistency (associata alle operazioni), entry consistency (data dalla struttura dei dati), scope consistency (data dalla struttura del programma). Libreria smReference di interfacciamento ad una DVSM, modello di consistenza esplicita, suo uso da ASSIST.
• 18/04 Libreria smReference
  Modello di memoria (separazione dello spazio condiviso da quello locale), modello di accesso ai dati (handle come oggetti opachi che puntano a segmenti condivisi, allocazione esplicita e dinamica, segmenti di dimensioni non limitate dallo spazio di memoria fisica/virtuale). Condivisione regolata dalla struttura dei programmi. Primitive base (REF_New, REF_Delete, REF_Read, REF_Write), con displacement (REF_D_Read, REF_D_Write) e per la condivisione via locking (REF_Lock, REF_Unlock). Cenni di implementazione sui supporti DVSA e adHOC. Esempio di implementazione di strutture dati complesse in memoria condivisa come classi C++ (Shared_Tree) e cenni alle memorie condivise orientate agli oggetti.

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

• 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. Riduzione logaritmica del numero di processori (lemma di Brent) con l'uso dell'algoritmo sequenziale su sottoinsiemi (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 e cenni ai parallel bridging models Articolo di Valiant sui Parallel Bridging Models Link al position paper di T.H.Cormen Pagina degli articoli di 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 Modelli algoritmici per memoria secondaria / gerarchie di memoria
  Panoramica generale dei collegamenti tra modelli paralleli fine grain (PRAM), coarse-grain o bulk parallel (BSP, GCM, LogP, QSM), modelli per memoria esterna (PDM ed altri) e Parallel Bridging Model. Cenni a problemi memory-intensive su piattaforme parallele (indicizzazione per web search, bioinformatica, data mining, streaming multimediale).
  Modelli di calcolo per memoria esterna; motivazioni pratiche, forte gap di prestazioni tra i livelli di memoria (p.es. latenza disco vs RAM : circa 10^6), necessità di misure di costo algoritmico realistiche per problemi I/O intensive, inadeguatezza dell'approccio a memoria virtuale per pattern arbitrari di accesso ai dati. Modello PDM; definizione, parametri, operazioni sui blocchi, modello di costo come numero di I/O; distinzione tra problemi batch/online; complessità delle operazioni fondamentali (scan, sort) e conseguenze (log → quasi costante nella pratica, permutazione generale e sort sono equivalenti); cenni agli effetti dello striping su dischi multipli (P=1, D>1). Uso prevalente del modello PDM con P=1. Analogia tra PDM con P>1 e BSP. Cenni a BSP* e D-BSP.
  Riferimenti: survey di J.S.Vitter “External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA”, ACM Computing Survey 33(2), vedi link sulla vecchia pagina del corso Pagina CCP 05/06; M.Coppola, M.Schmollinger “Hierarchical Models and Software Tools for Parallel Programming” LNCS 2625, cap 15
  Cenni ad ambienti di programmazione basati sul modello PDM: TPIE, VIC*, FG.
• 7/05 Ambienti di programmazione per memoria esterna
  Confronto tra tre sistemi diversi per astrazione fornita, metodologia di implementazione (run-time, compilatore, libreria), tipo di problemi e piattaforma di esecuzione. TPIE; modello di programmazione concreto derivato da PDM, implementazione ad alto livello. VIC*. FG come approccio che unisce parallelismo e gestione della memoria esterna; parallelismo pipeline/Dag, concetto di buffer gestito dal supporto, thumbnail come puntatore e meccanismo di controllo del trasferimento dati. Moduli funzionali e replicazione automatica (farm implicito). Confronto con l'approccio ASSIST in termini di espressività e complessità del supporto dell'ambiente.
  Modelli derivati dal BSP con costo di comunicazione più realistico: modello BSP*, concetto di critical block size, misura del costo in termini del numero di blocchi scambiati. Modello D-BSP, parametri di costo G(n) e L(n) funzioni della dimensione della (sotto)macchina e decomponibilità in insiemi di processi indipendenti. Cenni alla simulabilità in memoria esterna del BSP-*, ed al modello EdD-BSP (decomponibilità associata a skeleton).
• 9/05 Lezione cancellata.
• 11/05 Data Mining Parallelo - Parallelizzazione dell'algoritmo DBSCAN
  Metodo di clustering per densità. Approccio, problemi per dataset e spazi di dimensioni elevate. Strutture dati per indicizzazione spaziale: gli R-tree come classe di strutture efficienti, struttura generale ed operazioni base, lo R*-tree, proprietà specifiche. Il concetto di range e neighborhood query. Utilizzo nell'algoritmo DBSCAN: algoritmo sequenziale; procedura ExpandCluster; complessità; costo computazionale in pratica. Cenni alle parallelizazioni basate sul partizionamento del dataset (pDBSCAN), sull'esplorazione in parallelo di più punti; il problema della ricostruzione dei cluster. Decomposizione master-slave, con replicazione dello R*-tree (esecuzione delle query con un farm). Collo di bottiglia e ridondanza dei risultati, strategie di filtraggio distribuito dei dati. Prestazioni.
  Introduzione al problema della classificazione per induzione di alberi.
  Trovate vari link ad articoli sull'algoritmo DBSCAN sulla mia pagina personale (corso di CCP 05-05)

• 14/05 Problemi dividi e conquista
  I problemi dividi e conquista (D&C) in parallelo, ipotesi generali (cardinalità arbitraria e/o variabile di divisione, alberi non bilanciati, peso computazionale non omogeneo). N-body, algoritmo esatto, O(N²) per passo; quad-tree e oct-tree, decomposizione spaziale dei dati; algoritmo Barnes-Hut, approssimazione con centro di massa, informazioni riassuntive nell'oct-tree; ricostruzione dell'albero ad ogni passo, costo computazionale O(N log N) per passo.
  Classificazione come problema di data mining (supervised learning), modello di riferimento dei dati (casi/attributi nominali e continui), il modello di classificazione ad albero; C4.5; test su singolo attributo, esplorazione esaustiva dei test nell'intorno della soluzione parziale, ricerca greedy, formulazione D&C; espressione formale del criterio di split (information gain), algoritmo sequenziale per attributi nominali O(N) e continui O(N log N). Conseguenze del sorting per l'applicazione sequenziale e il caso parallelo. Possibili strategie di parallelizzazione di problemi D&C e loro problemi nel caso di D&C irregolare.
  Alcuni riferimenti:

• 16/05 C 4.5 parallelo, DM parallelo e gestione dei dati
  Analisi dell'algoritmo C4.5 e delle implementazioni in parallelo (SLIQ, SPRINT, ScalParC). Criterio di costo e necessità di calcolare gli istogrami delle classi sulle partizioni. Strategie di espansione in parallelo per task, per sottoalberi, per livelli; vantaggi e svantaggi, rispetto al massimo parallelismo esplicitabile, alla maggiore o minore sincronizzazione tra i nodi di calcolo, alla quantità di comunicazioni necessarie. Partizionamento del database verticale (sugli attributi) e orizzontale (sui casi), conseguenze sulle comunicazioni necessarie al calcolo degli istogrammi.
  Meccanismi di gestione dei dati nel Data Mining: flat files, sistemi di DBMS, introduzione di primitive dedicate nei due casi; vantaggi e svantaggi delle diverse scelte tecnologiche e pratiche (complessità di implementazione degli algoritmi, delle primitive di accesso ai dati, overhead di accesso). Meccanismi di Parallel data management, cenni alle scelte fatte nel prototipo Parallel Data Repository (portabilità inter applicazione ma non inter-architetturale, orientamento ai blocchi, primitive di accesso type-aware ottimizzate per il DM).
  Riferimenti:

• 18/05 Architetture Multicore
  Introduzione ai multicore, richiami alle motivazioni tecnologiche. Multicore simmetrici e asimmetrici. Core multipli, hypertreading, cenni ad approcci differenti (architettura Tera, Transputer). Architetture multicore asimmetriche: IBM CELL, Intel IXP2400; descrizione (in particolare la differene struttura di interconnessione nelle due CPU), discussione delle scelte di progettazione determinanti nelle due architetture (elavata banda di calcolo vs bassa potenza di calcolo rispetto alla banda di trasferimento). Cenni alle problematiche di programmazione a basso livello, e framework di programmazione più astratti. Architetture multicore simmetriche ad elevato parallelismo: Sun Niagara, Azul Vega 2; utilizzo prevalente per applicazioni multithread, database, supporto a macchine virtuali (Java, .Net) senza modifiche al modello di programmazione.
• 21/05
• 23/05
• 25/05