6.816/6.836 Multicore Programming
Spring 2016
image restricted to class participants
Instructor: Nir N Shavit
TAs: Michael Joseph Coulombe, Rati Gelashvili, Xiao Meng Zhang
Lecture: T 2-5 P.M. (32-144)
Information:
The computer industry is undergoing a paradigm shift to multicore and multiprocessor chips, a shift that will require a fundamental change in how we program. The art of multiprocessor programming, currently mastered by few, is more complex than programming uniprocessor machines, and requires an understanding of new computational principles, algorithms, and programming tools.
The key issues that distinguish multiprocessor programming from uniprocessor programming are the need to understand how to break applications into computations that can be executed in parallel, and perhaps more fundamentally, how these concurrent computations can coordinate with one another to allow this parallelism to translate into substantiative speedups.
There are few reference books addressing how to program multiprocessors. Most engineers must learn the tricks of the trade by asking help from more experienced friends and through a laborious trial and error process. This course aims to change this state of affairs, providing a comprehensive presentation of the principles and techniques available for programming multicore/multiprocessor machines.
The course will begin by covering the theoretical foundations of programming on multicore machines (we are strong believers that good practice requires understanding the theory). It will then move on to cover the real-world techniques used to program them. It will include a sequence of programming assignments of increasing difficulty, culminating with the design of a highly parallel map-reduce application, running on a state-of-the-art 80-way multicore machine.
Class Structure:
Our textbook will be "The Art of Multiprocessor
Programming" by Herlihy and Shavit.
There will be 6 total assignments, covering both theory and
practice (assignments 2-6 will have the practical part, the last
being the final project). For 6.836 assignments will contain
additional theoretical problems. The assignments will constitute
55% of the course grade.
There will be two exams, a midterm, worth 15% of the grade, and a
final exam, worth 25%. If the final exam score is higher, it will
also count for the midterm. The midterm will take place on
Wednesday, March 16, 7-9PM, in 4-370 and the final will take place
on Tuesday, May 17, from 9:00 to 12:00 Noon in the Track
(W35).
The remaining 5% of the course grade will be for in-class
participation.
Office Hours:
Xiao Meng Zhang M 3:30-5:30pm (32-G630), Michael Joseph Coulombe R
2-4pm (32-G630), Rati Gelashvili F 3-5pm (32-G630).
There will be recitations in the first week but no office hours. Office hours start from the second week (Feb 8th).
Recitations:
Recitation sections are on R 11-12, F 10-11 and F 11-12, in
38-166.
Resources:
We will use Piazza for class-related discussions. The class page
can be found at https://piazza.com/mit/spring2016/68166836/home
Announcements
Exam Review Session
There are no recitations or office hours today. On Monday 3-5pm, there will be an exam review session in G575.We have uploaded solutions to pset5, and will upload solutions to pset6 theory later today.
Announced on 13 May 2016 11:07 a.m. by Rati Gelashvili
Further Clar
For the final project, repeated nodes/edges are allowed on the path.You should output nodes from each of which you can start and traverse some edges pathLen times and end up at the destination node.
Announced on 04 May 2016 7:44 a.m. by Rati Gelashvili
Final Project Clarifications
Hello Everyone,Now that only the final project remains, here are some clarifications discussed on Piazza (and we recommend that you do check Piazza), but since all of you may not have seen it, summarized below.
To get the full (or close to full) credit on the final project, you do not need to drastically optimize performance and memory usage. The graphs on which we will run correctness tests will not be extremely large, and pathLen will also be reasonably small.
The extra credit benchmarks, however, will use a huge graph and
a larger pathLen. As some of you observed, in the expander graphs
like the one that the code template generates, quite soon storing
outputs for all nodes becomes unmanageable. We guarantee that the
graph that we will use (obviously) won't be like this, even
though it will also have certain random properties. Basically, if
you computed the answer for all nodes and stored this as a graph,
you would be able to fit several such graphs in memory. By several,
we mean 3, 4 or 5, a small constant, and more than this will result
in memory exception and you won't be eligible for the extra
credit.
In particular, storing pathLen or log(pathLen) graphs is out of the
question.
Also, we have parameters numMappers and numReducers to make our framework general and more configurable. For the extra credit tests, these will be roughly equal (so there in no point in artificially moving the complexity between map() and reduce() methods).
Moreover, for the extra credit tests, we will set numMappers and numReducers to be the maximum parallelism allowed by the hardware. We would like you to run each Map-Reduce invocation with these parameters (and don't run multiple invocations of Map-Reduce in parallel).
There might be more discussions on Piazza, so make sure to check it out periodically.
Announced on 30 April 2016 3:04 p.m. by Rati Gelashvili
4/28 Office Hour Change
Announced on 26 April 2016 4:27 p.m. by Michael Joseph Coulombe
Clarifications for Pset 5 Programming
Hi guys, just want to clarify three things about the programming assignment of problem set 5:(1) In the hash table that you build, you must store all mappings of words to line numbers (not just words alone). When we test your code, we will have test cases that traverse the table and look for lists of line numbers for a given word. So be sure to design your data structure to store this information.
(Also, if you want to be nice to us -- which we'd be really grateful for -- you can implement a find method in your table that for a given word returns a list of line numbers the word appears in. This find method is called sequentially and only after all the reducers are done, so you don't need to worry about concurrent/race conditions with the method call.)
(2) The add function returns a boolean indicating whether the node has been successfully added to the list or not. For the purpose of this assignment, add() will always return True.
(3) If you decide to use ALock for your hash table lock, please modify your code for the table to take in an input param that specifies the maximum number of threads.
Announced on 12 April 2016 5:32 p.m. by Xiao Meng Zhang
