{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:14:30Z","timestamp":1761808470346,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T00:00:00Z","timestamp":1631836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            Coarse-grained reconfigurable architecture (CGRA) mapping involves three main steps: placement, routing, and timing. The mapping is an NP-complete problem, and a common strategy is to decouple this process into its independent steps. This work focuses on the placement step, and its aim is to propose a technique that is both reasonably fast and leads to high-performance solutions. Furthermore, a near-optimal placement simplifies the following routing and timing steps. Exact solutions cannot find placements in a reasonable execution time as input designs increase in size. Heuristic solutions include meta-heuristics, such as Simulated Annealing (SA) and fast and straightforward greedy heuristics based on graph traversal. However, as these approaches are probabilistic and have a large design space, it is not easy to provide both run-time efficiency and good solution quality. We propose a graph traversal heuristic that provides the best of both: high-quality placements similar to SA and the execution time of graph traversal approaches. Our placement introduces novel ideas based on \u201cyou only traverse twice\u201d (YOTT) approach that performs a two-step graph traversal. The first traversal generates annotated data to guide the second step, which greedily performs the placement, node per node, aided by the annotated data and target architecture constraints. We introduce three new concepts to implement this technique: I\/O and reconvergence annotation, degree matching, and look-ahead placement. Our analysis of this approach explores the placement execution time\/quality trade-offs. We point out insights on how to analyze graph properties during dataflow mapping. Our results show that YOTT is 60.6\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , 9.7\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , and 2.3\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            faster than a high-quality SA, bounding box SA VPR, and multi-single traversal placements, respectively. Furthermore, YOTT reduces the average wire length and the maximal FIFO size (additional timing requirement on CGRAs) to avoid delay mismatches in fully pipelined architectures.\n          <\/jats:p>","DOI":"10.1145\/3477038","type":"journal-article","created":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T18:36:51Z","timestamp":1631903811000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["You Only Traverse Twice: A YOTT Placement, Routing, and Timing Approach for CGRAs"],"prefix":"10.1145","volume":"20","author":[{"given":"Michael","family":"Canesche","sequence":"first","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Westerley","family":"Carvalho","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucas","family":"Reis","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matheus","family":"Oliveira","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salles","family":"Magalh\u00e3es","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Jamieson","sequence":"additional","affiliation":[{"name":"Miami University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaugusto M.","family":"Nacif","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ricardo","family":"Ferreira","sequence":"additional","affiliation":[{"name":"Universidade Federal de Vi\u00e7osa, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3380446.3430618"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2019.00060"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/968878.969078"},{"key":"e_1_2_1_4_1","volume-title":"Jos\u00e9 Augusto Nacif, and Ricardo Ferreira","author":"Canesche Michael","year":"2020","unstructured":"Michael Canesche , Marcelo Menezes , Westerley Carvalho , Frank Torres , Peter Jamieson , Jos\u00e9 Augusto Nacif, and Ricardo Ferreira . 2020 . TRAVERSAL : A fast and adaptive graph-based placement and routing for CGRAs. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems ( 2020). Michael Canesche, Marcelo Menezes, Westerley Carvalho, Frank Torres, Peter Jamieson, Jos\u00e9 Augusto Nacif, and Ricardo Ferreira. 2020. TRAVERSAL: A fast and adaptive graph-based placement and routing for CGRAs. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems (2020)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICFPT51103.2020.00040"},{"volume-title":"FPGA Design Automation: A Survey","author":"Chen Deming","key":"e_1_2_1_6_1","unstructured":"Deming Chen , Jason Cong , and Peichan Pan . 2006. FPGA Design Automation: A Survey . Now Publishers Inc . Deming Chen, Jason Cong, and Peichan Pan. 2006. FPGA Design Automation: A Survey. Now Publishers Inc."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2655242"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3195970.3195986"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2650280.2650333"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/996070.1009932"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1878961.1878966"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2015.49"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RECONF.2006.307749"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ReConFig48160.2019.8994781"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2014.6893197"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2013.6621122"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2007.14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2013.6645514"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/INDIN.2011.6034997"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508128.1508158"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372780.3378174"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488756"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Manupa Karunaratne Dhananjaya Wijerathne Tulika Mitra and Li-Shiuan Peh. 2019. 4D-CGRA: Introducing branch dimension to spatio-temporal application mapping on CGRAs. In Iccad. 1\u20138.  Manupa Karunaratne Dhananjaya Wijerathne Tulika Mitra and Li-Shiuan Peh. 2019. 4D-CGRA: Introducing branch dimension to spatio-temporal application mapping on CGRAs. In Iccad. 1\u20138.","DOI":"10.1109\/ICCAD45719.2019.8942148"},{"key":"e_1_2_1_24_1","volume-title":"IEEE Symp on Circuits and Systems.","author":"Lai Yen-Tai","year":"2005","unstructured":"Yen-Tai Lai , Hsin-Ya Lai , and Chia-Nan Yeh . 2005 . Placement for the reconfigurable datapath architecture . In IEEE Symp on Circuits and Systems. Yen-Tai Lai, Hsin-Ya Lai, and Chia-Nan Yeh. 2005. Placement for the reconfigurable datapath architecture. In IEEE Symp on Circuits and Systems."},{"key":"e_1_2_1_25_1","unstructured":"LESC-UFV. 2021. Dataflow graph benchmarks. https:\/\/github.com\/lesc-ufv\/benchmarks-cases-2021.  LESC-UFV. 2021. Dataflow graph benchmarks. https:\/\/github.com\/lesc-ufv\/benchmarks-cases-2021."},{"key":"e_1_2_1_26_1","volume-title":"Chordmap: Automated mapping of streaming applications onto CGRA","author":"Li Zhaoying","year":"2021","unstructured":"Zhaoying Li , Dhananjaya Wijerathne , Xianzhang Chen , Anuj Pathania , and Tulika Mitra . 2021 . Chordmap: Automated mapping of streaming applications onto CGRA . IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems ( 2021), 1\u20131. https:\/\/doi.org\/10.1109\/TCAD.2021.3058313 10.1109\/TCAD.2021.3058313 Zhaoying Li, Dhananjaya Wijerathne, Xianzhang Chen, Anuj Pathania, and Tulika Mitra. 2021. Chordmap: Automated mapping of streaming applications onto CGRA. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems (2021), 1\u20131. https:\/\/doi.org\/10.1109\/TCAD.2021.3058313"},{"key":"e_1_2_1_27_1","volume-title":"Pan","author":"Lin Yibo","year":"2020","unstructured":"Yibo Lin , Zixuan Jiang , Jiaqi Gu , Wuxi Li , Shounak Dhar , Haoxing Ren , Brucek Khailany , and David Z . Pan . 2020 . Dreamplace : Deep learning toolkit-enabled gpu acceleration for modern vlsi placement. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems ( 2020). Yibo Lin, Zixuan Jiang, Jiaqi Gu, Wuxi Li, Shounak Dhar, Haoxing Ren, Brucek Khailany, and David Z. Pan. 2020. Dreamplace: Deep learning toolkit-enabled gpu acceleration for modern vlsi placement. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems (2020)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2878183"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068716.2068718"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL50879.2020.00033"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317745"},{"key":"e_1_2_1_32_1","unstructured":"Bingfeng Mei M. Berekovic and J. Y. Mignolet. 2007. Adres & dresc: Architecture and compiler for coarse-grain reconfigurable processors. In Fine-and Coarse-grain Reconfigurable Computing. Springer 255\u2013297.  Bingfeng Mei M. Berekovic and J. Y. Mignolet. 2007. Adres & dresc: Architecture and compiler for coarse-grain reconfigurable processors. In Fine-and Coarse-grain Reconfigurable Computing. Springer 255\u2013297."},{"key":"e_1_2_1_33_1","volume-title":"et\u00a0al","author":"Mirhoseini Azalia","year":"2021","unstructured":"Azalia Mirhoseini , Anna Goldie , Mustafa Yazgan , Joe Jiang , Ebrahim Songhori , Shen Wang , Young-Joon Lee , Eric Johnson , et\u00a0al . 2021 . A graph placement methodology for fast chip design. Nature 594 (2021). Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, et\u00a0al. 2021. A graph placement methodology for fast chip design. Nature 594 (2021)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3388617"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243176.3243212"},{"key":"e_1_2_1_36_1","unstructured":"University of Toronto. 2019. CGRA-ME. http:\/\/cgra-me.ece.utoronto.ca\/.  University of Toronto. 2019. CGRA-ME. http:\/\/cgra-me.ece.utoronto.ca\/."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454140"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD45719.2019.8942053"},{"key":"e_1_2_1_39_1","volume-title":"A survey on coarse-grained reconfigurable architectures from a performance perspective. Arxiv Preprint arXiv:2004.04509","author":"Podobas Artur","year":"2020","unstructured":"Artur Podobas , Kentaro Sano , and Satoshi Matsuoka . 2020. A survey on coarse-grained reconfigurable architectures from a performance perspective. Arxiv Preprint arXiv:2004.04509 ( 2020 ). Artur Podobas, Kentaro Sano, and Satoshi Matsuoka. 2020. A survey on coarse-grained reconfigurable architectures from a performance perspective. Arxiv Preprint arXiv:2004.04509 (2020)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD50377.2020.00070"},{"key":"e_1_2_1_41_1","unstructured":"Santa Barbara University of California. 2020. Express Benchmarks. https:\/\/web.ece.ucsb.edu\/EXPRESS\/benchmark\/.  Santa Barbara University of California. 2020. Express Benchmarks. https:\/\/web.ece.ucsb.edu\/EXPRESS\/benchmark\/."},{"volume-title":"2021 IEEE International Symposium on Circuits and Systems (ISCAS). 1\u20135.","author":"Vieira Maria","key":"e_1_2_1_42_1","unstructured":"Maria Vieira , Michael Canesche , Lucas Bragan\u00e7a , Josu\u00e9 Campos , Mateus Silva , Ricardo Ferreira , and Jose A. Nacif . 2021. RESHAPE: A run-time dataflow hardware-based mapping for CGRA overlays . In 2021 IEEE International Symposium on Circuits and Systems (ISCAS). 1\u20135. Maria Vieira, Michael Canesche, Lucas Bragan\u00e7a, Josu\u00e9 Campos, Mateus Silva, Ricardo Ferreira, and Jose A. Nacif. 2021. RESHAPE: A run-time dataflow hardware-based mapping for CGRA overlays. In 2021 IEEE International Symposium on Circuits and Systems (ISCAS). 1\u20135."},{"volume-title":"Symposium on Field-programmable Custom Computing Machines (FCCM).","author":"Matthew J.","key":"e_1_2_1_43_1","unstructured":"Matthew J. P. Walker and Jason H. Anderson. 2019. Generic connectivity-based CGRA mapping via integer linear programming . In Symposium on Field-programmable Custom Computing Machines (FCCM). Matthew J. P. Walker and Jason H. Anderson. 2019. Generic connectivity-based CGRA mapping via integer linear programming. In Symposium on Field-programmable Custom Computing Machines (FCCM)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICEIEC.2017.8076614"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2016.7446060"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00063"},{"key":"e_1_2_1_47_1","volume-title":"Himap: Fast and scalable high-quality mapping on CGRA via hierarchical abstraction. In Date.","author":"Wijerathne Dhananjaya","year":"2021","unstructured":"Dhananjaya Wijerathne , Zhaoying Li , Anuj Pathania , Tulika Mitra , and Lothar Thiele . 2021 . Himap: Fast and scalable high-quality mapping on CGRA via hierarchical abstraction. In Date. Dhananjaya Wijerathne, Zhaoying Li, Anuj Pathania, Tulika Mitra, and Lothar Thiele. 2021. Himap: Fast and scalable high-quality mapping on CGRA via hierarchical abstraction. In Date."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:47Z","timestamp":1750188647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,17]]},"references-count":47,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3477038"],"URL":"https:\/\/doi.org\/10.1145\/3477038","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2021,9,17]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}