ComputingComputer EngineeringComputer ScienceAlgorithmsReconfigurable ComputingSchedulingCongestion ControlCritical Path AnalysisRoutingRouting AlgorithmsRouting ArchitectureCongestion AvoidanceCongestion DetectionCongestion-aware RoutingCongestion-driven RoutingFpga Routing AlgorithmsRouting CongestionRouting Congestion ReductionRouting Optimization
PathFinder, a popular routing algorithm widely used in the state-of-the-art FPGA compilation tools such as VTR 8, has been reported to have a non-negligible variation in the routing quality under routing resource constraints. Several workaround methods have been proposed to mitigate this undesired effect while keeping the algorithm unchanged. In this paper, we take a fresh look at the PathFinder algorithm itself and identify that its inappropriate definition of routing congestion problems causes an issue in its congestion coefficient updating strategy and eventually leads to the variation in the routing quality under different routing orders. This problem is aggravated in VTR~8 and inevitably degrades the routing quality as the predefined routing order is not optimal in most cases. Based on these findings, we propose an enhanced PathFinder algorithm with redefined routing congestion problems to address the issue in the congestion coefficient updating strategy and algorithmically resolve the routing quality variation issue. This enhanced algorithm can be easily integrated into VTR~8 to benefit every researcher in our community. Evaluation results show that it reduces the longest critical path delay and the variation by up to 49.4% and 96.2% under routing resource constraints, respectively. The variation can be fully eliminated when sufficient routing iterations are performed.
6
Kevin E. Murray, Oleg Petelin, Sheng Zhong et al. · ACM Transactions on Reconfigurable Technology and Systems · 2020 · 293 citations
Using sparse crossbars within LUT
Guy Lemieux, David Lewis · 2001 · 72 citations
Timing-driven pathfinder pathology and remediation
Raphael Rubin, André DeHon · 2011 · 49 citations
Nachiket Kapre, Harnhua Ng, Kirvy Teo et al. · 2015 · 35 citations
Architecture, Computer Engineering, Computer-aided Design +12