Tags:
create new tag
view all tags

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.
Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2009-12-03 - IreneFinocchi





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback