{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:17:34Z","timestamp":1750306654138,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,3,17]],"date-time":"2015-03-17T00:00:00Z","timestamp":1426550400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"TU Delft, Netherlands"},{"name":"Brazilian Institutions: Science without Borders\/CNPq, CAPES, FAPEMIG, UFV, UFRGS, Funarpos\/FUNARBE, and Gapso"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2015,4,17]]},"abstract":"<jats:p>Dynamic Partial Reconfiguration (DPaR) enables efficient allocation of logic resources by adding new functionalities or by sharing and\/or multiplexing resources over time. Placement and routing (P&amp;R) is one of the most time-consuming steps in the DPaR flow. P&amp;R are two independent NP-complete problems, and, even for medium size circuits, traditional P&amp;R algorithms are not capable of placing and routing hardware modules at runtime. We propose a novel runtime P&amp;R algorithm for Field-Programmable Gate Array (FPGA)-based designs. Our algorithm models the FPGA as an implicit graph with a direct correspondence to the target FPGA. The P&amp;R is performed as a graph mapping problem by exploring the node locality during a depth-first traversal. We perform the P&amp;R using a greedy heuristic that executes in polynomial time. Unlike state-of-the-art algorithms, our approach does not try similar solutions, thus allowing the P&amp;R to execute in milliseconds. Our algorithm is also suitable for P&amp;R in fragmented regions. We generate results for a manufacturer-independent virtual FPGA. Compared with the most popular P&amp;R tool running the same benchmark suite, our algorithm is up to three orders of magnitude faster.<\/jats:p>","DOI":"10.1145\/2660775","type":"journal-article","created":{"date-parts":[[2015,3,19]],"date-time":"2015-03-19T12:13:49Z","timestamp":1426767229000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Runtime FPGA Placement and Routing Using Low-Complexity Graph Traversal"],"prefix":"10.1145","volume":"8","author":[{"given":"Ricardo","family":"Ferreira","sequence":"first","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luciana","family":"Rocha","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9 G.","family":"Santos","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 A. M.","family":"Nacif","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"Wong","sequence":"additional","affiliation":[{"name":"TU Delft, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luigi","family":"Carro","sequence":"additional","affiliation":[{"name":"Universidade Federal do Rio Grande do Sul, Porto Alegre, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,3,17]]},"reference":[{"volume-title":"International Conference on Field Programmable Logic and Applications (FPL\u201997)","author":"Betz V.","key":"e_1_2_1_1_1","unstructured":"V. Betz and J. Rose . 1997. VPR: A new packing, placement and routing tool for FPGA research . In International Conference on Field Programmable Logic and Applications (FPL\u201997) . Springer-Verlag, Berlin, 213--222. V. Betz and J. Rose. 1997. VPR: A new packing, placement and routing tool for FPGA research. In International Conference on Field Programmable Logic and Applications (FPL\u201997). Springer-Verlag, Berlin, 213--222."},{"volume-title":"International Conference on Microelectronics. IEEE, 204--208","author":"Dehyadgari M.","key":"e_1_2_1_2_1","unstructured":"M. Dehyadgari , M. Nickray , A. Afzali-Kusha , and Z. Navabi . 2005. Evaluation of pseudo adaptive XY routing using an object oriented model for NOC . In International Conference on Microelectronics. IEEE, 204--208 . M. Dehyadgari, M. Nickray, A. Afzali-Kusha, and Z. Navabi. 2005. Evaluation of pseudo adaptive XY routing using an object oriented model for NOC. In International Conference on Microelectronics. IEEE, 204--208."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800139.804563"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2007.14"},{"volume-title":"Automation and Test Conference (DATE\u201903)","author":"Gericota M. G.","key":"e_1_2_1_5_1","unstructured":"M. G. Gericota , G. R. Alves , M. L. Silva , and J. M. Ferreira . 2003. Run-time management of logic resources on reconfigurable systems. In Design , Automation and Test Conference (DATE\u201903) . ACM\/IEEE, 974--979. M. G. Gericota, G. R. Alves, M. L. Silva, and J. M. Ferreira. 2003. Run-time management of logic resources on reconfigurable systems. In Design, Automation and Test Conference (DATE\u201903). ACM\/IEEE, 974--979."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2011.67"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996820"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.135"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2061670"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488746"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.298203"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970353.1970355"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068716.2068718"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.842812"},{"key":"e_1_2_1_15_1","unstructured":"MCNC. 2010. BLIF Benchmark Suit. Retrieved from http:\/\/cadlab.cs.ucla.edu\/&sim;kirill\/.  MCNC. 2010. BLIF Benchmark Suit. Retrieved from http:\/\/cadlab.cs.ucla.edu\/&sim;kirill\/."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068716.2068722"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2012.40"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492185"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145694.2145713"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2011.02.001"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660775","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2660775","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:13Z","timestamp":1750229773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,17]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,4,17]]}},"alternative-id":["10.1145\/2660775"],"URL":"https:\/\/doi.org\/10.1145\/2660775","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2015,3,17]]},"assertion":[{"value":"2013-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}