Organization of CPS-615 page (first draft)

General Hardware and Software Resources

• Parallel Computing and Architecture (key topic)
  • Some lectures slides on SIMD, MIMD, etc.
  • Links to book chapters (e.g. from CSEP), etc.
  • Links to tutorials, etc.
• Algorithms and Applications (key topic)
  • Iterative numerical integration methods for ODE's, etc.
  • Motivation for PDEs, etc.
  • References to the CSEP project.
  • Intro to linear algebra, etc.
  • Finite element methods and CG solvers, etc.
  • Parallel algorithms for full matrices.
  • Other parallel algorithms.
• Programming Languages and Tools
  • Fortran90 and HPF
    • Fortran90 link to slides, tutorials, and other resources.
    • HPF links to slides, tutorials and other resources.
  • MPI
    • Links to slides.
    • Links to tutorials, manuals, examples, and other resources.

Course Summary and Lectures (including the audio) - listed by date

• Materials covered: a summary.
• Lectures
  • Lecture (1) foilsets -- September 3, 1996
    • Comments: Covers foils 1-6 upto: Basic Structure of Domain to be Updated in Parallel Version. Then from foil 25: General Features of Laplace Example, upto end of foilset.
    • Audio Recording: no audio is available.
  • Lecture (2) foilsets -- September 5, 1996
    • Comments: Lecture start with foil: Superconducting Technology -- Problems, with a discussion of:
      • This starts by considering the analytic form for communication overhead and illustrates its stencil dependence in simple local cases -- stressing relevance of grain size. This was covered in Homework 3.
      • The implication for scaling and generalizing from Laplace example is covered. We covered scaled speedup (fixed grain size) as well as fixed problem size. Also noted some useful material was missing and this was continued in next lecture (Sept 10) .
      • The lecture starts coverage of computer architecture covering base technologies with both CMOS covered in an earlier lecture contrasted to Quantum and Superconducting technology.
    • Audio Recording: on performance and computer technologies.
  • Lecture (3) foilsets -- September 10, 1996
    • Comments: start with foil MIMD Distributed Memory Architecture, with a discussion of:
      • Details of communication overhead in parallel processing for case where "range" of interaction is large.
      • Two old examples from Caltech illustrating correctness of analytic form.
      • Return to more discussion on computer architectures describing:
        1. Vector Supercomputers.
        2. General Relevance of data locality and pipelining.
        3. Flynn's classification (MIMD,SIMD etc.)
        4. Memory Structures.
        5. Initial issues in MIMD and SIMD discussion.
    • Audio Recording: on MIMD distributed memory architecture.
  • Lecture (4) foilsets -- September 12, 1996
    • Comments: continue with foil: Latency/Bandwidth Space for 0-byte message(Latency) and 1 MB message(bandwidth), with discussion of:
      1. MIMD and SIMD with distributed shared memory.
      2. MetaComputers.
      3. Special Purpose Architectures.
      4. Granularity with technological changes forcing larger process sizes.
      5. Overview of Communication Networks with Switches vs. Buses Topologies.
      6. Typical values in today's machines.
      7. Start detailed discussion of software technologies in HPCC where we cover Fortran 90, HPF and MPI with basic overview and Fortran90/HPF as it covered in this foilset: HPCC Software Technologies Fall 96 -- Overview and HPF
    • Audio Recording: on latency/bandwidth space for 0-byte message(Latency) and 1 MB message(bandwidth).
  • Lecture (5) foilsets -- September 17, 1996
    • Comments: we returned to Laplace equation discussion (which we had used for performance analysis) starting with foil: Discretized Form of Laplace'e Equation on a Parallel Processor in Programming Models and Performance for Laplace's Equation discussing sequential and HPF implementation. We briefly mentioned MPI version and introduced Fortran90 ending with foil: Important Features of Fortran90 in HPCC Software Technologies Fall 96 -- Overview and HPF.
      1. This took us back to the discussion of parallel software in the context of example of Jacobi Iteration for Laplace equation in a square box of 256 grid points on 16 processors.
      2. We already used this example to discuss performance earlier in the semester.
      3. HPF was briefly covered as well as brief discussion of MPI implementation of this example.
      4. The lecture was finished with initial remarks on Fortran90.
    • Audio Recording: no audio for this lecture.
  • Lecture(6) foilsets -- September 24, 1996
    • Comments: start with foil Introduction to Fortran90 Arrays covered in an overview of Fortran 90 and HPF with a discussion of Fortran 90 features at a higher level, then comparing programming models and how HPF fits into that model. The last foil for this discussion was Data Parallel Programming Model. Next, the discussion shifted to the foilset Overview of Programming Paradigms and Relation to Applications to discuss our theory of problem architecture ending at foil: The Mapping of Heterogeneous Metaproblems onto Heterogeneous Metacomputer Systems.
      1. This continues the discussion of Fortran 90 with a set of overview remarks on each of the key new capabilities of this language.
      2. We also comment on value of Fortran90/HPF in a world that will switch to Java.
      3. We digressed to discuss a general theory of problem architectures as this explains such things as:
         • HPCC versus Software Engineering.
         • HPF versus MPI.
         • The types of applications each software model is designed to address.
    • Audio Recording: Introduction to F90 Features, Rationale for HPF and Problem Architecture.
  • Lecture(7) foilsets -- September 26, 1996
    • Comments:
      1. Started with covering our Web based Virtual Programming Laboratory(VPL).
      2. Then we returned to Problem Architecture discussion from foils The map of Problem - Computer is performed in two or more stages to `What determines when Parallelism is Clear?'.
      3. We skipped more descriptive material on HPF to begin the language discussion from foils: Parallelism in HPF to Examples of Align Directive.
      4. Homework5 and Homework6 included basic exploration of VPL and the first Fortran90 examples.
    • Audio Recording: Introduction to Virtual Programming Lab -- Problem Architecture Continued and Start of Real HPF.
  • Lecture(8) foilsets -- October 1, 1996
    • Comments: HPF discussion continued covering not only the basic syntax but also examples of the different distribution strategies of BLOCK, CYCLIC and CYCLIC(number). The discussion ended at foil: WHERE (masked array assignment) in HPF.
    • Audio Recording: Align and Distribute in HPF.
  • Lecture(9) foilsets -- October 3, 1996
    • Comments: HPF discussion continued by Tom Haupt.
    • Audio Recording: none available.
  • Lecture(10) foilsets -- October 8, 1996
    • Comments: more HPF discussion continued by Tom Haupt.
    • Audio Recording: none available.
  • Lecture(11) foilsets -- October 10, 1996
    • Comments: we started out discussion of Ordinary Differential Equations (ODE) and the N-body problem. Numerical methods for ODE were covered completely then started a discussion of parallel N-body algorithms getting upto foil: Simple Data Parallel Version of N-Body Force Computation.
    • Audio Recording: Discussion of Ordinary Differential Equations and Start of Parallel N-Body Algorithm.
  • Lecture(12) foilsets -- October 15, 1996
    • Comments:
      1. Finished discussion of ODE's and particle dynamics stopping at foil: N-body Problem is a one dimensional Algorithm.
      2. Started a discussion of Numerical Integration getting upto foil: Use of High Order Newton Cotes.
      3. Homework7 was assigned to do some in depth programming using VPL.
    • Audio Recording: < a href="http://www.npac.syr.edu/users/gcf/cps615oct1596/index.html"> End of N-Body Discussion and Beginning of Numerical Integration .
  • Lecture(13) foilsets -- October 17, 1996
    • Comments:
      1. Continued discussion of Numerical Integration from foil 10: Strategies for Manipulating Integrals before using Standard Numerical Integration to foil 33: Why Monte Carlo Methods Are Best in Multidimensional Integrals.
      2. Then went back and discussed basic statistics and random numbers ending at foil 9: The Gaussian Distribution.
      3. ee Paul Coddington's recent article on Random Number Generation.
    • Audio Recording: not available.
  • Lecture(14) foilsets -- October 22, 1996
    • Comments: We finished discussion of Statistics and Random Numbers (In preparation for Monte Carlo) covering:
      1. Completion of the simple overview of statistics.
      2. Covering Gaussian Random Numbers and Numerical Generation of Random Numbers both sequentially and in parallel.
      3. We described he central limit theorem which underlies Monte Carlo method.
      4. We returned to Numerical Integration starting the discussion of Monte Carlo Integration finishing at foil 48: Stock Market Example of Multiple Monte Carlo ...
      5. Homework8 was set and the problem basically combines random number generation with the N-body problem.
    • Audio Recording: Basic Overview of Random Numbers and First Part of Monte Carlo Integration.
  • Lecture(15) foilsets -- October 24, 1996
    • Comments: Two different topics were covered. First, starting with last remarks on Monte Carlo methods from Numerical Integration which includes:
      1. Monte Carlo Integration for large scale Problems using Experimental and Theoretical high energy physics as an example.
      2. This includes accept-reject methods, uniform weighting and parallel algorithms.
      3. The lecture finally finishes with HPF discussion in foil: HPF$ INDEPENDENT, NEW Variable embarrassingly parallel DO INDEPENDENT discussed in Monte Carlo case and HPF2 Changes.
    • Audio Recording: End of Numerical Integration and Very End of HPF.
  • Lecture(16) foilsets -- October 31, 1996
    • Comments: MPI coverage was started with foilset: Message Passing Interface MPI for users upto foil with title Blocking Receive MPI_Recv(C) MPI_RECV(Fortran).
      1. Note the old reference to MPI is here.
      2. Peter Pacheco's MPI tutorial is here.
    • Audio Recording: Initial Lecture on MPI ending with discussion of basic MPI_SEND.
  • Lecture(17) foilsets -- November 7, 1996
    • Comments: Message Passing Interface MPI for users coverage continued. Also, we returned to Laplace Example -- Programming Models and Performance to discuss MPI implementation of 2D Jacobi's Equation.
    • Audio Recording: Completion of MPI foilset and Application to Jacobi Iteration in 2D.
  • Lecture(18) foilsets -- November 14, 1996
    • Comments:
      1. We described physical simulation methods and in particular CFD from foilset: Background in Partial Differential Equations with attention to CFD.
      2. We stressed the computational complexity difference between Laplace's Equations and those of CFD (Navier Stokes Equation).
    • Audio Recording: Physical Simulation Techniques and Structure of CFD.
  • Lecture(18) and (19) foilsets -- November 21 and 25, 1996
    • Comments:
      1. We went back and discussed linear algebra and particular eigenvalues and eigenvectors using foilset: Linear Algebra Presentation.
      2. We went back to (the point where we left it on November 18th lecture) Module on Iterative PDE Solvers and completed the discussion on convergence using eigenvalues of iteration matrix.
      3. A good introduction to numerical linear algebra is available at HPSC group at the University of Colorado.
      4. For an overview of three iterative methods we discussed see Brief Review of Jacobi, SOR, and Conjugate Gradients Methods also for more info and other reviews see homepage of Jim Demmel at UC Berkeley.
      5. We followed this by starting the discussion of the finite element method using the foilset: Finite Element and Conjugate Gradient Presentation. We only covered the first five foils: Integral Formulation of Finite Element Method to Triangular Elements in Two Dimensions.
    • Audio Recording: none available.
  • Lecture(20) foilsets -- November 26, 1996
    • Comments:
      1. More in depth discussion of the Finite Element method and its solution with the conjugate gradient approach using the foilset: Finite Element and Conjugate Gradient Presentation.
      2. A new reference which seems very good on the conjugate gradient is An Introduction to Conjugate Gradient Method Without the Agonizing Pain by Jonathan Shewchuk from CMU (look in section called reports in this URL).
      3. Here we set the final problem set which was a mini-project worth 25% of the overall grade.
    • Audio Recording: Finite Elements(Continued) and Conjugate Gradient.
  • Lecture(21) foilsets -- December 5, 1996
    • Comments: Covered linear programming extracted from foilset: Some Practical Optimization Methods and full matrices from foilset: Parallel Full Matrix Algorithms.
      1. It started with a survey of applications which use full matrix algorithms.
      2. As usual we did matrix multiplication in detail including our method and that due to Cannon.
      3. We described MPI implementation using nifty group communicators.
      4. A Performance analysis showed that full matrix algorithms behave like two dimensional problems.
    • Audio Recording: Linear Programming and Whirlwind Full Matrix Discussion.

Student Activities and Assignments

• Students pages
• Assignments
  • For Fall 1995
  • For Fall 1996
• Program examples
• List of previous assigned projects
  • programs
  • reports

Additional Resources

• Foilsets of all lectures (listed by title)
• Audio recordings of all lectures (listed by title)
• Books online (e.g. Parallel Computing Works)
• General reviews
• List of pages of similar topics
• More links of other resources
  • Hierarchy of Parallel and Supercomputing Sites by David Bader.
  • Nan's Parallel Computing Page.
  • SEL-HPC article archive (especially high performance computing).
  • Hensa archive in the UK.
  • Yahoo!

Programming Lab Tools

• Virtual Programming Lab (VPL)

Suggestion: MOMspider (or Multi-owner Maintenance Spider) can be used to maintain the tree structure of this page.