2005-2006 Complementi di Calcolo Parallelo e Distribuito
Annunci relativi al corso
Archivio
- 23/03/2006
- Lezioni di recupero il 21/4 ed il 28/4 in aula D1.
- 22/02/2006
- Il giorno 13 marzo non ci sarà lezione.
- 22/02/2006
- Variazione Orario. come riportato dal sito della segreteria, la lezione del lunedì e' spostata in aula B1. La lezione del mercoledì e' spostata al giovedì mattina 11-13, aula D1.
- 06/02/2006
- Causa concomitanti impegni di ricerca, il corso di CCP non inizierà la settimana del 13 febbraio. La prima lezione si terrà Lunedì 20 Febbraio. Gli studenti interessati al corso sono pregati di contattare il docente per e-mail, per risolvere alcuni casi di sovrapposizione dell'orario con altri corsi.
- 16/01/2006
- Riunione preliminare al corso, il 1 febbraio alle ore 12.00, Dipartimento di Informatica, aula Seminari Ovest.
- 10/05/2006
- Recupero lezioni. Venerdì 12, 19, 26 maggio ore 11-13.
12 maggio : aula A.
19, 26 maggio : aula D1.
Resta da stabilire l'eventuale presentazione di seminari durante le ultime lezioni.
- 03/04/2006
- Il ricevimento da oggi al 19 Aprile compresi sarà su appuntamento via mail.
Informazioni essenziali
- Titolare:
- Massimo Coppola
- Pagina Web Ufficiale:
- Link alla segreteria didattica
- Orari:
- Orario Definitivo
Giorno | Ora | Aula |
Lunedì | 14-16 | B1 |
Giovedì | 11-13 | D1 |
- Orario di ricevimento:
- Martedì 15-17, o su appuntamento.
- Programma:
-
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.
- Materiale didattico:
-
- B. Wilkinson, M. Allen Parallel Programming, 2nd edition. 2005, Prentice-Hall. Disponibile in Biblioteca la prima edizione, C.1.2 w74 INF .
La maggior parte, vedi elenco lezioni.
- 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 (sarà reso disponibile durante il corso).
- (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
- Prerequisiti
- Sono un prerequisito fondamentale i corsi di Architettura 1 e 2 :
-
Architettura degli elaboratori (AE AA008)
-
Architetture parallele e distribuite (ASE AA024)
Si assume la conoscenza del linguaggio C o C++.
- Altri riferimenti:
- -
Seminari e progetti di fine corso
Proposte di seminari e progetti
Le proposte di entrambi i tipi devono essere oggetto di discussione ed accordo con il docente, e comunque consentire di dare una valutazione finale su un elaborato scritto ed una presentazione od esame orale.
Analisi di ambienti di programmazione
Di seguito trovate i riferimenti ai siti web di possibili argomenti, altri possono essere discussi ed aggiunti.
L'esame è costituito dalla valutazione dell'elaborato scritto e dal seminario svolto in aula.
L'argomento sono uno o più articoli scelti dal candidato (previo accordo su quali), eventualmente confrontando il particolare ambiente con MPI o con ASSIST, dove questo abbia senso, oppure provando ad utilizzare il tool e discutendo gli esperimenti eseguiti.
La valutazione dell'elaborato e della sua presentazione terrà conto di come e con che profondità siano coperti i tre aspetti Descrittivo, di Valutazione delle prestazioni e Valutazione della Programmabilità.
Seminari assegnati
- Proactive
- Ibis
- Processori multi-core
e modelli di programmazione
Progetti Assegnati
- muSkel
(descrizione, documentazione javaDoc, articoli, download)
- eSkel
(descrizione, articoli, alcuni esempi, download)
- Proactive
- Ibis
(descrizione, manuale, articoli, download)
- Il framework FG
(descrizione, articoli, tutorial, esempi, download)
Caratteristiche degli ambienti la cui valutazione è richiesta, ordinate per temi principali.
Descrizione dell'approccio
- Descrizione generale delle caratteristiche e dell'impostazione del sistema;
- Descrivere il tipo di modello di programmazione parallelo
- non strutturato/schemi paralleli/skeleton
- forme di parallelismo espandibili o fisse
- design pattern o skeleton forniti
- quali problematiche sono gestite
- sicurezza,
- controllo degli accessi,
- fallimenti di rete,
- sbilanciamento del carico,
- migrazione dei processi.
Aspetto prestazionale
- latenza, banda di comunicazione
- tempo di creazione di un oggetto remoto, o di una chiamata di metodo.
- possibilità di attraversare i firewall
- configurabilità,
- numero di porte richieste
- utilizzo di macchine virtuali
- costo in prestazioni delle caratteristiche generali fornite
Aspetto della programmabilità
- modularità
- riuso del codice
- percentuale di codice aggiunto/modificato nella trasformazione da programma sequenziale a parallelo,
- quantità e tipo delle modifiche richieste, ad esempio
- gestione di eccezioni,
- mantenere strutture dati aggiuntive,
- controllare direttamente la suddivisione del lavoro in parallelo
- integrazione con altri framework, standard, modelli a componenti
- complessità di realizzazione nello sfruttare le caratteristiche più avanzate del sistema.
Realizzazione di piccoli progetti
Realizzazione e discussione di progetti collegati agli argomenti visti nel corso, eventualmente a partire da codice sequenziale o parallelo già disponibile.
Gli ambienti per la realizzazione sono principalmente ASSIST ed MPI, si può concordare l'uso di un ambiente differente, scelto tra quelli oggetto di approfondimento.
- Implementazione del k-means in MPI e ASSIST.
- Implementazione di DBSCAN a partire dal codice della struttura dati R*-tree.
- Test dell'algoritmo di sort Slabpose con FG, implementazione in ASSIST.
- Implementazione di bucket e sample sort in ASSIST per array di dati più grandi della memoria locale e/o della memoria aggregata.
Link e informazioni utili
Sezione in fase di sviluppo.
Siti Web, Articoli scientifici
Mandelbrot
K-means parallelo
DBSCAN parallelo
Classificazione parallela
Sort parallelo
N-body parallelo
Programmazione genetica
Esplorazione / Ottimizzazione combinatoria
Software e librerie standard
Esecuzione di programmi MPI
Nota: contrariamente a quanto detto a lezione, la versione di MPI installata sulle macchine del centro di calcolo NON è omogenea; tendenzialmente MPICH sulle macchine Debian, LAM MPI sulle RedHat.
Bibliografia aggiuntiva
Memorie esterne
-
Survey Vitter: Jeff Vitter. External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA, ACM Computing Survey 33(2) Jun 2001, pp.209-271
N-body
- Articolo di J.P. Singh Jaswinder Pal Singh, Chris Holt, Takashi Totsuka, Anoop Gupta and John L. Hennessy. Load Balancing and Data Locality in Adaptive Hierarchical N-body Methods: Barnes-Hut, Fast Multipole, and Radiosity Journal of Parallel and Distributed Computing, 27 (2) p.118-141, 1995. Il file può dare problemi di visualizzazione e stampa.
N-Queen ed ottimizzazione combinatoria
Algoritmi Genetici