Slides for lecture 7

()

Introduction

Lecture slides taken from Dr. Rodric Rabbah (IBM)

  • From 6.189 IAP at MIT in 2007
  • Programming the Playstation 3

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

4 steps to 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

The figure below demonstrates that the same amount of work when split into more fine-grained UEs is easier to distribute evenly between resources, and provides more opportunity for pipelining. The coarse-grained side shows time disparity between PE0 and PE1, so the fine granularity balances better.

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

Finding Concurrency

There are three primary ways to decompose a program for concurrency. A single program may have opportunities for each of these.

  • Task decomposition
    • Parallelism in the application
  • Pipeline task decomposition
    • Data assembly lines
    • Producer-consumer chains
  • Data decomposition
    • Same computation is applied to small data chunks derived from large data set

The following figure exposes all three of these decomposition opportunities:

Task Decomposition

  • Start with a good understanding of the problem being solved
  • Programs naturally decompose into tasks. Common decompositions:
    • Function Calls
    • Distinct loop iterations
  • Easiest to start with many tasks and fuse them later rather than too few tasks and later trying to split them
    • Parallelize as much as possible and then recombine (fuse) later
  • Tasks should not be tied to a specific architecture
  • Tasks should have enough work to amortize the cost of creating and managing them
  • Tasks should be sufficiently independent that managing dependencies doesn’t become a bottleneck
  • Tasks have to be simple enough that code remains readable and easy to understand and debug.

Pipeline Decomposition

  • Data is flowing through a sequence of stages like an assembly line
  • Examples:
    • The instruction pipeline in modern CPUs
    • Pipes of commands in UNIX: cat foobar.c | grep bar | wc
    • Signal processing
    • Graphics

Data Decomposition

  • Data decomposition is a good starting point whe
    • Main computation is organized around manipulation of a large data structure
    • Similar operations are applied to different parts of the data structure
  • Geometric data structure examples:
    • Decomposition of arrays along rows, columns, or blocks
  • Decomposition of meshes into domains
  • Recursive data structures
    • Decomposition of trees into sub-trees
  • Guidelines:
    • Size and number of data chunks should support a wide range of executions
    • Data chunks should generate comparable amounts of work for load balancing
    • Complex data compositions can get difficult to manage and debug
  • Examples:
    • Molecular dynamics:
      • Partition problem space into blocks of molecules
      • Geometric decomposition
    • Merge sort:
      • Recursive decomposition

Dependency Analysis:

To be concurrent, two tasks have to be independent. This can be characterized by Bernstein’s Condition:

R_i: set of memory locations read (input) by task T_i

W_j: set of memory locations written (output) by task T_j

Two tasks T1 and T2 are parallel if

  1. input to T1 is not part of output from T2
  2. input to T2 is not part of output from T1
  3. outputs from T1 and T2 do not overlap

Algorithm Structure

Once the algorithm is split into independent tasks, map the tasks to units of execution. The concurrency usually implies how to organize the tasks onto UEs:

  • Organize by tasks
  • Organize by data decomposition
  • Organize by flow of data

Organize by Tasks

If tasks are recursive, organize by Divide and Conquer. Otherwise, organize by task parallelism.

  • Divide and Conquer
    • Subproblems may not be uniform (unbalanced trees)
    • May require dynamic load balancing
  • Task Parallelism
    • Tasks are associated with iterations of a loop
    • Tasks largely known at the start of the computation
    • All tasks may not need to complete to arrive at a solution. Example: searching for first occurrence of a specific value. Can stop when the value is found.

Organize by Data

Use if the primary decomposition is operations on a central data structure. Use recursive data organization for recursive (e.g. tree) data structures, and use geometric organization for arrays and linear data structures

  • Recursive Data
    • Although it often appears that the only way to solve a problem is to sequentially move through the data structure, there are often opportunities to reshape the operations to expose the concurrency.
    • Example: For each node in a forest of rooted directed trees, find the root of the tree containing the node
      • Sequential way: For each node, proceed through successors until the root is found. O(n)
      • Parallel way: for each node, find its successor’s successor. Repeat until no more changes. O(log n)
      • Work vs. Concurrency Tradeoff: The parallel approach produces more work than sequential approach ( O(n log n) vs. O(n) ), but the work can be completed in less time due to concurrency. This trade off of increased work vs. decreased execution time is common for this pattern.
      • Two models for work:
        • RAM (Random Access Memory) model: compute counts, but storage accesses don’t
        • PRAM (Parallel RAM) model: ignore communication, just count compute and synchronization

Organize by Flow of Data

The flow of data (i.e. dependencies) may impose some ordering of the tasks. If the flow is regular, one-way, and mostly stable, use a Pipeline. If flow is irregular, dynamic, or unpredictable use Event-based coordination

  • Pipeline Throughput vs. Latency
    • Amount of concurrency in a pipelie is limited by the number of stages
    • Works best if pipelne fill/drain overhead is small compared to overall running time
    • Performance usually measured by throughput
    • Pipeline latency (time from in to out) is important for real-time applications
  • Event-based coordination
    • Interactions can vary over unpredictable intervals
    • Dependencies may cause deadlocks
    • Granularity of the tasks is a major concern since dynamic scheduling has overhead and may be inefficient.