Parallel Programming

Vassar College, Fall 2020
Syllabus / Course Wiki

Welcome to our course wiki. It will be updated throughout the semester with important course information, so check here regularly.

Professor: Marc Smith
Office: SP 104.5 (teaching fully remote)
Office Hours: Tue/Thu/Fri 4-5pm; and by appointment Zoom
Phone: 845 437 7497
Email: mlsmith (best way to contact me!)
Time (when) Mon/Wed 12:00–1:15pm
Zoom (where) Zoom link available in Moodle

Required Text: M. Ben-Ari. Principles of Concurrent and Distributed Programming, Second Edition. Addison-Wesley. © 2006.

Recommended Text: Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language, Second Edition. Prentice Hall, © 1988.

Restricted access (requires authentication)

Prerequisites: The prerequisites for this course are CMPU-203 and CMPU-224. While a solid foundation in data structures and algorithms is required for all upper level computer science courses, you may be wondering why this course also draws upon computer organization? The short answer is no matter what the model of concurrency, the parallel and distributed programmer must have a thorough understanding of computer architecture, including the resources that make interprocess communication possible. An additional reason for requiring CMPU-224 is we will be programming in the C programming language, and (among other languages) UPC, a parallel C language extension. To understand C, in large part, is to understand pointers; to understand pointers is to understand assembly language, which is taught in computer organization.

Overview: You may have noticed that Vassar's introductory curriculum (since spring 2009) is not like that of many other colleges and universities. To put it delicately, we don't teach Java (or Python) in 101, and these “popular” languages are not especially emphasized in the rest of our curriculum. Instead, we teach functional programming in the first course, with an emphasis on structural recursion. Why did we make this change? Structural recursion provides a natural transition not only to Object-Oriented Design in 102, but also enhances the presentation of discrete mathematical structures in 145. What we don't emphasize in 101 is that functional programming also plants the seeds for introducing parallel programming concepts.

Top-down design? Divide-n-Conquer? Recursion? These are all techniques you've learned for breaking up a problem into subproblems. Fine, but why must the subproblems execute sequentially? Object-oriented? How does OO computation proceed? By objects sending messages to other objects. Indeed, message passing is one of the two major concurrency paradigms (the other is shared memory). But most of the OO programs you've seen consist of a single thread of execution, where the effect is one object executing while the rest “sleep”; effectively, objects take turns executing one at a time. This is not natural, but it is also not surprising given the origins of modern computing. The von Neumann model had a strong influence on the subsequent adoption of imperative languages over functional (a bias we strive to overcome with our intro CS curriculum at Vassar). Many programming language abstractions have emerged to date, including sequential composition (think semicolons between statements), conditional expressions (if-else statements), and recursion (of which for and while loops are special cases). But as I've already hinted, abstractions for parallel composition exist, and in this class we will explore them. It's time to think outside the sequential box. Concurrency is not just about making things faster, it's more importantly about being able to express solutions to many problems more naturally.

A few words about the texts I chose: I chose two texts this semester−one required and one recommended. The required text is closely related to the title of this course: Principles of Concurrent and Distributed Programming. I especially like the author's choice and organization of topics, and decision not to emphasize any particular programming language. Languages we will use this semester include UPC (with a crash course in C), Ruby (and Rinda), kroc (or maybe Go), Java, and time permitting, maybe one or two more: the Spin model–checker, and Erlang. Since UPC is an extension of the C programming language, which you may or may not have experience using, I recommended the K&R text, which you may have heard referred to as “the bible” of C programming. You also may have heard K&R is not a good book to learn C. I disagree. This criticism was more true of the first edition, not the second. Furthermore, C will not be your first programming language, and I have great confidence in your ability to learn C from its source: K&R.

Goals: We are in the midst of a “Concurrency Revolution” (a term coined by Herb Sutter, of Microsoft Research). Already the computers we buy and use are multicore (multiple processors arranged on a single chip). If we are to continue to take advantage of increased processing capability in the software we write, we must learn to master a new programming paradigm. Toward this end, the following are goals of this course:

  1. Learn different approaches to modeling concurrency
  2. Gain practical experience writing programs for each of these models
  3. Recognize and understand the challenges and dangers of concurrency
  4. Learn programming techniques to help avoid these dangers
  5. Learn how to simulate one model of concurrency with another
  6. Provide a foundation for learning additional models and implementations of concurrency

Topics / Course Outline: In this course we will study the general area of concurrency. Parallel and distributed computing are special cases of concurrency. When two or more processes execute concurrently, they need to communicate and coordinate. The ability to communicate and coordinate is hardware (architecture and network) and software (operating system and programming language) dependent. More paradigms and design patterns exist to address this problem than can be covered in a single course (or a single textbook), so I have selected three models that I hope will provide you with the ability to explore other models of concurrency on your own. In addition, since one of the programming languages we'll be using is based on an extension to the C programming language, we will learn C (with an emphasis on pointers, and not to be confused with C++) along the way this semester.

What follows is an outline of main topics we will cover this semester. We will cover designated parts of the following chapters from the Ben-Ari text. Programming languages that correspond to a chapter are shown inside parentheses, and described further, below. Chapters may not be covered sequentially (sorry, I couldn't resist!) so that programming assignments may be more evenly distributed throughout the semester.

  1. What is Concurrent Programming?
  2. The Concurrent Programming Abstraction
  3. The Critical Section Problem
  4. Verification of Concurrent Programs (jSpin)
  5. Advanced Algorithms for the Critical Section Problem
  6. Semaphores (UPC and Java)
  7. Monitors (Java)
  8. Channels (occam/kroc, or Go)
  9. Spaces (Ruby and the Rinda library)

Material not covered in the texts will be supplemented with other electronic references, handouts, and from lecture notes.

Programming Paradigms/Languages:

  1. Sequential Computation (and introduction to C Language programming)
  2. Linda and Tuple Space (a distributed, associative shared memory model of concurrency; programming in Ruby with the Rinda library)
  3. UPC (a distributed, addressable shared memory model of concurrency; programming in UPC)
  4. CSP (a synchronous, message-passing model of concurrency; programming in one of JCSP, kroc, or Go)

Interleaved within the above paradigms, we will investigate and consider some subset of the following:

  1. communication and coordination models, techniques (i.e., shared memory, message passing)
  2. synchronization primitives (e.g., semaphores, monitors, channels, spaces)
  3. simulations of one synchronization paradigm with another
  4. design and analysis of parallel algorithms
  5. classic problems (e.g., deadlock, livelock, infinite postponement)
  6. Case Studies (e.g., Max, Prime number sieve, Barber shop, One-lane bridge, Critical Section, Readers/Writers, Dining Philosophers)

Software / Computing Environment: We will be writing programs this semester in a variety of languages. One language, in particular, derives from the C programming language: UPC (Unified Parallel C). In addition, we will study some combination of occam (using the kroc compiler), JCSP (Communicating Sequential Processes for Java), or the Go programming language. Compilers for these languages are free and available for download on the internet, if you are interested in obtaining your own copies of the course software. Related links are provided near the top of this page. Time permitting, we will briefly discuss Java's java.util.concurrent package available in J2SE 5.0.

For most of our programming assignments, we will be using the Linux workstations in the Asprey Lab, which are all single-socket, quad-core processors. All programs you hand in must be compiled for, and execute on, the Asprey Lab workstations.

Office Hours: This is the first of many times that I will ask you to come see me any time you have questions. Office hours are the best time to come by, but feel free to come by at other times, too, although just before class is usually a bad time to reach me since I am busy with last-minute class preparations. Please feel free to make an appointment if you prefer. One of the advantages of attending Vassar over larger colleges and universities is that we have relatively small classes, and we have faculty who are willing to take the time to help you learn when you ask. It frustrates us when we miss opportunities to pull students out of confusion. Active learning is particularly important in this course. Many of the concepts we will cover build on each other. If you find yourself stuck trying to understand something, it will only make catching up later that much worse. This is another reason to keep up with assigned work.

Discussion: So take advantage of your instructor – and your fellow students. Ask questions in and out of class. If you have a question, you can bet you're not the only one in class with that question. Answering a classmate's question is a great way to gauge your own understanding of a topic or concept. For my part, I'll try to make the material as easy to digest as possible, but I need your help identifying the things that are confusing you.

Feedback: Please feel free to raise any concerns or complaints about the course directly with me. You are also welcome to send me your concerns anonymously. I will gladly respond to them. I also encourage you to let me know when something about the course is going well – I'll try to keep doing it.

Attendance: You are expected to attend every class, although I won't record your attendance for the sake of doing so. As a courtesy, I expect prior notification when you choose not to attend class, and official notes of explanation (e.g., from the Dean of Studies office, or the Health Service) for any unforeseen absences (e.g., illness, injury, family emergency). You are responsible for all information presented in class, whether or not you are present.

Participation, Assignments, Lateness, Exams, and Grades: There will be regular homework and programming assignments, and occasional announced quizzes, as well as one midterm and one final exam. There will be no opportunity to turn in a homework assignment late once any part of its solution has been discussed in class. For similar reasons there will be no make-up quizzes. During discussions, I do not expect you to give correct explanations or answers to my questions, but I do expect you to try to give reasons for your answers. Participation (written and oral) requires attendance, therefore attendance is essential to your overall class performance.

The date for the midterm has already been set (Thu, Mar 12). Alternative arrangements are possible under extraordinary circumstances and with ample prior notice. The final exam will be held during this class's predetermined final exam period. The course grade will be determined as follows:

10% Homeworks, Attendance, and Participation
40% Programming Assignments
25% Midterm assignment
25% Final assignment

Your final grade will be determined by your overall average; the weighted sum of the averages from your participation and programming assignments, midterm and final exams. If your overall average is at least 90%, you will get an A; at least 80%, you will get a B; and so on. The final lines might be drawn somewhat below these levels, and pluses or minuses added at the instructor's discretion (e.g., based on your attendance and class participation).

Additional Notes regarding Homework: Keeping up with and understanding the homework and programming assignments is your key to success in this course. This point cannot be stressed enough. For some programming assignments, we may try practicing pair programming with a partner. Furthermore, you are encouraged, but not required, to work with other students on the homework assignments! Such collaboration can be a powerful learning aid. But…

Academic Integrity: Please don't cheat. Read Going to the Source. Since this course is concerned with composing code, the guidelines that apply to writing in general apply equally to the writing of computer programs. Copying someone else's code without attribution amounts to plagiarism. So give proper attribution for the help you receive. Quoting from chapter X of Going to the Source, “In suspected cases of plagiarism, the instructor prepares a written statement of complaint to the Academic Panel.” Please don't put yourself or your professor in that position. When in doubt, ask me before seeking any help from another source.

Students with disabilities: Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity (AEO). Students in need of disability (ADA/504) accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course that have been approved by the Office for Accessibility and Educational Opportunity, as indicated in your AEO accommodation letter.

Title IX Statement: Vassar College is committed to providing a safe learning environment for all students that is free of all forms of discrimination and sexual harassment, including sexual assault, relationship abuse, and stalking. If you (or someone you know) has experienced or experiences any of these incidents, know that you are not alone. Vassar College has staff members trained to support you in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, helping with legal protective orders, and more.

Please be aware all Vassar faculty members are “responsible employees,” which means that if you tell me about a situation involving sexual harassment, sexual assault, relationship abuse, or stalking, I must share that information with the Title IX Coordinator. Although I have to make that notification, the Title IX office will only provide outreach by email. You will control how your case will be handled — you don’t have to read or respond to the email, and it is completely up to you whether to pursue a formal complaint. Our goal is to make sure you are aware of the range of options available to you and have access to the resources you need.

If you wish to speak to someone privately, you can contact any of the following on-campus resources:

The SAVP website ( and the Title IX section of the EOAA website ( have more information, as well as links to both on- and off-campus resources.