Routing Algorithms for FPGAs With Sparse Intra-Cluster Routing Crossbars

Modern FPGAs employ sparse crossbars in their intra-cluster routing. Modeling these crossbars enlarges the Routing Resource Graph (RRG), a data structure used by most FPGA routers, while enlarging the search space for finding legal routes. The authors introduce two scalable routing heuristics for FPGAs with sparse intra-cluster routing crossbars: SElective RRG Expansion (SERRGE), which compresses the RRG, and dynamically decompresses it during routing, and Partial Pre-Routing (PPR), which locally routes all nets in each cluster, and routes global nets afterwards.