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.
|