{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:54Z","timestamp":1750307214189,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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. Archit. Code Optim."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Many automatic software parallelization systems have been proposed in the past decades, but most of them are dedicated to source-to-source transformations. This paper shows that parallelizing executable programs is feasible, even if they require complex transformations, and in effect decouples parallelization from compilation, for example, for closed-source or legacy software, where binary code is the only available representation.<\/jats:p>\n          <jats:p>We propose an automatic parallelizer, which is able to perform advanced parallelization on binary code. It first parses the binary code and extracts high-level information. From this information, a C program is generated. This program captures only a subset of the program semantics, namely, loops and memory accesses. This C program is then parallelized using existing, state-of-the-art parallelizers, including advanced polyhedral parallelizers. The original program semantics is then re-injected, and the transformed parallel loop nests are recompiled by a standard C compiler.<\/jats:p>\n          <jats:p>We show on the PolyBench benchmark suite that our system successfully detects and parallelizes almost all the loop nests from the binary code, using a recent polyhedral loop parallelizer as a backend. The paper ends by elaborating a strategy to parallelize more complex programs, such as those containing non-linear accesses to memory, and provides a few example case-studies.<\/jats:p>","DOI":"10.1145\/2086696.2086718","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Polyhedral parallelization of binary code"],"prefix":"10.1145","volume":"8","author":[{"given":"Benoit","family":"Pradelle","sequence":"first","affiliation":[{"name":"INRIA Nancy Grand Est and LSIIT, Universit\u00e9 de Strasbourg, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Ketterlin","sequence":"additional","affiliation":[{"name":"INRIA Nancy Grand Est and LSIIT, Universit\u00e9 de Strasbourg, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philippe","family":"Clauss","sequence":"additional","affiliation":[{"name":"INRIA Nancy Grand Est and LSIIT, Universit\u00e9 de Strasbourg, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Appel A. and Ginsburg M. 2004. Modern Compiler Implementation in C. Cambridge University Press.   Appel A. and Ginsburg M. 2004. Modern Compiler Implementation in C. Cambridge University Press."},{"volume-title":"Proceedings of CPC '09","author":"Bae H.","key":"e_1_2_1_2_1","unstructured":"Bae , H. , Bachega , L. , Dave , C. , Lee , S.-I. , Lee , S. , Min , S.-J. , Eigenmann , R. , and Midkiff , S . 2009. Cetus: A source-to-source compiler infrastructure for multicores . In Proceedings of CPC '09 . Bae, H., Bachega, L., Dave, C., Lee, S.-I., Lee, S., Min, S.-J., Eigenmann, R., and Midkiff, S. 2009. Cetus: A source-to-source compiler infrastructure for multicores. In Proceedings of CPC '09."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025127.1025992"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2008.2002049"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008069920230"},{"volume-title":"Proceedings of CC'04","author":"Clauss P.","key":"e_1_2_1_7_1","unstructured":"Clauss , P. and Tchoupaeva , I . 2004. A symbolic spproach to Bernstein expansion for program analysis and optimization . In Proceedings of CC'04 . Springer. Clauss, P. and Tchoupaeva, I. 2004. A symbolic spproach to Bernstein expansion for program analysis and optimization. In Proceedings of CC'04. Springer."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944862.1944882"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"volume-title":"Proceedings of the IEEE\/ACM International Symposium on Code Generation and Optimization. 64--73","author":"Hertzberg B.","key":"e_1_2_1_12_1","unstructured":"Hertzberg , B. and Olukotun , K . 2011. Runtime automatic speculative parallelization . In Proceedings of the IEEE\/ACM International Symposium on Code Generation and Optimization. 64--73 . Hertzberg, B. and Olukotun, K. 2011. Runtime automatic speculative parallelization. In Proceedings of the IEEE\/ACM International Symposium on Code Generation and Optimization. 64--73."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2010.27"},{"volume-title":"Proceedings of ISPASS '10","author":"Laurenzano M. A.","key":"e_1_2_1_14_1","unstructured":"Laurenzano , M. A. , Tikir , M. M. , Carrington , L. , and Snavely , A . 2010. PEBIL: Efficient static binary instrumentation for linux . In Proceedings of ISPASS '10 . Laurenzano, M. A., Tikir, M. M., Carrington, L., and Snavely, A. 2010. PEBIL: Efficient static binary instrumentation for linux. In Proceedings of ISPASS '10."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122971.1122997"},{"key":"e_1_2_1_16_1","unstructured":"Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann.   Muchnick S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann."},{"volume-title":"Proceedings of the Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems. 77--84","author":"Ootsu K.","key":"e_1_2_1_17_1","unstructured":"Ootsu , K. , Yokota , T. , Ono , T. , and Baba , T . 2002. Preliminary evaluation of a binary translation system for multithreaded processors . In Proceedings of the Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems. 77--84 . Ootsu, K., Yokota, T., Ono, T., and Baba, T. 2002. Preliminary evaluation of a binary translation system for multithreaded processors. In Proceedings of the Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems. 77--84."},{"key":"e_1_2_1_18_1","unstructured":"openmp 2008. The OpenMP API specification. http:\/\/www.openmp.org.  openmp 2008. The OpenMP API specification. http:\/\/www.openmp.org."},{"key":"e_1_2_1_19_1","unstructured":"polybench 2010. Polybenchs 1.0. http:\/\/www-rocq.inria.fr\/pouchet\/software\/polybenchs.  polybench 2010. Polybenchs 1.0. http:\/\/www-rocq.inria.fr\/pouchet\/software\/polybenchs."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.14"},{"volume-title":"Proceedings of the Workshop on Binary Translation.","author":"Schwarz B.","key":"e_1_2_1_21_1","unstructured":"Schwarz , B. , Debray , S. , Andrews , G. , and Legendre , M . 2001. Plto: A link-time optimizer for the intel ia-32 architecture . In Proceedings of the Workshop on Binary Translation. Schwarz, B., Debray, S., Andrews, G., and Legendre, M. 2001. Plto: A link-time optimizer for the intel ia-32 architecture. In Proceedings of the Workshop on Binary Translation."},{"key":"e_1_2_1_22_1","unstructured":"SpecOMP 2001. SPEC OMP benchmark suite. http:\/\/www.spec.org\/omp\/.  SpecOMP 2001. SPEC OMP benchmark suite. http:\/\/www.spec.org\/omp\/."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSPIT.2005.1577061"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888455"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1231-0"},{"key":"e_1_2_1_26_1","unstructured":"Yang J. Skadron K. Soffa M.-L. and Whitehouse K. Feasibility of dynamic binary parallelization. http:\/\/www.usenix.org\/event\/hotpar11\/tech\/final_files\/Yang.pdf.  Yang J. Skadron K. Soffa M.-L. and Whitehouse K. Feasibility of dynamic binary parallelization. http:\/\/www.usenix.org\/event\/hotpar11\/tech\/final_files\/Yang.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1128022.1128040"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2086696.2086718","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2086696.2086718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:43Z","timestamp":1750241203000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2086696.2086718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2086696.2086718"],"URL":"https:\/\/doi.org\/10.1145\/2086696.2086718","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}