Diario delle lezioni (Algoritmi Paralleli e Distribuiti, A.A. 2009-2010)

• 28 Sep - Introduzione al corso. Memoria condivisa. Modello PRAM (esempio: somma di n numeri). Modello multicore e thread asincroni (esempio: enumerazione di primi)

• 01 Oct - Alice, Bob e il cortile "esclusivo": tre protocolli

• 05 Oct - Alice e Bob divorziano: Bob produce, Alice consuma. 2-thread locks: classe LockOne

• 08 Oct - 2-thread locks: LockTwo e Peterson. Lock first-come-first-served: algoritmo di Lamport (bakery).

• 12 Oct - Bakery: mutua esclusione. Bounded timestamps: grafo delle precedenze.

• 15 Oct - Lower bound. Peterson all'opera: in teoria è corretto, ma perché non funziona? Primitive hardware di sincronizzazione: TAS e TTAS lock.

• 19 Oct - Architetture NUMA e SMP. Cache coherence. Contatore condiviso tramite compare-and-swap. Wait e lock freedom. Introduzione alla correttezza.

• 22 Oct - Tutto su consistenza quiescente e consistenza sequenziale. Introduzione alla linearizzabilità.

• 26 Oct - Lezione annullata

• 29 Oct - Lezione annullata

• 02 Nov - Linearizzabilità. Introduzione alle liste concorrenti.

• 05 Nov - Liste concorrenti: sincronizzazione coarse-grained, fine-grained (hand-by-hand locking), ottimistica (wait-free traversal + validation).

• 09 Nov - Interruzione didattica

• 12 Nov - PROVA INTERMEDIA

• 16 Nov - Sincronizzazione lazy. Introduzione all'implementazione non bloccante: AtomicMarkableReference.

• 19 Nov - Implementazione non bloccante. Richiamo al modello PRAM.

• 23 Nov - Somme prefisse. Merging e ranking: algoritmo surplus log e seriale.

• 26 Nov - Ranking efficiente in tempo logaritmico. Mergesort parallelo. Accelerating cascades: selezione.

• 30 Nov - Implementazione parallela dell'algoritmo del mediano dei mediani. Introduzione al pipelining.

• 02 Dec - Inserimento pipelined in alberi 2-3. Discussione esoneri.

• 07 Dec - Tour di Eulero e problemi su alberi.

• 10 Dec - Dynamic program analysis ed implicazioni algoritmiche.

• 14 Dec - Seminari: queue locks e hierarchical locks.

• 18 Dec - Seminari: transactional memories.

• 07 Jan - Seminari: code, software combining.

• 11 Jan - Seminari: hashing.

• 14 Jan - Seminari: pile, skiplists.

• 18 Jan - Seminari: code con priorità, barriers.