Parallel Programming from Scratch

  • Start with an algorithm
    • An algorithm is a sequence of steps to solve a problem
    • The sequence is not usually described in a parallel way
  • Make sure there is parallelism
    • Minimize the synchronization points
  • Don’t forget about locality or Communication Cost

Creating a parallel program

There are 4 basic steps to creating a parallel program:

  1. Decomposition into tasks
  2. Assignment of tasks to Units of Execution (UE = processes or threads)
  3. Orchestration of UE’s Communication and Synchronization. At this point you have a parallel program
  4. Mapping of parallel program onto processors or hardware

Re-engineering for parallelism

More often than not, a parallel program is usually re-engineered from an existing sequential program. The primary reasons for this are that sequential code is easier to write and debug and usually the least-complicated embodiment of an algorithm. Main considerations:

  • Is the program numerically well-behaved?
    • Some algorithms will produce different results if steps are performed in different order.
    • Example: Floating point rounding errors
  • Get user acceptance
    • Set reasonable performance expectations
    • Determine the user’s required precision or repeatability requirements (see numerical stability issues above).
  • Define a testing protocol
  • Identify program hot spots and start with them first
    • Target the areas that will give the most bang-for-the-buck
    • Test each small change against reference model to ease debugging later

Decomposition

The main tasks of decomposition are:

  • Identify concurrency and decide at what level to exploit it
  • Breakup the computation into tasks to be divided among processes. These tasks may become available dynamically and the number may change over time.
  • Make sure there are enough tasks to keep processors busy. i.e. check to see if there is enough parallelism.

Amdahl’s Law:

Amdahl’s Law is commonly used to express the potential program speedup due to parallelization:

The performance improvement to be gained from using some faster mode of execution is limited by the fraction of the time the faster mode can be used.

Restated: Potential program speedup is defined by the fraction of code that can be parallelized.

If p = fraction of work that can be parallelized

and n = the number of processors

{$ \begin{align} speedup &= \frac {old\_running\_time} {new\_running\_time} &= \frac {1} {(1-p)+\frac {p} {n}} \end{align} $}

For maximum efficency, only parallelize things that are worthwhile.

Assignment

  • Use a structured approach using well known patterns
  • As programmers, worry about partitioning first
    • Try to be architecture independent
  • Main considerations:
    • Granularity
    • Locality

Fine vs. Coarse Granularity

There is a tradeoff between fine- and coarse-grained concurrency.

  • Fine-grained
    • Low compute / communication ratio
    • Small amounts of computational work between communication stages
    • High communication overhead
      • Communication overhead could be alleviated by hardware assistance
  • Coarse-grained
    • High computation to communication ratio
    • Large amounts of computational work between communication
    • Harder to load-balance efficiently

Orchestration and mapping

  • Computation and communication concurrency
  • Preserve locality of data
  • Schedule tasks to satisfy dependencies early
  • Survey available mechanisms on target system

Using patterns

Patterns act as a cookbook: capturing previous experence and providing a common vocabulary. Using patterns also aids software modularity and reuse.

History:

  • Patterns originally developed by Christopher Alexander in 1977 for city planning, landscaping, and architecture
  • Gang of Four (Gamma, Helm, Johnson, Vlissides) wrote Design Patterns: Elements of Reuseable Object-Oriented Software in 1995
    • Subdivide patterns into creational, structural, and behavioral

Patterns for Parallelizing Programs

  • Patterns for Parallel Programming by Mattson, Sanders, Massingill in 2005
  • Four design spaces:
    • Algorithm Expression
      • Finding Concurrency
      • Algorithm Structure
    • Software Construction
      • Supporting Structures
      • Implementation Mechanisms