Parallel Algorithms

• Text: "The Design and Analysis of Parallel Algorithms"
  • Author: Justin R. Smith
  • Publisher: Oxford University Press
  • ISBN:019-507-8810
  • Web page

Book selection in compressed pdf format
Book selection in compressed postscript
Selection 2 in compressed postscript
Selection 2 in compressed pdf
Selection 3 in compressed postscript
Selection 3 in compressed pdf
Selection 4 (chapter 6) in postscript

Sign up sheet for presentations

Web page to look up your grades at any time

Notes on computing eigenvalues of matrices
This web page uses MathML and is only viewable by a browser that supports it (Mozilla or Amaya)

Goals of this course

To acquaint students with:

• Applications of parallel processing,
• a "taxonomy" of parallel processing architectures:
  • MIMD verses SIMD
  • systolic and VLSI algorithms
  • types of memory access (CREW verses CRCW)
  • network architectures (hypercube, butterfly)
• Overview of parallel processing and its applications
• Models of parallel computation.
  • The PRAM model and SIMD computation.
  • A sorting algorithm.
• Theoretical Issues
  • P-completeness and inherently sequential problems.
  • Relations between PRAM models.
• Linear algebra:
  • Multiplication of matrices
  • Reif-Pan algorithm for matrix inversion.
  • Gauss-Seidel algorithm for solving systems of linear equations.
• Applications to the numerical solution of partial differential equations.
  • Laplace's equation
  • Heat equation
  • Wave equation
• Quantum Computing
  • Concepts of quantum mechanics (wave-particle duality). The Copenhagen Model.
  • Multi-particle systems (quantum entanglement)
  • Many worlds interpretation
  • Reversible computations, quantum gates
  • Algorithms. A tutorial on quantum computing

Links

• The Connection Machine Home Page
• Algorithms in High-Performance Fortran
• PVM Home Page
• Internet Parallel Computing Archive
• Oxford Quantum Computing Institute
• Beowulf Home Page
• MPI Home Page
• Star Bridge Systems
• FORK PRAM simulator and language (From a group developing a PRAM computer).
• Top 500 Supercomputers in the world (all of which are parallel).
• Setting up a trusted ssh interface between two hosts
• Information on pthreads: Pthreads is one of the easiest systems to use for parallel programming on a MIMD computer running Linux:
  Pthreads tutorial
• A description of the Many Worlds Interpretation of Quantum Mechanics
• Quantum::Entangle
  A Perl module that simulates Quantum computing (there is more than one universe in which to do it)

Up to my home page