Advanced Topics in Concurrent Programming

 

Computer Science Seminar,  236832,  Spring 2022

Instructor: Erez Petrank, erez@cs, office: Taub 528. Phone: 829-4942.

 

Announcements:

 

Topics:

Introduction (all talks in this section are taken from the Art of Multiprocessor Programming by Herlihy & Shavit available at the library):

  1. Introduction to Concurrency: hardware and software, see Appendix A and B of the book. Assigned to Elad Kinsbruner. Presentation (March 30)
  2. "Spin locks and contention in practice", chapter 7 in the book.  Assigned to Arad Kotzer. Presentation (March 30)
  3. "Monitors and Blocking Synchronization",  chapter 8 in the book. Assigned to Tamir Daniel. Presentation (April 6)
  4. Properties of concurrent computation: correctness and progress, chapter 3 in the book.  Assigned to Erez Petrank. Presentation (April 6)

Concurrent Algorithms (several talks in this section (those referenced as "chapter n") are taken from the Art of Multiprocessor Programming by Herlihy & Shavit available at the library):

  1. Linked Lists: the Role of Locking, chapter 9. Assigned to Erez Petrank. Presentation () (April 13)
  2. Concurrent Queues and the ABA Problem, chapter 10. Assigned to Jonathan Ziskind. Presentation (April 27)
  3. Wait-free Queues (paper). Assigned to Hen Kas Sharir. Presentation (April 27)
  4. Concurrent Stacks and Elimination, chapter 11. Assigned to Tomer Adar. Presentation (May 2)
  5. Counting, Sorting, and Distributed Coordination, chapter 12. Assigned to Itay Eilat. Presentation (May 2)  
  6. Concurrent hashing and natural parallelism, chapter 13. Assigned to Yosef Goren. Presentation (May 18)
  7. Skiplists and Balanced Search, chapter 14. Assigned to Hod Badichi. Presentation (May 18)
  8. "A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention", (paper). Assigned to Omer Yerushalmi. Presentation (May 25)
  9. Futures, Scheduling, and Work Distribution, chapter 16.
  10. Barriers, chapter 17. Assigned to Nadav Adir.>Presentation (June 1)
  11. "Flat Combining", (paper). Assigned to Yonatan Medan. Presentation (June 1)
  12. "Lock-Free Snapshots", (paper). Assigned to Lior Cohen. Presentation (May 25)
  13. "Lock-Free Snapshots by multiversioning", (paper).

Memory Management for lock-free Data Structures:

  1. Hazard pointers (paper). Assigned to Erez Petrank. Presentation (June 8)
  2. Optimistic access (paper). Assigned to Erez Petrank. (June 8)
  3. IBR: Interval Based Reclamation (see paper).
  4. Hazard Eras - Non-Blocking Memory Reclamation (see paper). Assigned to Alon Kitin. Presentation (June 19)
  5. NBR: neutralization based reclamation (see paper). 
  6. VBR: Version Based Reclamation (see paper).

Debugging:

  1. Debugging tools: Microsoft's Chess (paper). Assigned to Yaniv Goft. Presentation (June 29)
  2. IBM’s synchronization coverage for testing (see paper). 
  3. A Randomized Scheduler for Bug Finding (see paper). Assigned to Amir Bishara. Presentation (June 22)
  4. Deterministic parallelism (see paper). Assigned to Avidan Borisov. Presentation (June 22)
  5. Record-Replay parallel executions (see paper

Systems Scalability:

  1. An Analysis of Linux Scalability to Many Cores. (see paper). Assigned to Yaniv Holder. Presentation (June 29)

Concurrent data structures on GPUs:

  1. Performance Evaluation of Concurrent Lock-free Data Structures on GPUs. (see paper). Assigned to Ella Sheory. Presentation (June 19)
  2. Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores. (see paper).

Concurrent data structures on non-volatile memory:

  1. A persistent lock-free queue for non-volatile memory. (see paper).
  2. Log-Free Concurrent Data Structures. (see paper).
  3. Efficient Lock-Free Durable Sets. (see paper).
  4. The Inherent Cost of Remembering Consistently. (see paper).
  5. Mirror: making lock-free data structures persistent. (see paper).
  6. Dalí: A Periodically Persistent Hash Map. (see paper).
  7. A Fast, General System for Buffered Persistent Data Structures. (see paper).

 

 

Grading

 

Administrative

 

Material Covered in the Seminar:

The day that every (new) computer employs parallel processing has arrived. But writing concurrent programs is notoriously difficult and a large amount of traditional sequential code exists. A major challenge to the industry and (applied) research today is to find ways to make the programming for concurrent systems easier and accessible for all programmers. We will present concurrency programming setting, discuss several concurrent data structures, and present server architecture. Another major challenge is the debugging and more generally the reliability of concurrent programs. Some bugs only appear infrequently under specific scheduling scenarios. What are the right tools to discover such bugs and fix them? What are the tools to verify that a code is correct? More challenges relate to progress guarantees, specifically, lock-freedom. In this seminar, we will discuss some of these questions and check which answers exist today.

 

Assignments:

Each student will prepare a talk on one of the topics above.   

 

Course Registration:

Registration is manual and we will attempt to match the registered students with the seminar topics. Please send an email to the lecturer (erez@cs) with your name, student id, grades transcript (תדפיס ציונים), and relevant experience in industry or lab projects. In addition, let me know if you can come to class physically to attend the seminar (in case the authorities allow physical teaching), or whether you cannot come to class, e.g., because you have special COVID conditions that prevent you from coming.

The final list of registered students will be determined after the first lecture in the beginning of the spring semester.