{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T16:13:29Z","timestamp":1781194409447,"version":"3.54.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,8,25]],"date-time":"2020-08-25T00:00:00Z","timestamp":1598313600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007229","name":"Bijzonder Onderzoeksfonds UGent","doi-asserted-by":"publisher","award":["01SC1917"],"award-info":[{"award-number":["01SC1917"]}],"id":[{"id":"10.13039\/501100007229","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["No. 201607000035"],"award-info":[{"award-number":["No. 201607000035"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>Routing is a crucial step in Field Programmable Gate Array (FPGA) physical design, as it determines the routes of signals in the circuit, which impacts the design implementation quality significantly. It can be very time-consuming to successfully route all the signals of large circuits that utilize many FPGA resources. Attempts have been made to shorten the routing runtime for efficient design exploration while expecting high-quality implementations. In this work, we elaborate on the connection-based routing strategy and algorithmic enhancements to improve the serial FPGA routing. We also explore a recursive partitioning-based parallelization technique to further accelerate the routing process. To exploit more parallelism by a finer granularity in both spatial partitioning and routing, a connection-aware routing bounding box model is proposed for the source-sink connections of the nets. It is built upon the location information of each connection\u2019s source, sink, and the geometric center of the net that the connection belongs to, different from the existing net-based routing bounding box that covers all the pins of the entire net. We present that the proposed connection-aware routing bounding box is more beneficial for parallel routing than the existing net-based routing bounding box. The quality and runtime of the serial and multi-threaded routers are compared to the router in VPR 7.0.7. The large heterogeneous Titan23 designs that are targeted to a detailed representation of the Stratix IV FPGA are used for benchmarking. With eight threads, the parallel router using the connection-aware routing bounding box model reaches a speedup of 6.1\u00d7 over the serial router in VPR 7.0.7, which is 1.24\u00d7 faster than the one using the existing net-based routing bounding box model, while reducing the total wire-length by 10% and the critical path delay by 7%.<\/jats:p>","DOI":"10.1145\/3406959","type":"journal-article","created":{"date-parts":[[2020,8,25]],"date-time":"2020-08-25T16:07:30Z","timestamp":1598371650000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Accelerating FPGA Routing Through Algorithmic Enhancements and Connection-aware Parallelization"],"prefix":"10.1145","volume":"13","author":[{"given":"Yun","family":"Zhou","sequence":"first","affiliation":[{"name":"Ghent University, Technologiepark-Zwijnaarde, Ghent, Flanders, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dries","family":"Vercruyce","sequence":"additional","affiliation":[{"name":"Ghent University, Technologiepark-Zwijnaarde, Ghent, Flanders, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dirk","family":"Stroobandt","sequence":"additional","affiliation":[{"name":"Ghent University, Technologiepark-Zwijnaarde, Ghent, Flanders, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,8,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/647924.738755"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/296399.296428"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2011.84"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2011.2165715"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2202326"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 26th International Conference on Field Programmable Logic and Applications (FPL\u201916)","author":"Hoo C. H.","unstructured":"C. H. Hoo , Y. Ha , and A. Kumar . 2016. ParaFRo: A hybrid parallel FPGA router using fine grained synchronization and partitioning . In Proceedings of the 26th International Conference on Field Programmable Logic and Applications (FPL\u201916) . 1--11. C. H. Hoo, Y. Ha, and A. Kumar. 2016. ParaFRo: A hybrid parallel FPGA router using fine grained synchronization and partitioning. In Proceedings of the 26th International Conference on Field Programmable Logic and Applications (FPL\u201916). 1--11."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3174243.3174246"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2617593"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068716.2068718"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/201310.201328"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 28th International Conference on Field Programmable Logic and Applications (FPL\u201918)","author":"Moctar Y.","unstructured":"Y. Moctar , M. Stojilovi\u0107 , and P. Brisk . 2018. Deterministic parallel routing for FPGAs based on Galois parallel execution model . In Proceedings of the 28th International Conference on Field Programmable Logic and Applications (FPL\u201918) . 21--25. Y. Moctar, M. Stojilovi\u0107, and P. Brisk. 2018. Deterministic parallel routing for FPGAs based on Galois parallel execution model. In Proceedings of the 28th International Conference on Field Programmable Logic and Applications (FPL\u201918). 21--25."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593177"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629579"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2840819.2840836"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021732"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the IEEE 36th International Conference on Computer Design (ICCD\u201918)","author":"Shen M.","unstructured":"M. Shen and N. Xiao . 2018. Fine-grained parallel routing for FPGAs with selective expansion . In Proceedings of the IEEE 36th International Conference on Computer Design (ICCD\u201918) . 577--586. M. Shen and N. Xiao. 2018. Fine-grained parallel routing for FPGAs with selective expansion. In Proceedings of the IEEE 36th International Conference on Computer Design (ICCD\u201918). 577--586."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the IEEE 36th International Conference on Computer Design (ICCD\u201918)","author":"Shen M.","unstructured":"M. Shen and N. Xiao . 2018. Load balance-aware multi-core parallel routing for large-scale FPGAs . In Proceedings of the IEEE 36th International Conference on Computer Design (ICCD\u201918) . 595--602. M. Shen and N. Xiao. 2018. Load balance-aware multi-core parallel routing for large-scale FPGAs. In Proceedings of the IEEE 36th International Conference on Computer Design (ICCD\u201918). 595--602."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/275107.275134"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Field-Programmable Technology (FPT\u201913)","author":"Vansteenkiste E.","unstructured":"E. Vansteenkiste , K. Bruneel , and D. Stroobandt . 2013. A connection-based router for FPGAs . In Proceedings of the International Conference on Field-Programmable Technology (FPT\u201913) . 326--329. E. Vansteenkiste, K. Bruneel, and D. Stroobandt. 2013. A connection-based router for FPGAs. In Proceedings of the International Conference on Field-Programmable Technology (FPT\u201913). 326--329."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2017.2717786"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201919)","author":"Vercruyce D.","unstructured":"D. Vercruyce , E. Vansteenkiste , and D. Stroobandt . 2019. CRoute: A fast high-quality timing-driven connection-based FPGA router . In Proceedings of the IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201919) . 53--60. D. Vercruyce, E. Vansteenkiste, and D. Stroobandt. 2019. CRoute: A fast high-quality timing-driven connection-based FPGA router. In Proceedings of the IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201919). 53--60."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2017.2768416"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2019.2901243"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 23rd International Conference on Field programmable Logic and Applications. 1--4.","author":"Zhu C.","unstructured":"C. Zhu , J. Wang , and J. Lai . 2013. A novel net-partition-based multithread FPGA routing method . In Proceedings of the 23rd International Conference on Field programmable Logic and Applications. 1--4. C. Zhu, J. Wang, and J. Lai. 2013. A novel net-partition-based multithread FPGA routing method. In Proceedings of the 23rd International Conference on Field programmable Logic and Applications. 1--4."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406959","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:39:01Z","timestamp":1750199941000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,25]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3406959"],"URL":"https:\/\/doi.org\/10.1145\/3406959","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,25]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}