Topic 8. Models and levels of parallelism, grid systems; designing parallel algorithms for vectors, matrices, and numerical methods

Goal: become familiar with the levels and models of parallelism (dependency graph, PRAM, work and span, BSP), grid systems, and the PCAM design methodology; learn to distribute vectors and matrices among threads and to parallelize numerical integration, root finding, iterative methods, and the solution of ODE systems with static and dynamic load balancing; master analytical speedup prediction and comparing predictions with measurements.

Lecture contents

1. Levels and models of parallelism — Levels of parallelism · Models of parallel computation
2. Grid systems and Foster’s methodology — Grid systems · Foster’s PCAM methodology
3. Data decomposition and integration — Vector decomposition · Matrix decomposition · Parallel numerical integration
4. Numerical methods and performance prediction — Parallel solution of nonlinear equations · The conjugate gradient method · Systems of ordinary differential equations · Analytical performance prediction
5. Examples and common mistakes — Program examples · Common mistakes

Practice and review

• Practice — 3 worked examples with complete code and output
• Tasks — 30 variants, each with tasks at three difficulty levels
• Summary — conclusions, self-check questions, and useful links