TL;DR
This paper tackles the growing memory demands of FPGA routing algorithms, which are becoming a bottleneck for designing larger and more complex FPGAs. The authors propose novel techniques to significantly reduce both static (architectural) and dynamic (temporary routing data) memory footprints, leading to substantial memory savings without sacrificing routing solution quality.
What Problem Does This Paper Address?
As Field-Programmable Gate Arrays (FPGAs) grow in capacity, the associated Computer-Aided Design (CAD) tools, particularly the routing algorithms, struggle with escalating memory requirements. This leads to longer compile times, the need for more powerful (and expensive) workstations, and can even prevent the compilation of large designs altogether. The problem is twofold: the static memory needed to represent the FPGA's physical routing resources and programmable connections, and the dynamic memory used for temporary routing data like scoring and traceback information. Existing approaches often focus on reducing compile time but overlook memory footprint, which is becoming a critical scalability issue.
Methods
The paper introduces two main sets of techniques:
1. Reducing Static Architectural Data Memory: * Tile-Based Representation: Instead of explicitly representing every wire and switch, the FPGA is divided into "tiles." Each tile type represents a group of identical physical resources. * Graph Abstraction: A Routing Resource Graph (RRG) is used, but it's constructed based on these tiles. Connections within a tile are modeled traditionally, while connections between tiles are represented by "wrap-around" edges with "delta" values indicating the relative tile position. This significantly reduces the number of nodes and edges compared to a full RRG, and crucially, its size is no longer dependent on the FPGA array size. * Modified Routing Algorithm: The router needs to track the (x,y) tile coordinates of explored resources and use the delta information to determine which edges correspond to physical connections at runtime.
2. Reducing Dynamic Temporary Routing Data Memory: * Lifespan Analysis of TRDOs: The authors analyze the lifespan of Temporary Routing Data Objects (TRDOs), which store scoring and traceback information for each routing resource. They observe that TRDOs are not needed for unexplored resources and that their data might not need to persist throughout the entire routing process. * Memory Management Schemes: * Scheme 1 (No Deallocation): Baseline, TRDOs persist throughout. * Scheme 2 (Iteration-Based Deallocation): TRDOs are deallocated at the end of a routing iteration if the resource is unused and its parameters haven't changed. * Scheme 3 (Net-Based Deallocation): TRDOs are deallocated after each net is routed, offering aggressive memory reduction but potentially higher runtime overhead. * Design-Adaptive Memory Management: A novel approach that orders nets intelligently by dividing the FPGA into regions. Nets are routed within their assigned regions, and deallocation is performed per region, balancing memory reduction with runtime.
Datasets
The authors evaluated their techniques using:
- MCNC Benchmark Circuits: Specifically, the 20 largest circuits from this suite.
- Synthetic Benchmark Circuits: Seven circuits created by stitching together MCNC circuits, designed to be larger than typical MCNC benchmarks.
The paper does not introduce new benchmark datasets.
Key Insights and Ideas
- FPGA Regularity is Key: The core insight for static memory reduction is that the inherent regularity of FPGAs can be exploited by abstracting the architecture into tile types, decoupling memory requirements from raw FPGA size.
- Dynamic Data Lifespan Matters: The temporary routing data (TRDOs) is not static; its usage patterns and lifespan can be analyzed to implement intelligent memory allocation and deallocation strategies.
- Trade-off is Manageable: While reducing memory often incurs a runtime penalty, the paper demonstrates that this trade-off can be managed. For designs that fit within available physical memory, even a slightly increased runtime is preferable to the catastrophic performance degradation (thrashing) or outright failure caused by exceeding memory limits.
- Cache Performance Not a Major Bottleneck (in VPR): Surprisingly, the authors found that their memory management schemes did not significantly degrade cache performance in the VPR router, likely due to the existing data access patterns. This might differ in commercially optimized routers.
Key Results
- Static Memory Reduction: The proposed tile-based representation reduces the architectural data memory footprint by an order of magnitude, making it independent of FPGA size. However, this leads to an average routing time increase of 126% and an overall compile time increase of 28%.
- Dynamic Memory Reduction: The memory management schemes, particularly the design-adaptive approach, reduce the peak TRDO memory usage by 24% to 43% on average, with theoretical limits reaching 51%.
- Runtime Impact: The design-adaptive algorithm for dynamic memory management incurs a runtime penalty of approximately 10.4%. Scheme 3 (net-based deallocation) showed a significant runtime overhead (144%), while Schemes 1 and 2 had more modest increases.
- Scalability: The techniques are shown to be effective across various FPGA array sizes (N), channel widths (W), and wire segment lengths (L).
Limitations and Future Work
- Runtime Overhead: The primary limitation is the increased runtime associated with the memory-saving techniques. While this is acceptable when memory is the bottleneck, it's a trade-off that needs careful consideration.
- Cache Performance in Commercial Tools: The authors note that their findings on cache performance might not hold for commercially optimized FPGA routers, which may have different memory access patterns.
- Future Work: The paper suggests exploring more aggressive deallocation schemes (e.g., deallocating after every x nets) and investigating the impact of these techniques on commercial FPGA routing tools. They also mention that their modified VPR tool is available to the research community.
Summary updated