TL;DR
This paper tackles the challenge of maximizing iteration-level parallelism in loops, a crucial step for efficiently utilizing modern multi-core processors. The authors introduce an optimal two-phase approach that models loop transformations as graph retiming to strategically migrate data dependencies, thereby enabling more iterations to run concurrently.
What Problem Does This Paper Address?
Modern processors are increasingly equipped with multiple cores, but fully exploiting this parallel hardware requires software that can effectively parallelize computations. While thread-level parallelism is often handled by programmers or high-level tools, achieving parallelism at the finer granularity of loop iterations (iteration-level parallelism) is significantly more complex. Loops often contain data dependencies between iterations, which inherently limit how many iterations can execute simultaneously. These dependencies can be categorized as "serial loops" (DOSER), "parallel loops" (DOALL), or "partially parallel loops" (DOACR). This paper focuses on optimizing DOSER and DOACR loops, specifically addressing the bottleneck caused by "dependence cycles" – a set of statements strongly connected by dependencies. Existing methods for parallelizing such loops are often approximate. This work aims to provide an optimal solution for maximizing the number of concurrently executable iterations.
Methods
The core of the paper's approach lies in reframing loop parallelization as a graph optimization problem.
- Dependence Graph Modeling: Loops are first represented as dependence graphs (G = (V, E, w)), where nodes represent statements and edges represent data dependencies with associated "dependence distances" (weights). Intra-iteration dependencies have a weight of 0, while inter-iteration dependencies have positive weights.
- Retiming for Dependence Migration: The key innovation is using "retiming," a technique borrowed from circuit design, to model the migration of dependencies. Retiming assigns an integer value to each node, effectively shifting dependence weights from incoming edges to outgoing edges. A legal retiming ensures that all resulting edge weights remain non-negative, preserving program correctness. The goal is to find a retiming function that maximizes the minimum non-zero edge weight in the transformed graph. This minimum weight directly corresponds to the number of independent iterations that can run in parallel.
- Two-Phase Optimal Approach:
- Phase 1: Dependence Migration Algorithm (DMA): This phase finds the optimal retiming function. The algorithm classifies dependence graphs into three types: Directed Acyclic Graphs (DAGs), Cyclic Graphs with Single Cycle (CGSC), and Cyclic Graphs with Multiple Cycles (CGMC). For DAGs and CGSCs, polynomial-time algorithms (DAG_Migration and Single_Cycle_Migration) are proposed. For CGMCs, an Integer Linear Programming (ILP) formulation is used to find the optimal retiming.
- Phase 2: Loop Transformation Algorithm: Once the optimal retiming function is found, this phase generates the transformed loop code. This involves creating a new loop kernel, a prologue (for initial iterations that depend on earlier, non-existent iterations), and an epilogue (for final iterations).
Datasets
The paper evaluates its technique using a set of six benchmark loop kernels commonly found in prior work on loop parallelization, including SHRINKING, BREAKING, LPDOSER, REORDER, BMLA, and EDDR. These benchmarks are described as having single or multiple cycles in their dependence graphs. No new benchmarks were introduced.
Key Insights and Ideas
- Retiming as a Universal Transformation Tool: The paper elegantly demonstrates how retiming, a concept from hardware design, can be directly applied to software loop transformations to manipulate data dependencies. This provides a powerful and unified framework.
- Maximizing Minimum Non-Zero Edge Weight: The core insight is that the maximum achievable parallelism is directly dictated by the minimum non-zero edge weight in the dependence graph. By maximizing this value through retiming, we achieve optimal iteration-level parallelism.
- Optimal Solution for DOACR Loops: The paper claims to provide the first optimal solution for maximizing iteration-level parallelism in DOACR loops, which are notoriously difficult to parallelize.
- Case Analysis for Efficiency: Classifying dependence graphs into DAGs, CGSCs, and CGMCs allows for tailored and efficient algorithms, with polynomial-time solutions for simpler cases and an ILP approach for the more complex multi-cycle scenarios.
Key Results
The paper demonstrates that its optimal approach significantly enhances loop parallelism compared to existing cycle-shrinking and partitioning techniques. For instance, in the "BREAKING" benchmark, existing methods achieve a parallelism of 1, while the proposed technique achieves 6. The evaluation shows that for all tested benchmarks, the proposed method achieves higher or equal parallelism compared to prior work, with substantial improvements in several cases. The transformed dependence graphs are shown to have maximized minimum non-zero edge weights, directly reflecting the increased parallelism.
Limitations and Future Work
- Focus on Single Loops: The current work focuses on parallelizing individual loops. The authors suggest future work on combining their technique with loop vectorization and extending it to handle nested loops for greater parallelism.
- ILP Solver Performance: While the ILP approach for CGMCs is optimal, its practical performance depends on the efficiency of the ILP solver for the specific problem instances encountered in real code. The paper mentions that the ILP formulation is "solved efficiently for the dependence graphs found in real code," but this is a potential area for further investigation.
Summary updated