Lectures (no audio included) of CPS-615 Fall 1996

• 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.
• Lecture (2) foilsets -- September 5, 1996
  • Comments: 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.
• 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.
• 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
• 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.
• 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.
• 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.
• 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.
• Lecture(9) foilsets -- October 3, 1996
  • Comments: HPF discussion continued by Tom Haupt.
• Lecture(10) foilsets -- October 8, 1996
  • Comments: more HPF discussion continued by Tom Haupt.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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).
• Lecture(19) and (20) 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.
• Lecture(21) 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.
• Lecture(22) 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.