Scientific computational algorithms on vector and parallel computers. Speedup, algorithm complexity, interprocesses communication, synchronization, modern algorithms for linear systems, programming techniques, code optimization.
- Need for Faster and Faster Computations Weather prediction Computational fluid dynamics Monte Carlo methods Other
- Vector, Parallel Computation Increase cycle time -- advances in solid-state physics Operation of a von Neumann computer Cycle time =1/instruction rate, MPS, FLOPS, MFLOPS Remote computer usage notes Parallelize the computations SIMD, MIMD Amdahl's law a. Profilers Vector computers -- single CPU, pipelining (SIMD) a. Operation calculations -- asymptotic rate, Hockney's Law, equiv. CPU's b. Cray programming notes (1) Recognizing and treating loop dependencies Parallel computers -- memory classification a. Shared memory -- bus, switch (1) Lock and barrier solutions to contention and race conditions (2) Shared memory programming notes (a) Recognizing and treating data dependencies b. Distributed memory -- topology (1) Linear array, ring (2) Mesh (3) Hypercube -- nodes, connectivity, diameter (4) Massively parallel -- SIMD (5) CM Programming Notes (6) LAN Parallel operation equations a. Speedup, efficiency, communication delay
- Basic Linear Computational Tasks Task description Scalar merge -- e.g., sum a vector-fan-in Vector addition, scalar multiplication Matrix vector product -- i,j forms Matrix matrix product Matrix transposition Banded matrix products Partial sums, partial products -- recursive doubling a. pdf to cdf problem b. Polynomial evaluation problem