Parallel Computing Task Dependency Graph

Preliminaries

• A directed path in the task dependency graph represents a sequence of tasks that must be processed in a specific order.
• The longest path in the graph determines the shortest time in which the program can be executed in parallel.
• The length of the longest path is called the critical path length.

Critical Path Length

• The critical path length determines the shortest parallel execution time.
• In the given graphs, the critical path lengths are 27 and 34.

Limits on Parallel Performance

• There is an inherent bound on how fine the granularity of a computation can be.
• Concurrent tasks may have to exchange data with other tasks, resulting in communication overhead.
• The tradeoff between granularity and associated overheads determines performance bounds.

Partitioning Techniques

• Recursive Decomposition: suited for problems solved using divide and conquer strategies.
• Data Decomposition
• Exploratory Decomposition
• Speculative Decomposition

Recursive Decomposition

• Decompose problems into sub-problems that can be solved in parallel.
• Need to think recursively, not sequentially.

Examples of Recursive Decomposition

• Quicksort: partitioning the list around the pivot, and processing sublists concurrently.
• Finding the Min/Max/Sum: using associative and commutative operations.

Parallel Algorithm Design

• Look at Ian Foster's Methodology (PCAM)
• Partition: decompose the problem and identify concurrent tasks.
• Communication: often dictated by partition.
• Agglomeration (clustering/blocking): often not much can be done here.
• Mapping: a difficult problem, involving load balancing.

Task Dependency Graph

• Illustrated as a directed graph or adjacency matrix.
• Nodes represent tasks, and edges denote dependencies between tasks.

Degree of Concurrency

• The number of tasks that can be executed in parallel.
• Maximum Degree of Concurrency: the maximum number of tasks at any point during execution.
• Average Degree of Concurrency: the average number of tasks processed in parallel over the execution of the program.
• The degree of concurrency increases as the decomposition becomes finer in granularity.