Complementi di Calcolo Parallelo e Distribuito, A.A. 2006/2007

Docente: Massimo Coppola

Il programma del corso cambia leggermente di anno in anno. Invito quindi gli studenti

• a fare riferimento anche alla pagina del corso dell'anno accademico 2005-2006 : CCP 05-06

• a registrarsi per ricevere notifiche dalla pagina delle Corso di CCP : Novità.

Attenzione! Nuova variazione dell'orario, a partire dal 19/03/2007

** Ricevimento **

Appuntamento in altri orari su richiesta (meglio via e-mail).

Il corso approfondisce i paradigmi di base e le tecniche della programmazione parallela, introducendo all'utilizzo sia di librerie di programmazione standard, a basso livello, sia di linguaggi di programmazione ad alto livello.

Nel corso vengono studiati da un punto di vista teorico, ed analizzati in pratica con esempi di applicazioni reali, i paradigmi di programmazione a scambio di messaggi ed a memoria condivisa. Tali paradigmi realizzativi sono applicati alle forme di parallelismo di base usate nella programmazione parallela e distribuita, e valutati in termini di performance teorica (analisi delle gerarchie di memoria, modelli di performance), pratica, di efficacia dal punto di vista del software engineering.

• Richiami di valutazione delle prestazioni in parallelo. Il paradigma a scambio di messaggi. Programmazione a basso livello: introduzione ad MPI, concetti base e funzionalità principali. Comunicatori, primitive punto a punto e collettive, tipi di dati.
• Problemi fondamentali: classi data parallel e task parallel, decomposizione del calcolo e bilanciamento del carico. Problemi regolari ed irregolari. Esempi di implementazione delle forme base di parallelismo (pipeline, farm, map, divide et impera …) in C/C++ ed MPI; valutazione delle prestazioni.
• La programmazione parallela ad alto livello: l'ambiente ASSIST. Utilizzo delle forme di parallelismo base in Assist. Esempi di applicazioni e valutazione delle prestazioni.
• Il paradigma a memoria condivisa. Le gerarchie di memoria: memoria centrale / dischi; memoria locale / memoria condivisa. Cenni agli algoritmi per le gerarchie di memoria. Implementazione a software delle memorie condivise: Distributed Virtually Shared Memory. Contenimento e mascheramento della latenza di accesso. Tecniche di programmazione ed esempi di soluzione di problemi tramite memoria condivisa.
• Tra i possibili approfondimenti nella parte finale del corsi o argomenti di progetto: I/O parallelo, algoritmi memory-intensive e data mining parallelo; esempi di applicazioni complesse; applicazione delle metodologie alle piattaforme di griglia.

• B. Wilkinson, M. Allen Parallel Programming, 2nd edition. 2005, Prentice-Hall. Disponibile in Biblioteca la prima edizione, C.1.2 w74 INF .

** Testo Principale. **

• A. Grama, A. Gupta, G. Karypis, V. Kumar Introduction to Parallel Computing, 2nd edition. 2003, Addison Wesley. Disponibile in Biblioteca la prima edizione D.1.3 k96 INF

Solo alcune parti, specificate a lezione.

• Standard MPI, versione 1.1

Solo le parti specificate nell'elenco delle lezioni.

• Tutorial di utilizzo del compilatore Assist Tutorial ASSIST Febbraio 2007 e del server di esecuzione GEA, versione Novembre 2006.
• (Dispense di ASE) — M. Vanneschi, Architetture Parallele e Distribuite. Servizio Editoriale Universitario, Università di Pisa, 2004-05.
• Brevi fotocopie e dispense distribuite durante il corso

Si assume la conoscenza del linguaggio C o C++. Sono un prerequisito fondamentale i corsi di Architettura 1 e 2 :

• Architettura degli elaboratori (AE AA008)
• Architetture parallele e distribuite (ASE AA024)

L'elenco del contenuto delle lezioni e' disponibile alla pagina apposita: CCP 06-07: elenco delle lezioni

L'esame può essere sostenuto in due modi

• in forma seminariale, con la presentazione ai colleghi di una relazione da produrre anche in forma scritta su un argomento concordato con il docente, che sviluppi il materiale trattato nel corso delle lezioni; tale modalita', salvo casi particolari, e' da considerarsi valida entro le date degli appelli di luglio.
• sotto forma di progetto individuale, ad esempio utilizzando uno dei sistemi software esaminati nel corso per implementare uno degli algoritmi studiati; si terrà conto della soluzione fornita in sé, ma anche della capacità del candidato di valutare aspetti vantaggiosi e svantaggiosi del particolare sistema scelto (si veda in proposito la tabella di valutazione usata nel corso del 2005-06). Sono in generale accettati (previa discussione) progetti implementativi in più ambienti diversi, tra cui MPI e ASSIST, con attenzione al confronto prestazionale ed espressivo tra gli ambienti scelti.

Gli argomenti elencati costituiscono un suggerimento, non un vincolo, comunque consiglio di discuterne di persona prima di iniziare il lavoro.

• Realizzazione di algoritmi paralleli out-of-core con FG, analisi approfondita del framework FG, confronto di espressività con altri sistemi.
• Studio di algoritmi BSP che risolvono i problemi visti nel corso: ricerca in letteratura, implementazione su librerie BSP, emulazione su ASSIST, su MPI. Approfondimenti sulla simulabilità in memoria esterna di modelli della famiglia BSP, approfondimenti sul modello EdD-BSP.
• Sviluppo di una versione di DBSCAN parallelo in ASSIST, a partire anche dal codice esistente in SkIE.
• Implementazione in parallelo di algoritmi di classificazione per tree induction (C4.5 e simili). È possibile sviluppare il prototipo esistente di C4.5 in ASSIST.