{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T06:08:19Z","timestamp":1773382099767,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T00:00:00Z","timestamp":1748649600000},"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. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Coarse-grained Reconfigurable Architectures (CGRAs) offer energy efficiency and programmability, making them integral to modern high-performance computing. However, complicated compilation when mapping the Dataflow Graph (DFG) to CGRA components leads to significant time overhead, area inefficiency, and routing challenges, especially for large-scale applications today. In this article, a fast and accurate DFG mapping approach called PRISA is proposed to reduce the compilation delay and obtain mapping solutions with higher qualities in a more reasonable time. This approach analytically identifies the potential and weak regions in the space of mapping solutions to guide the search algorithm and prevent ineffective examinations. Moreover, using the potential solutions and a novel sparse matrix permutation technique, we introduced Selective Initial Solution (SIS) to further improve the performance of PRISA without needing long-time optimizations. As the computational requirements in the PRISA are performed analytically, there is no additional time overhead. We conducted extensive experiments on the benchmark graphs of CGRA-ME and VPR-8 toolkits and obtained outstanding results compared to integer linear programming, evolutionary, and graph traversal approaches in terms of compilation time and mapping communication cost. Our approach could map the DFGs of VPR-8 toolkit with 3.64 maximal FIFO size requirement and 53.5 ms time overhead, on average.<\/jats:p>","DOI":"10.1145\/3723045","type":"journal-article","created":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T18:47:01Z","timestamp":1742323621000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["PRISA: A Potential Region-based Intelligent Search Algorithm for Dataflow Graph Mapping in Spatial CGRAs"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2749-8980","authenticated-orcid":false,"given":"Seyed Mehdi","family":"Mohtavipour","sequence":"first","affiliation":[{"name":"Iran University of Science and Technology, Tehran, Iran"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6042-0993","authenticated-orcid":false,"given":"Hadi Shahriar","family":"Shahhoseini","sequence":"additional","affiliation":[{"name":"Iran University of Science and Technology, Tehran, Iran"}]}],"member":"320","published-online":{"date-parts":[[2025,5,31]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"41","article-title":"Review of recent trends in Coarse Grain Reconfigurable Architectures for signal processing applications","volume":"18","author":"Raghavachari R.","year":"2018","unstructured":"R. Raghavachari and M. Sridharan. 2018. Review of recent trends in Coarse Grain Reconfigurable Architectures for signal processing applications. Advances in Systems Science and Applications 18 (2018), 41\u201358.","journal-title":"Advances in Systems Science and Applications"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3193827"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2019.2909046"},{"key":"e_1_3_1_5_2","first-page":"109","volume-title":"Proceedings of the 19th Annual International Symposium on Field-Programmable Custom Computing Machines","author":"Patel K.","year":"2011","unstructured":"K. Patel, S. McGettrick, and C. J. Bleakley. 2011. SYSCORE: A coarse grained reconfigurable array architecture for low energy biosignal processing. In Proceedings of the 19th Annual International Symposium on Field-Programmable Custom Computing Machines, 109\u2013112."},{"key":"e_1_3_1_6_2","first-page":"1","volume-title":"Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED)","author":"Yuan Z.","year":"2017","unstructured":"Z. Yuan, Y. Liu, J. Yue, J. Li, and H. Yang. 2017. CORAL: Coarse-grained reconfigurable architecture for convolutional neural networks. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED), 1\u20136."},{"key":"e_1_3_1_7_2","first-page":"73","volume-title":"Proceedings of the 9th International Symposium on Embedded Multicore\/Many-Core Systems-on-Chip","author":"Tanomoto M.","year":"2015","unstructured":"M. Tanomoto, S. Takamaeda-Yamazaki, J. Yao, and Y. Nakashima. 2015. A CGRA-based approach for accelerating convolutional neural networks. In Proceedings of the 9th International Symposium on Embedded Multicore\/Many-Core Systems-on-Chip, 73\u201380."},{"key":"e_1_3_1_8_2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1007\/978-3-540-77560-7_6","volume-title":"Proceedings of the International Conference on High-Performance Embedded Architectures and Compilers","author":"Bouwens F.","year":"2008","unstructured":"F. Bouwens, M. Berekovic, B. D. Sutter, and G. Gaydadjiev. 2008. Architecture enhancements for the ADRES coarse-grained reconfigurable array. In Proceedings of the International Conference on High-Performance Embedded Architectures and Compilers, 66\u201381."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3241793.3241806"},{"key":"e_1_3_1_10_2","first-page":"268","volume-title":"Proceedings of the 47th Annual International Symposium on Computer Architecture (ISCA)","author":"Weng J.","year":"2020","unstructured":"J. Weng, S. Liu, V. Dadu, Z. Wang, P. Shah, and T. Nowatzki. 2020. DSAGEN: Synthesizing programmable spatial accelerators. In Proceedings of the 47th Annual International Symposium on Computer Architecture (ISCA), 268\u2013281."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2525981"},{"key":"e_1_3_1_12_2","first-page":"1027","volume-title":"Proceedings of the 48th Annual International Symposium on Computer Architecture (ISCA)","author":"Gobieski G.","year":"2021","unstructured":"G. Gobieski, A. O. Atli, K. Mai, B. Lucia, and N. Beckmann. 2021. Snafu: An ultra-low-power, energy-minimal CGRA-generation framework and architecture. In Proceedings of the 48th Annual International Symposium on Computer Architecture (ISCA), 1027\u20131040."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASP-DAC52403.2022.9712515"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3468874"},{"key":"e_1_3_1_15_2","first-page":"268","volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications","author":"Van Essen B.","year":"2009","unstructured":"B. Van Essen, A. Wood, A. Carroll, S. Friedman, R. Panda, B. Ylvisaker, C. Ebeling, and S. Hauck. 2009. Static versus scheduled interconnect in coarse-grained reconfigurable arrays. In Proceedings of the International Conference on Field Programmable Logic and Applications, 268\u2013275."},{"issue":"6","key":"e_1_3_1_16_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3357375","article-title":"A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications","volume":"52","author":"Liu L.","year":"2020","unstructured":"L. Liu, J. Zhu, Z. Li, Y. Lu, Y. Deng, J. Han, S. Yin, and S. Wei. 2020. A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications. ACM Computing Surveys 52, 6 (2020), 1\u201339.","journal-title":"ACM Computing Surveys"},{"issue":"1","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3550071","article-title":"An efficient and flexible stochastic CGRA mapping approach","volume":"22","author":"Das S.","year":"2022","unstructured":"S. Das, K. J. Martin, T. Peyret, and P. Coussy. 2022. An efficient and flexible stochastic CGRA mapping approach. ACM Transactions on Embedded Computing Systems 22, 1 (2022) 1\u201325.","journal-title":"ACM Transactions on Embedded Computing Systems"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3195970.3195986"},{"key":"e_1_3_1_19_2","first-page":"65","volume-title":"Proceedings of the 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)","author":"Walker M. J.","year":"2019","unstructured":"M. J. Walker and J. H. Anderson. 2019. Generic connectivity-based CGRA mapping via integer linear programming. In Proceedings of the 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 65\u201373."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3470496.3527426"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2020.3009225"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2878180"},{"key":"e_1_3_1_23_2","first-page":"184","volume-title":"Proceedings of the 28th International Conference on Application-Specific Systems, Architectures and Processors (ASAP)","author":"Chin S. A.","year":"2017","unstructured":"S. A. Chin, N. Sakamoto, A. Rui, J. Zhao, J. H. Kim, Y. Hara-Azumi, and J. Anderson. 2017. CGRA-ME: A unified framework for CGRA modelling and exploration. In Proceedings of the 28th International Conference on Application-Specific Systems, Architectures and Processors (ASAP), 184\u2013189."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3388617"},{"key":"e_1_3_1_25_2","first-page":"145","volume-title":"Proceedings of the International Conference of Soft Computing and Pattern Recognition","author":"Gnanaolivu R.","year":"2010","unstructured":"R. Gnanaolivu, T. S. Norvell, and R. Venkatesan. 2010. Mapping loops onto coarse-grained reconfigurable architectures using particle swarm optimization. In Proceedings of the International Conference of Soft Computing and Pattern Recognition, 145\u2013151."},{"key":"e_1_3_1_26_2","first-page":"219","volume-title":"Proceedings of the International Symposium on Applied Reconfigurable Computing","author":"Zhou L.","year":"2013","unstructured":"L. Zhou, D. Liu, B. Zhang, and H. Liu. 2013. Ant colony optimization for application mapping in coarse-grained reconfigurable array. In Proceedings of the International Symposium on Applied Reconfigurable Computing, 219\u2013219."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2655242"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3058313"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2008.2001746"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055188"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3107746"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-019-03056-5"},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/ISVLSI.2007.14","volume-title":"Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI \u201907)","author":"Ferreira R.","year":"2007","unstructured":"R. Ferreira, A. Garcia, T. Teixeira, and J. M. Cardoso. 2007. A polynomial placement algorithm for data driven coarse-grained reconfigurable architectures. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI \u201907), 61\u201366."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3025513"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3477038"},{"key":"e_1_3_1_36_2","first-page":"1","volume-title":"Proceedings of the International Symposium on Circuits and Systems (ISCAS)","author":"Yin S.","year":"2017","unstructured":"S. Yin, D. Liu, L. Sun, L. Liu, and S. Wei. 2017. DFGNet: Mapping dataflow graph onto CGRA by a deep learning approach. In Proceedings of the International Symposium on Circuits and Systems (ISCAS), 1\u20134."},{"key":"e_1_3_1_37_2","first-page":"444","volume-title":"Proceedings of the International Symposium on High-Performance Computer Architecture (HPCA)","author":"Li Z.","year":"2022","unstructured":"Z. Li, D. Wu, D. Wijerathne, and T. Mitra. 2022. LISA: Graph neural network based portable mapping on spatial accelerators. In Proceedings of the International Symposium on High-Performance Computer Architecture (HPCA), 444\u2013459."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3579371.3589081"},{"key":"e_1_3_1_39_2","unstructured":"S. B. University of California. 2020. Express Benchmarks. Retrieved from https:\/\/web.ece.ucsb.edu\/EXPRESS\/benchmark\/"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-6505-7_6"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243176.3243212"},{"key":"e_1_3_1_42_2","first-page":"305","volume-title":"Proceedings of the International Conference on Field-Programmable Logic and Applications (FPL)","author":"Zhou G.","year":"2023","unstructured":"G. Zhou, M. Stojilovi\u0107, and J. H. Anderson. 2023. GRAMM: Fast CGRA application mapping based on a heuristic for finding graph minors. In Proceedings of the International Conference on Field-Programmable Logic and Applications (FPL), 305\u2013310."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723045","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3723045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:56:42Z","timestamp":1750298202000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,31]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3723045"],"URL":"https:\/\/doi.org\/10.1145\/3723045","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,31]]},"assertion":[{"value":"2024-02-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-31","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}