ON THIS PAGE:

Course Objectives

Prerequisites

Approach

Typical Text

Course Outline

Course Objectives
This is an introductory graduate course covering several aspects of parallel and distributed systems. Upon completion, the student should

• be able to design and analyze concurrent algorithms for a variety of problems and computational models,
• be familiar with the fundamentals of the architecture and systems software of parallel and distributed systems
• have experience with the implementation of parallel applications on several platforms, and be able to evaluate their performance.

Prerequisites
Undergraduate-level familiarity with the design and analysis of sequential algorithms (e.g. COMP 550), elementary operating systems concepts (e.g. COMP 530), and computer organization (e.g. COMP 411) is expected.

Approach
The course follows a conventional model of lectures; readings from notes and the research literature; written assignments, programming assignments, and exams.

Typical Text
Notes and extracts from the literature.

Course Outline
The material is organized around various models of parallel and distributed computing. Each model is illustrated by using it to develop and analyze specific algorithms, and examining some practical issues such as programming and performance evaluation. The following topics are covered in approximately the order and number of lectures indicated.

• Course Overview and Motivation (1)

• Shared Memory Models (13)
  • PRAM and Work-Time Models: algorithm design techniques, asymptotic analysis, relative power and limitations of PRAM models. (4)
  • Loop-Level Parallelism: OpenMP directives and scheduling, memory hierarchy and cache coherence. Barnes-Hut N-body algorithm, performance evaluation (4)
  • Multithreading: synchronization, locking, mutual exclusion, atomicity memory consistency models, Java threads, Cilk. (5)

• Distributed Memory Models (13)
  • Bulk Synchronous Model: performance analysis, bulk communication operations, sorting algorithms, performance parameters of current multiprocessors, performance evaluation (5)
  • Message Passing Model: SPMD programming, Message Passing Interface (MPI), cluster computing. (2)
  • Client-server Model: internet supercomputers (1)
  • Network Models: communication network topology and metrics, routing, flow control; design and analysis of basic communication operations. (3)
  • Ordering of events in distributed systems: clock synchronization, logical clocks (2)

• Future Trends (1)
  Example algorithms are chosen to highlight the differences in development approach using different models, to introduce issues in analysis of parallel and distributed algorithms and to illustrate the interplay between theoretical models and implementation issues.