Advanced Topics in Concurrent Programming

 

Computer Science Seminar,  236832,  Winter 2016/7

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 Ariel Kolikant. Presentation
  2. "Spin locks and contention in practice", chapter 7 in the book. 
  3. "Monitors and Blocking Synchronization",  chapter 8 in the book.  Assigned to Koral Chepnik. Presentation
  4. Properties of concurrent computation: correctness and progress, chapter 3 in the book. Assigned to Ali Tabaja. Presentation

Concurrent Algorithms (all talks in this section, except 7, 14, and 15, 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
  2. Concurrent Queues and the ABA Problem, chapter 10. Assigned to Gail Weiss. Presentation
  3. Wait-free Queues (paper).  Assigned to Noa Shahar. Presentation
  4. Concurrent Stacks and Elimination, chapter 11.  Assigned to Michal Dory. Presentation
  5. Counting, Sorting, and Distributed Coordination, chapter 12.  Assigned to Ori Roth. Presentation
  6. Concurrent hashing and natural parallelism, chapter 13. Assigned to Orit Mussel. Presentation
  7. Skiplists and Balanced Search, chapter 14. Assigned to Yaniv Rubin. Presentation
  8. Priority Queues, chapter 15. Assigned to Avner Elizarov. Presentation
  9. Futures, Scheduling, and Work Distribution, chapter 16.
  10. Memroy management for lock-free data structures: hazard pointers (paper). Assigned to Gregory Schwartzman. Presentation
  11. Memory management for lock-free data structures: optimistic access (paper). Assigned to Olga Geller. Presentation
  12. Barriers, chapter 16.  Assigned to Amit Rapaport. Presentation

Debugging:

  1. Debugging tools: Microsoft's Chess (paper).
  2. IBM’s synchronization coverage for testing (see paper). 
  3. A Randomized Scheduler for Bug Finding (see paper and a follow-up).
  4. Deterministic parallelism (see paper).
  5. Record-Replay parallel executions (see paper

Systems Scalability:

  1. An Analysis of Linux Scalability to Many Cores. (see paper).  Assigned to Roded Zetz. Presentation

Concurrent data structures on GPUs:

  1. Performance Evaluation of Concurrent Lock-free Data Structures on GPUs. (see paper). 
  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. Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory. (see paper). 
  2. Persistent B+-Trees in Non-Volatile Main Memory. (see paper).

Server architectures:

  1. Reliability: Amazon's Dynamo. Assigned to Anthony Lechtman. Presentation
  2. Facebook's (now Apache's) Cassandra: see this paper. Assigned to Naama Baumel. Presentation
  3. Google's Big-Table. Assigned to Itamar Hatzor. Presentation
  4. Spanner: Google’s Globally-Distributed Database. Assigned to Kfir Lev-Ari. Presentation

Languages and Runtimes for Concurrent and Distributed Programming:

  1. Microsoft’s Orleans runtime (see paper). 
  2. IBM's X10 programming language. (See webpage for researchers.). 
  3. Google's Map-Reduce. See also this paper. Assigned to Yonathan Zarecki. Presentation
  4. Sun's Fortress (see paper, and slides from a tutorial). 
  5. The Cilk programming language and implementation (see paper). Assigned to Gal Sade. Presentation
  6. Microsoft's Singularity project (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, accumulated average, umber of academic points accumulated by the end of the current semester, relevant courses studied, 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 winter semester.