ICS 643: Parallel Algorithms (Fall 2016)

Instructor: Nodari Sitchinava
Email: nodari@hawaii.edu
Location: Holmes Hall 243
Time: Monday, Wednesday 10:30-11:45pm
Office Hours: 1-2pm in POST 309C

Previous offerings: Fall 2014 (eCafe Reviews)

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.

Registering for the course

I am traveling during the first week of classes. So the first "real" lecture will not be until after the add date, if you are considering registering for the course after attending the first couple of lectures. Therefore, if you are wondering if this course is for you, I suggest you email me as soon as possible.

During the first week (in lieu of the lectures), there will be a take-home assessment exam, which will be posted on this webpage. The assessment exam will not be graded. The goal of the assessment exam is to give me and you (the student) an idea of how prepared you are to take the course and to adjust the course and topics approriately. Therefore, although the exam is not graded, to give an accurate picture of your preparedness, solve all the problems to the best of your ability. The exam should be individual effort, but you are allowed to use the CLRS textbook (standard text for undergraduate algorithms course). If you would like to hear feedback on your preparedness before the drop date, email me your exam before noon on Wednesday, August 24. Otherwise, it is due at 5pm on Friday, August 26, by email.


This is a course on advanced algorithmic concepts, so you should be very comfortable with asymptotic notation, design and analysis of basic algorithms, and the algorithms taught in an undergraduate algorithms course (most of the material from the CLRS textbook), hence, the 'B' or better requirement in ICS 311. If you are a graduate student who took an algorithms course outside of the UH system, email me with a brief description of the algorithms course(s) that you have taken (a link to the course webpage is a plus) and I'll provide you with an override to register for the course.

Reading Material

There is no required textbook, however, majority of the material will be from the following textbook: It is placed on 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.

The following manuscript is also a good introduction to parallel algorithms:

You might also want to consider the following book for additional reading on more advanced concepts:

Assessment (Grading)

The grade in the course will consist of the following components:


Content. The notes you write should cover all the material covered during the relevant lecture. Your notes should be understandable to someone who has not been to the lecture. You should write in full sentences where appropriate; point form (like I write on the board) is often too terse to follow without a sound track (though occasionally it is appropriate). Use numbered sections, subsections, etc. to organize the material hierarchically and with meaningful titles. If you feel it is appropriate, use nested bullets to organize material hierarchically even deeper. Try to preserve the motivation, difficulties, solution ideas, failed attempts, and partial results obtained along the way in the actual lecture.

Format. Write your notes using LaTeX, with figures in Encapsulated PostScript (generated from xfig, ipe, Adobe Illustrator or whatever you want). Start from the Latex template, which sets the style.

Timing. Try to write the lecture notes for a class on the same day while the material is fresh in your mind and it will save you time. You should finish the first draft of your notes and send it to me by two days after the lecture. Then I'll either send you comments via email or we'll schedule a meeting to go over your write-up, I'll make suggestions, you'll make a second pass, and send it to me. I'll make the final pass, and post it on the webpage. The goal will be to get the notes out by one week after the corresponding class.


There will be 3-5 homeworks (once every 2-3 weeks) throughout the semester. You may collaborate with anyone on the homeworks, but you must write up your own solutions. You must write the names of everyone you discussed the solution with in your homework write-up. The homework must be typed up. It will be due at the beginning of the lecture on the day it is due and can be either submitted in person in lecture (preferred) or emailed to me before the class.

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, if homework is worth 30 points and is due at 10:30am on Wednesday, submitting it before Thursday 10:30am will result in deduction of 10 points; submitting it before Friday 10:30am, will result in deduction of 20 points; submitting it after Friday 10:30am will result in deduction of 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.


Goal. Ideal outcome of the project at the end of the class is for you to obtain results that can be published at an algorithms conference. To receive full credit on the project, you do not have to achieve this goal (that's the nature of research), but that should be your goal. If you do not achieve publishable results, your write-up should describe the ideas and approaches you took to solve the problem.

Topic. The topic of your research project should be related to parallel algorithms. I will be available for brainstorming during office hours for possible topic of interest. You must be interested in the topic, but I must approve the topic, so check with me first.

Format. Here is a list of possible formats of the project. This list is not exhaustive, so if you have an interesting idea that you don't see on the list below, come discuss it with me.

Write-up. The project must be written up in a research paper format. It should be somewhere between 6 to 15 single-spaced pages with 1 inch margins. It should start with a title, author and a 1-2 paragraph abstract. The body of the write-up should consist of introduction, the body and the conclusions. The introduction should describe the problem you are addressing, present a brief literature review of related results on the topic, and a summary of your results. The body should describe your solution, teachnique/approach to solving it and results. If you haven't achieved significant results, you should still describe the techniques/approaches you have tried and why they didn't work. The conclusions should summarize what you have presented and present possible directions for future research, e.g. open problems that remain unsolved and/or possible approaches that you might have tried if you had more time. You are welcome to collaborate on the project with anyone (even outside the class), including me, but you should give credit to people you have collaborated with. This is the nature of research.

Presentation. At the end of the semester you should give a 30 minute presentation about your project.


The following topics will be covered in class during the semester:


Specific topics will be filled in the schedule as they are covered during the semester.

Week Day Date Topic Scribe Notes Notes
1 Mon Aug 22 NO CLASS (Nodari is at a conference): Take-home assessment exam Due 5:00pm on Friday, August 26 (by email)
Wed Aug 24 NO CLASS (Nodari is at a conference): Finish the take-home assessment exam
2 Mon Aug 29 NO CLASS (Nodari is sick)
Wed Aug 31 Introduction to parallel algorithms
3 Mon Sep 5 HOLIDAY: Labor Day
Wed Sep 7 Models of parallel computation Notes 02 Reading: [BM04, sections 1.1], [J92, section 1.1-1.3]
4 Mon Sep 12 Models of parallel computation (cont.)
Brent's Theorem
Notes 03 Reading: [BM04, sections 1.2-1.4], [J92, section 1.4-1.5]
Wed Sep 14 Work vs cost; Efficiency Notes 04 Reading: [J92, section 1.5-1.6]
5 Mon Sep 19 Simmulation of CRCW PRAM on EREW PRAM Notes 05
Wed Sep 21 Simple prefix sums Notes 06 Reading: [HS86]
6 Mon Sep 26 Work-efficient prefix sums Notes 07 Reading: [J92, section 2.1][B93, sections 1.1-1.2]
Wed Sep 28 Segmented prefix sums Notes 08 Reading: [B93, sections 1.4.1, 1.5]
Homework 1 out
7 Mon Oct 3 Finding minimum Reading: [J92, section 2.6]
Wed Oct 5 Partitioning; Simple work-efficient merging Notes 10 Reading: [J92, section 2.4]
8 Mon Oct 10 O(log log n) merging Reading: [J92, section 4.1-4.2.3]
Wed Oct 12 Finish O(log log n) merging. Parallel Search Trees Reading: [J92, section 2.5]
Homework 1 due
9 Mon Oct 17 Pipelining, Pipelined Mergesort Reading: [J92, sections 2.5, 4.3]
Homework 2 out
Wed Oct 19 Pipelined Mergesort (cont.), Merging with covers Reading: [J92, sections 4.2.4, 4.3.2]
10 Mon Oct 24 Pipelined Mergesort (cont.) Reading: [J92, sections 4.2.4, 4.3.2]
Wed Oct 26 Pipelined Mergesort (cont.), Sorting Networks Reading: [J92, sections 4.3.2, 4.4]
11 Mon Oct 31 0-1 Principle Reading: [0-1 Notes, 0-1 Notes2]
Wed Nov 2 Bitonic Mergesort Reading: [J92, section 4.4]
Homework 2 due
Homework 3 out
12 Mon Nov 7 List Ranking Reading: [J92, section 3.1.1]
Wed Nov 9 NO CLASS (Nodari is traveling)
13 Mon Nov 14 Deterministic coin tossing, 3-coloring of linked list Reading: [J92, section 2.7]
Wed Nov 16 O(log n) List Ranking Reading: [J92, section 3.1.2]
Homework 3 due
14 Mon Nov 21 Euler Tour Technique. Problems on trees Reading: [J92, section 3.2]
Homework 4 out
Wed Nov 23 Tree contraction, arithmetic expression evaluation Reading: [J92, section 3.3]
15 Mon Nov 28 Lowest Common Ancestor (LCA), Range Minima Queries (RMQ) Reading: [J92, section 3.4]
Wed Nov 30 Connected Components, Minimum Spanning Tree Reading: [J92, sections 5.1-5.2]
16 Mon Dec 5 Convex Hull Reading: [J92, section 6.1]
Homework 4 due
Wed Dec 7 Project presentations Project due

Reading Materials