ICS 443: Parallel Algorithms

Description: Introduction to parallel models of computation and design and analysis of parallel algorithms.

Objectives

• The students will be aware of current models of parallel computation
• The students will be proficient with algorithmic techniques for designing parallel algorithms
• The students will be able to apply these techniques to design new parallel algorithm
• The students will be able to analyze the efficiency of parallel algorithms

Course Learning Outcomes

• Students will be able to identify various models of parallel computation
• Students will be able to list fundamental parallel algorithms
• Students will be able to use learned techniques to implement parallel algorithms on modern many-core architectures
• Students will be able to carry out analysis of parallel algorithms
• Students will be able to differentiate between efficient and inefficient parallel algorithms
• Students will be able to design efficient parallel algorithms
• Students will be able to check parallel algorithms for correctness
• Students will be able to analyze the runtime and efficiency of parallel algorithms.

Program Learning Outcomes

• a. Students can apply knowledge of computing and mathematics appropriate to the discipline
• b. Students can analyze a problem, and identify and define the computing requirements appropriate to its solution
• c. Students can design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs
• d. Students can function effectively on teams to accomplish a common goal
• f. Students can communicate effectively with a range of audiences
• h. Students can recognize the need for and an ability to engage in continuing professional development
• i. Students can use current techniques, skills, and tools necessary for computing practice

Prerequisites: 311 with C or better

Textbook(s): Joseph Jaja, Introduction to Parallel Algorithms, Addison Wesley, 1992.

Grading: The students will be graded on class participation (20\%), homeworks (40\%), and the final exam (40\%).

Policies: Late homework policy: Homeworks are due on Thursday at 1:30pm (the beginning of the lecture). Late homeworks can be emailed to the instructor. Penalty for late homeworks is a letter grade reduction (e.g. from A to B) for within each 24 hours that it is late. For example, submission of homework that deserves a letter grade A will be graded B if submitted between Thursday 1:30pm and Friday 1:30pm; will be graded C if submitted before Saturday 1:30pm; and will be graded D if submitted before Sunday 1:30pm. Extenuating circumstances do arise, therefore, a single homework will be accepted up to 72 hours late without any reduction in grade.

Schedule

• Week 1: Introduction, models of parallel computation, Brent’s scheduling principle
• Week 2: Parallel scan, prefix sums
• Week 3: Searching, selection, basic sorting
• Week 4: Sorting networks, 0-1 principle
• Week 5: List ranking, pointer jumping, symmetry breaking
• Week 6: Tree algorithms
• Week 7: Lowest common ancestors, range minima queries
• Week 8, 9: Graph algorithms: Connected and biconnected components, minimum spanning trees, shortest paths
• Week 10,11:Computational Geometry: convex hull, half-plane intersection, planesweep
• Week 12-13: Linear algebra: matrix-matrix and matrix-vector multiplication
• Week 14: Numerical algorithms
• Week 15: String algorithms
• Week 16: Advanced models of computation, limits of parallelism, P-completeness