Programma del Corso (Algoritmi Paralleli e Distribuiti, A.A. 2009-2010)
a) Introduzione
- Modello multicore
- Un esempio "giocattolo": contatore condiviso.
- Produttore e consumatore
- Legge di Amdahl
Rif. [HS08] Capitolo 1: tutto.
b) Sezioni critiche e mutua esclusione
- 2-thread locks: algoritmo di Peterson
- n-thread locks: algoritmo di Lamport
- Fairness
- Timestamp limitati
- Lower bound sul numero di locazioni di memoria nel caso di 3 thread
- Test-and-Set locks: TAS e TTAS
- Backoff esponenziale
Rif. [HS08] Capitolo 2: tutto tranne il paragrafo 2.4. Capitolo 7, paragrafi da 7.1 a 7.4. Appendice B, paragrafi da B.1 a B.6.
c) Correttezza e progresso
- Consistenza quiescente
- Consistenza sequenziale
- Linearizzabilità
- Nozioni di progresso nel caso di sincronizzazione bloccante e non.
Rif. [HS08] Capitolo 3: tutto tranne i paragrafi 3.7.1 e 3.8.
d) Caso di studio: liste concorrenti
- Sincronizzazione coarse-grained
- Sincronizzazione fine-grained
- Sincronizzazione ottimistica
- Sincronizzazione lazy
- Sincronizzazione non bloccante
Rif. [HS08] Capitolo 9: tutto.
e) Algoritmi paralleli
- Modello PRAM, lettura e scrittura esclusive o concorrenti
- Calcolo di somme e somme prefisse
- Merging e ranking, ranking efficiente in tempo logaritmico. Mergesort parallelo.
- Accelerating cascades: selezione. Implementazione parallela dell'algoritmo del mediano dei mediani
- Pipelining e implementazione di alberi 2-3.
- Tour di Eulero e problemi su alberi.
Rif. [V09] Capitoli 1 e 2, paragrafo 3.1, capitoli 4 e 5, capitolo 7 tranne paragrafo 7.3, paragrafi 9.1 e 9.2. [CP09] Slides dell'8/5/09 (tour di Eulero).
Riferimenti bibliografici:
- [HS08] "The art of multiprocessor programming", Herlihy e Shavit, 2008.
- [V09] Dispensa Uzi Vishkin, "Thinking in parallel: some basic data-parallel algorithms and techniques", 2009.
- [CP09] Appunti del corso svolto nell'A.A. 2008-2009, a cura della Prof.ssa Petreschi e del Dott. Caminiti.