文档介绍：March 27, 2002
Math/CS 4777 Class Notes
by
R. Shonkwiler
School of Mathematics
ia Institute of Technology
Atlanta, GA 30332
e-mail: ******@
Copyright R. Shonkwiler 1997, 1998, 1999, 2000, 2001
March 27, 2002
Vector/Parallel puting
I. Introduction
A. Need for faster and putations
1. Some programming challenges
a. weather prediction
b. Computational Fluid Dynamics, ohydro Dynam-
ics
c. Monte Carlo Methods
B. Securing putation – advances in solid-state physics
1. operation of the von puter
2. cycle time, instruction rate, MIPS, MFLOPS
C. Securing putation – vectorization, SIMD
1. putation
a. caching, pipelining, etc
b. Hockney’s formulas, asymptotic performance, gain, etc
C. Securing putation – parallelization, MIMD
1. Architectures – Shared putation
a. jiffylube model, grain size and other terms
b. amdahl’s law
i. profilers
2. Architectures – Distributed putation: topology
a. ring
b. mesh
c. hypercube
d. LAN
e.
3. puting issues
II. Parallel Processing
A. Representation – Directed Acyclic Graphs
1. complexity, T∞, Tp, Speedup, Efficiency
a. fan-in
March 27, 2002
b. recursive doubling
i. pdf to cdf problem
c. russian peasant
evaluation problem
B. putation – Numerical Linear Algebra
1. loop parallelization
a. parallelizable/vectorizable loops
C. Implementation – mechanistic considerations
1. Implementation issues – synchronization
a. race conditions – barriers
b. mutexes
2. Vector
3. Fork
4. Threads
5. doacross/pragmas
III. Fundamentals of putation
A. Numerical Error
1. floating point numbers
a. roundoff
b. machine epsilon
c. calculation condition
B. Basic Matrix Algebra
1. scalar product, matrix transposition
2. Scalar Merge (fan-in), vector addition, Hadamard product
3. Matrix vector product, matrix matrix product – i, j, k forms
D. Banded matix products
1. matrix vector product
2. matrix matrix product
IV. Dir