ProgrammaDelCorso < Algo_par

---++Programma del Corso (Algoritmi Paralleli e Distribuiti, A.A. 2009-2010)

*<font color= 990000 >a) Introduzione</font>*

   * Modello multicore
   * Un esempio "giocattolo": contatore condiviso.
   * Produttore e consumatore
   * Legge di Amdahl

_Rif._ [HS08] Capitolo 1: tutto. 


*<font color= 990000 >b) Sezioni critiche e mutua esclusione</font>*

   * 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.


*<font color= 990000 >c) Correttezza e progresso</font>*

   * 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. 


*<font color= 990000 >d) Caso di studio: liste concorrenti</font>*

   * Sincronizzazione coarse-grained
   * Sincronizzazione fine-grained
   * Sincronizzazione ottimistica
   * Sincronizzazione lazy
   * Sincronizzazione non bloccante

_Rif._ [HS08] Capitolo 9: tutto. 

*<font color= 990000 >e) Algoritmi paralleli</font>*

   * 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.
This topic: Algo_par_dis > WebHome > WebHome0910 > ProgrammaDelCorso
Topic revision: r2 - 2009-12-03 - IreneFinocchi