{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T23:27:42Z","timestamp":1759879662323,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,1,25]],"date-time":"2016-01-25T00:00:00Z","timestamp":1453680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-0915766"],"award-info":[{"award-number":["CCF-0915766"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2016,1,25]]},"abstract":"<jats:p>The optimization of short sequences of loop-free, fixed-point assembly code sequences is an important problem in high-performance computing. However, the competing constraints of transformation correctness and performance improvement often force even special purpose compilers to produce sub-optimal code. We show that by encoding these constraints as terms in a cost function, and using a Markov Chain Monte Carlo sampler to rapidly explore the space of all possible code sequences, we are able to generate aggressively optimized versions of a given target code sequence. Beginning from binaries compiled by 11vm --O0, we are able to produce provably correct code sequences that either match or outperform the code produced by qcc --O3, icc --O3, and in some cases expert handwritten assembly.<\/jats:p>","DOI":"10.1145\/2863701","type":"journal-article","created":{"date-parts":[[2016,1,26]],"date-time":"2016-01-26T13:25:01Z","timestamp":1453814701000},"page":"114-122","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Stochastic program optimization"],"prefix":"10.1145","volume":"59","author":[{"given":"Eric","family":"Schkufza","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Rahul","family":"Sharma","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Alex","family":"Aiken","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]}],"member":"320","published-online":{"date-parts":[[2016,1,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020281327116"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008","author":"Bansal S.","year":"2008","unstructured":"Bansal , S. , Aiken , A. Binary translation using peephole superoptimizers . In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008 . R. Draves and R. van Renesse, eds. (San Diego, CA, USA, December 8--10 , 2008 ). USENIX Association, 177--192. Bansal, S., Aiken, A. Binary translation using peephole superoptimizers. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008. R. Draves and R. van Renesse, eds. (San Diego, CA, USA, December 8--10, 2008). USENIX Association, 177--192."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567807"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008","author":"Cadar C.","year":"2008","unstructured":"Cadar , C. , Dunbar , D. , Engler , D.R. Klee : Unassisted and automatic generation of high-coverage tests for complex systems programs . In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008 . R. Draves and R. van Renesse, eds. (San Diego, CA, USA, December 8--10 , 2008 ). USENIX Association, 209--224. Cadar, C., Dunbar, D., Engler, D.R. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008. R. Draves and R. van Renesse, eds. (San Diego, CA, USA, December 8--10, 2008). USENIX Association, 209--224."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1770351.1770421"},{"key":"e_1_2_1_6_1","volume-title":"Markov Chain Monte Carlo in Practice","author":"Gilks W.R.","year":"1999","unstructured":"Gilks , W.R. Markov Chain Monte Carlo in Practice . Chapman and Hall\/CRC , 1999 . Gilks, W.R. Markov Chain Monte Carlo in Practice. Chapman and Hall\/CRC, 1999."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993506"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512566"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 27th International Conference on Machine Learning (ICML-10)","author":"Liang P.","year":"2010","unstructured":"Liang , P. , Jordan , M.I. , Klein , D. Learning programs : A hierarchical Bayesian approach . In Proceedings of the 27th International Conference on Machine Learning (ICML-10) . J. F\u00fcrnkranz and T. Joachims, eds. (Haifa, Israel, June 21--24 , 2010 ). Omnipress, 639--646. Liang, P., Jordan, M.I., Klein, D. Learning programs: A hierarchical Bayesian approach. In Proceedings of the 27th International Conference on Machine Learning (ICML-10). J. F\u00fcrnkranz and T. Joachims, eds. (Haifa, Israel, June 21--24, 2010). Omnipress, 639--646."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065034"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/36206.36194"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451150"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594302"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509509"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(1:10)2011"},{"key":"e_1_2_1_18_1","volume-title":"Inc.","author":"Warren H.S.","year":"2002","unstructured":"Warren , H.S. Hacker's Delight . Addison-Wesley Longman Publishing Co ., Inc. , Boston, MA, USA , 2002 . Warren, H.S. Hacker's Delight. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2002."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2863701","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2863701","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:03:34Z","timestamp":1750273414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2863701"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,25]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,1,25]]}},"alternative-id":["10.1145\/2863701"],"URL":"https:\/\/doi.org\/10.1145\/2863701","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2016,1,25]]},"assertion":[{"value":"2016-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}