TL;DR
This paper introduces FlexC, a novel compiler that enables domain-specific CGRAs (Coarse-Grained Reconfigurable Arrays) to execute software outside their intended domains. By employing equality saturation for intelligent code rewriting, FlexC significantly expands the range of applications that can be accelerated on specialized hardware, achieving substantial speedups.
What Problem Does This Paper Address?
Specialized hardware accelerators, like CGRAs, promise significant performance and energy efficiency gains over general-purpose CPUs. However, their effectiveness is often limited by a "domain-restriction problem": they are designed for specific types of computations, and if a program uses even a single unsupported operation, the entire program cannot be accelerated. This inflexibility makes it difficult to adapt these accelerators to evolving software landscapes, leading to underutilization and high hardware costs. Existing compilers struggle to overcome this by rewriting code to fit the CGRA's capabilities, often getting stuck in local optima or failing to find valid transformations.
Methods
FlexC tackles the domain-restriction problem through a sophisticated dataflow rewriting approach. At its core is equality saturation, a technique that explores a vast space of equivalent program transformations to find one that is compatible with the target CGRA. Unlike traditional greedy rewriting, which applies rules sequentially and can get stuck, equality saturation builds an "e-graph" that compactly represents all possible program variations.
FlexC's process involves:
- Input: A Data-Flow Graph (DFG) representing a loop, a set of rewrite rules, and a CGRA specification.
- Hybrid Rewriting: FlexC first attempts a fast greedy rewrite. If this fails to find a suitable solution, it falls back to the more exhaustive equality saturation.
- Equality Saturation: This phase iteratively applies rewrite rules to the e-graph, exploring many equivalent program forms. The process continues until saturation (no more rules can be applied) or a timeout.
- Cost Model: A crucial component is the cost function, which penalizes unsupported operations heavily, guiding the search towards compilable programs.
- Output: The best-suited DFG is then passed to a traditional CGRA compiler (OpenCGRA) for configuration generation.
FlexC supports custom rewrite rules, allowing it to be adapted to various CGRA architectures and their specific instruction sets.
Datasets
The paper utilizes a benchmark suite of 2188 real-world loop kernels extracted from open-source projects in multimedia, compression, and simulation domains. These loops are selected to be the innermost loops, free of internal branches or function calls, and containing at least one array access, making them suitable for CGRA scheduling. The benchmark suite is notable for its size and diversity, aiming to capture a wider range of programming patterns than typical academic benchmarks.
Key Insights and Ideas
- Equality saturation is key to unlocking CGRA potential: The paper strongly demonstrates that traditional greedy rewriting is insufficient for complex CGRA compilation. Equality saturation's ability to explore a vast search space is crucial for finding valid transformations, especially for highly specialized CGRAs.
- Domain-specific rules are powerful, but generality matters: While custom rules tailored to specific CGRAs (like floating-point or stochastic computing rules) significantly boost compilation rates, FlexC's core integer ruleset provides a strong baseline that works across diverse architectures.
- Specialization can be a double-edged sword: More specialized CGRAs benefit more dramatically from FlexC's rewriting capabilities, as they are more likely to have unsupported operations. However, this also means they are inherently less flexible without such a compiler.
- Rewriting can enable speedups even if it makes code "more complex": The paper shows that by enabling code to run on specialized hardware, even if the rewritten code appears more complex (e.g., using shifts instead of multiplications), significant speedups can be achieved.
Key Results
- FlexC increases the number of loop kernels that can be compiled to heterogeneous CGRAs by 2.2x compared to existing approaches.
- This increased compilation rate leads to an average 3x speedup compared to a low-power ARM A5 CPU on kernels that would otherwise be unsupported.
- For highly specialized CGRAs like SC-CGRA, FlexC can increase the number of supported loops by up to 5.2x.
- FlexC demonstrates applicability across a wide range of CGRA specializations, from very specialized to more generic architectures.
- The hybrid rewriting strategy (greedy + equality saturation) effectively balances compilation speed and success rate.
Limitations and Future Work
- Compile time: While FlexC's compile times are considered reasonable, equality saturation can still lead to long exploration times for very complex programs. The paper uses iteration and node limits to manage this, but further optimizations for scaling are always beneficial.
- CGRA compiler backend: FlexC relies on OpenCGRA as its backend for generating CGRA configurations. Its applicability to other CGRA compiler backends is mentioned but not extensively demonstrated.
- Future work: The authors suggest exploring more sophisticated rewrite rule generation, further optimizing equality saturation for even larger search spaces, and applying FlexC to a broader range of hardware accelerators beyond CGRAs. The potential for using machine learning to guide rewrite rule selection or e-graph exploration is also an open avenue.
Summary updated