Diario delle lezioni

Per ogni lezione vengono riportati riferimenti a paragrafi dei libri di testo e/o articoli scientifici.

Avvertimento

L’unione dei paragrafi può non rappresentare la totalità degli argomenti trattati durante la lezione.

---

16/04/2025 - TBD

• TBD

---

14/04/2025 - Strutture dati concorrenti: FIFO Queue

• TBD

Riferimenti libro di testo

• [t1] ?

Link di approfondimento

• TBD

---

09/04/2025 - Strutture dati concorrenti: Set (approfondimenti) e Priority Queue

• Set

  • Harris + Search index

    • Resizable hash table

    • Skip list NUMASK

• Lock-free Priority Queue

  • Richiami

    • Heap

    • Calendar Queue

  • Linearizable (Sundell and Tsigats)

  • Lazy deletion

    • Timestamping (Lothan and Shavit)

    • Marked prefix (Linden and Johosson)

  • Adaptive (Marotta and Ianni and Pellegrini and Quaglia)

Altre Fonti

• Resizable hash table: Split-ordered lists: Lock-free extensible hash tables

• NUMASK: High Performance Scalable Skip List for NUMA

• Priority Queue by Sundell et al: Fast and lock-free concurrent priority queues for multi-thread systems

• Priority Queue by Lothan et al: Skiplist-based concurrent priority queues

• Priority Queue by Linden et al: A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention

• Priority Queue by Marotta et al:

  • A Lock-Free O(1) Event Pool and its Application to Share-Everything PDES Platforms

  • A conflict-resilient lock-free calendar queue for scalable share-everything PDES platforms

  • A Conflict-Resilient Lock-Free Linearizable Calendar Queue

---

07/04/2025 - Strutture dati concorrenti: Set Hashtable e Skip list

• Hashtable

• Skip list

Altre fonti

• High performance dynamic lock-free hash tables and list-based sets

• Skip lists: a probabilistic alternative to balanced trees

• Practical Lock-Feedom. Section 4.3.3

---

02/04/2025 - Strutture dati concorrenti: Set Lazy

• Set * Lazy list

Riferimenti libro di testo

• [t1] Sezione 9.6, 9.7

Altre fonti

• A Lazy Concurrent List-Based Set Algorithm

---

31/03/2025 - Strutture dati concorrenti: Set Harris

• Set * Harris” Linked List

Riferimenti libro di testo

• [t1] Sezione 9.8

• [t2] Sezione 8.3

Altre fonti

• A Pragmatic Implementation of Non-blocking Linked-Lists

---

26/03/2025 - Strutture dati concorrenti: Set

• Set * ADT * Global lock * Lock Coupling

Riferimenti libro di testo

• [t1] Sezione 9.1, 9.2, 9.3, 9.4, 9.5

24/03/2025 - Proprietà: Progresso

• Deadlock freedom

• Starvation freedom

• Lock freedom

• Wait freedom

• Obstruction freedom

• Minimal and maximal progress

• Fair execution

• Dependent and independent progress

• Blocking vs Non-blocking progress

• Esecuzione in isolamento

Riferimenti libro di testo

• [t1] Sezione 3.6, 3.7

• [t2] Sezione 3.2

Altre fonti

• On the nature of progress

---

19/03/2025 - Stack parte 2

• Stack

  • treiber, elimination stack

• Microbenchmark * rand * lrand48_r

Riferimenti libro di testo

• [t1] Sezione 11.2, 11.3

• [t2] Sezione 8.8

Altre fonti

• Elimination stack: A Scalable Lock-free Stack Algorithm

• rand

• lrand48_r

• GCC Thread Local Storage

17/03/2025 - Introduzione a strutture dati concorrenti - Stack parte 1

• Utilizzo di perf

• Stack * seriale, concorrente (pthread spinlock e mutex), treiber

Riferimenti libro di testo

• [t1] Sezione 11.1, 11.2

Altre fonti

• perf: * Perfwiki * Linux man

• Read Modify Write: Efficient synchronization of multiprocessors with shared memory

• Compare and swap: __sync built-in

• Treiber stack: Systems Programming: Coping With Parallelism

---

12/03/2025 - Proprietà: Correttezza

• Preliminari

  • ADT

  • History

  • Equivalenza

• Criteri

  • Sequential consistency

  • Linearizability

  • Sistemi transazionali

    • Serializability

    • Strict serializatbility

Riferimenti libro di testo

• [t1] Sezione 3.1, 3.2, 3.4, 3.5, 3.6, 3.6.1

• [t2] Sezione 3.1

Altre fonti

• Sequential consistency: How to make a multiprocessor computer that correctly executes multiprocess programs

• Linearizability: a correctness condition for concurrent objects

• Serializability: The Serializability of Concurrent Database Updates

---

10/03/2025 - Proprietà: Scalabilità

• Leggi di Amdahl, Gustafson, Sun-Li

• Scalabilità forte e debole

Riferimenti libro di testo

• [t1] Sezione 1.6

Altre fonti

• Another view on parallel speedup

• Legge di Amdahl Sezione 4 Eq. 11

---

05/03/2025 - Introduzione al corso (parte 2)

• Introduzione alla programmazione concorrente e parallela

  • Un esempio di programmazione concorrente e parallela: contare i numeri primi (parte 2)

---

Riferimenti libro di testo

• [t1] Sezione 1.1

Altre fonti

• Fetch and add: __sync built-in

• pthread_create

• pthread_exit

• pthread_join

• pthread_spin_init

• pthread_mutex_init

• pthread_create

• pthread_exit

• pthread_join

• pthread_spin_init

• pthread_mutex_init

03/03/2025 - Introduzione al corso (parte 1)

• Presentazione del corso

  • Programma

  • Prerequisiti

  • Libri di testo

  • Prova d’esame

  • Sito web

• Introduzione alla programmazione concorrente e parallela

  • Evoluzione dei processori

  • Un esempio di programmazione concorrente e parallela: contare i numeri primi (parte 1)

Riferimenti libro di testo

• [t1] Sezione 1.1

Altre fonti

• The free lunch is over by Herb Sutter

• Welcome to the jungle by Herb Sutter

• 50 Years of Microprocessor Trend Data by K. Rupp