798 Multicore programming
Instructor: Trevor Brown
E-mail: trevor (dot) brown (at) uwaterloo (dot) ca (include 798 in your subject)
Times: MW 3:30-4:50, DC 2585
My office: DC 2338
Please join and use the new class Piazza for your questions (unless they are sensitive).
We will also use Piazza to coordinate student presentation paper selections and for assignment submission.
- Nov 27: Assignment 3 is posted! It is due soon (Tue Dec 11th). Go go go!
- Nov 12: Assignment 2 deadline moved to Monday Nov 19.
- Nov 5: Assignment 2 is posted! It is due very soon (Wed Nov 14th), so start on it ASAP!
- Nov 5: See new requirement for student presentations (meeting to give feedback on slides)
- Oct 25: C++ Code is posted for the OpenMP, GDB and Valgrind examples in the Week 6 slides (below)
- Oct 24: Guidelines and samples/templates posted for paper reviews and presentation feedback (on Piazza)
- Oct 8: Guidelines are posted for students presenting papers and listening to presentations
- Oct 8: Assignment submission guidelines added
- Oct 8: There is now a class Piazza - Join it!!
- Oct 1: There will be no class on Monday the 8th, or Wednesday the 10th, or Friday the 12th. (Happy reading week!)
- Oct 1: Student presentation dates have been updated
- Oct 1: Assignment 1 is out!
|Week 1 - Monday
||Asynchronous shared memory, counters, linearizability, cache coherence, false sharing
Paper that introduced Linearizability
A few slides on cache coherence (Technion)
|Week 1 - Wednesday
||More on padding, lock-freedom, lock-free stack (& proof sketch)
Treiber stack (original paper)
Optional: a later stack technique (elimination)
Optional: even later stacks
Optional: hazard pointers (memory reclamation)
Optional: Treiber stack with hazard pointers for memory reclamation
|Week 2 - Monday
||Stacks, queues, relaxed data structures, hash tables
Optional: first lock-free queue
Optional: newer queues
Optional: Multi-Queue paper (mostly about graphs)
|Week 2 - Wednesday
||Hash tables and deletion
Expandable hash table we are studying
|Week 3 - Monday
||Expanding a hash table
(Same hash table paper as last class)
|Week 3 - Wednesday
||More efficient expansion, linked data structures
Harris' linked list
|Week 4 - Monday
||k-word CAS and a doubly-linked list
|Week 4 - Wednesday
||Implementing DCSS and k-word CAS
k-CAS paper we are studying
My own fast C++ code for k-CAS (uses advanced techniques)
|Week 5 - Monday
||Wrapping up k-word CAS
Optional: my paper showing how to reuse descriptors
|Week 5 - Wednesday
Intel's restricted transactional memory (RTM) - also called HTM / TSX-NI
Nice article on lock elision and Intel's RTM
Some slides on using lock elision in Linux kernel
|Week 6 - Monday
||Advanced uses of transactional memory, OpenMP
Paper that introduced HTM-based KCAS
Nice slides on OpenMP
C++ code examples for this lecture's OpenMP slides
|Week 6 - Wednesday
||Try-locks, versioned locks, lock-based KCAS + HTM, debugging tools
GCC transactional memory intrinsics
A GDB tutorial (incl. relevant compilation options)
Very short Valgrind intro
A few nice Valgrind examples
A guide to Valgrind (with good frequently asked questions)
C++ code examples for this lecture's GDB and Valgrind slides
Assignment 3 [Starting code]
Assignment 2 [Starting code]
- Submit your assignment on Piazza in the "assignment 3" folder as a private post to instructors.
- Submit everything in a single ZIP file attached to your post.
Assignment 1 [Starting code]
- Submit your assignment on Piazza in the "assignment 2" folder as a private post to instructors.
- Submit everything (your PDF and your code) in a single ZIP file attached to your post.
- Submit your assignment on Piazza, in folder "assignment 1," as a private post with "Instructors" as the only users with view permissions.
- The written portion of the assignment should be submitted as a PDF attachment to your post (12pt+ font please).
- The code portion should be submitted as a ZIP attachment to your post.
- Your code should compile when I execute "make"
The current presentation schedule is here.
- Please choose your paper by Oct 12, and make your selection on Piazza
- Two weeks before your presentation, I would like to meet to discuss a rough outline of your presentation
- e-mail me to schedule a meeting
- e-mail me a ~1 page PDF outline (just bullet points) at least 24h before our meeting (earlier = better)
- [NEW] Approximately one week before your presentation, I would like to meet to give feedback on your slides!
Student presentation guidelines
- One week before your presentation, post to Piazza (presentations folder) announcing your paper
- ~30 minute presentation, ~15 minute discussion
- Give a high level overview of the algorithm/data structure/idea
- Present aspects of the paper that you would be interested to hear (no proofs / deep details unless that's what you would be interested in)
- Try to extract the most interesting aspects of the ideas (discard uninteresting details)
- Proving you understand everything is not as important as conveying something interesting to the audience
- Big fonts (28pt+), do not use too much text
- Start with one or two examples of the problem being solved! Don't worry about it being too simple!
- Prepare some discussion questions to drive the discussion if needed
- If you can, try to be ready to take student questions during the talk
- After your presentation, post your slides in your Piazza announcement post
Presenting students will be graded on their presentations.
Briefly read / skim the two papers before class (see paper announcement posts in Piazza)
- Detailed read through of introduction, related work, conclusion
- Quick skim through the other parts of the paper
- This should take at most 2 hours per paper
- For each presentation, I will create a public Piazza folder
- Each class, pick one paper to write a summary on (following the format on Piazza)
- Submit this summary as a private post in the appropriate Piazza folder
- Each class, pick one presentation to provide feedback on (following the format on Piazza)
- Submit via a Piazza post that is anonymous to students (but not to me!) in the appropriate Piazza folder
- In the week you present, you are exempt, and do not have to write any summary / feedback
Listening students will be graded on their reviews and feedback.
See Piazza to determine which papers are already taken.
GPU data structures and algorithms
NUMA systems (multiple physical processors)