{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:18:45Z","timestamp":1767917925637,"version":"3.49.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T00:00:00Z","timestamp":1498780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Center for Advancing Electronics Dresden"},{"name":"Graduiertenkolleg Experimentelle und konstruktive Algebra"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>With the surge of multi- and many-core systems, much research has focused on algorithms for mapping and scheduling on these complex platforms. Large classes of these algorithms face scalability problems. This is why diverse methods are commonly used for reducing the search space. While most such approaches leverage the inherent symmetry of architectures and applications, they do it in a problem-specific and intuitive way. However, intuitive approaches become impractical with growing hardware complexity, like Network-on-Chip interconnect or heterogeneous cores. In this article, we present a formal framework that can determine the inherent local and global symmetry of architectures and applications algorithmically and leverage these for problems in software synthesis. Our approach is based on the mathematical theory of groups and a generalization called inverse semigroups. We evaluate our approach in two state-of-the-art mapping frameworks. Even for the platforms with a handful of cores of today and moderate-sized benchmarks, our approach consistently yields reductions of the overall execution time of algorithms. We obtain a speedup of more than 10 \u00d7 for one use-case and saved 10% of time in another.<\/jats:p>","DOI":"10.1145\/3095747","type":"journal-article","created":{"date-parts":[[2017,7,21]],"date-time":"2017-07-21T12:24:07Z","timestamp":1500639847000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Symmetry in Software Synthesis"],"prefix":"10.1145","volume":"14","author":[{"given":"Andr\u00e9s","family":"Goens","sequence":"first","affiliation":[{"name":"Center for Advancing Electronics Dresden (cfaed), Chair for Compiler Construction, TU Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Siccha","sequence":"additional","affiliation":[{"name":"Lehr- und Forschungsgebiet Algebra, Lehrstuhl B f\u00fcr Mathematik, RWTH Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeronimo","family":"Castrillon","sequence":"additional","affiliation":[{"name":"Center for Advancing Electronics Dresden (cfaed), Chair for Compiler Construction, TU Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Graph isomorphism in quasipolynomial time. arXiv preprint arXiv:1512.03547","author":"Babai L\u00e1szl\u00f3","year":"2015"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872414"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3746"},{"key":"e_1_2_2_4_1","volume-title":"Maximizing Multicore Efficiency with Navigator Runtime. White Paper. (Feb","author":"Biscondi Eric","year":"2012"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1996.0125"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPA.2013.6703835"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2011.2173941"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2011.6045483"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228597"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2532862"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/HLDVT.2007.4392782"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2013.139"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSMC.1988.712894"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670342"},{"key":"e_1_2_2_15_1","volume-title":"Multi-objective Optimization Using Evolutionary Algorithms","author":"Deb K."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87527-7"},{"key":"e_1_2_2_17_1","unstructured":"J. East A. Egri-Nagy J. D. Mitchell and Y. P\u00e9resse. 2015. Computing finite semigroups. arXiv preprint arXiv:1510.01868 (2015).  J. East A. Egri-Nagy J. D. Mitchell and Y. P\u00e9resse. 2015. Computing finite semigroups. arXiv preprint arXiv:1510.01868 (2015)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2005.860766"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the IFIP International Embedded Systems Symposium (IESS). Foz do Igua\u00e7u, Brazil.","author":"Goens Andr\u00e9s","year":"2015"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSoC.2016.48"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/CoolChips.2014.6842946"},{"key":"e_1_2_2_22_1","volume-title":"ARM White Paper","author":"Greenhalgh P.","year":"2011"},{"key":"e_1_2_2_23_1","first-page":"11","article-title":"Adapteva: More flops, less watts","volume":"6","author":"Gwennap Linley","year":"2011","journal-title":"Microprocessor Report"},{"key":"e_1_2_2_24_1","volume-title":"Parallel Computing Technologies","author":"Hannig Frank"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078659.3078667"},{"key":"e_1_2_2_26_1","volume-title":"Theory and Practice of Algorithms in (Computer) Systems","author":"Junttila Tommi"},{"key":"e_1_2_2_27_1","volume-title":"Information Processing\u201974: Proceedings of the IFIP Congress","volume":"74","author":"Kahn Gilles","year":"1974"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455229.1455230"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2744916"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 18th Annual Symposium on Integrated Circuits and System Design. ACM, 190--195","author":"Kreutz M\u00e1rcio"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1142\/3645"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe. EDA Consortium, 641--646","author":"Liu Hung-Yi"},{"key":"e_1_2_2_34_1","volume-title":"Antonio Fern\u00e1ndez Anta, and Luis N\u00fa\u00f1ez Chiroque","author":"L\u00f3pez-Presa Jos\u00e9 Luis","year":"2011"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2001.10504443"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"issue":"8","key":"e_1_2_2_37_1","first-page":"0","article-title":"Semigroups","volume":"2","author":"Mitchell J. D.","year":"2016","journal-title":"Version"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSoC.2013.6675280"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2014.7094761"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1233748.1233750"},{"key":"e_1_2_2_41_1","unstructured":"M. Pelcat K. Desnos L. Maggiani Y. Liu J. Heulot J. F. Nezan and S. Bhattacharyya. 2015. Models of Architecture. Research Report PREESM\/2015-12TR01 2015. IETR\/INSA Rennes ; Scuola Superiore Sant\u2019Anna Pisa ; Institut Pascal Clermont Ferrand ; University of Maryland College Park ; Tampere University of Technology Tampere. https:\/\/hal.archives-ouvertes.fr\/hal-01244470  M. Pelcat K. Desnos L. Maggiani Y. Liu J. Heulot J. F. Nezan and S. Bhattacharyya. 2015. Models of Architecture. Research Report PREESM\/2015-12TR01 2015. IETR\/INSA Rennes ; Scuola Superiore Sant\u2019Anna Pisa ; Institut Pascal Clermont Ferrand ; University of Maryland College Park ; Tampere University of Technology Tampere. https:\/\/hal.archives-ouvertes.fr\/hal-01244470"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.16"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2014.46"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2680542"},{"key":"e_1_2_2_45_1","volume-title":"TILE-Gx100 ManyCore Processor: Acceleration Interfaces and Architecture. Presented at HotChips 23. (Aug","author":"Ramey Carl","year":"2011"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2744840"},{"key":"e_1_2_2_47_1","unstructured":"T. Schwarzer A. Weichslgartner M. Gla S. Wildermann P. Brand and J. Teich. 2017. Symmetry-eliminating Design Space Exploration for Hybrid Application Mapping on Many-Core Architectures. Retrieved from https:\/\/cris.fau.de\/converis\/publicweb\/Publication\/1061555.  T. Schwarzer A. Weichslgartner M. Gla S. Wildermann P. Brand and J. Teich. 2017. Symmetry-eliminating Design Space Exploration for Hybrid Application Mapping on Many-Core Architectures. Retrieved from https:\/\/cris.fau.de\/converis\/publicweb\/Publication\/1061555."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546549"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSoC.2012.15"},{"key":"e_1_2_2_50_1","unstructured":"Software Solutions GmbH Silexica. 2016. SLXMapper. Retrieved from http:\/\/www.silexica.com.  Software Solutions GmbH Silexica. 2016. SLXMapper. Retrieved from http:\/\/www.silexica.com."},{"key":"e_1_2_2_51_1","unstructured":"Charles C. Sims. 1970. Computational methods in the study of permutation groups. In Computational Problems in Abstract Algebra. 169--183.  Charles C. Sims. 1970. Computational methods in the study of permutation groups. In Computational Problems in Abstract Algebra. 169--183."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488734"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390191.2390200"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1111111103419896"},{"issue":"8","key":"e_1_2_2_55_1","first-page":"5","article-title":"GAP -- Groups, Algorithms, and Programming","volume":"4","author":"The GAP Group","year":"2016","journal-title":"Version"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2007.53"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2013.05.023"},{"key":"e_1_2_2_58_1","volume-title":"International Journal of High Performance Computing Applications","author":"Varghese Anish","year":"2015"},{"key":"e_1_2_2_59_1","first-page":"37","article-title":"Design space reduction for multi-objective optimization and robust design optimization problems","volume":"113","author":"Gary Wang G.","year":"2004","journal-title":"SAE SP"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2906363.2906370"},{"key":"e_1_2_2_61_1","first-page":"744","article-title":"Groupoids: Unifying internal and external symmetry","volume":"43","author":"Weinstein A.","year":"1996","journal-title":"Notices of the AMS"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3095747","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3095747","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:53Z","timestamp":1750217813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3095747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,30]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3095747"],"URL":"https:\/\/doi.org\/10.1145\/3095747","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,30]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}