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.