Patterns for Parallelizing Programs

4 Design Spaces

  • Algorithm Expression
    • Finding Concurrency
      • Expose concurrent tasks
    • Algorithm Structure
      • Map tasks to processes to exploit parallel architecture
  • Software Construction
    • Supporting Structures
      • Code and data structuring patterns
    • Implementation Mechanisms
      • Low level mechanisms used to write parallel programs

Recap

Decomposition

  • Keep things general and simple
    • Consider rough machine properties only (10, 1000, 1M, …)
  • Task
    • Decide what tasks are
      • How many tasks depends on how much parallelism you want
      • Communication and synchronization overheads larger with smaller tasks
      • More overhead with respect to keeping track of tasks as the number of tasks increases
    • Natural in some programs
    • Need to balance overheads of fine-grained with degree of parallelism
  • Data
    • Often looks similar to tasks, differs in how you begin to look for parallelism
    • Things often simpler/low overhead/more direct when thinking of data → things are usually well-defined
    • Sometime you just can’t think about data → need to think about tasks instead
    • Natural in some programs, less general than task
    • Consider data structure
  • Pipeline
    • Common, overlapping communication and computation very useful
    • An algorithm:
      • Sequence of steps:
        • Lok for parallelism within a step
        • Or, steps aren’t really dependent
    • Stages ~ O(1); In the real world, reducing by a constant (e.g., factor of 5) can actually help
    • Reduce the degree of other parallelism needed

Dependencies

  • Equivalent to RAW/WAW/WAR

Algorithm Structure

Design Space

  • Are there opportunities for load balancing?
  • Using multiple design patterns is possible in a hierarchical fashion
  • Given a collection of concurrent tasks, what’s the next step?
  • Map tasks to units of execution (e.g., threads)
  • Important Considerations
    • Magnitude of number of execution units platform will support
    • Cost of sharing information among execution units
    • Avoid tendency to over contrain the implementation
      • Don’t think of specific architecture details yet (e.g., using a 4-core machine)
      • Work well on the intended platform
      • Flexible enough to easily adapt to different architectures

Major Organizing Principle

  • How to determine the algorithm structure that represents the mapping of tasks to units of execution?
  • Concurrency usually implies major organizing principle
    • Organize by tasks
    • Organize by data decomposition
    • Organize by flow of data
  • For example, take pipeline, and try to find tasks within the pipeline
    • Or, take tasks, find pipelines within the tasks

Organize by Tasks?

  • Is it recursive?
    • Yes: Divide and Conquer
    • No: Task Parallelism
  • If tasks don’t have a natural decomposition via recursion, then tasks may have significant dependencies which can lead to large communication/synchronization overheads if the divide an conquer approach is used.

Task Parallelism

  • Molecular Dynamics
    • Non-bonded force calculations, some dependencies
  • Common Factors
    • 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

Divide and Conquer

  • For recursive programs: divide and conquer
    • Subproblems may not be uniform
    • May require dynamic load balancing
    • Usually in a parallel program, the program is done when the last task is done.
    • If in Divide and Conquer, If we find that not all tasks are equivalent, then we have a load balance problem → while some resources are sitting idle waiting → wasted resources
    • For example, while threads are waiting for a barrier, we waste those resources by sitting idle waiting until the final thread reaches the barrier
    • Consider dynamic load balancing → split a particularly busy task so a particularly free resource can steal work from the particularly busy unit (there is overhead though; likely also need to get the working set to steal work)

Organize by Data?

  • Operations on a central data structure
    • Arrays and linear data structures
    • Recursive data structures
    • Recursive?
      • Yes: Recursive Data
      • No: Geometric Decomposition
  • What if data has no dependencies between units? Either decomposition is fine: treat it as geometric, for example.
  • What if there is dependency between data? Then it is a geometric or recursive decomposition
  • Graph Partition: best way is a recursive approach despite the data not being organized in a recursive fashion. This approach generally ends up being close to optimal, anyway.

Recursive Data

  • Computation on a list, tree, or graph
    • Often appears the only way to solve a problem is to sequentialy move through the data structure
  • There are however opportunities to reshape the operations in a way that exposes concurrency

Recursive Data Example: Find the Root

  • Given a forest of rooted directed trees, for each node, find the root of the tree containing the node
  • Sequential Algorithm
    • Step 1: Find all nodes, am I the root?
    • Step 2: List of Roots → Breadth first traversal at each root assigning each node its root
  • Parallel
    • First Approach
      • For each node, parent pointer traversal until get to root. Assume n nodes, n processors, d depth. The algorithm is O(n * d)/n
    • Second Approach
      • Geometric Decomposition
      • Find the parent’s parent (grand parent)
      • Find grandparent’s grandparent (great great grand parent)
      • Etc. until everyone knows root
      • O(n * log d)/n
      • But, there’s more synchronization overhead, despite being algorithmically faster
    • Another Approach
      • For all nodes: In parallel, am I root?
      • For all roots → Breadth first approach originating at root; splitting to multiple children at each step can spawn more parallel work to do

Work vs. Concurrency Tradeoff

  • Parallel restructuring of find the root algorithm leads to O(n log n) work vs. O(n) with sequential approach
  • Most strategies based on this pattern similarly trade off increase in total work for decrease in execution time due to concurrency (parallel often has more work, but is faster)

Organize by flow of Data?

  • In some application domains, the flow of data imposes ordering on the tasks
    • Regular, one-way, mostly stable data flow
    • Irregular, dynamic, or unpredicatable data flow
  • Regular?
    • Yes: Pipeline
    • No: Event-Based Coordination

Pipeline Throughput vs. Latency

  • Amount of concurrency in a pipeline is limited by the number of stages
  • Works best if the time to fill and drain the pipeline is small compared to overall running time
  • Performance metric is usually the throughput
    • Rate at which data appear at the end of the pipeline per time unit (e.g., frames per second)
    • Relates to load balance
      • Assign processing elements to each stage in relation to how long each stage takes. Ideally, we wish each stage to take equivalent time for best load balance.
  • Pipeline latency is important for real-time applications
    • Time interval from data input to pipeline, to data output

Event-Based Coordination

  • In this pattern, interaction of tasks to process data can vary over unpredicatable intervals
  • Problem with event-based coordination: since it’s more complex, it is easier to end up in a deadlock situation
    • Dynamic scheduling has overhead and may be inefficient
      • Granularity a major concern
  • Event based coordination can be forced into a pipeline model (each task does every stage, but nops in unnecessary stages) → innefficient/not a good idea
  • Another option is various “static” dataflow models
    • E.g., synchronous dataflow

Code Supporting Structures

  • Loop Parallelism
  • Master/Worker
  • Fork/Join
  • SPMD
  • Map/Reduce

Loop Parallelism Pattern

  • Many programs are expressed using iterative constructs
    • Programming models like OpenMP provide directives to automatically assign loop iteration to execution units
    • Expecially good when code cannot be massively restructured
  • E.g., #pragma omp parallel for
    • Each loop iteration is essentially independent work

Master/Worker Pattern

  • General Idea:
    • One master is aware of all independent tasks
    • Master creates workers and assigns independent tasks to workers
    • Workers notify master when the task is complete
  • Particularly relevant for problems using task parallelism pattern where tasks have no dependencies
    • Embarrassingly parallel (EP) problems
  • Main challenge in determining when the entire problem is complete
    • Not all tasks may take the same amount of time; task length may not be known beforehand

Fork/Join Pattern

  • Tasks are created dynamically
    • Tasks can create more tasks
  • Manages tasks according to their relationship
  • Parent task creates new tasks (fork) then waits until they complete (join) before continuing on with the computation
  • Good for recursive problems
  • In a way, a loop is a massive fork/join
    • Key difference → in loop parallelism pattern, you often know statically the number of loop iterations. In fork/join, the number of forks can be dynamically determined

SPMD

  • Kind of like SIMD, but much higher granularity
  • MPI, Beowulf cluster are SPMD pattern
  • Single Program Multiple Data: create a single source-code image that run son each processor
    • Initialize
    • Obtain a unique identifier
    • Run the same program on each processor
      • Identifier and input data differentiate behavior
    • Distribute data
    • Finalize
  • Challenges
    • Split data correctly
    • Correctly combine the results
    • Achieve an even distribution of the work
    • For programs that need dynamic load balancing, an alternative pattern is more suitable