Advanced Topics in Concurrent Programming

Computer Science Seminar 3,  236803,  Spring 2012

Instructor: Erez Petrank, erezcs.technion.ac.il, office: Taub 528. Phone: 829-4942.

 

Announcements

¥   Notice that Tuesday May 15th has also been declared as an academic Thursday.

¥   On Monday (!) April 23rd (which is an academic Thursday) weÕll have our next seminar talks by Nitzan and Eyal.

¥   On Thursday April 19th there is no meeting as I am out of the country.

¥   On Thursday April 12th there is no meeting due to Passover.

¥   On Thursday April 5th weÕll have an invited talk by Ofir Amir on Netflix.

¥   A link to the library copy of the course book is here.

¥   My introductory talk can be found here. (see also a pdf version.) 

¥   For those preparing a talk from the book, there is an errata document here .

¥   The topics have been assigned as below. If anybody would like to be on a waiting list (in case someone cancels) please let me know. Everybody (even if not registered) is welcomed to come and listen to the talks.

¥   There were 60 requests and only 20 spots in the seminar, so I was not able to satisfy most of the requests.

¥   Out of the 27 topics below, 20 were picked by students and these form the seminar topics.

Topics:

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

1.    "Spin locks and contention in practice" chapter 7 in the book. Assigned to Daniel Garfunkel.  The presentation is here.

2.           "Monitors and Blocking Synchronization", chapter 8 in the book. Assigned to Avishai Gretz. The presentation is here.

Data Race Detection:

3.           Data race detection: preliminaries and survey. Assigned to Hadar Sivan. The presentation is here.

4.           Data race detection: computational aspects. Assigned to Arnon Yogev. The presentation is here.



 

Concurrent Algorithms (all talks in this section, except 10, 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 Nitzan Chrizman. The presentation is here.

6.           Concurrent Queues and the ABA Problem, chapter 10. Assigned to Eyal Zohar. The presentation is here. A print version is here.

7.           Wait-free Queues (paper).  Assigned to Dana Drachsler. The presentation is here.

8.           Concurrent Stacks and Elimination, chapter 11. Assigned to Avichai Shlezinger. The presentation is here.

9.           Counting, Sorting, and Distributed Coordination, chapter 12. Assigned to Matan Hamillis. The presentation is here.

10.        Concurrent hashing and natural parallelism, chapter 13. Assigned to Alexander Yavorovsky. The presentation is here.

11.         Skiplists and Balanced Search, chapter 14. Assigned to Shai Barad. The presentation is here.

12.        Priority Queues, chapter 15. Assigned to Alexander Nus. The presentation is here.

13.        Futures, Scheduling, and Work Distribution, chapter 16. Assigned to Lila Shnaiderman. The presentation is here.

Server architectures:

14.                 NetFlixÕs story. Invited talk by Ofir Amir.

15.                 Reliability: Amazon's Dynamo. Assigned to Edward Dovzhik. The presentation is here

Languages for Concurrent Programming:

16.                 Google's Map-Reduce. See also this paper. Assigned to Amit Carmeli.

17.                 Google's Big-Table. Assigned to Haitham Khateeb.

18.                 Sun's Fortress (see paper). Assigned to Dor Zomer.



Debugging:

19.                 Debugging tools: Microsoft's Chess (paper). Assigned to Yuval Degani.

20.                 IBMÕs synchronization coverage for testing (see paper).  Assigned to Asaf Corem.

21.                 Deterministic parallelism (see paper) . Assigned to Adi Fuchs.

 



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-70 minutes.

¥   Main goal: make people understand!

Administrative

¥   Course syllabus (in Hebrew)

¥   Prerequisites: Algorithms 1 (234247)  and  Operating Systems (234123). Further knowledge in concurrent systems and programming languages 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 using Powerpoint slides.    

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.