Seminar in Concurrent Programming
- 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 19 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.
- Introduction to Concurrency: hardware and software, see Appendix A and B of the book.
- "Spin locks and contention in practice", chapter 7 in the book.
- "Monitors and Blocking Synchronization", chapter 8 in the book.
- Properties of concurrent computation: correctness and progress, chapter 3 in the book. Assigned to Erez Petrank. Presentation
- Linked Lists: the Role of Locking, chapter 9. Assigned to Erez Petrank. Presentation
- Concurrent Queues and the ABA Problem, chapter 10.
- Wait-free Queues (paper).
- Concurrent Stacks and Elimination, chapter 11.
- Concurrent hashing and natural parallelism, chapter 13.
- Skiplists and Balanced Search, chapter 14.
- "A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention", (paper).
- Futures, Scheduling, and Work Distribution, chapter 16.
- Barriers, chapter 17.
- "Lock-Free Snapshots", (paper).
- "Lock-Free Snapshots by multiversioning", (paper).
- "Concurrent Size", (paper).
- Counting, Sorting, and Distributed Coordination, chapter 12.
- "Flat Combining", (paper).
- Hazard pointers (paper). Assigned to Erez Petrank. Presentation
- Optimistic access (paper). Assigned to Erez Petrank.
- IBR: Interval Based Reclamation (see paper).
- Hazard Eras - Non-Blocking Memory Reclamation (see paper).
- NBR: neutralization based reclamation (see paper).
- VBR: Version Based Reclamation (see paper).
- Debugging tools: Microsoft's Chess (paper).
- IBM’s synchronization coverage for testing (see paper).
- A Randomized Scheduler for Bug Finding (see paper).
- Deterministic parallelism (see paper).
- Record-Replay parallel executions (see paper)
- An Analysis of Linux Scalability to Many Cores. (see paper).
- Performance Evaluation of Concurrent Lock-free Data Structures on GPUs. (see paper).
- Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores. (see paper).
- A persistent lock-free queue for non-volatile memory. (see paper).
- Log-Free Concurrent Data Structures. (see paper).
- Efficient Lock-Free Durable Sets. (see paper).
- The Inherent Cost of Remembering Consistently. (see paper).
- Mirror: making lock-free data structures persistent. (see paper).
- Dalí: A Periodically Persistent Hash Map. (see paper).
- A Fast, General System for Buffered Persistent Data Structures. (see paper).
- Lecture (at least 85%),
- Participation (at most 15%),
- Reduction of 5 points for each (unjustified) absence. A justified absence requires a summary of the 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!
- 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.)
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.
Each student will prepare a talk on one of the topics above.
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, updated 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.