{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:00:38Z","timestamp":1774630838608,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T00:00:00Z","timestamp":1530316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Lattice Semiconductor and the NSERC\/Altera Industrial Research Chair in Programmable Silicon"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>FPGA routing architectures consist of routing wires and programmable switches that together account for the majority of the fabric delay and area, making evaluation and optimization of an FPGA\u2019s routing architecture very important. Routing architectures have traditionally been evaluated using a full synthesize, pack, place and route CAD flow over a suite of benchmark circuits. While the results are accurate, a full CAD flow has a long runtime and is often tuned to a specific FPGA architecture type, which limits exploration of different architecture options early in the design process. In this article, we present Wotan, a tool to quickly estimate routability for a wide range of architectures without the use of benchmark circuits. At its core, our routability predictor efficiently counts paths through the FPGA routing graph to (1) estimate the probability of node congestion and (2) estimate the probabilities to successfully route a randomized subset of<jats:italic>(source, sink)<\/jats:italic>pairs, which are then combined into an overall routability metric. We describe our predictor and present routability estimates for a range of 6-LUT and 4-LUT architectures using mixes of wire types connected in complex ways, showing a rank correlation of 0.91 with routability results from the full VPR CAD flow while requiring 18\u00d7 less CPU effort.<\/jats:p>","DOI":"10.1145\/3195800","type":"journal-article","created":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T11:58:04Z","timestamp":1532606284000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Wotan"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8535-3432","authenticated-orcid":false,"given":"Oleg","family":"Petelin","sequence":"first","affiliation":[{"name":"University of Toronto, Ontario, Canada"}]},{"given":"Vaughn","family":"Betz","sequence":"additional","affiliation":[{"name":"University of Toronto, Ontario, Canada"}]}],"member":"320","published-online":{"date-parts":[[2018,7,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/296399.296428"},{"key":"e_1_2_1_2_1","volume-title":"Architecture and CAD for Deep-Submicron FPGAs","author":"Betz Vaughn","unstructured":"Vaughn Betz , Jonathan Rose , and Alexander Marquardt . 1999. Architecture and CAD for Deep-Submicron FPGAs . Kluwer Academic Publishers . Vaughn Betz, Jonathan Rose, and Alexander Marquardt. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.251146"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/225871.225886"},{"key":"e_1_2_1_5_1","volume-title":"The Combinatorics of Network Reliability","author":"Colbourn Charles","unstructured":"Charles Colbourn . 1987. The Combinatorics of Network Reliability . Oxford University Press . Charles Colbourn. 1987. The Combinatorics of Network Reliability. Oxford University Press."},{"key":"e_1_2_1_6_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas","unstructured":"Thomas Cormen , Charles Leiserson , Ronald Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). The MIT Press . Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press.","edition":"3"},{"key":"e_1_2_1_7_1","volume-title":"Advancing Moore\u2019s Law","author":"Intel Corporation","year":"2014","unstructured":"Intel Corporation . 2014. Advancing Moore\u2019s Law in 2014 . Retrieved from https:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/presentation\/advancing-moores-law-in-2014-presentation.pdf. Intel Corporation. 2014. Advancing Moore\u2019s Law in 2014. Retrieved from https:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/presentation\/advancing-moores-law-in-2014-presentation.pdf."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950413.1950449"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1981.1084958"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344671.1344694"},{"key":"e_1_2_1_11_1","unstructured":"International Technology Roadmap for Semiconductors. 2013. Interconnect. Retrieved from http:\/\/www.itrs2.net\/2013-itrs.html. International Technology Roadmap for Semiconductors. 2013. Interconnect. Retrieved from http:\/\/www.itrs2.net\/2013-itrs.html."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.857312"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774597"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1117201.1117205"},{"key":"e_1_2_1_15_1","unstructured":"Lattice Semiconductor. 2017. iCE40 LP\/HX family data sheet. Lattice Semiconductor. 2017. iCE40 LP\/HX family data sheet."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"G. Lemieux E. Lee M. Tom and A. Yu. 2004. Directional and single-driver wires in FPGA interconnect. In FPT. 41--48. G. Lemieux E. Lee M. Tom and A. Yu. 2004. Directional and single-driver wires in FPGA interconnect. In FPT. 41--48.","DOI":"10.1109\/FPT.2004.1393249"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435264.2435292"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2061530"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.974135"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2617593"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(56)90044-8"},{"key":"e_1_2_1_22_1","volume-title":"Titan: Enabling large and complex benchmarks in academic CAD. In FPL.","author":"Murray Kevin","year":"2013","unstructured":"Kevin Murray , Scott Whitty , Suya Liu , Jason Luu , and Vaughn Betz . 2013 . Titan: Enabling large and complex benchmarks in academic CAD. In FPL. Kevin Murray, Scott Whitty, Suya Liu, Jason Luu, and Vaughn Betz. 2013. Titan: Enabling large and complex benchmarks in academic CAD. In FPL."},{"key":"e_1_2_1_23_1","volume-title":"Wotan: A tool for rapid evaluation of FPGA architecture routability without benchmarks. In FPL.","author":"Petelin Oleg","year":"2015","unstructured":"Oleg Petelin and Vaughn Betz . 2015 . Wotan: A tool for rapid evaluation of FPGA architecture routability without benchmarks. In FPL. Oleg Petelin and Vaughn Betz. 2015. Wotan: A tool for rapid evaluation of FPGA architecture routability without benchmarks. In FPL."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Oleg Petelin and Vaughn Betz. 2016. The speed of diversity: Exploring complex FPGA routing topologies for the global metal layer. In FPL. Oleg Petelin and Vaughn Betz. 2016. The speed of diversity: Exploring complex FPGA routing topologies for the global metal layer. In FPL.","DOI":"10.1109\/FPL.2016.7577326"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Justin Richardson Steven Fingulin Diwakar Raghunathan Chris Massie Alan George and Herman Lam. 2010. Comparative analysis of HPC and accelerator devices: Computation memory I\/O and power. In HPRCTA. 1--10. Justin Richardson Steven Fingulin Diwakar Raghunathan Chris Massie Alan George and Herman Lam. 2010. Comparative analysis of HPC and accelerator devices: Computation memory I\/O and power. In HPRCTA. 1--10.","DOI":"10.1109\/HPRCTA.2010.5670797"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.75006"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Akshay Sharma Carl Ebeling and Scott Hauck. 2005. Architecture adaptive routability-driven placement for FPGAs. In FPL. 427--432. Akshay Sharma Carl Ebeling and Scott Hauck. 2005. Architecture adaptive routability-driven placement for FPGAs. In FPL. 427--432.","DOI":"10.1145\/1046192.1046235"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Akshay Sharma and Scott Hauck. 2005. Accelerating FPGA routing using architecture-adaptive A* techniques. In FPT. 225--232. Akshay Sharma and Scott Hauck. 2005. Accelerating FPGA routing using architecture-adaptive A* techniques. In FPT. 225--232.","DOI":"10.1109\/FPT.2005.1568551"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Alastair Smith George Constantinides Steven Wilton and Peter Cheung. 2009. Concurrently optimizing FPGA architecture parameters and transistor sizing: Implications for FPGA design. In FPT. 54--61. Alastair Smith George Constantinides Steven Wilton and Peter Cheung. 2009. Concurrently optimizing FPGA architecture parameters and transistor sizing: Implications for FPGA design. In FPT. 54--61.","DOI":"10.1109\/FPT.2009.5377647"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508128.1508156"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3195800","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3195800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T01:53:09Z","timestamp":1751766789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3195800"}},"subtitle":["Evaluating FPGA Architecture Routability without Benchmarks"],"short-title":[],"issued":{"date-parts":[[2018,6,30]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3195800"],"URL":"https:\/\/doi.org\/10.1145\/3195800","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,30]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}