Tentative Syllabus for COM 3640
Parallel Algorithms                                              Spring, 1999
COM 3640						   Tues., 5:30 - 8:30
						       Professor G. Cooperman



Course Description:

Cheap, powerful parallel computers exist today.  One can program in
threads on top of shared memory computers, as witnessed by
the multi-processor offerings of UNIX and Windows-based vendors.
One can also program distributed, socket-based applications for
workstations over Ethernet using both RISC and Pentium architectures.

    As each new generation of computer technology re-invents itself, it
often follows the path of a previous generation. In analogy with
sequential programming, parallel programming has an assembly language.
(In fact it has three:  POSIX threads, sockets, and MPI.)  Luckily,
unlike sequential computers, these three assembly languages have been
more or less standardized. Unfortunately, there is not yet a standard
for a high level language. While Java may replace C as a "systems"
language, there are several competing attempts at a truly high level
language. These include Distributed Shared Memory (DSM) and parallel
libraries (object-based, client-server based, etc.).

    As with sequential programming, it is important to learn certain
basic data structures and algorithms. For sequential programming,
arrays, linked lists, binary trees, sorting, hashing, and other
concepts are essential. For parallel programming, one must add
parallel sorting, merging, ranking, parallel prefix computations,
pointer jumping, and other techniques.

    For parallel programming, even the models of computational
complexity have changed. Sequential programming has a simple model of
one time unit per primitive operation and zero cost for memory access.
Parallel programs are commonly modelled by PRAM (Parallel Random
Access Memory) and circuit models. Both of these models are at times
unsatisfactory, and bridging models  (e.g.:  QSM, BSP, and logP)
have been developed to "bridge" the gap between theory and practice.


Faculty Information:
    Professor G. Cooperman
    Office: 215 Cullinane Hall
    e-mail: gene (any CCS computer) or gene@ccs.neu.edu
    Phone: 373-8686
    Office Hours: Mon. 3:00 - 4:00, after class (Mon., 8:15).,
			and by appointment.


Textbook:

Parallel Programming:  Techniques and Applications Using Networked
Workstations and Parallel Computers
  Barry Wilkinson, Michael Allen, Prentice-Hall, 1999


Exams and Grades:

    There will be one mid-term, one or two homework assignments and
a project. They will be weighted 35% for the midterm, 25% for the
homework, and 40% for the project. All homework assignments will be
equally weighted. Students will have an opportunity to choose a
project from a range including extending an implementation of MPI,
solving an applied problem using a parallel tool, and a study of
current literature on some parallel algorithms.

Syllabus:

Week          Topics                                  Recommended Readings
Mar. 30       Introduction                            
	      (Dist. memory vs. shared memory;
	       parallel prefix, PRAM and Circuit models)
Apr. 6        POSIX Threads and Sockets
	      (cache coherence, memory consistency, bus snooping)
Apr. 13       Brent's Theorem, Theoretical Models  
              (PRAM, Circuit, bridging models:  QSM, BSP, logP)
Apr. 20       Primitive parallel algorithms and MPI   
	      (parallel prefix, pointer jumping, list-ranking, parity)
Apr. 27       Higher parallel algorithms              
	      (sorting, merge, matrix multiplication and inverse, possibly FFT)
May 4         Mid-term
May 11        Higher level tools:   TOP-C(NoW), QUARK(DSM), CILK(SMP)
May 18        More higher level tools:  comparison of features of systems
May 25        Wide-area distributed and O/O computing:  Legion
Jun. 1        Topics of interest to class;  project due that week