ICS 691: Parallel Algorithms (Fall 2014)

Instructor: Nodari Sitchinava
Email: nodari (at) hawaii (dot) edu
Location: Hamilton 3G (in basement of the Hamilton Library)
Time: Tuesday, Thursday 1:30-2:45pm
Office Hours: Tuesday 3-4, POST 306B


Course Description: 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.

This course will teach how to design and analyze algorithms for parallel systems. The students will learn the techniques for designing and analyzing parallel algorithms for various parallel models of computation (shared memory, distributed memory, interconnection networks) and how these models relate to modern parallel systems, such as multicores, clusters and GPUs. There will be a final project on the topic of student's choice.

Prerequisites: An algorithms course (ICS 311 or equivalent) or permission of the instructor.

Recommended Reading:
The first book, which contains most of the course material, is placed as a course reserve (under call number "QA76.58 .J35 1992") in the Wong Audiovisual Center on the third floor of Sinclair Library and can be checked out for up to 4 hours at a time. For more information on course reserves please see this link.

Homeworks: There will be 4 homeworks throughout the semester. Homework will be due at the begining of the corresponding Thursday lecture, i.e., at 1:30pm and can be submitted in person in lecture or emailed to me before the class. Homework can be typed or hand-written, however, I must understand the handwriting to grade it.

Late Homeworks: Late homeworks can be emailed to me. Penalty for late homeworks is 33% of the maximum number of points within every 24 hours that it is late. For example, submission of homework that is worth 30 total points before Friday 1:30pm will be deducted 10 points. Submissions before Saturday 1:30pm, will be deducted 20 points. Submissions after Saturday 1:30pm will be deducted full 30 points, thus, are not worth anything. Extenuating circumstances do arise, therefore, a single homework will be accepted up to 48 hours late without any point deductions.

Final project: The course will have a final project. The students have a choice of either 1) implementing one of the algorithms presented in class, 2) performing a literature survey of parallel algorithms not presented in class, or 3) performing orginal research on the topic of parallel algorithms. Upon the completion of the project the students will submit a written report and present their results in front of the class.

Grading: Grades are based on class participation (20%), homeworks (40%), and the term project which will include a final written report and an oral presentation of the results (40%).

Topics: The course will cover parallel algorithms for fundamental problems (scanning, searching, sorting), graphs, computational geometry, linear algebra, strings, as well as algorithms and models for advanced architectures, such as multicores, GPU, MapReduce. The schedule below will be updated with the topics as they are covered.

Schedule

Class Day Date Topic Notes
1 Tue Aug 26 Introduction
Models of computation
2 Thu Aug 28 Models of computation
Brent's scheduling principle
3 Tue Sep 2 Prefix sums
4 Thu Sep 4 Prefix sums
5 Tue Sep 9 Collaborative exercises Handout
6 Thu Sep 11 Collaborative exercises
7 Tue Sep 16 First-order recurrences and segmented prefix sums Notes (Sections 1.4 and 1.5)
8 Thu Sep 18 Segmented prefix sums: applications
Discussion of the collaborative exercises		 Homework 1 out
9 Tue Sep 23 Searching
10 Thu Sep 25 Simple merging, mergesort
11 Tue Sep 30 O(log log n) merging
Merging using c-covers
12 Thu Oct 2 Pipelined mergesort Homework 1 due
13 Tue Oct 7 Pipelined mergesort
Sorting Networks
14 Thu Oct 9 Sorting Networks
0-1 principle
15 Tue Oct 14 List Ranking Homework 2 out
16 Thu Oct 16 List Ranking (cont.), Deterministic coin tossing
17 Tue Oct 21 O(log n) List Ranking
18 Thu Oct 23 Tree Contraction
19 Tue Oct 28 Expression Evaluation
Lowest Common Ancestors (LCA), Range Minima Queries (RMQ)
20 Thu Oct 30 Connected Components on dense graphs Homework 3 out, Homework 2 due
-- Tue Nov 4 Holiday: Election Day
21 Thu Nov 6 Connected Components on sparse graphs
-- Tue Nov 11 Holiday: Veterans' Day
22 Thu Nov 13 Minimum spanning tree, All-pairs shortest paths Homework 3 due
23 Tue Nov 18 Convex hull, intersection of half-planes, 2-variable linear programming
24 Thu Nov 20 Plane sweep tree Homework 4 out
25 Tue Nov 25 NO CLASS
-- Thu Nov 27 Holiday: Thanksgiving Day
26 Tue Dec 2 2-D Counting problems: Dominance counting, Orthogonal range counting, Orthogonal line segment intersection counting
27 Thu Dec 4 Advanced parallel models of computation: PEM, GPU, MapReduce Homework 4 due
28 Tue Dec 9 Project presentations
29 Thu Dec 11 Project presentations Project due