Algoritmi Paralleli e Distribuiti (A.A. 2009-2010)

Docente: Irene Finocchi

Ricevimento: speditemi mail per prendere un appuntamento ("cognome" AT di.uniroma1.it). Il mio studio è nella sede di Via Salaria, stanza 311. Tel: 06-49918428.

Avvisi

  • Risultati appello del 3 febbraio 2010. Per vedere il compito e avere chiarimenti prima del prossimo appello, potete venire martedì 16 febbraio alle 9:30 nel mio ufficio. Per la verbalizzazione fisserò una data successiva, congiunta con il secondo appello.

  • Recupero lezione persa lunedì 11 gennaio: mi scuso per l'assenza di lunedì. Possiamo recuperare le ore perse giovedì 14 gennaio, alle 9:00, in aula Alfa. Nel caso in cui l'Alfa dovesse essere occupata, ci sposteremo in Aula Seminari al terzo piano.

  • Nuova organizzazione seminari:
    • Lunedì 14 dicembre: queue locks (speakers: Bovi, Bartoloni) e hierarchical locks (speaker: Cascitelli).
    • Venerdì 18 dicembre: transactional memories (speakers: Perta, Vincenti).
    • Giovedì 7 gennaio: code, software combining (speakers: Benothman, Agostini, Epasto, Sterpa).
    • Lunedì 11 gennaio: hashing (speakers: Di Francesco, Di Federico, Di Marco).
    • Giovedì 14 gennaio: pile (speakers: Lombardi, Cipriani). Skiplists (speakers: Vaino, Bruno).
    • Lunedì 18 gennaio: code con priorità (speakers: Chiarelli, Stanisci). Barriers (speaker: Nicoletti). In aula seminari.

  • Recupero lezione persa giovedì 17 dicembre: possiamo recuperare le ore perse questo giovedì nel giorno successivo, venerdì 18 dicembre, dalle 12:00 alle 13:30, sempre in aula Alfa (nello slot riservato alla lezione di Sistemi Wireless della Prof.ssa Petrioli). Fatemi sapere se avete problemi, soprattutto gli speaker.

  • Giovedì 17 dicembre: vi confermo che la didattica dal terzo anno in poi è sospesa a causa dell'incontro con le aziende. Sto cercando uno slot (successivo a giovedì, al limite dopo le vacanze) in cui inserire i seminari che sarebbero stati previsti. Stay tuned: spero di risolvere rapidamente il problema e aggiornarvi quanto prima.

  • Risultati esonero! Per vedere il compito o avere chiarimenti, mercoledì 2 dicembre in aula oppure speditemi mail per venire a ricevimento.

  • Cambio aula: la lezione di lunedì 18 gennaio si svolgerà in aula seminari (stesso orario), poiché l'aula alfa sarà occupata per una seduta di laurea.

  • Assegnamento seminari:
    • Lunedì 14 dicembre: queue locks (speakers: Bovi, Bartoloni) e hierarchical locks (speaker: Cascitelli).
    • Giovedì 17 dicembre: barriers (speaker: Nicoletti). Transactional memories (speakers: Perta, Vincenti).
    • Giovedì 7 gennaio: code, software combining (speakers: Benothman, Agostini, Epasto, Sterpa).
    • Lunedì 11 gennaio: hashing (speakers: Di Francesco, Di Federico, Di Marco).
    • Giovedì 14 gennaio: pile (speakers: Lombardi, Cipriani). Skiplists (speakers: Vaino, Bruno).
    • Lunedì 18 gennaio: code con priorità (speakers: Chiarelli, Stanisci). In aula seminari.

Obiettivi del corso e programma

Nel corso studieremo tecniche per la progettazione di algoritmi paralleli (alberi bilanciati, partizionamento, accelerating cascades, pipelining, tour di Eulero, salto del puntatore, symmetry breaking) ed affronteremo alcune problematiche concrete relative alla programmazione di processori multicore (classici problemi di coordinamento e di gestione di memoria condivisa, definizioni di correttezza in contesti concorrenti, primitive di sincronizzazione, implementazione ed analisi di strutture dati concorrenti, contatori condivisi).

Programma dettagliato. Il programma definitivo, con riferimenti bibliografici, è disponibile a questo link.

Modalità d'esame

L'esame consiste di due prove: un "orale-scritto" (ovvero un orale svolto per iscritto, 60%) ed una presentazione orale (corredata da lucidi) su un argomento assegnato a metà corso (40%).

Nella settimana di interruzione della didattica è prevista una prova intermedia sugli argomenti affrontati nella prima parte del corso.

Libri di testo e materiale di studio

Per la parte sul multicore:

  • Maurice Herlihy & Nir Shavit, "The art of multiprocessor programming", Morgan Kaufmann Publishers, 2008.

Una copia del libro è disponibile nella nostra biblioteca.

Slides su liste collegate:

Per la parte sul parallelo (PRAM):

  • Dispensa del Prof. Uzi Vishkin, "Thinking in parallel: some basic data-parallel algorithms and techniques", 2009, disponibile a questo link.
  • Appunti del corso svolto nell'A.A. 2008-2009, a cura della Prof.ssa Petreschi e del Dott. Caminiti, disponibili a questo link.

Diario delle lezioni

Settembre 2009
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
  01 02 03 04 05 06
07 08 09 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28
Introduzione al corso. Memoria condivisa. Modello PRAM (esempio: somma di n numeri). Modello multicore e thread asincroni (esempio: enumerazione di primi)
29 30        

Ottobre 2009
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
      01
Alice, Bob e il cortile "esclusivo": tre protocolli
02 03 04
05
Alice e Bob divorziano: Bob produce, Alice consuma. 2-thread locks: classe LockOne
06 07 08
2-thread locks: LockTwo e Peterson. Lock first-come-first-served: algoritmo di Lamport (bakery).
09 10 11
12
Bakery: mutua esclusione. Bounded timestamps: grafo delle precedenze.
13 14 15
Lower bound. Peterson all'opera: in teoria è corretto, ma perché non funziona? Primitive hardware di sincronizzazione: TAS e TTAS lock.
16 17 18
19
Architetture NUMA e SMP. Cache coherence. Contatore condiviso tramite compare-and-swap. Wait e lock freedom. Introduzione alla correttezza.
20 21 22
Tutto su consistenza quiescente e consistenza sequenziale. Introduzione alla linearizzabilità.
23 24 25
26
Lezione annullata
27 28 29
Lezione annullata
30 31  

Novembre 2009
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
            01
02
Linearizzabilità. Introduzione alle liste concorrenti.
03 04 05
Liste concorrenti: sincronizzazione coarse-grained, fine-grained (hand-by-hand locking), ottimistica (wait-free traversal + validation).
06 07 08
09
Interruzione didattica
10 11 12
PROVA INTERMEDIA
13 14 15
16
Sincronizzazione lazy. Introduzione all'implementazione non bloccante: AtomicMarkableReference.
17 18 19
Implementazione non bloccante. Richiamo al modello PRAM.
20 21 22
23
Somme prefisse. Merging e ranking: algoritmo surplus log e seriale.
24 25 26
Ranking efficiente in tempo logaritmico. Mergesort parallelo. Accelerating cascades: selezione.
27 28 29
30
Implementazione parallela dell'algoritmo del mediano dei mediani. Introduzione al pipelining.
           

Dicembre 2009
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
  01 02
Inserimento pipelined in alberi 2-3. Discussione esoneri.
03 04 05 06
07
Tour di Eulero e problemi su alberi.
08 09 10
Dynamic program analysis ed implicazioni algoritmiche.
11 12 13
14
Seminari: queue locks e hierarchical locks.
15 16 17 18
Seminari: transactional memories.
19 20
21 22 23 24 25 26 27
28 29 30 31      

Gennaio 2010
Lunedì Martedì Mercoledì Giovedì Venerdì Sabato Domenica
        01 02 03
04 05 06 07
Seminari: code, software combining.
08 09 10
11
Seminari: hashing.
12 13 14
Seminari: pile, skiplists.
15 16 17
18
Seminari: code con priorità, barriers.
19 20 21 22 23 24
25 26 27 28 29 30 31

Diario delle lezioni in formato testo




This topic: Algo_par_dis > WebHome > WebHome0910
Topic revision: r27 - 2010-03-01 - IreneFinocchi
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback