Why Multiprocessor Programming?
The computer industry is undergoing a paradigm shift. Chip manufacturers are shifting development resources away from single-processor chips to a new generation of multi-processor chips known as multicores.
This fundamental change in our core computing architecture 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.
Concurrent computation on uniprocessor and multiprocessor architectures have many aspects in common. The key issue that distinguishes multiprocessor programming from concurrent uniprocessor programming is the need to understand how concurrent computations on separate processors coordinate with one another, a broad and intricate problem area we call multiprocessor synchronization.
Our textbook is The Art of Multiprocesor Programming, Revised Print, by Maurice Herlihy and Nir Shavit. Students will be able to provide comments and feedback on it using MIT's NB. The textbook is also available to students through the Brown University Library website.
Course Information
The course will approach multiprocessor programming from two complementary directions. In the first part of the course, we focus on foundations: what do our programs and machines need to provide in order to ensure that concurrent programs do what we expect. We use an idealized model of computation in which multiple concurrent threads manipulate a set of shared objects. This model is essentially the model presented by standard Java™ or C++ threads packages.
The foundations section is intended to build up the reader's intuition and confidence in understanding and reasoning about concurrency. We approach this goal using examples, counter-examples, models, and exercises. These elements are laid out in a structured and progressive manner, from simple machine instructions to powerful universal constructions, the equivalent of Turing machines for multiprocessors.
The second part of the course will be concerned with performance. Reasoning about the performance of concurrent programs and data structures is very different in flavor from reasoning about their sequential counterparts. Sequential programming is based on a well-established and well-understood set of abstractions. There is little or no need to understand the specifics of the underlying architecture. In multiprocessor programming, by contrast, there are no such well-established abstractions. It is impossible to reason effectively about the performance of a concurrent data structure without understanding the fundamentals of the underlying architecture.
The performance part of the course will revisit many of the issues first raised in the foundations section, but in a more realistic model that exposes those aspects of the underlying architecture that most influence performance. The course then goes through a sequence of fundamental data structures, the concurrent analogs of the data structures found in any undergraduate data structures course, and a few coordination structures that are unique to the world of multithreaded computation. These data structures are introduced in an incremental way, each one extending the techniques developed for its predecessors. Each of these data structures is useful in and of itself as a reference. Moreover, by the end, the student will have built up a solid understanding of the fundamentals of concurrent data structure design, and should be well-prepared to design and implement his or her own concurrent data structures.
Our hope is that at the end of the course students will have a basic understanding of both the foundations and the practice of multiprocessor and multicore programming.
Earning Capstone Credit
This course can be taken as a capstone course. Doing so will require the completion of an additional project. See here for more information and here for the specifications of the packet filtering project. Useful jar files here.
Collaboration Policy
What's permitted: talking about the homework problems with other students; using other textbooks; using the Internet.
What's not permitted: obtaining the answer directly from anyone or anything else in any form.
TA Hours
TAs for the course will hold weekly hours for 2 hours each on Zoom. The policies are as follows:
Come to hours with one or more questions in mind about the homework or progamming assignment, or a bug in your code. The TAs reserve the right to turn you away if you don't have anything in mind.
The TAs are always happy to help on hours. We can better serve you if you make a good faith attempt to do research on or solve the issue you're facing before coming to hours. It is certainly more expedient to avoid coming to hours in situations where you can resolve the problem yourself, and if you haven't made any progress, you can better lead the TA to what specific issue you're facing.
The TAs have not necessarily studied the capstone component of this course in detail. We'll do our best but make no promises about what we know.
For written homework questions, you may not refer directly to your homework during TA hours. You may bring in a set of short notes or list of questions to organize your thoughts for the session. You may take away written notes from the session, but they must be viewed and approved by the TA - bullet points and TODO's pertinent to the assignment are fine, paragraphs that answer the homework questions directly are not.
The TAs can also help you debug your code. However, you may not listen in on another student's debugging session.
One person may spend at most 15 minutes at a time receiving help from a TA. The only exception is when you are the only person in line, in which case after 15 minutes you can stay until someone else gets in line.
Multiple people can have a group session with the TA on the same conceptual (read: you may not have your code open or ask about implementation details!) topic. These discussions will be limited to 30 minutes. You may listen in on a group discussion while holding your place in line for different questions, and may follow up with more specific questions on the same material after the discussion is over.
Be courteous to other students and the TA on hours. The TAs reserve the right to call you in if you are harassing other students or TAs. If it continues or is sufficiently severe, the TAs reserve the right to eject you from hours.
-Isms and other bigotry are not welcome at hours, and willfully engaging in this sort of behavior is not tolerated. We acknowledge that even well-intended people can cause this sort of harm unintentionally, and the course staff will deal with these sorts of problems should they arise. As above, the TAs reserve the right to call you in or eject you from hours for this sort of behavior depending on the severity.
If you are having negative experiences with another student on hours and the TA does not notice, feel free to tell the TA if you are comfortable doing so, or email the TA or HTA afterwards. Make sure to be clear on what you would like the TA to do -- you are entitled to harassment-free hours and we will avoid going against your wishes whenever possible.
If you are having negative experiences with the course staff, if you are comfortable doing so, you may let another staff member know. If you do not feel comfortable doing so, the department offers other avenues for you (see "Diversity" below.)
Zoom hours structure: Each TA's Zoom link can be found on our hours calendar. Please sign up for hours on signmeup as usual, and join the Zoom meeting. You will be initially placed in a waiting room and let into the meeting when it is your turn (once your name has been claimed on signmeup).
Ed Discussion
The course Ed page is here. Ed Discussion is intended primarily for short clarification questions regarding anything about the course, from assignments to policies. You may post under your own name or anonymously to all except instructors, and you may post publicly or privately. Do note that if we think a privately asked question would be helpful for other students, we will make it public.
Ed is not a debugging platform. For coding assignments, if you are confused about what some code should be doing, you may post a short snippet privately (or publicly if it's all stencil code.) If you know what you want your code to do but it isn't working, come to TA hours. The TAs and professor cannot compile Java with their eyes.
Additionally, we expect you to adhere to the same rules about harassment and -isms on Ed as on hours.
Diversity
Our intent is that this course provide a welcoming environment for all students who satisfy the prerequisites. Our TAs have undergone training in diversity and inclusion; all members of the CS community, including faculty and staff, are expected to treat one another in a professional manner. If you feel you have not been treated in a professional manner by any of the course staff, please contact either Prof. Herlihy (the instructor), Prof. Doeppner (the director of undergraduate studies), Prof. Cetintemel (the department chair), or Laura Dobler (the department's coordinator for diversity and inclusion initiatives). We take all complaints about unprofessional behavior seriously.
Accommodations
If you feel you have physical, psychological, or learning disabilities that could affect your performance in the course, we urge you to contact SEAS. We will do whatever we can to support accommodations recommended by SEAS.
If you feel you need other accommodations outside the scope of SEAS, feel free to contact Maurice or the HTA. We will do our best to work something out with you.
Mental Health
Being a student can be very stressful. If you feel you are under too much pressure or there are psychological issues that are keeping you from performing well at Brown, we encourage you to contact Brown's Counseling and Psychological Services. They provide confidential counseling.
Coping with Unforeseen Events
If there are events that are upsetting to you, whether political, family-related, natural disaster-related, etc., that affect your ability to do well in class, we are happy to take them into account with respect to our late and incomplete policies. Please feel free to talk to Prof. Herlihy about this.
Grading
8 Homeworks: 40% (5% each)
3 Midterms: 40% (13.33...% each)
5 Programming Assignments: 20% (4% each)
Homeworks are due on the appropriate day through submission on Gradescope. All homework assignments must be turned in individually. We do not accept late homeworks except for cases which merit an extension. However, we will drop your lowest 2 homework scores from your final grade. The only identifying piece of information on submitted handins should be your Banner ID, but this is not necessary. If your homework assignment includes your name anywhere in the file, we reserve the right to take 20% off your assignment's grade.
Programming assignments are also due the appropriate day and should be submitted through gradescope as well. You should not need to submit any identifying information with this handin either. We also do not accept late programming assignments except for cases which merit an extension.
If there are any extenuating circumstances which may merit an extension, please contact Prof. Herlihy. (The TAs cannot grant extensions.)
Additionally, systemic issues such as a CS department outage may merit classwide due date updates. We will push back the due date one day each time this happens:
The department machines go down for 1 hour or more within 6 hours of the due time.
The department machines go down for 6 hours or more within 3 days of the due date, causing one or more students to be unable to work on the assignment. (The TAs don't assume you're working between 2 and 8 AM, but if you are, let us know!)
The department machines go down for 24 hours or more.