Understanding Maximal Parallelism in a Directed Acyclic Graph (DAG)

Introduction

Maximal parallelism refers to the highest degree of concurrent execution achievable within a computational model, particularly a Directed Acyclic Graph (DAG). In such graphs, nodes represent computations or tasks, and directed edges signify dependencies. Calculating maximal parallelism in a DAG is crucial for optimizing resource allocation and minimizing the overall execution time in parallel computing environments.

Structure of a DAG

A DAG is a graph with directed edges and no cycles, which ensures a clear hierarchy from source nodes (with no incoming edges) to sink nodes (with no outgoing edges). The lack of cycles prevents any circular task dependencies, allowing for an efficient topological sorting.

Calculating Maximal Parallelism

Maximal parallelism in a DAG can be evaluated by examining its layers or levels, each representing a set of tasks that can be executed concurrently at a given point in time. Here's a step-by-step procedure:

1. Topological Sorting:
   • Perform a topological sort on the DAG to get an ordered sequence of tasks where each task only appears after all its prerequisites.
2. Level Assignment:
   • Assign a level number to each node using dynamic programming:
   • Traverse through nodes from the topological sort.
   • For a given node v, set its level L(v) as 1 + max({L(u) | u is a predecessor of v}).
3. Determine Maximal Parallelism:
   • The maximal parallelism is given by the maximum number of nodes that reside on the same level.
   • More formally, if nodes are partitioned into levels L_1, L_2, ..., L_k, where L_i represents the set of nodes at level i, then the maximal parallelism is max(|L_1|, |L_2|, ..., |L_k|).

Example

Consider the DAG:

1    A
2   / \
3  B   C
4   \ /
5    D
6   / \
7  E   F

• Topological Order: A, B, C, D, E, F
• Level Assignment:
  • L(A) = 1
  • L(B) = 2, L(C) = 2
  • L(D) = 3
  • L(E) = 4, L(F) = 4
• Parallel Tasks by Levels:
  • Level 1: {A}
  • Level 2: {B, C}
  • Level 3: {D}
  • Level 4: {E, F}

From the above, the maximal parallelism is max(1, 2, 1, 2) = 2.

Technical Considerations

• Complexity: The complexity of determining maximal parallelism is primarily driven by the topological sort (O(V + E), where V is the number of vertices and E is the number of edges), and traversing the graph to assign levels.
• Hardware Constraints: Although the theoretical maximal parallelism might be high, practical limitations such as the number of available processors or other resources can further constrain achievable parallelism.
• Balancing Loads: Attention should be paid to load balancing. Tasks across levels should be managed to avoid some processors being idle while others are overloaded.

Table: Summary of Key Concepts

Conclusion

Calculating maximal parallelism in a DAG is a fundamental step towards optimizing parallel execution in computational tasks. By understanding the dependencies and arranging tasks at various levels, one can effectively distribute workloads across available resources, paving the way for efficient parallel processing. This analysis helps in anticipating computational bottlenecks and guiding the architecture of parallel systems.