CSC 2/458

Parallel and Distributed Systems

Spring 2022

Both parallel and distributed systems can be defined as a collection of processing elements that communicate and cooperate to achieve a common goal. Advances in processor technology have resulted in today's computer systems using parallelism at all levels: within each CPU by executing multiple instructions from the same thread of control simultaneously (superscalar architectures/instruction-level parallelism); by executing multiple intructions from different threads of control simultaneously (simultaneous multithreading); by introducing multiple cores in a single chip (chip multiprocessors); by using multiple chips to form multiprocessors; or via multiple networked nodes to form a cluster; making parallel systems increasingly ubiquitous. Simultaneously, advances in networking technology have created an explosion of distributed applications, making distributed computing an inherent fabric in our day-to-day lives. This course will focus on the principles of parallel and distributed systems and the implementation and performance issues associated with them. We will examine programming models/interfaces to parallel and distributed computing, interprocess communication, synchronization and consistency models, fault tolerance and reliability, distributed process management, parallel machine architectures, parallel program optimization, and the interaction of the compiler, run-time, and machine architecture.

This course follows the College credit hour policy for four-credit courses. This course meets twice weekly for three academic hours per week. The course also includes independent out-of-class assignments and activities for an average of one academic hour per week. These activities include reading academic papers for in-class discussion, researching a specific course topic for in-class presentation of the material, and group meetings to discuss project design, tools, and/or application domains for a term project.

Class time: 3.25---4.40 p.m., Mondays and Wednesdays.
Class location: Dewey Room 2110E or online (zoom link via blackboard)

Instructor:

TA:

Questions and Answers

Prerequisites:

Material we will use:

Schedule

Distributed Systems, 2017 Edition: Maarten van Steen and Andrew S. Tanenbaum

Parallel Computer Architecture, A Hardware/Software Approach, 1999 Edition: David E. Culler, Jaswinder Pal Singh, and Anoop Gupta

Introduction to Parallel Computing, Anantha Grama, George Karypis, Vipin Kumar, and Anshul Gupta (Publishers: Addison-Wesley)

Distributed Systems: Concepts and Design, third edition, George Coulouris, Jean Dollimore, and Tim Kindberg (Publishers: Addison-Wesley)

The Art of Multiprocessor Programming: Maurice Herlihy and Nir Shavit (Publishers: Morgan Kaufmann)

High Performance Compilers for Parallel Computing, 1996 Edition: Michael Wolfe

Shared-Memory Synchronization, Michael L. Scott

Optimizing Compilers for Modern Architectures, 2002 Edition: Randy Allen and Ken Kennedy

Foundations of Multithreaded, Parallel, and Distributed Programming, 2000 Edition: Gregory R. Andrews (Publishers: Addison-Wesley)

(Some) Topics Covered:

Basics of parallelization and parallelization strategies

Parallel/distributed programming models and interfaces - shared memory vs. message passing vs. remote procedure call (RPC) vs. global address space languages: e.g., pthreads, MPI, MapReduce, OpenMP, HPF, UPC, language-level threads (e.g., Java)

Parallel machine architectures - shared and distributed memory machines, multicore and multithreaded chips, interconnection networks

Parallel program optimization techniques - synchronization granularity, dependences, scheduling, load balancing

Synchronization - hardware primitives, logical and physical clocks, mutual exclusion, distributed transactions, transactional memory

Consistency and coherence - data-centric versus client-centric consistency models, cache coherence protocols

Fault tolerance and reliability - fail-stop versus byzantine failure models, two- and three-phase commits, reliable group communication, checkpointing, message logging

Assignments and Grading

There will be two or three small programming assignments, a couple of written homework assignments, a term project, and potentially one exam. There may also be occasional spot quizzes. The course will consist of a combination of lectures and student presentations. Grading will be based on the assignments, project, presentations, exam (maybe)/quizzes, and class participation and attendance. The tentative grading scheme is as follows:

• 30% class participation and attendance, class presentation(s)
• 20% programming assignments
• 30% term project
• 20% homeworks/quizzes/exams (the latter if any)

Possible semester projects

Academic Honesty Policy:

Posting homework and project solutions to public repositories on sites like GitHub is a violation of the College’s Academic Honesty Policy, Section V.B.2 “Giving Unauthorized Aid.”

If you do start with someone else's code (e.g., you download a procedure from the web so that you can get the rest of your project working, or you build on someone else's work or program), you must (1) either have the author’s explicit permission or the material must be publicly available, and (2) label what parts of your code you copied and from where, clearly and prominently, when you hand it in. Note that you will get credit only for the parts of your assignment that you implemented yourself. Written assignments are similarly expected to be in your own words, and must include appropriate citation to content that you might be summarizing. Any direct use of someone else's words or pictures requires quotation and attribution.

Quizzes and exams (if any) must be strictly individual work.

Links to Relevant Documentation

Paper (and Chapter) Reading List