Parallel Computing

Location, Time
Instructor: Xuhao Chen
Office Hours: Time, Location

Course Description

This course is a research-oriented course on algorithm engineering, which will cover both the theory and practice of algorithms and data structures. Students will learn about models of computation, algorithm design and analysis, and performance engineering of algorithm implementations. We will study the design and implementation of sequential, parallel, cache-efficient, external-memory, and write-efficient algorithms for fundamental problems in computing. Many of the principles of algorithm engineering will be illustrated in the context of parallel algorithms and graph problems. Students will read and present research papers, write paper reviews, complete assignments that involve both theory and implementation, participate in classroom discussions, and complete a semester-long research project. Class time will consist of lectures, student presentations, and group project meetings. This course is suitable for graduate students or advanced undergraduates. Mathematical maturity and familiarity with algorithm analysis and performance engineering will be assumed.


Students taking this course should be familiar with C programming.

Prior knowledge of computer architecture concepts such as data locality will be useful but not required.


Grades for this course will be based on a series of 3-5 programming assignments.

Textbook (Optional)


Computing Resources

We will be using Amazon Web Services.

Schedule and Slides

3 / 27 Course Introduction Paper reading
Paper reading
3 / 29 Parallel Algorithms Paper reading
Assignment 1
4 / 03 Parallel Graph Traversal Paper reading
Paper reading
4 / 05 Shared-Memory Graph Algorithms Paper reading
4 / 10 Sorting and In-Place Algorithms Paper reading
Paper reading
4 / 12 External-Memory Algorithms Paper reading
Paper reading
4 / 17 Cache-Oblivious Algorithms Paper reading
Assignment 1 due
4 / 19 Parallel Cache-Oblivious Algorithms Paper reading
Assignment 2
4 / 24 Distributed Graph Frameworks Paper reading
4 / 26 Disk-based Graph Frameworks Paper reading
5 / 01 Locality in Graph Processing Paper reading
Paper reading
5 / 03 NVRAM and Streaming Graph Paper reading
5 / 08 Subgraph Counting Paper reading
Final project
5 / 10 Subgraph Finding Frameworks Paper reading
5 / 15 Parallel Subgraph Finding and Peeling Paper reading
Final project proposal due
5 / 17 Graph Coloring and GPU Graph Processing Paper reading
Assignment 2 due
5 / 22 Aggregation and Join Paper reading
Paper reading
5 / 24 Union Find Paper reading
Paper reading
5 / 29 Graph Compression and Reordering Paper reading
Paper reading
5 / 31 Graph Clustering Paper reading
5 / 31 Suffix Arrays and Trees Paper reading
Final project due