Tags:
create new tag
view all tags

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



Edit | Attach | Watch | Print version | History: r27 < r26 < r25 < r24 < r23 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r27 - 2010-03-01 - IreneFinocchi






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