15-852: Parallel and Concurrent Algorithms (Spring 26)
- Instructor:
Guy Blelloch
- TA:
Andrew Brady
- Time: Tuesday and Thursday 3:30 - 4:50
- Place: GHC 4303
- Andrew's Office Hours:Friday 2:00-3:00,GHC5101 or 5th floor Commons Table 1
- Credit: 12 Units
- Prerequisites: An advanced undergrad course in algorithms
(15-451 or equivalent will suffice).
Schedule:
-
Week 1
- Jan 13
- Overview, Introduction, Models
- Main Reading
· Introduction to Parallel Algorithms (sections 1, 2, 3).
- More detailed readings on models
· Circuit model (section 3.3)
· P-complete algorithms (section 4)
- Assignment 1 out
· Assignment 1
- Jan 15
- Models Continued, Scan and Search
- Readings
· Introduction to Parallel Algorithms (sections 4.1 and 4.2).
-
Week 2
- Jan 20
- Merging and Sorting
- Readings
· Introduction to Parallel Algorithms (sections 5.1--5.3).
- Jan 22
- Sorting Continued
- Readings
· Introduction to Parallel Algorithms (sections 5.4-5.5).
-
Week 3
- Jan 27
- No class, Assignment 1 due
- Jan 29
- Deterministic Sample Sort
-
Week 4
- Feb 3
- Randomized Sample Sort
- Feb 5
- Parlay demo
-
Week 5
- Feb 10
- List contraction
- Feb 12
- Graphs: BFS, MIS
- Assignment 2 released, due February 22
-
Week 6
- Feb 17
- Graphs: Connectivity
- Feb 19
- Graphs: LDD
- Readings
· Lecture notes Chapter 6.3
-
Week 7
- Feb 24
- Graphs: Spanners
- Feb 26
- Parallelizing iterative sequential algorithms
- Readings
· Lecture Slides
- Feb 27
- Project proposal examples released, proposal due Mar 14
- Assignment 3 released, due Mar 14
-
Week 8
- Mar 10
- Parallel Batch-Dynamic Orientation
- Mar 12
- Parallel Batch-Dynamic Trees
-
Week 9
- Mar 17
- 2D linear programming
- Project work begins
- Mar 19
- Convex Hull
-
Week 10
- Mar 24
- Balanced Binary search trees
- Mar 26
- Work-Stealing Schedulers
-
Week 10
- Mar 31
- Concurrency: Intro
- Apr 2
- Linearizability, Lock-free read-write
-
Week 11
- Apr 7
- Optimistic Locking
- Apr 9
- No class, Carnival
-
Week 12
- Apr 14
- Lock-Free Sorted Linked List
- Apr 16
- TBD
-
Week 13
- Apr 21
- Last Class, Topic TBD
- Apr 21
- Exam released, due Apr 23
- Apr 23
- No class, exam due
-
Week 14
- May 1
- Project Due
Course Description:
This is an advanced course on the theory, and some practice, of
parallel and concurrent algorithms. We will start by discussing
models and then go through a variety of topics including algorithms
for sorting, strings, graphs, and geometry. The focus will be on
so-called work-efficient algorithms (i.e. algorithms that do no more work
than their sequential counterpart). The goal is both to get a broad
view of the techniques used to design such algorithms, as well as
going into some depth on a handful of recent breakthroughs in the
design of parallel algorithms. We will discuss practical
implementations of most of the algorithms we cover.
Method of Evaluation:
The course grade will be based on a handful of assignments, a final
project report, and a final.
The final project will be over 5 weeks and can be either a
pure theory project, a systems project, or a combination of both.
Course Outcomes:
The course outcome will ideally be the ability to design your own efficient parallel and concurrent algorithms for topics you are working on or are interested in.
Specific Topics:
Expected course topics include: Parallel models, work-stealing
scheduling, list-ranking, merging, sorting, Euler trees, dynamic
algorithms, suffix arrays, cartesian trees, balanced trees,
low-diameter graph decomposition, connectivity and biconnectivity,
maximal-independent sets, strongly-connected components, graph
spanners, set cover, convex-hulls, closest pairs, and Delaunay
triangulation. All of these, of course, are in the context of
parallelism and concurrency.
Parlaylib:
We will be
using parlaylib
for some of the assignments. It is based on C++. You can find many
examples of parallel algorithms in parlaylib in the
examples
directory. See the .h files since the .cpp files are just
drivers.
Guy Blelloch,
guyb@cs.cmu.edu.