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.
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.
The following manuscript is also a good introduction to parallel algorithms:
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.
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 |