enforcing long-path timing closure for fpga routing with path searches on clamped lexicographic spirals
As FPGA implementations become more popular in production deployment, improved performance-driven routers are vital in preserving performance upstream from the FPGA design flow. In this paper, a novel long-path timing-driven router, SpiralRoute, is presented. SpiralRoute is a negotiation-based router with a novel path search on a clamped lexicographic spiral cost structure, and provides a guarantee of long-path timing compliance if a legal solution is found. We describe important components of SpiralRoute, including the application of polynomial-time optimal weighted budget distribution to improve connection budget quality, the construction of arbitrary-length lexicographic composition of totally-ordered monoids with order-preserving addition for admissible path search under A*, a trie-of-stacks data structure that allows path candidate extraction and storage to be independent of the size of the index, and a new greedy algorithm for the maintainence of routing tree topology. The efficacy of SpiralRoute is demonstrated by completing 19 instances of long-path timing-driven routing within timing budget that the published timing-driven router VPR 4.30 does not complete. However, SpiralRoute runtimes are slower than VPR 4.30 but we contend that the additional runtime is an acceptable tradeoff for guaranteed solution quality at completion, especially for production circuit routing
fpga timing-driven routing lexicographic search negotiated congestion