Course Resources
Links to all resources for this course can be found in the
TWiki
page for CS 181E.
Prerequisite
This course should be accessible to anyone familiar with the
foundations of sequential algorithms and data structures, and with
basic Java programming.
The official prerequisite for this course
is an introduction to sequential programming in Java e.g., as in
CS 60.
The unofficial prerequisite is a healthy curiosity about the changing
foundations of software, now that parallel computing is ubiquitous
across smartphones, laptops, desktops, servers, supercomputers, and data centers.
Course Objectives
The goal of this course is to introduce you to the fundamentals of
parallel programming and parallel algorithms, using a pedagogic
approach that exposes you to the intellectual challenges in parallel
software without enmeshing you in the jargon and lower-level details
of today's parallel systems. A strong grasp of the course
fundamentals will enable you to quickly pick up any specific parallel
programming model that you may encounter in the future, and also
prepare you for studying advanced topics related to parallelism
and concurrency in future courses e.g., parallel algorithms, architecture and organization
of parallel computers, operating systems, distributed computing, use of parallelism in computational science,
and graphics and visualization.
To ensure that students get a strong grasp of parallel programming
foundations, the classes and homeworks will place equal emphasis on
advancing both theoretical and practical knowledge. The programming
component of the course work will use a simple parallel extension to
the Java language called Habanero-Java (HJ), developed in the Habanero
Multicore Software Research project at Rice University. An abstract performance model for HJ programs will be available to
aid you in the complexity analysis of parallel programs before you embark
on performance evaluations on real parallel machines. The use of
Java will be confined to a subset of the Java 5 language that should
also be accessible to C programmers --- advanced Java features
(e.g., wildcards in generics) will not be used. However, an important goal is that, at the end of CS181E, you'll feel
comfortable programming in any parallel language for which you are
familiar with the underlying sequential
language; the parallel programming primitives should be easily
recognizable based on the primitives studied in the course.
Course Overview
CS 181E, Fundamentals of Parallel Programming, provides the student
with a
comprehensive introduction to the key building blocks of parallel
software, which includes the following concepts:
- Primitive constructs for task creation & termination, synchronization, task and data distribution
- Abstract models: parallel computations, computation graphs,
Flynn's taxonomy (instruction vs. data parallelism), PRAM model
- Parallel algorithms and data structures including lists, strings, trees, graphs, matrices
- Common parallel programming patterns including task parallelism,
pipeline parallelism, data parallelism,
divide-and-conquer parallelism, map-reduce, concurrent event
processing including graphical user interfaces.
These concepts will be introduced in four modules:
- Deterministic Shared-Memory Parallelism: creation and coordination
of parallelism, collective & point-to-point synchronization
(phasers, barriers),
abstract performance metrics (work, span, critical paths), Amdahl's
Law, weak
vs. strong scaling, data races and determinism, data race avoidance
(immutability, futures, accumulators, dataflow),
deadlock avoidance, abstract vs. real
performance (granularity, scalability), parallel sorting algorithms.
- Nondeterministic Shared-Memory Parallelism (Concurrency): critical
sections, atomicity, isolation, high level data races,
nondeterminism, linearizability, liveness/progress.
guarantees, actors, request-response parallelism
- Distributed-Memory Parallelism: memory hierarchies, cache affinity, false
sharing, message-passing (MPI), communication overheads (bandwidth, latency), MapReduce, systolic arrays,
accelerators, GPGPUs.
- Real-world Parallel Programming Models and Challenges: Java Concurrency,
locks, condition variables, semaphores, memory consistency models,
comparison of parallel programming models (.Net Task
Parallel Library, OpenMP, CUDA, OpenCL); energy efficiency, data
movement, resilience.
Logistics
Class Times and Place: Monday and Wednesday, 4:15pm -- 5:30pm,
Parsons 1285
This is a half-semester course. The first lecture will be held on
Wednesday, September 5th, and the last lecture will be held on
Wednesday, October 17th.
Instructor: Vivek Sarkar (Rice University)
Office: Sprague Hall 414
E-mail: vsarkar AT cs DOT hmc DOT edu
Office hours: Monday, 3:00pm - 4:00pm, "Hot Air" Computer Lab,
Beckman Hall B105 (additional times available by appointment)
Co-instructor: Ran Libeskind-Hadas
Office: Olin 1258A
Phone: 909-621-8976
E-mail: hadas AT cs DOT hmc DOT edu
Graders/Tutors ("Grutors"):
Matt Prince (mprince AT g DOT hmc DOT edu)
Mary Rachel Stimson (mstimson AT g DOT hmc DOT edu)
Habanero Java Support (Rice University):
Vincent Cave (vincent.cave AT rice DOT edu)
Shams Imam (shams AT rice DOT edu)
Online Help:
We will use Piazza for class discussion and questions. The system is highly
catered to getting you help fast and efficiently from classmates, the grutors,
and the instructors. Two members of the Habanero Java team from Rice
University will also monitor questions on Piazza to help answer
questions related to the HJ software.
Find and sign up for
our Piazza class page at:
http://www.piazza.com/hmc/fall2012/cs181e.
For more extensive help, please see an instructor or a grutor in
person.
Grading: Assignments, Exam, Participation
Your final grade will be determined by a weighted average of your grades on
each course component. Components will be weighted roughly as follows:
- Weekly assignments: 70%
- Take-home Final Exam: 20%
- Class Participation: 10%
There will be a total of 6 weekly assignments for this half-semester
course. Each assignment will include one written exercise and one
programming exercise. Assignments will be announced in class on each
Wednesday, and are due by 11:59pm of the following Tuesday.
All assignment scores will be included in your final grade.
We will use the following guidelines in grading the programming
components of the weekly assignments:
- 75% of the points will be given for a program that meets
the exact specifications of the assignment.
- 25% of the points will be given for good design, style,
testing and robustness. Good design and style means, for example, that
your program is divided into small logical functions, new classes are
defined and used when appropriate, and the program uses efficient
algorithms and data structures. Your program should also be robust in
the sense that it handles minor aberrations in user input, though
extensive input error-checking is not required unless so specified.
Finally, the code must be readable and well-documented.
We will try to provide very clear feedback indicating what could be
done to improve the program when points are deducted. If the feedback isn't entirely clear to
you, please talk to me or one of the grutors.
The take-home final exam will be a 3-hour exam available for pick-up
after the last class on Wednesday, October 17th, and due by 5pm on October 19th.
Class participation includes good-faith effort on in-class worksheets
("quizzes") which will be given in every class.
Worksheets will
not be graded, but solutions will be presented in class; your actual results on the
worksheets will not impact your grade, but good-faith participation will.
You will be asked to turn in your worksheets at the end of each
class, and (for whomever interested) they will be available for pick-up 24 hours later.
Attendance
On-time attendance at lectures is required in order
to pass this course. Attendance is of course also necessary for
you to submit worksheets/quizzes.
If you cannot attend due to illness or an
emergency, please contact us before the missed class if at all
possible (or very shortly thereafter if not).
If you need to miss class for any other reason,
you must get permission in advance.
Texts and Software
There is no required textbook for CS 181E. Instead, course handouts will
be provided for the four modules, and the class slides will also be
made available. The handout for Moduel 1 can be found here.
We will also provide optional references for further
reading in the slides and handouts.
All programming assignments will use the Habanero Java software.
Assignments
There will be an assignment every week, given on Wednesday and due by
11:59pm on the following Tuesday.
Since we use an automated procedure to determine submission
time, if you submit even slightly after midnight, it will be recorded
as being submitted the next day.
You have two late days or "CS 181E Euros" that you may use at
your discretion -- you don't need to tell us in advance. A late day
allows you to turn in an assignment 24 hours late with no penalty. You
may not use two late days on the same assignment. Late homeworks will
not be accepted once these late days have been used.
Honor Code and Collaboration Policy
All students in this class are expected to abide by the Harvey Mudd
Honor Code for work in this course.
Collaboration on homeworks is permitted and encouraged.
Here are the stipulations:
- You may only discuss problems with students currently in the
class, the grutors, and the instructors. Do not discuss the problems with
other students not currently in the class.
- Collaboration is limited to discussion. You may use
a whiteboard, blackboard, or paper as part of your discussion, but
you should erase or throw away those written materials before starting your
own write-up.
- Each individual must write up their own solutions.
- Looking for solutions or hints on the web, books, course notes
from previous semesters, or any other source is not permitted.
- You should indicate at the top of your homework submission who
you collaborated or consulted with on that assignment.
Use of laptops and portable devices in class
As a courtesy to your fellow students and your instructor, please do
not use laptops, iPads, mobile phones, etc. in class. If you genuinely need to use such
a device in class, please talk to the instructors (Ran or Vivek) and we'll find a way for you to
do so.
Independent Study Option
Since this is a 1.5 credit half-semester class, we will offer
interested students the option of registering for an additional 1.5 credits of
independent study for the second half of the semester to conduct a
project on a topic of their choosing related to the class material.
The independent study project can be done individually or in small groups of 2
or 3 students.
Acknowledgment
Much of the text in this page was adapted from the web pages for the
Fall 2012 offering of CS 60 and the Spring 2012 offering of CS 140.
