{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T03:33:32Z","timestamp":1773804812214,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,3,28]],"date-time":"2016-03-28T00:00:00Z","timestamp":1459123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"FCT","award":["SFRH\/BD\/82606\/2011 and FEDER\/ON2"],"award-info":[{"award-number":["SFRH\/BD\/82606\/2011 and FEDER\/ON2"]}]},{"name":"FCT project","award":["NORTE-07-124-FEDER-000062"],"award-info":[{"award-number":["NORTE-07-124-FEDER-000062"]}]},{"DOI":"10.13039\/501100002322","name":"CAPES","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ACE Associated Compiler Experts bv, The Netherlands"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2016,4,5]]},"abstract":"<jats:p>A large number of compiler optimizations are nowadays available to users. These optimizations interact with each other and with the input code in several and complex ways. The sequence of application of optimization passes can have a significant impact on the performance achieved. The effect of the optimizations is both platform and application dependent. The exhaustive exploration of all viable sequences of compiler optimizations for a given code fragment is not feasible. As this exploration is a complex and time-consuming task, several researchers have focused on Design Space Exploration (DSE) strategies both to select optimization sequences to improve the performance of each function of the application and to reduce the exploration time. In this article, we present a DSE scheme based on a clustering approach for grouping functions with similarities and exploration of a reduced search space resulting from the combination of optimizations previously suggested for the functions in each group. The identification of similarities between functions uses a data mining method that is applied to a symbolic code representation. The data mining process combines three algorithms to generate clusters: the Normalized Compression Distance, the Neighbor Joining, and a new ambiguity-based clustering algorithm. Our experiments for evaluating the effectiveness of the proposed approach address the exploration of optimization sequences in the context of the ReflectC compiler, considering 49 compilation passes while targeting a Xilinx MicroBlaze processor, and aiming at performance improvements for 51 functions and four applications. Experimental results reveal that the use of our clustering-based DSE approach achieves a significant reduction in the total exploration time of the search space (20\u00d7 over a Genetic Algorithm approach) at the same time that considerable performance speedups (41% over the baseline) were obtained using the optimized codes. Additional experiments were performed considering the LLVM compiler, considering 124 compilation passes, and targeting a LEON3 processor. The results show that our approach achieved geometric mean speedups of 1.49 \u00d7 , 1.32 \u00d7 , and 1.24 \u00d7 for the best 10, 20, and 30 functions, respectively, and a global improvement of 7% over the performance obtained when compiling with -O2.<\/jats:p>","DOI":"10.1145\/2883614","type":"journal-article","created":{"date-parts":[[2016,3,28]],"date-time":"2016-03-28T12:53:25Z","timestamp":1459169605000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Clustering-Based Selection for the Exploration of Compiler Optimization Sequences"],"prefix":"10.1145","volume":"13","author":[{"given":"Luiz G. A.","family":"Martins","sequence":"first","affiliation":[{"name":"Federal University of Uberl\u00e2ndia, MG, Brazil"}]},{"given":"Ricardo","family":"Nobre","sequence":"additional","affiliation":[{"name":"University of Porto, Porto, Portugal"}]},{"given":"Jo\u00e3o M. P.","family":"Cardoso","sequence":"additional","affiliation":[{"name":"University of Porto, Porto, Portugal"}]},{"given":"Alexandre C. B.","family":"Delbem","sequence":"additional","affiliation":[{"name":"University of S\u00e3o Paulo, SP, Brazil"}]},{"given":"Eduardo","family":"Marques","sequence":"additional","affiliation":[{"name":"University of S\u00e3o Paulo, SP, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2016,3,28]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"ACE. 2012. CoSy Compiler Development System. Retrieved from http:\/\/www.ace.nl\/compiler\/cosy.html.  ACE. 2012. CoSy Compiler Development System. Retrieved from http:\/\/www.ace.nl\/compiler\/cosy.html."},{"key":"e_1_2_1_2_1","unstructured":"Aeroflex. 2003. TSIM2 ERC32\/LEON Simulator. Retrieved from http:\/\/www.gaisler.com\/index.php\/products\/simulators\/tsim.  Aeroflex. 2003. TSIM2 ERC32\/LEON Simulator. Retrieved from http:\/\/www.gaisler.com\/index.php\/products\/simulators\/tsim."},{"key":"e_1_2_1_3_1","unstructured":"Aeroflex. 2005. LEON3 Processor. Retrieved from http:\/\/www.gaisler.com\/index.php\/products\/processors\/leon3.  Aeroflex. 2005. LEON3 Processor. Retrieved from http:\/\/www.gaisler.com\/index.php\/products\/processors\/leon3."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2006.37"},{"key":"e_1_2_1_5_1","volume-title":"Proc. of the ACM Conf. on Languages, Compilers, and Tools for Embedded Systems (LCTES\u201904)","volume":"39","author":"Almagor L.","unstructured":"L. Almagor , K. D. Cooper , A. Grosul , T. J. Harvey , S. W. Reeves , D. Subramanian , L. Torczon , and T. Waterman . 2004. Finding effective compilation sequences . In Proc. of the ACM Conf. on Languages, Compilers, and Tools for Embedded Systems (LCTES\u201904) , Vol. 39 . 231--239. L. Almagor, K. D. Cooper, A. Grosul, T. J. Harvey, S. W. Reeves, D. Subramanian, L. Torczon, and T. Waterman. 2004. Finding effective compilation sequences. In Proc. of the ACM Conf. on Languages, Compilers, and Tools for Embedded Systems (LCTES\u201904), Vol. 39. 231--239."},{"key":"e_1_2_1_6_1","volume-title":"IEEE 12th Symp. on Embedded Systems for Real-time Multimedia (ESTIMedia\u201914)","author":"Ashouri A. H.","unstructured":"A. H. Ashouri , G. Mariani , G. Palermo , and C. Silvano . 2014. A Bayesian network approach for compiler auto-tuning for embedded processors . In IEEE 12th Symp. on Embedded Systems for Real-time Multimedia (ESTIMedia\u201914) . 90--97. A. H. Ashouri, G. Mariani, G. Palermo, and C. Silvano. 2014. A Bayesian network approach for compiler auto-tuning for embedded processors. In IEEE 12th Symp. on Embedded Systems for Real-time Multimedia (ESTIMedia\u201914). 90--97."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"J. M. P. Cardoso P. C. Diniz J. G. F. Coutinho and Z. M. Petrov (Eds.). 2013. Compilation and Synthesis for Embedded Reconfigurable Systems: An Aspect-Oriented Approach. Springer.  J. M. P. Cardoso P. C. Diniz J. G. F. Coutinho and Z. M. Petrov (Eds.). 2013. Compilation and Synthesis for Embedded Reconfigurable Systems: An Aspect-Oriented Approach. Springer.","DOI":"10.1007\/978-1-4614-4894-5"},{"key":"e_1_2_1_8_1","volume-title":"Proc. of the 11th ACM Int. Conf. on Aspect-Oriented Software Development (AOSD\u201912)","author":"Cardoso J. M. P.","unstructured":"J. M. P. Cardoso , T. Carvalho , J. G. F. Coutinho , W. Luk , R. Nobre , P. Diniz , and Z. M. Petrov . 2012. LARA: An aspect-oriented programming language for embedded systems . In Proc. of the 11th ACM Int. Conf. on Aspect-Oriented Software Development (AOSD\u201912) . 179--190. J. M. P. Cardoso, T. Carvalho, J. G. F. Coutinho, W. Luk, R. Nobre, P. Diniz, and Z. M. Petrov. 2012. LARA: An aspect-oriented programming language for embedded systems. In Proc. of the 11th ACM Int. Conf. on Aspect-Oriented Software Development (AOSD\u201912). 179--190."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167492"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2355585.2355594"},{"key":"e_1_2_1_11_1","volume-title":"Proc. of the IEEE Trans. Information Theory (AOSD\u201912)","volume":"51","author":"Cilibrasi A. R.","unstructured":"A. R. Cilibrasi and A. P. Vitanyi . 2005. Clustering by compression . In Proc. of the IEEE Trans. Information Theory (AOSD\u201912) , Vol. 51 . 1523--1545. A. R. Cilibrasi and A. P. Vitanyi. 2005. Clustering by compression. In Proc. of the IEEE Trans. Information Theory (AOSD\u201912), Vol. 51. 1523--1545."},{"key":"e_1_2_1_12_1","unstructured":"A. R. Cilibrasi A. L. Cruz S. de Rooij and M. Keijzer. 2008. CompLearn Toolkit. Retrieved from http:\/\/www.complearn.org\/.  A. R. Cilibrasi A. L. Cruz S. de Rooij and M. Keijzer. 2008. CompLearn Toolkit. Retrieved from http:\/\/www.complearn.org\/."},{"key":"e_1_2_1_13_1","volume-title":"Proc. of the ACM Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES\u201999)","author":"Cooper K. D.","unstructured":"K. D. Cooper , P. J. Schielke , and D. Subramanian . 1999. Optimizing for reduced code space using genetic algorithms . In Proc. of the ACM Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES\u201999) . 1--9. K. D. Cooper, P. J. Schielke, and D. Subramanian. 1999. Optimizing for reduced code space using genetic algorithms. In Proc. of the ACM Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES\u201999). 1--9."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-006-7954-5"},{"key":"e_1_2_1_15_1","unstructured":"J. Felsenstein. 2003. Inferring Phylogenies. Sinauer Associates.  J. Felsenstein. 2003. Inferring Phylogenies. Sinauer Associates."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-010-0161-2"},{"key":"e_1_2_1_17_1","volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"Goldberg D. E.","unstructured":"D. E. Goldberg . 1989. Genetic Algorithms in Search, Optimization and Machine Learning . Addison-Wesley Longman . D. E. Goldberg. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman."},{"key":"e_1_2_1_18_1","volume-title":"Proc. of the IEEE Int. Workshop of the Workload Characterization (WWC\u201901)","author":"Guthaus M. R.","unstructured":"M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , and R. B. Brown . 2001. MiBench: A free, commercially representative embedded benchmark suite . In Proc. of the IEEE Int. Workshop of the Workload Characterization (WWC\u201901) . 3--14. M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. 2001. MiBench: A free, commercially representative embedded benchmark suite. In Proc. of the IEEE Int. Workshop of the Workload Characterization (WWC\u201901). 3--14."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062261.1062293"},{"key":"e_1_2_1_20_1","volume-title":"Proc. of the 6th Int. Symp. on Code Generation and Optimization (CGO\u201908)","author":"Hoste K.","unstructured":"K. Hoste and L. Eeckhout . 2008. Cole: Compiler optimization level exploration . In Proc. of the 6th Int. Symp. on Code Generation and Optimization (CGO\u201908) . 165--174. K. Hoste and L. Eeckhout. 2008. Cole: Compiler optimization level exploration. In Proc. of the 6th Int. Symp. on Code Generation and Optimization (CGO\u201908). 165--174."},{"key":"e_1_2_1_21_1","volume-title":"Proc. of the IEEE Int. Symp. on Field-Programmable Custom Computing Machines (FCCM\u201913)","author":"Huang Q.","unstructured":"Q. Huang , R. Lian , A. Canis , J. Choi , R. Xi , S. Brown , and J. Anderson . 2013. The effect of compiler optimizations on high-level synthesis for FPGAs . In Proc. of the IEEE Int. Symp. on Field-Programmable Custom Computing Machines (FCCM\u201913) . 89--96. Q. Huang, R. Lian, A. Canis, J. Choi, R. Xi, S. Brown, and J. Anderson. 2013. The effect of compiler optimizations on high-level synthesis for FPGAs. In Proc. of the IEEE Int. Symp. on Field-Programmable Custom Computing Machines (FCCM\u201913). 89--96."},{"key":"e_1_2_1_22_1","volume-title":"Proc. of the Conf. on Compilers, Archit. and Synthesis for Embedded Systems (CASES\u201913)","author":"Jantz M. R.","unstructured":"M. R. Jantz and P. A. Kulkarni . 2013. Exploiting phase inter-dependencies for faster iterative compiler optimization phase order searches . In Proc. of the Conf. on Compilers, Archit. and Synthesis for Embedded Systems (CASES\u201913) . 7:1--7:10. M. R. Jantz and P. A. Kulkarni. 2013. Exploiting phase inter-dependencies for faster iterative compiler optimization phase order searches. In Proc. of the Conf. on Compilers, Archit. and Synthesis for Embedded Systems (CASES\u201913). 7:1--7:10."},{"key":"e_1_2_1_23_1","volume-title":"Proc. of the ACM Conf. on Lang., Comp., and Tools for Emb. Syst. (LCTES\u201910)","author":"Kulkarni P. A.","unstructured":"P. A. Kulkarni , M. R. Jantz , and D. B. Whalley . 2010. Improving both the performance benefits and speed of optimization phase sequence searches . In Proc. of the ACM Conf. on Lang., Comp., and Tools for Emb. Syst. (LCTES\u201910) . 95--104. P. A. Kulkarni, M. R. Jantz, and D. B. Whalley. 2010. Improving both the performance benefits and speed of optimization phase sequence searches. In Proc. of the ACM Conf. on Lang., Comp., and Tools for Emb. Syst. (LCTES\u201910). 95--104."},{"key":"e_1_2_1_24_1","volume-title":"Proc. of the IEEE Int. Symp. on Code Generation and Optimization (CGO\u201907)","author":"Kulkarni P. A.","unstructured":"P. A. Kulkarni , D. B. Whalley , and G. S. Tyson . 2007. Evaluating heuristic optimization phase order search algorithms . In Proc. of the IEEE Int. Symp. on Code Generation and Optimization (CGO\u201907) . 157--169. P. A. Kulkarni, D. B. Whalley, and G. S. Tyson. 2007. Evaluating heuristic optimization phase order search algorithms. In Proc. of the IEEE Int. Symp. on Code Generation and Optimization (CGO\u201907). 157--169."},{"key":"e_1_2_1_25_1","volume-title":"Proc. of the ACM Conf. on Object Oriented Programming Systems Lang. and Applications (OOPSLA\u201912)","author":"Kulkarni S.","unstructured":"S. Kulkarni and J. Cavazos . 2012. Mitigating the compiler optimization phase-ordering problem using machine learning . In Proc. of the ACM Conf. on Object Oriented Programming Systems Lang. and Applications (OOPSLA\u201912) . 147--162. S. Kulkarni and J. Cavazos. 2012. Mitigating the compiler optimization phase-ordering problem using machine learning. In Proc. of the ACM Conf. on Object Oriented Programming Systems Lang. and Applications (OOPSLA\u201912). 147--162."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1509864.1509865"},{"key":"e_1_2_1_27_1","volume-title":"Proc. of the Int. Symp. on Code Generation and Optimization (CGO&rsquo;\u201904)","author":"Lattner C.","unstructured":"C. Lattner and V. Adve . 2004. LLVM: A compilation framework for lifelong program analysis & transformation . In Proc. of the Int. Symp. on Code Generation and Optimization (CGO&rsquo;\u201904) . 75. C. Lattner and V. Adve. 2004. LLVM: A compilation framework for lifelong program analysis & transformation. In Proc. of the Int. Symp. on Code Generation and Optimization (CGO&rsquo;\u201904). 75."},{"key":"e_1_2_1_28_1","unstructured":"C. G. Lee. 2002. UTDSP benchmark suite. (2002). http:\/\/www.eecg.toronto.edu\/&sim;corinna\/DSP\/infrastructure\/UTDSP.tar.gz.  C. G. Lee. 2002. UTDSP benchmark suite. (2002). http:\/\/www.eecg.toronto.edu\/&sim;corinna\/DSP\/infrastructure\/UTDSP.tar.gz."},{"key":"e_1_2_1_29_1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"Li M.","unstructured":"M. Li and P. M. B. Vitanyi . 1997. An Introduction to Kolmogorov Complexity and Its Applications ( 2 nd ed.). Springer-Verlag . M. Li and P. M. B. Vitanyi. 1997. An Introduction to Kolmogorov Complexity and Its Applications (2nd ed.). Springer-Verlag.","edition":"2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2014.6900634"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597809.2597821"},{"key":"e_1_2_1_32_1","volume-title":"Networks: An Introduction","author":"Newman M.","unstructured":"M. Newman . 2010. Networks: An Introduction . Oxford University Press . M. Newman. 2010. Networks: An Introduction. Oxford University Press."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353445.1353451"},{"key":"e_1_2_1_34_1","first-page":"4","article-title":"Finding good optimization sequences covering program space","volume":"9","author":"Purini S.","year":"2013","unstructured":"S. Purini and L. Jain . 2013 . Finding good optimization sequences covering program space . ACM Trans. Architect. Code Optim. 9 , 4 (January 2013), 56:1--56:23. S. Purini and L. Jain. 2013. Finding good optimization sequences covering program space. ACM Trans. Architect. Code Optim. 9, 4 (January 2013), 56:1--56:23.","journal-title":"ACM Trans. Architect. Code Optim."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2009.02.007"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2010.62"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ReConFig.2011.51"},{"key":"e_1_2_1_38_1","volume-title":"Proc. of the Int. Symp. on Code Generation and Optimization (CGO\u201911)","author":"Sanchez R.","unstructured":"R. Sanchez , J. Amaral , D. Szafron , M. Pirvu , and M. Stoodley . 2011. Using machines to learn method-specific compilation strategies . In Proc. of the Int. Symp. on Code Generation and Optimization (CGO\u201911) . 257--266. R. Sanchez, J. Amaral, D. Szafron, M. Pirvu, and M. Stoodley. 2011. Using machines to learn method-specific compilation strategies. In Proc. of the Int. Symp. on Code Generation and Optimization (CGO\u201911). 257--266."},{"key":"e_1_2_1_39_1","unstructured":"Texas Instruments. 2003a. TMS320C64x DSP Library: Programmer\u2019s Reference. (2003).  Texas Instruments. 2003a. TMS320C64x DSP Library: Programmer\u2019s Reference. (2003)."},{"key":"e_1_2_1_40_1","unstructured":"Texas Instruments. 2003b. TMS320C64x Image\/Video Processing Library. (2003).  Texas Instruments. 2003b. TMS320C64x Image\/Video Processing Library. (2003)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.32614\/RJ-2014-011"},{"key":"e_1_2_1_42_1","volume-title":"Proc. of the 15th ISCB Conf. on Intelligent Systems for Molecular Biology","volume":"23","author":"Wheeler T.","unstructured":"T. Wheeler and J. Kececioglu . 2007. Multiple alignment by aligning alignments . In Proc. of the 15th ISCB Conf. on Intelligent Systems for Molecular Biology , Bioinformatics , Vol. 23 . i559--i568. T. Wheeler and J. Kececioglu. 2007. Multiple alignment by aligning alignments. In Proc. of the 15th ISCB Conf. on Intelligent Systems for Molecular Biology, Bioinformatics, Vol. 23. i559--i568."},{"key":"e_1_2_1_43_1","unstructured":"E. Zitzler M. Laumanns and L. Thiele. 2001. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Computer Engineering and Networks Lab Technical Report TR-200. Swiss Federal Institute of Technology Cambridge MA.  E. Zitzler M. Laumanns and L. Thiele. 2001. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Computer Engineering and Networks Lab Technical Report TR-200. Swiss Federal Institute of Technology Cambridge MA."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2883614","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2883614","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:12Z","timestamp":1750273452000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2883614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,28]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,4,5]]}},"alternative-id":["10.1145\/2883614"],"URL":"https:\/\/doi.org\/10.1145\/2883614","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,28]]},"assertion":[{"value":"2015-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}