ICS 643 Spring 2022 Parallel Algorithms

About

Parallel processors are everywhere: servers, desktops, tablets, even cell phones. However, writing programs that take advantage of all the available parallelism is challenging, in part because it requires different techniques than what we have learned in the sequential algorithms courses.

In this course you will learn the techniques for designing and analyzing parallel algorithms – algorithms to solve a problem if it is implemented on a system with multiple processors.

Topics and Schedule

The following is a tentative schedule of the topics that will be covered in this class and is subject to change. The students are expected to know the material from the undergraduate algorithms course (e.g., ICS 311) and are encouraged to review it prior to the start of the semester.

This course is run concurrently with ICS 443 – an undergraduate version of this course. Neither course assumes any prior knowledge of parallel algorithms and there is quite a bit of overlap in topics between the two courses. However, as a graduate course, this course will progress at a faster pace than ICS 443 and will cover topics more in-depth.

Week Day Date Topic Lecture Notes
Reading
Assignments
1 Mon Jan 10 Introduction Slides
[E19, Appendix I]
[E19, Appendix II]
Wed Jan 12 Models of parallel computation Slides
[BM04, sections 1.1]
[J92, sections 1.1-1.3, 2.6.1]
2 Mon Jan 17 HOLIDAY: MLK Day
Wed Jan 19 Work-depth analysis
Brent's scheduling principle
Slides
[BM04, sections 1.1-1.4, 2.1]
[J92, section 1.3-1.6]
Homework 1 due
3 Mon Jan 24 Parallel prefix sums Slides
[J92, section 2.1]
[B93, sections 1.1-1.2]
[HS86]
Wed Jan 26 Applications of prefix sums Slides
[B93, sections 1.3, 1.5.1]
4 Mon Jan 31 Segmented prefix sums [B93, sections 1.4.1, 1.5]
Wed Feb 2 Segmented prefix sums (cont.)
Applications of segmented prefix sums
Slides
[B93, section 1.4.1, 1.5]
Homework 2 due
DROP Without W
5 Mon Feb 7 Iterative Quicksort Slides
[J92, sections 1.5 ]
Wed Feb 9 Finding Minimum
Parallel Search
[J92, sections 2.6, 4.1]
6 Mon Feb 14 Simple Parallel Mergesort [J92, sections 2.4, 4.3.1]
Wed Feb 16 Work-optimal Merge [J92, section 4.2, 4.3.1] Homework 3 due
7 Mon Feb 21 HOLIDAY: President's Day
Wed Feb 23 O(log log n) merging [J92, section 4.2, 4.3.1]
8 Mon Feb 28 Optimal O(log n) mergesort [J92, section 4.3.2]
Wed Mar 2 Sorting networks [J92, section 4.4]
[L01]
[L02]
[L03]
Homework 4 due
9 Mon Mar 7 Take-home Midterm Exam
Wed Mar 9 Take-home Midterm Exam Midterm Exam due
Mon Mar 14 SPRING RECESS
Wed Mar 16 SPRING RECESS
10 Mon Mar 21 Sorting networks (cont.) [J92, section 4.4]
[L01]
[L02]
[L03]
Wed Mar 23 Pointer hopping Slides
[J92, section 3.1]
11 Mon Mar 28 Randomized list ranking [J92, sections 3.1, 9.2.1] DROP With W
Wed Mar 30 Deterministic symmetry breaking [J92, sections 2.7.1-2.7.2, 3.1.1]
12 Mon Apr 4 Work-optimal 3-coloring [J92, sections 2.7.3, 3.1.1]
Wed Apr 6 Work-optimal list ranking
Euler Tour technique
[J92, section 3.1.2, 3.2] Homework 5 due
13 Mon Apr 11 Euler Tour technique
Simple tree problems
[J92, section 3.2]
Wed Apr 13 Tree contraction
Expression tree evaluation
[J92, sections 3.3]
14 Mon Apr 18 Lowest Common Ancestor (LCA)
Range minima queries
[J92, section 3.4]
Wed Apr 20 Connected Components [J92, sections 5.1-5.2] Homework 6 due
15 Mon Apr 25 Minimum Spanning Tree
Matrix multiplication
All-pairs shortest paths
[J92, sections, 5.2, 5.5]
Wed Apr 27 Student Presentations
16 Mon May 2 Student Presentations
Wed May 4 Student Presentations

Reading Material

[B93] Guy Blelloch: Prefix Sums and Their Applications. A chapter from Synthesis of Parallel Algorithms, John Reif (Editor).

[BM04] Guy Blelloch and Bruce Maggs: Parallel Algorithms. A chapter from Computer Science Handbook, Second Edition, Allen B. Tucker (Editor).

[E19] Jeff Erickson, Algorithms, 1st Edition. Available free online, 2019.

[HS86] W. Daniel Hillis, Guy L. Steele, Data Parallel Algorithms, Communications of the ACM 29(12): 1170-1183, 1986.

[J92] Joseph JáJá, Introduction to Parallel Algorithms. Addison Wesley, 1992. ISBN: 9780201548563. Availability at UH Library.

[L01] Hans Werner Lang: Sorting Networks.

[L02] Hans Werner Lang: Proof of 0-1 Principle.

[L03] Hans Werner Lang: Bitonic Sort Notes.