Date: Tue, 26 Nov 1996 18:40:55 GMT
Server: NCSA/1.5.1
Last-modified: Tue, 16 Jan 1996 21:09:57 GMT
Content-type: text/html
Content-length: 6043
CS 156: Parallel and Real-Time Computation
URL http://www.cs.hmc.edu/~keller/cs156.html
Computer Science 156: Parallel and Real-Time Computation
Course Personnel:
- Instructor: Robert Keller
242 Olin (4-5 p.m. MTuWTh or by appt.), keller@muddcs, x 18483
- Secretary: Nancy Mandala 240 Olin (1-5 M-F) nancy@muddcs, x 18225
- CS Intern (for account problems, etc.): TBD, 101 Beckman, TBD@muddcs, x 73485
Catalog Description
Characteristics and
applications of parallel and real-time systems. Specification
techniques, architectures, languages, design, and implementation. 3
credit hours.
Prerequisites: Prerequisites: CS 124 and 131.
3 credit hours.
Texts
Michael J. Quinn. Parallel computing: Theory and practice. Second Edition. McGraw-Hill (1994).
Selected references such as papers will be provided.
Course Requirements
There will be two or three programming assignments on parallel
machines, as well as some written assignments. Participants will present
short tutorial lectures on a chosen topic. Participants will choose a
project with the instructor's approval, and report the results to
the class.
CS 152 Topic Outline
MQ denotes reading pages in Quinn's book.
- Motivation for parallel computing MQ 1-24
- Response time
- User concurrency
- Throughput
- Fault tolerance
- Logical structuring
- Example parallel applications
- Expression evaluation
- Matrix computations
- Database search
- Sorting
- Measuring and analyzing parallel program performance
- Serial vs. parallel time, speedup
- Efficiency
- Generic models
- Theoretically-Motivated Models
- PRAM (parallel random-access machine) MQ 25-51
- DAG (directed acyclic graph) model
- WT (work-time) model (JaJa)
- BSP (bulk-synchronous parallelism)
- Architecturally-Motivated Models
- Interconnection Networks MQ 52-89
- MIMD (multiple-instruction-stream, multiple-data-stream)
- SIMD (single-instruction-stream, multiple-data-stream)
- SPMD (single-program, multiple-data)
- Language-Motivated Models
- Dataflow
- Systolic arrays
- Functional programming
- Logic programming (goal trees)
- Object-oriented programming
- Architecture Studies MQ 52-89
- SIMD architectures
- Connection Machine
- ICL DAP
- Masspar
- MIMD architectures
- Shared memory
- Sequent Symmetry
- Cray T3D
- Partitioned memory
- NUMA (non-uniform memory access machines)
- Clusters
- Other architectures
- Dataflow
- Graph reduction
- VLIW (very-long instruction word machines)
- Systolic arrays
- Neural networks
- Programming
- Low-level
- Review of processes, communication
- Rendezvous
- Unix process management
- Barrier synchronization
- Mach
- Higher level
- Linda
- Futures
- APL-like operators
- Language issues
- Parallel decomposition
- Dataflow analysis
- Grain-size
- Trace scheduling
- Languages MQ 91-130
- Concurrent Functional Languages
- Sisal
- MultiLisp
- Fortran 90, High-Performance Fortran
- Ada 9x
- Concurrent C
- *c, *Lisp
- Concurrent Prolog, Strand
- PVM, MPI
- Mapping and scheduling MQ 131-156
- Other System issues
- Scalability, Isoefficiency metric (Kumar)
- Cache coherence
- Combining networks
- Load balancing
- Deadlocks
- Fault tolerance
- Algorithm Studies
- Elementary MQ 157-177
- Matrix multiplication MQ 178-197
- Fast Fourier Transform MQ 198-216
- Solving Linear Systems MQ 217-254
- Sorting MQ 255-293
- Parallel Search MQ 294-308
- Graph Algorithms MQ 309-335
- Combinatorial Search MQ 336-366
- Applications and case studies
- Finite elements
- Parallel logic programs
- Monte Carlo traveling salesman problem
- Many-body simulation
- Theorem proving
- Real-Time Systems
- Characteristics and examples of real-time systems
- Timing and performance issues
- Handling time delays and timeouts
- Deadline specification and scheduling
- Language requirements
Table of Contents, Parallel Computing: Theory and Practice
- Introduction
- PRAM Algorithms
- Processor Arrays, Multiprocessors, and Multicomputers
- Parallel Programming Languages
- Mapping and Scheduling
- Elementary Parallel Algorithms
- Matrix Multiplication
- The Fast Fourier Transform
- Solving Linear Systems
- Sorting
- Dictionary Operations
- Graph Algorithms
- Combinatorial Search
Some additional references
- Joseph JaJa, An introduction to parallel algorithms, Addision-Wesley 1992.
- Guy E. Blelloch. Vector models for data-parallel computing, MIT Press 1990.
- Vipin Kumar, et al., Introduction to parallel computing, design and analysis of algorithms, Benjamin/Cummings 1994.
- Geoffrey Fox, et al., Parallel computing works!, Morgan-Kauffman 1994.
- Gregory Pfister, In search of clusters, Prentice-Hall 1995.
RCS $Id: cs156.html,v 1.2 1996/01/16 19:25:55 keller Exp keller $