Advanced Topics in Concurrent Programming

Computer Science Seminar,  236832,  Spring 2021

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

Announcements:

• This is a link to the story about the bug in the Pathfinder Shuttle to Mars .
• We will continue to run the seminar on Zoom. Four students said it would be extremely difficult for them to come physically and two said they will not be able to come. This is perfectly fine at this time of the pandemic. See you on April 21st on Zoom.
• My first talk's presentation is here.
• We will run the seminar on Zoom (non-hybrid) and all students give talks via zoom. This might change during the semester as we go along; I will keep you updated.
• The zoom link for our meetings is available only to Technion users (so please sign in to access): https://technion.zoom.us/j/98032346750 .
• This year there were too many requests to register (more than twice as many as I could accept). I apologize to all students that could not register. Students I could enroll are listed on this page.
• See registration instructions at the end of the page.
• There exists an errata file with known errors in the book. If your lecture is from the book, please take a look at it.
• About the schedule of the talks: the students who will register will pick about 17 of the (unassigned) topics below. Each selected topic will be given in a single class (50 minutes), meaning 2 topics a week. So the exact timing of a lecture will be determined only when all registered students will pick their topics, which will probably only happen at the first week on the semester. But the order between talks is as listed below.

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.
2. "Spin locks and contention in practice", chapter 7 in the book.  Assigned to Adi Simhi. Presentation (Week 2.)
3. "Monitors and Blocking Synchronization",  chapter 8 in the book. Assigned to Nadav Elias. Presentation (Week 2.)
4. Properties of concurrent computation: correctness and progress, chapter 3 in the book. Assigned to Amit Ganz. (Week 4.) Presentation

Concurrent Algorithms (all talks in this section, except 7, 12, 14, and 15, are taken from the Art of Multiprocessor Programming by Herlihy & Shavit available at the library):

5. Linked Lists: the Role of Locking, chapter 9. Assigned to Erez Petrank. Presentation (Week 3.)
6. Concurrent Queues and the ABA Problem, chapter 10. Assigned to Yuval Lubarsky. (Week 4.) Presentation
7. Wait-free Queues (paper). Assigned to Samy Zaitoun. (Week 5.) Presentation
8. Concurrent Stacks and Elimination, chapter 11. Assigned to Oren Rozenberg. (Week 5.) Presentation
9. Counting, Sorting, and Distributed Coordination, chapter 12. 
10. Concurrent hashing and natural parallelism, chapter 13. Assigned to Alice Epstein. (Week 6.) Presentation
11. Skiplists and Balanced Search, chapter 14. Assigned to Michael Mendelson Mintz. (Week 6.) Presentation
12. "A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention", (paper). Assigned to Barak Belogolovsky. (Week 7.) Presentation
13. Futures, Scheduling, and Work Distribution, chapter 16. Assigned to Shaked Elias-Zada. (Week 7.) Presentation
14. Memroy management for lock-free data structures: hazard pointers (paper). Assigned to Erez Petrank. Presentation (Week 8.)
15. Memory management for lock-free data structures: optimistic access (paper). Assigned to Erez Petrank. (Week 8.)
16. Barriers, chapter 17. Assigned to Omer Aviram. (Week 9.)  Presentation
17. "Lock-Free Snapshots I", (paper).
18. "Lock-Free Snapshots II", (paper).
19. "Flat Combining", (paper).

Debugging:

20. Debugging tools: Microsoft's Chess (paper).Assigned to Sagi Levanon. (Week 9.) Presentation
21. IBM’s synchronization coverage for testing (see paper). 
22. A Randomized Scheduler for Bug Finding (see paper).
23. Deterministic parallelism (see paper). Assigned to Almog Zur. (Week 10.) Presentation
24. Record-Replay parallel executions (see paper) 

Systems Scalability:

30. An Analysis of Linux Scalability to Many Cores. (see paper). Assigned to Idan Raz. (Week 10.) Presentation

Concurrent data structures on GPUs:

35. Performance Evaluation of Concurrent Lock-free Data Structures on GPUs. (see paper). Assigned to Dan Kalifa. (Week 11.) Presentation
36. 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:

40. A persistent lock-free queue for non-volatile memory. (see paper). Assigned to (guest lecturer) Michal Friedman. (Week 12.) Presentation
41. Log-Free Concurrent Data Structures. (see paper).
42. Efficient Lock-Free Durable Sets. (see paper). Assigned to Noa Schiller. (Week 12.) Presentation
43. Persistent B+-Trees in Non-Volatile Main Memory. (see paper).
44. The Inherent Cost of Remembering Consistently. (see paper).

Languages and Runtimes for Concurrent and Distributed Programming:

50. Microsoft’s Orleans runtime (see paper). 
51. Google's Map-Reduce. See also this paper.
52. The Cilk programming language and implementation (see paper).

Server architectures:

60. Reliability: Amazon's Dynamo. Assigned to Ramy Fakhoury. (Week 11.) Presentation
61. Facebook's (now Apache's) Cassandra: see this paper. Assigned to Shai Feldman. (Week 13.) Presentation
62. Spanner: Google’s Globally-Distributed Database. Assigned to Tomer Voronov. (Week 13.) Presentation

Grading

• Lecture (at least 85%),
• Participation (at most 15%),
• Reduction of 5 points for each (unjustified) absence.
• Each justified absence requires summary of missed lecture.
• The talk will be graded by: Knowledge of the material, Slides effectiveness, Communication of the ideas, and working within the time limit of 50 minutes.
• Main goal: make people understand!

Administrative

• Course syllabus (in Hebrew)
• Prerequisites: Algorithms 1 (234247)  and  Operating Systems (234123). Further knowledge in concurrent systems will help to understand the topics presented.
• Reception hours: TBD. (If this is not a good time for you, contact me by email to schedule an alternative.)

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.

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