Introduction to Parallel Computing

Introduction

• Introduction to the topic of parallel computing

Books

• HPC: "Software Optimization for High Performance Computing: Creating Faster Applications" by K.R. Wadleigh and I.L. Crawford, Hewlett-Packard professional books, Prentice Hall.
• OPT: "The Software Optimization Cookbook" (2nd ed.) by R. Gerber, A. Bik, K. Smith, and X. Tian, Intel Press.
• PP2: "Parallel Programming: Techniques and Applications using Networked Workstations and Parallel Computers" (2nd ed.) by B. Wilkinson and M. Allen, Prentice Hall.
• PSC: "Parallel Scientific Computing in C++ and MPI" by G. Karniadakis and R. Kirby II, Cambridge University Press.
• SPC: "Scientific Parallel Computing" by L.R. Scott, T. Clark, and B. Bagheri, Princeton University Press.
• SRC: "Sourcebook of Parallel Programming" by J. Dongara, I. Foster, G. Fox, W. Gropp, K. Kennedy, L. Torczon, and A. White (eds), Morgan Kaufmann.

Introduction

• Why parallel computing?
• Why not parallel computing?
• Benefit depends on speedup, efficiency, and scalability of parallel algorithms
• What are the limitations to parallel speedup?
• The future of computing
• Lessons learned
• Further reading

Why Parallel?

• It's not always obvious that a parallel algorithm has benefits, must consider wanting to do things faster (same work in less time), or bigger (more work in same time).
• Both these reasons can produce better results, which is the meaningful outcome of parallelization.

Faster, Bigger!

• Increased demand for computational power to improve speed or accuracy of solutions to real-world problems (faster computations and/or bigger simulations)
• Computations must be completed in acceptable time (real-time computation)

Faster, Bigger!

• Illustrative example: weather prediction simulation should not take longer than the event itself.
• Atmosphere of Earth divided into 5 x 10⁸ cubes, each 1 x 1 x 1 mile, stacked 10 miles high.
• 200 floating-point operations per cube to complete one time step.
• 10⁴ time steps for a 7-day forecast.
• 10¹⁵ floating-point operations needed.
• This takes 10⁶ seconds (10 days) on a 1 GFLOP machine

Grand Challenge Problems

• "Grand Challenge" problems cannot be solved in reasonable time with today's computers.
• Examples:
  • Applied Fluid Dynamics
  • Meso- to Macro-Scale Environmental Modeling
  • Ecosystem Simulations
  • Biomedical Imaging and Biomechanics
  • Molecular Biology
  • Molecular Design and Process Optimization
  • Fundamental Computational Sciences
  • Nuclear power and weapons simulations

Physical Limits

• Which tasks are too big for one CPU?
• Calculation example: for (i =0; i < ONE TRILLION; i++){ z[i] = x[i] + y[i]; }
• 3 x 10¹² memory moves per second required.
• Data travels at speed of light (3 x 10⁸ m/s)
• Distance between CPU and memory (r) must satisfy 3 x 10¹² r = 3 x 10⁸ × 1 giving r = 10^-4 meters.
• Memory cell size: 2 x 10^-4 m / (√3 x 10⁶) = 10^-10 m

CPU Energy Consumption & Heat Dissipation

• Increased power requirements of newer chips will lead to CPUs hotter than the surface of the sun by 2010 (Intel CTO)
• Parallelism can help to conserve energy.

Important Factors

• Physical limitations: speed of light, CPU heat dissipation
• Economic factors: cheaper components to achieve comparable levels of aggregate performance
• Scalability: subdividing data over CPUs to match algorithms and resources for increased performance
• Memory: increase aggregate memory bandwidth with processing power at a reasonable cost

And Why Not Parallel?

• Bad parallel programs can be worse than sequential counterparts.
• Slower: due to communication overhead.
• Scalability: some parallel algorithms are only faster when problem size is large.
• Need to understand the problem and use common sense.
• Not all problems are amenable to parallelism.
• Course will focus on non-parallel optimizations for sequential programs to get better performance

And Why Not Parallel?

• Some algorithms are inherently sequential (Collatz conjecture example).

Speedup

• Definition: speedup of an algorithm using P processors (S_p = t_s / t_p).
• t_s = execution time of best sequential algorithm.
• t_p = execution time of the parallel algorithm.
• Perfect or ideal speedup if S_p = P.
• Linear speedup if S_p ≈ P.
• Superlinear speedup if S_p >P for some P.

Relative Speedup

• Definition: The relative speedup (S¹_p = t₁/t_p).
• t₁ = execution time of the parallel algorithm on one processor.
• Similarly, S^k_p = t_k/t_p .
• k < P.
• Used when k is the smallest number of processors on which the problem runs efficiently

An Example

• Parallel search by partitioning the search space into P chunks.
• Worst case for sequential search (item in last chunk): S_p → ∞ as ∆t tends to zero.
• Best case for sequential search (item in first chunk) : S_p = 1.

Effects that can Cause Superlinear Speedup

• Cache effects: Data is partitioned, distributed over P processors, individual data items (much) smaller, may fit in processor's data cache.
• Algorithm with linear speedup: extra reduction in cache misses may lead to superlinear speedup.

Efficiency

• Definition: Efficiency of an algorithm using P processors (E_p = S_p / P).
• Efficiency estimates how well-utilized the processors are, compared to effort lost in idling and communication/synchronization.
• Ideal (or perfect) speedup means 100% efficiency (E_p = 1).

Scalability

• Speedup describes how parallel algorithm's performance changes with increasing P.
• Scalability concerns efficiency of the algorithm with changing problem size (N) by choosing P dependent on N.
• Definition: algorithm is scalable if there is minimal efficiency ε > 0 such that for any problem size N, there's a processor # (P(N)) that tends to infinity as N tends to infinity; where efficiency E_P(N) ≥ ε > 0

Amdahl's Law

• Several factors limit speedup:
  • Processors may be idle.
  • Extra computations in parallel version.
  • Overhead in communication and synchronization.
• Consider fraction (f) of sequential computation that cannot be divided into concurrent tasks.

Amdahl's Law

• Amdahl's law states that speedup given P processors is S_p = t_s / (f * t_s + (1-f)*t_s/P) = P / (1+(P-1)f)
• Maximum speedup is limited by f^-1 as P → ∞

Gustafson's Law

• Amdahl's law based on fixed workload/problem size per processor.
• Gustafson's law defines scaled speedup by keeping parallel execution time constant.
• S_P,N = P + (1 - P)α(N)

Limitations to Speedup: Data Dependences

• Collatz iteration loop has a loop-carried dependence (n's value carried over to next iteration).
• Loops with loop-carried dependences cannot be parallelized.

Limitations to Speedup: Data Dependences

• Example: Gauss-Seidel and Jacobi iteration loops.
• Jacobi iteration doesn't exhibit loop-carried dependences, allowing partitioning and distribution to processors.

-Three simple example loops to initialize a finite difference matrix.

• Which loop(s) can be parallelized?
• Which loop likely runs more efficiently on a sequential machine?

Limitations to Speedup: Data Dependences

• Presence of dependences between events in two or more tasks limits parallelization strategies for conserving energy.

Efficient Parallel Execution

• Trying to construct parallel version of an algorithm is not the "end-all" for high performance computing.
• Amdahl's law: maximum speedup is bounded by f^-1 as P → ∞.
• Efficient parallel execution is important to optimize non-parallel fraction (f) and parallel tasks.
• Improving sequential execution, I/O, communication and synchronization reduces the sequential fraction.

Limitations to Speedup: Memory Locality

• Memory hierarchy forms barrier to performance when locality is poor.
• Temporal locality: same memory location repeatedly accessed.
• Spatial locality: consecutive memory locations accessed (or "sufficiently near").
• Memory wall: growing disparity of speed between CPU and external memory.

Efficient Sequential Execution

• Memory effects are primary concern for optimal sequential execution.
• Store-load dependences: data flow through memory
• Cache misses, TLB misses, page faults.
• CPU resource effects: limited floating point units, unpredictable branching.
• Compiler optimizations helpful for efficient sequential execution.

Lessons Learned from the Past

• Parallel computing can transform science and engineering by solving societal challenges.
• Redesigning an application, rather than just porting, may be necessary.
• Hardware underutilization can stem from poor software and algorithms.
• Portability of software is an issue.
• Parallelism isn't everything, good commercial software is rare.

Any questions?

• Open question for clarifying any remaining points.

This quiz introduces the fundamental concepts of parallel computing, discussing its significance and potential benefits. You will explore why parallel computing is essential and the challenges associated with it, as well as the insights provided by various key texts in the field.