CE113: Parallel and Concurrent Programming
 
Catalog copy 
Introduction to parallel and concurrent programming.  Topics include
 types of parallel computers and programming platforms, basic and
 advanced programming techniques, performance   Prerequisites: course
 110 and Computer Science 101.  R. Hughey, K. Obraczka, L. De Alfaro,
 T. Madhyastha



Explanation of prerequisites:
CE110:  Students need to be familiar with architecture, especially
 caching, for the discussions about parallel architectures.  It may be
 appropriate to change this to CE110 or CE111.
CS101:  Students need to understand algorithms and asymptotics to be
 able to create and analyze parallel and concurrent programs.
 
Required skills to pass the course.
1. Ability to design and efficiently implement message passing algorithms
   using an appropriate language or library.
2. Ability to design and efficiently implement threaded code using an
   appropriate language or library.
3. Ability to describe and analyze the performance of such code
4. Ability to understand basic concepts and uses of parallel and
   distributed computing and systems.


Core topics (must be taught)
1. Basic parallel, distributed, and multiprocessor architectural
   concepts
   a. Connection networks
   b. Shared memory
   c. Distributed memory
   d. Flynn's Classification
   e. UMA/NUMA/etc
   f. Amdahl's Law (introduced in CE110)
   g. Asymptotics as applied to parallel algorithms
2. Message-passing programming and algorithm design
3. Multi-threaded programming and algorithm design
4. Current issues in all main topics
5. A selection of parallel and distributed algorithms from chosen 
   disiplines (instructor's choice) that emphasize
   a. Performance analysis
   b. Problem partitioning
   c. Sychronization

Optional topics 
1.  Specific architecutures (Blue Gene, UCSC Kestrel, Illiac,
    dual-processor Pentiums, the CBSE Cluster, etc)
2.  SIMD programming
3.  Additional programming languages or methodologies

Core lab exercises 
1.  Writing MPI programs of varying difficulty
2.  Writing pthreads programs of varying difficulty
3.  Writing about parallel algorithms and their performance.
 
Optional lab exercises 
1.  Writing UCSC Kestrel SIMD parallel processor programs
 
Comments on related concurrent courses 
None.

 
Comments on follow-on courses 
CE220  Parallel Processing studies parallel and distributed
  architectures at the graduate level.
CE290M Topics in Parallel Processing usually focusses on practical
  parallel algorithms with a far higher level of analysis than CE113.
CS290S  Topics in Systems  has at times focussed on cluster and grid
  computing research.

Text 

Barry Wilkinson and Michael Allen, "Parallel Programming: Techniques
 and Applications Using Networked Workstations and Parallel
 Computers", Prentice, 1999.  Second edition expected in 2003.  A
 parallel programming text designed specifically for undergraduates,
 this book has clear, short chapters on all the important issues, and
 more detailed chapters on various applicaions (sorting, image
 analysis, numerical methods, and searching).


Other reading:  

Richard Hughey and the UCSC Kestrel Group, Docomentation of the
 Kestrel System, 2000.  For SIMD assembly language programming on the
 512-processor Kestrel system.

Peter S. Pacheco, "Parallel Programming with MPI", Morgan Kaufmann,
 1997.  Too narrowly focussed on MPI for a text.

Ian Foster, "Designing and Building Parallel Programs," Addison
 Wesley, 1995.  A good reference, but more at the graduate level.

Russ Miller and Laurence Boxer, "Algorithms Sequential & Parallel:  A
 Unified Approach," , Prentice, 2000.  Meant to be an undergraduate
 algorithms text (as for CS101), so too elementary for this class.

Prepared by Richard Hughey, 10/02