• Home
• Descriptor
• Announcements
• Schedule and Notes
• Assignments
• Feedback
• Sponsors

• View
• Print
• Logout ()
• Login

Lecture 8 Notes - Patterns for Parallel Programming

4 Design Spaces

• Algorithm Expression

1. Finding Concurrency
   • Expose concurrent tasks: tasks, pipelines, and data decomposition
2. Algorithm Structure
   • Map tasks to processes to exploit parallel architecture

• Software Construction

1. Supporting Structures
   • Code and data structuring patterns
2. Implementation Mechanisms
   • Low level mechanisms used to write parallel programs

Finding Concurrency

• To expose concurrent tasks: Tasks, Pipelines, and Data decomposition
• Dependency analysis is required – can two tasks run in parallel?
• Bernstein’s Condition - Two tasks T₁ and T₂ is parallel if:
  1. Input (R₁, read from memory) to T₁ is not part #of output (W₂, write to memory) from T₂
  2. Input (R₂) to T₂ is not part of output (W₁) from T₁
  3. Outputs from T₁ and T₂ do not overlap (no race condition, different memory/register)

   Ex)  Given two tasks, T1: a = x + y and T2: b = x + z,

        R1 = {x, y} and W1 = ā, R2={x, z} and W2={b},

        (1) R1 ∩ W2 = ø,  (2) R2 ∩ W1 = ø, and (3) W1 ∩ W2 = ø

        Therefore, T1 and T2 can run in parallel.

Algorithm Structure

• Given a collection of concurrent tasks, the next step is to map those tasks to units of execution (actual machine resources, e.g. threads)
• Important Considerations
  • Number of execution units
  • Cost of sharing information
  • Do not target a specific system

Major Organizing Principles - How to determine the algorithm structure

• Organize by tasks: (Recursive)? Divide and Conquer : Task Parallelism
  • Task parallelism: iterations of a loop, type of application
  • Divide and Conquer
    • Problem → (split) subproblems → compute each subproblem → (join) Solution
    • Subproblems may not be uniform → requiring dynamic load balancing for long running tasks
• Organize by data: (Recursive)? Recursive Data : Geometric Decomposition
  • Recursive Data: linked list, tree, graph

   Ex) Finding the root in a tree: 

       - Complexity: Parallel - O(nlogn) vs. Sequential - O(n)

       - Trade-off: in parallel, total work (increase), time (decrease)

• Geometric Decomposition: arrays, linear data structure

• Organize by flow of data: (Regular)? Pipeline : Event-based Coordination
  • Pipeline
    • When one-way, stable data flow
    • Trade-off: Throughput vs. Latency
    • The number of stages limits the concurrency of a pipeline
    • Although performance metric is throughput, latency is important to real-time applications
  • Event-based coordination
    • When dynamic, unpredictable data flow

Code Supporting Structures

• Loop parallelism
  • Many programs are expressed using iterative constructs
  • Very common nature (no dependency required)
• Master/Worker
  • Master(independent tasks) = work queue, client/server
  • It is difficult to determine when the entire problem is complete.
• Fork/Join
  • Parent task creates new tasks (fork) then waits until they complete (join) before continuing on.
  • Dynamic - Tasks can create more tasks. (ex) Pthread
• SPMD (Single Program Multiple Data)
  • The same program runs on each processor → distributed data
  • (c.f.) SIMD for instruction
• Map/Reduce:
  • Map phase: a single function to all data - each result is a tuple of value and tag
  • Reduce phase: the results are combined – same tag. (ex) Google
• Communication and Synchronization Patterns
  • Communication
    • Point-to-point: know who
    • Broadcast: don’t know who
    • Reduction: temp → 1 result
    • Multicast: more than one
  • Synchronization
    • Locks (mutual exclusion): two tasks
    • Monitors (events): for every
    • Barriers (wait for all)

Algorithm Structure and Organization (Instructor’s View)

Implementation Mechanisms