{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:22Z","timestamp":1750306102041,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T00:00:00Z","timestamp":1507766400000},"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":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2017,10,12]]},"abstract":"<jats:p>Heterogeneous architectures characterize today hardware ranging from super-computers to smartphones. However, in spite of this importance, programming such systems is still challenging. In particular, it is challenging to map computations to the different processors of a heterogeneous device. In this paper, we provide a static analysis that mitigates this problem. Our contributions are two-fold: first, we provide a semi-context-sensitive algorithm, which analyzes the program's call graph to determine the best processor for each calling context. This algorithm is parameterized by a cost model, which takes into consideration processor's characteristics and data transfer time. Second, we show how to use simulated annealing to calibrate this cost model for a given heterogeneous architecture. We have used our ideas to build Etino, a tool that annotates C programs with OpenACC or OpenMP 4.0 directives. Etino generates code for a CPU-GPU architecture without user intervention. Experiments on classic benchmarks reveal speedups of up to 75x. Moreover, our calibration process lets avoid slowdowns of up to 720x which trivial parallelization approaches would yield.<\/jats:p>","DOI":"10.1145\/3133874","type":"journal-article","created":{"date-parts":[[2017,10,13]],"date-time":"2017-10-13T15:15:45Z","timestamp":1507907745000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Static placement of computation on heterogeneous devices"],"prefix":"10.1145","volume":"1","author":[{"given":"Gabriel","family":"Poesia","sequence":"first","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Breno","family":"Guimar\u00e3es","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabr\u00edcio","family":"Ferracioli","sequence":"additional","affiliation":[{"name":"LG Electronics, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,10,12]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"2006","unstructured":"Alfred V. Aho , Monica S. Lam , Ravi Sethi , and Jeffrey D . Ullman . 2006 . Compilers : Principles, Techniques, and Tools (2nd Edition). Addison Wesley , Boston, MA, USA. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, Boston, MA, USA."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858965.2814285"},{"key":"e_1_2_2_3_1","unstructured":"M. Amini C. Ancourt F. Coelho B. Creusillet S. Guelton F. Irigoin P. Jouvelot R. Keryell and P. Villalon. 2012. PIPS Is not (only) Polyhedral Software. Technical Report. IMPACT.  M. Amini C. Ancourt F. Coelho B. Creusillet S. Guelton F. Irigoin P. Jouvelot R. Keryell and P. Villalon. 2012. PIPS Is not (only) Polyhedral Software. Technical Report. IMPACT."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721654.1721672"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1631"},{"key":"e_1_2_2_6_1","volume-title":"Quintana-Ort\u00ed","author":"Ayguad\u00e9 Eduard","year":"2009","unstructured":"Eduard Ayguad\u00e9 , Rosa M. Badia , Francisco D. Igual , Jes\u00fas Labarta , Rafael Mayo , and Enrique S . Quintana-Ort\u00ed . 2009 . An Extension of the StarSs Programming Model for Platforms with Multiple GP Us. In Euro-Par. Springer , Heidelberg, Germany, 851\u2013862. Eduard Ayguad\u00e9, Rosa M. Badia, Francisco D. Igual, Jes\u00fas Labarta, Rafael Mayo, and Enrique S. Quintana-Ort\u00ed. 2009. An Extension of the StarSs Programming Model for Platforms with Multiple GP Us. In Euro-Par. Springer, Heidelberg, Germany, 851\u2013862."},{"key":"e_1_2_2_7_1","volume-title":"FPGA Programming for the Masses. Queue 11, 2","author":"Bacon David","year":"2013","unstructured":"David Bacon , Rodric Rabbah , and Sunil Shukla . 2013. FPGA Programming for the Masses. Queue 11, 2 ( 2013 ), 40:40\u201340:52. David Bacon, Rodric Rabbah, and Sunil Shukla. 2013. FPGA Programming for the Masses. Queue 11, 2 (2013), 40:40\u201340:52."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2016.711"},{"volume-title":"CGO","author":"Barik Rajkishore","key":"e_1_2_2_9_1","unstructured":"Rajkishore Barik , Naila Farooqui , Brian T. Lewis , Chunling Hu , and Tatiana Shpeisman . 2016. A Black-box Approach to Energy-aware Scheduling on Integrated CP U-GP U Systems . In CGO . ACM , New York, NY, USA , 70\u201381. Rajkishore Barik, Naila Farooqui, Brian T. Lewis, Chunling Hu, and Tatiana Shpeisman. 2016. A Black-box Approach to Energy-aware Scheduling on Integrated CP U-GP U Systems. In CGO. ACM, New York, NY, USA, 70\u201381."},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Muthu Manikandan Baskaran J. Ramanujam and P. Sadayappan. 2010. Automatic C-to-CUDA Code Generation for Affine Programs. In CC. Springer Heidelberg Germany 244\u2013263.  Muthu Manikandan Baskaran J. Ramanujam and P. Sadayappan. 2010. Automatic C-to-CUDA Code Generation for Affine Programs. In CC. Springer Heidelberg Germany 244\u2013263.","DOI":"10.1007\/978-3-642-11970-5_14"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342013493644"},{"volume-title":"Dynamic Programming","author":"Bellman Richard Ernest","key":"e_1_2_2_12_1","unstructured":"Richard Ernest Bellman . 1957. Dynamic Programming . Princeton University Press , Princeton, NJ, USA . Richard Ernest Bellman. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ, USA."},{"volume-title":"Coordinating GP U Threads for OpenMP 4.0 in LLVM","author":"Bertolli Carlo","key":"e_1_2_2_13_1","unstructured":"Carlo Bertolli , Samuel Antao , Alexandre Eichenberger , Kevin O\u2019Brien , Zehra Sura , Arpith Jacob , Tong Chen , and Olivier Sallenave . 2014. Coordinating GP U Threads for OpenMP 4.0 in LLVM . In LLVM-HPC. IEEE , New York, NY, USA , 12\u201321. Carlo Bertolli, Samuel Antao, Alexandre Eichenberger, Kevin O\u2019Brien, Zehra Sura, Arpith Jacob, Tong Chen, and Olivier Sallenave. 2014. Coordinating GP U Threads for OpenMP 4.0 in LLVM. In LLVM-HPC. IEEE, New York, NY, USA, 12\u201321."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2012.6237020"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00940812"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294265"},{"key":"e_1_2_2_17_1","first-page":"1","article-title":"An Analysis of Accelerator Coupling in Heterogeneous Architectures. In DAC. ACM, New York","volume":"202","author":"Cota Emilio G.","year":"2015","unstructured":"Emilio G. Cota , Paolo Mantovani , Giuseppe Di Guglielmo , and Luca P. Carloni . 2015 . An Analysis of Accelerator Coupling in Heterogeneous Architectures. In DAC. ACM, New York , NY, USA , 202 : 1 \u2013 202 :6. Emilio G. Cota, Paolo Mantovani, Giuseppe Di Guglielmo, and Luca P. Carloni. 2015. An Analysis of Accelerator Coupling in Heterogeneous Architectures. In DAC. ACM, New York, NY, USA, 202:1\u2013202:6.","journal-title":"NY, USA"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2012.09.006"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1383422.1383447"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2008.57"},{"volume-title":"Efficient Parallel Algorithms","author":"Gibbons Alan","key":"e_1_2_2_21_1","unstructured":"Alan Gibbons . 1988. Efficient Parallel Algorithms . Cambridge University Press, Cambridge , UK. Alan Gibbons. 1988. Efficient Parallel Algorithms. Cambridge University Press, Cambridge, UK."},{"volume-title":"Beyond Do Loops: Data Transfer Generation with Convex Array Regions","author":"Guelton Serge","key":"e_1_2_2_22_1","unstructured":"Serge Guelton , Mehdi Amini , and B\u00e9atrice Creusillet . 2012. Beyond Do Loops: Data Transfer Generation with Convex Array Regions . In LCPC. Springer , Heidelberg, Germany , 249\u2013263. Serge Guelton, Mehdi Amini, and B\u00e9atrice Creusillet. 2012. Beyond Do Loops: Data Transfer Generation with Convex Array Regions. In LCPC. Springer, Heidelberg, Germany, 249\u2013263."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70545-1_35"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161004"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854047"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1296907.1296909"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.09.001"},{"volume-title":"IJCAI. Morgan Kaufmann","author":"Kohavi Ron","key":"e_1_2_2_28_1","unstructured":"Ron Kohavi . 1995. A Study of Cross-validation and Bootstrap for Accuracy Estimation and Model Selection . In IJCAI. Morgan Kaufmann , Burlington, MA, USA , 1137\u20131143. Ron Kohavi. 1995. A Study of Cross-validation and Bootstrap for Accuracy Estimation and Model Selection. In IJCAI. Morgan Kaufmann, Burlington, MA, USA, 1137\u20131143."},{"key":"e_1_2_2_29_1","volume-title":"IPMACC: Open Source OpenACC to CUDA\/OpenCL Translator. CoRR abs\/1412.1127","author":"Lashgar Ahmad","year":"2014","unstructured":"Ahmad Lashgar , Alireza Majidi , and Amirali Baniasadi . 2014 . IPMACC: Open Source OpenACC to CUDA\/OpenCL Translator. CoRR abs\/1412.1127 (2014), 1\u20139. Ahmad Lashgar, Alireza Majidi, and Amirali Baniasadi. 2014. IPMACC: Open Source OpenACC to CUDA\/OpenCL Translator. CoRR abs\/1412.1127 (2014), 1\u20139."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_5"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2015.11.012"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854040"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084540"},{"volume-title":"SBAC-PAD","author":"Mendon\u00e7a Gleison","key":"e_1_2_2_35_1","unstructured":"Gleison Mendon\u00e7a , Breno Guimaraes , P\u00e9ricles Alves , M\u00e1rcio Pereira , Guido Ara\u00fajo , and Fernando Magno Quint ao Pereira . 2016. Automatic Insertion of Copy Annotation in Data-Parallel Programs . In SBAC-PAD . ACM , New York, NY, USA , 1\u20138. Gleison Mendon\u00e7a, Breno Guimaraes, P\u00e9ricles Alves, M\u00e1rcio Pereira, Guido Ara\u00fajo, and Fernando Magno Quint ao Pereira. 2016. Automatic Insertion of Copy Annotation in Data-Parallel Programs. In SBAC-PAD. ACM, New York, NY, USA, 1\u20138."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806631"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2954679.2872411"},{"key":"e_1_2_2_38_1","first-page":"56","article-title":"The GP U Computing Era","volume":"30","author":"Nickolls John","year":"2010","unstructured":"John Nickolls and William J. Dally . 2010 . The GP U Computing Era . Micro 30 (2010), 56 \u2013 69 . John Nickolls and William J. Dally. 2010. The GP U Computing Era. Micro 30 (2010), 56\u201369.","journal-title":"Micro"},{"volume-title":"Graphics and Computing GPUs","author":"Nickolls John","key":"e_1_2_2_39_1","unstructured":"John Nickolls and David Kirk . 2009. Graphics and Computing GPUs . Computer Organization and Design, (Patterson and Hennessy) (4th ed.). Elsevier , Amsterdam, Netherlands, Chapter A, A.1 \u2013 A.77. John Nickolls and David Kirk. 2009. Graphics and Computing GPUs. Computer Organization and Design, (Patterson and Hennessy) (4th ed.). Elsevier, Amsterdam, Netherlands, Chapter A, A.1 \u2013 A.77."},{"key":"e_1_2_2_40_1","volume-title":"Hanne Riis Nielson, and Chris Hankin","author":"Nielson Flemming","year":"2005","unstructured":"Flemming Nielson , Hanne Riis Nielson, and Chris Hankin . 2005 . Principles of program analysis. Springer , Heidelberg, Germany. Flemming Nielson, Hanne Riis Nielson, and Chris Hankin. 2005. Principles of program analysis. Springer, Heidelberg, Germany."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.13"},{"key":"e_1_2_2_42_1","volume-title":"Bones: An Automatic Skeleton-Based C-to-CUDA Compiler for GP Us. TACO 11, 4","author":"Cedric Nugteren and Henk Corp","year":"2014","unstructured":"Cedric Nugteren and Henk Corp oraal. 2014 . Bones: An Automatic Skeleton-Based C-to-CUDA Compiler for GP Us. TACO 11, 4 (2014), 35:1\u201335:25. Cedric Nugteren and Henk Corporaal. 2014. Bones: An Automatic Skeleton-Based C-to-CUDA Compiler for GP Us. TACO 11, 4 (2014), 35:1\u201335:25."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2015.7056037"},{"key":"e_1_2_2_44_1","unstructured":"PGI. 2016. Compiler User\u2019s Guide. (2016). http:\/\/www.pgroup.com\/ doc\/pgiug.pdf.  PGI. 2016. Compiler User\u2019s Guide. (2016). http:\/\/www.pgroup.com\/ doc\/pgiug.pdf."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628077"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057387.1057388"},{"key":"e_1_2_2_47_1","article-title":"Divergence Analysis","volume":"35","author":"Sampaio Diogo","year":"2014","unstructured":"Diogo Sampaio , Rafael Martins de Souza , Sylvain Collange , and Fernando Magno Quint\u00e3o Pereira . 2014 . Divergence Analysis . ACM Trans. Program. Lang. Syst. 35 , 4, Article 13 (2014), 36 pages. Diogo Sampaio, Rafael Martins de Souza, Sylvain Collange, and Fernando Magno Quint\u00e3o Pereira. 2014. Divergence Analysis. ACM Trans. Program. Lang. Syst. 35, 4, Article 13 (2014), 36 pages.","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2016598.2016600"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.54007"},{"volume-title":"PPoPP","author":"Sim Jaewoong","key":"e_1_2_2_50_1","unstructured":"Jaewoong Sim , Aniruddha Dasgupta , Hyesoon Kim , and Richard Vuduc . 2012. A Performance Analysis Framework for Identifying Potential Benefits in GPGP U Applications . In PPoPP . ACM , New York, NY, USA , 11\u201322. Jaewoong Sim, Aniruddha Dasgupta, Hyesoon Kim, and Richard Vuduc. 2012. A Performance Analysis Framework for Identifying Potential Benefits in GPGP U Applications. In PPoPP. ACM, New York, NY, USA, 11\u201322."},{"volume-title":"DAC. ACM","author":"Singh Amit Kumar","key":"e_1_2_2_51_1","unstructured":"Amit Kumar Singh , Muhammad Shafique , Akash Kumar , and J\u00f6rg Henkel . 2013. Mapping on Multi\/Many-core Systems: Survey of Current and Emerging Trends . In DAC. ACM , New York, NY, USA , Article 1, 10 pages. Amit Kumar Singh, Muhammad Shafique, Akash Kumar, and J\u00f6rg Henkel. 2013. Mapping on Multi\/Many-core Systems: Survey of Current and Emerging Trends. In DAC. ACM, New York, NY, USA, Article 1, 10 pages."},{"key":"e_1_2_2_52_1","volume-title":"Cameron","author":"Song Shuaiwen","year":"2013","unstructured":"Shuaiwen Song , Chunyi Su , Barry Rountree , and Kirk W . Cameron . 2013 . A Simplified and Accurate Model of PowerPerformance Efficiency on Emergent GP U Architectures. In IPDPS. IEEE, New York, NY, USA , 673\u2013686. Shuaiwen Song, Chunyi Su, Barry Rountree, and Kirk W. Cameron. 2013. A Simplified and Accurate Model of PowerPerformance Efficiency on Emergent GP U Architectures. In IPDPS. IEEE, New York, NY, USA, 673\u2013686."},{"key":"e_1_2_2_53_1","volume-title":"Henrique Nazar\u00e9 Santos, and Fernando Magno Quint\u00e3o Pereira.","author":"Sperle Campos Victor Hugo","year":"2016","unstructured":"Victor Hugo Sperle Campos , P\u00e9ricles Rafael Alves , Henrique Nazar\u00e9 Santos, and Fernando Magno Quint\u00e3o Pereira. 2016 . Restrictification of Function Arguments. In CC. ACM, New York, NY, USA , 163\u2013173. Victor Hugo Sperle Campos, P\u00e9ricles Rafael Alves, Henrique Nazar\u00e9 Santos, and Fernando Magno Quint\u00e3o Pereira. 2016. Restrictification of Function Arguments. In CC. ACM, New York, NY, USA, 163\u2013173."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2010.69"},{"key":"e_1_2_2_55_1","volume-title":"Albert Cohen, Jos\u00e9 Ignacio G\u00f3mez, Christian Tenllado, and Francky Catthoor.","author":"Verdoolaege Sven","year":"2013","unstructured":"Sven Verdoolaege , Juan Carlos Juega , Albert Cohen, Jos\u00e9 Ignacio G\u00f3mez, Christian Tenllado, and Francky Catthoor. 2013 . Polyhedral Parallel Code Generation for CUDA. TACO 9, 4 (2013), 54:1\u201354:23. Sven Verdoolaege, Juan Carlos Juega, Albert Cohen, Jos\u00e9 Ignacio G\u00f3mez, Christian Tenllado, and Francky Catthoor. 2013. Polyhedral Parallel Code Generation for CUDA. TACO 9, 4 (2013), 54:1\u201354:23."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038228.3038235"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"key":"e_1_2_2_58_1","volume-title":"High Performance Compilers for Parallel Computing","author":"Wolfe Michael","unstructured":"Michael Wolfe . 1996. High Performance Compilers for Parallel Computing ( 1 st ed.). Adison-Wesley , Boston, MA, USA . Michael Wolfe. 1996. High Performance Compilers for Parallel Computing (1st ed.). Adison-Wesley, Boston, MA, USA.","edition":"1"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.56"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2959689.2960086"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1577129.1577132"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133874","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3133874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:34Z","timestamp":1750217434000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,12]]},"references-count":61,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2017,10,12]]}},"alternative-id":["10.1145\/3133874"],"URL":"https:\/\/doi.org\/10.1145\/3133874","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2017,10,12]]},"assertion":[{"value":"2017-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}