CS798 Multicore programming - W21 term

Instructor: Trevor Brown
E-mail: trevor ( d o t ) brown ( a t ) uwaterloo ( d o t ) ca (include 798 in your subject)
Times: Asynchronous pre-recorded videos
Tutorials / discussion: weekly synchronous online, time to be decided by class poll
My office: DC 2338 ( not that I am allowed in it :) )
Course syllabus

Relevant Links

Marmoset (for submitting code)
Crowdmark (for submitting written material -- may need to switch from instructor view to student view at the top right)
Re: dev environment, my current recommendation is to use VSCode with the Remote Development (Microsoft) extension, which allows you to connect via SSH to remote servers and develop on them directly as if they were local. You probably don't have 32 cores on your desktop/laptop, and developing/testing on a large scale machine is a must to understand how your code will scale. Some tips and tricks for connecting to our servers (some of which you'll gain access to) and configuring vscode.
You should know about pubkey authentication, bash tools, and it can't hurt to know about TMUX

Slides

Class	Topics	Video	Slides	Supplementary material (Optional!)
Lecture 1 - Sep. 4	Threading model, linearizability, atomics, counters	See Learn	v2: PowerPoint \| PDF (lower quality)	Recommended: Paper that introduced Linearizability
Lecture 2 - Sep. 9	Sharded counters, cache coherence, false sharing, padding, locks, fetch-and-add	See Learn	v3: PowerPoint \| PDF (lower quality)
Lecture 3 - Sep. 11	Instruction reordering, stacks	See Learn	v4: PowerPoint \| PDF (lower quality)	Recommended: Treiber stack (original paper) A later stack technique (elimination) Even later stacks Hazard pointers (memory reclamation) Treiber stack with hazard pointers for memory reclamation
Lecture 4 - Sep. 16	Linearizability proof for the lock-free stack, ordering vs concurrency	See Learn	v3: Powerpoint \| PDF (lower quality)
Lecture 5 - Sep. 18	Harnessing disorder: relaxed (multi-)queues, NUMA effects and thread pinning	See Learn	v2: Powerpoint \| PDF (lower quality)	First lock-free queue \| Newer queues Multi-Queue paper (mostly about graph algorithms)
Lecture 6 - Sep. 23	Concurrent hash tables (lock-based and lock-free)	See Learn	v2: Powerpoint \| PDF (lower quality)
Lecture 7 - Sep. 25	Concurrent hash tables with expansion	See Learn	v2: Powerpoint \| PDF (lower quality)	Expandable hash table we are studying
Lecture 8 - Sep. 30	Finishing hash table expansion, starting linked data structures	See Learn	v3: Powerpoint \| PDF (lower quality)
Lecture 9 - Oct. 2	Sketch of Harris list, difficulty of doubly-linked lists with lock-free searches	See Learn	v2: Powerpoint \| PDF (lower quality)	Recommended(!): Harris' linked list
Lecture 10 - Oct. 7	Higher level sync primitives: Doubly-linked list via k-word CAS	See Learn	v2: Powerpoint \| PDF (lower quality)
Lecture 11 - Oct. 9	Implementing KCAS (and DCSS) from single word CAS	See Learn	v2: Powerpoint \| PDF (lower quality)	Recommended: KCAS implementation we are studying
Lecture 12 - Oct. 21	Implementing KCAS, reclaiming descriptors (briefly)	See Learn	v1: Powerpoint \| PDF (lower quality)
Lecture 13 - Oct. 23	Hardware transactional memory, and TLE	See Learn	v1: Powerpoint \| PDF (lower quality)	GCC transactional memory intrinsics
Lecture 14 - Oct. 28	Advanced transactional memory	See Learn	v2: Powerpoint \| PDF (lower quality)	My paper that I mentioned in class (wrapping code in a transaction and repeatedly transforming it)
Lecture 15 - Oct. 30	Versioned locks, snapshots, version-lock-based KCAS	See Learn	v3: Powerpoint \| PDF (lower quality)
Lecture 16 - Nov. 4	Optimizing lock-based KCAS with HTM, OpenMP, debugging/perf	See Learn	v2: Powerpoint \| PDF (lower quality)
Lecture 17 - Nov. 6	Epoch-based memory reclamation, experimental methodology	See Learn	v2: Powerpoint \| PDF (lower quality)	See section 5.2.3 of Fraser's thesis for a discussion of EBR Another paper that describes EBR and does some performance experiments

Assignments

See Learn.

Student presentation guidelines

DETAILS NOT YET DECIDED. Talks might be synchronous or recorded videos. I will probably resolve this with a class vote/poll.

Presentation
- Start with one or two examples of the problem being solved! Don't worry about it being too simple!
- 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
Discussion
- Prepare some discussion questions to drive the discussion if needed
- Answer questions about the paper on the forum (exact medium to be determined)
Just before/after your presentation, post your slides publicly

More soon, on Learn...