15897: Parallelism and Concurrency

This course covers fundamental parallel algorithms and implementation techniques for them and provides a concise overview of quantum computing as a different emerging form of parallelism.

The first half the course will be lecture based, whereas the second half will focus on projects. The students will jointly work with the instructor to complete a project of their choosing. The aim of the project will be to obtain an initial result that could be submitted as a conference paper.

Covered topics include

• Model of parallelism (PRAM Model, Vector Model, High Level Models)

• Building blocks (parallel map, reduce, search, scan, merge, etc)

• Parallel sorting (merge sort, sample sort)

• Parallel graph algorithms (BFS, low diameter decomposition, reachability, shortest paths, MIS, etc)

• Parallel tree and graph contraction and their applications

• Concurrency: non-blocking data structures

• Parallel scheduling (offline scheduling, online scheduling, work stealing, responsive scheduling)

• Programming parallel algorithms in modern languages (parallelism primitives, run-time systems for parallelism)

• From classical to quantum: parallelism in quantum computation (mathematical foundations for quantum computing, the quantum circuit model, research problems in quantum computing)