Field-Programmable Gate Array (FPGA) routing is computationally expensive, taking hours or days with no guarantee of success. While prior work has used machine learning (ML) to guide placement and routing or predict routing outcomes, the process remains challenging to model precisely. A recent work has proposed using ML to predict the number of iterations remaining in a negotiated congestion router while it runs, enabling early termination of routing runs unlikely to succeed. However, that approach has key limitations hindering its utility: (1) iteration count is poorly correlated with runtime, (2) it ignores prediction confidence when deciding whether to exit, and (3) it cannot assess whether extending a routing run past a predefined limit is worthwhile. This paper presents a new ML-based framework that addresses these limitations. We introduce a method for estimating router workload based on node traversals in the FPGA routing resource graph, which strongly correlates with runtime and enables more accurate early exit decisions. We also propose a tunable success-confidence threshold that allows users to trade off runtime against success rate and we design a ML mixture of experts architecture to enable this thresholding effectively. Finally, we show how our architecture can “look ahead” to determine whether a routing run is likely to succeed if allowed to delay termination and continue past its initial time limit. We implement our approach on top of the negotiated congestion routing algorithm and, in our experiments on very difficult-toroute circuits, we find that the number of circuits successfully routed within a fixed cumulative routing time budget increases by 215 % compared with the approach from prior work.

Field-Programmable Gate Array (FPGA) routing is computationally expensive, taking hours or days with no guarantee of success. While prior work has used machine learning (ML) to guide placement and routing or predict routing outcomes, the process remains challenging to model precisely. This demo presents a new machine learning-based tool that addresses this problem.

The prefabricated resources in a field-programmable gate array (FPGA) can pose challenges resulting in unexpectedly long routing times. This sometimes leads to FPGA engineers prematurely terminating a viable routing run because they mistakenly believe the lengthy runtime indicates an unroutable design. In other cases, the FPGA engineer may wait long periods of time on a run that is doomed to never converge to a solution. As this leads to time wasted on runs which never reach design closure in either case, it is ideal to instead have an ML model decide whether or not to terminate routing. In this work, we introduce data-driven machine learning (ML) techniques for predicting both FPGA design routability and routing runtime continuously during routing.

In this paper, we present a Machine Learning (ML) Mixture of Experts (MoE) technique to predict the number of iterations needed for a Pathfinder-based FPGA router to complete a routing problem. Given a placed circuit, our technique uses features gathered on each routing iteration to predict if the circuit is routable and how many more iterations will be required to successfully route the circuit. This enables early exit for routing problems which are unlikely to be completed in a target number of iterations. Such early exit may help to achieve a successful route within tractable time by allowing the user to quickly retry the circuit compilation with a different random seed, a modified circuit design, or a different FPGA. We demonstrate our predictor in the VTR 8 framework; compared to VTR's predictor, our ML predictor incurs lower prediction errors on the Koios Deep Learning and Titan23 benchmark suites. Based on our tests, equipping VTR with our ML predictor would reduce time wasted on unroutable designs by 31% while also allowing 28% more routable designs to be completed.

Field-Programmable Custom Compute technology is now commonplace in important commercial settings. This has primarily been driven by improvements in Field-Programmable Gate Array (FPGA) technology. Commercial use cases typically demand the implementation of complex designs on large FPGAs, increasing typical FPGA design compile times. In particular, the routing compilation step can take days to complete. Amplifying the negative impact of these long compilations is that FPGA users have no guarantee that compilation will be successful.

In this poster, we present a Machine Learning (ML) technique to predict the number of iterations needed for a Pathfinder-based FPGA router to complete a routing problem. Given a placed circuit, our technique uses features gathered on each routing iteration to predict if the circuit is routable and how many more iterations will be required to successfully route the circuit. This enables early exit for routing problems which are unlikely to be completed in a target number of iterations. Such early exit may help to achieve a successful route within tractable time by allowing the user to quickly retry the circuit compilation with a different random seed, a modified circuit design, or a different FPGA. We demonstrate our predictor in the VTR 8 framework; compared to VTR's predictor, our ML predictor incurs lower prediction errors on the Koios Deep Learning benchmark suite. This corresponds with an approximate time saving of 48% from early rejection of unroutable FPGA designs while also successfully completing 5% more routable designs and having a 93% shorter early exit latency.

Avoiding congestion for routing resources has become one of the most important placement objectives. In this paper, we present a machine-learning model for accurately and efficiently estimating congestion during FPGA placement. Compared with the state-of-the-art machine-learning congestion-estimation model, our results show a 25% improvement in prediction accuracy. This makes our model competitive with congestion estimates produced using a global router. However, our model runs, on average, 291x faster than the global router.