{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:39:15Z","timestamp":1742920755972,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031249495"},{"type":"electronic","value":"9783031249501"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-24950-1_1","type":"book-chapter","created":{"date-parts":[[2023,1,16]],"date-time":"2023-01-16T14:03:19Z","timestamp":1673877799000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Distributing and\u00a0Parallelizing Non-canonical Loops"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6346-3043","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Aubert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Rubiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7354-5330","authenticated-orcid":false,"given":"Neea","family":"Rusch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6313-0898","authenticated-orcid":false,"given":"Thomas","family":"Seiller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,17]]},"reference":[{"issue":"1","key":"1_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0956796801004191","volume":"12","author":"A Abel","year":"2002","unstructured":"Abel, A., Altenkirch, T.: A predicative analysis of structural recursion. J. Funct. Program. 12(1), 1\u201341 (2002). https:\/\/doi.org\/10.1017\/S0956796801004191","journal-title":"J. Funct. Program."},{"issue":"5","key":"1_CR2","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1109\/TC.1981.1675792","volume":"30","author":"W Abu-Sufah","year":"1981","unstructured":"Abu-Sufah, W., Kuck, D.J., Lawrie, D.H.: On the performance enhancement of paging systems through program analysis and transformations. IEE Trans. Comput. 30(5), 341\u2013356 (1981). https:\/\/doi.org\/10.1109\/TC.1981.1675792","journal-title":"IEE Trans. Comput."},{"key":"1_CR3","volume-title":"Compilers: Principles, Techniques, and Tools","author":"AV Aho","year":"2006","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison Wesley, Boston (2006)","edition":"2"},{"key":"1_CR4","unstructured":"Amini, M.: Source-to-source automatic program transformations for GPU-like hardware accelerators. Theses, Ecole Nationale Sup\u00e9rieure des Mines de Paris, December 2012. https:\/\/pastel.archives-ouvertes.fr\/pastel-00958033"},{"key":"1_CR5","unstructured":"Amini, M., et al.: Par4All: from convex array regions to heterogeneous computing. In: IMPACT 2012 : Second International Workshop on Polyhedral Compilation Techniques HiPEAC 2012. Paris, France, January 2012. https:\/\/hal-mines-paristech.archives-ouvertes.fr\/hal- 00744733"},{"issue":"9","key":"1_CR6","doi-asserted-by":"publisher","first-page":"6753","DOI":"10.1007\/s11227-019-03109-9","volume":"76","author":"H Arabnejad","year":"2019","unstructured":"Arabnejad, H., Bispo, J., Cardoso, J.M.P., Barbosa, J.G.: Source-to-source compilation targeting OpenMP-based automatic parallelization of C applications. J. Supercomput. 76(9), 6753\u20136785 (2019). https:\/\/doi.org\/10.1007\/s11227-019-03109-9","journal-title":"J. Supercomput."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Aubert, C., Rubiano, T., Rusch, N., Seiller, T.: A novel loop fission technique inspired by implicit computational complexity, May 2022. https:\/\/hal.archives-ouvertes.fr\/hal-03669387v1. draft","DOI":"10.1007\/978-3-031-24950-1_1"},{"key":"1_CR8","doi-asserted-by":"publisher","unstructured":"Aubert, C., Rubiano, T., Rusch, N., Seiller, T.: Loop fission benchmarks (2022). https:\/\/doi.org\/10.5281\/zenodo.7080145. https:\/\/github.com\/statycc\/loop-fission","DOI":"10.5281\/zenodo.7080145"},{"key":"1_CR9","doi-asserted-by":"publisher","unstructured":"Aubert, C., Rubiano, T., Rusch, N., Seiller, T.: MWP-analysis improvement and implementation: realizing implicit computational complexity. In: Felty, A.P. (ed.) 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022). Leibniz International Proceedings in Informatics, vol. 228, pp. 26:1\u201326:23. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.FSCD.2022.26","DOI":"10.4230\/LIPIcs.FSCD.2022.26"},{"key":"1_CR10","unstructured":"Aubert, C., Rubiano, T., Rusch, N., Seiller, T.: pymwp: MWP analysis in Python, September 2022. https:\/\/github.com\/statycc\/pymwp\/"},{"issue":"6","key":"1_CR11","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1007\/s10766-012-0211-z","volume":"41","author":"H Bae","year":"2013","unstructured":"Bae, H., et al.: The Cetus source-to-source compiler infrastructure: overview and evaluation. Int. J. Parallel Program. 41(6), 753\u2013767 (2013). https:\/\/doi.org\/10.1007\/s10766-012-0211-z","journal-title":"Int. J. Parallel Program."},{"key":"1_CR12","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., Katoen, J., Larsen, K.: Principles of Model Checking. MIT Press, Cambridge (2008)"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-642-11970-5_16","volume-title":"Compiler Construction","author":"M-W Benabderrahmane","year":"2010","unstructured":"Benabderrahmane, M.-W., Pouchet, L.-N., Cohen, A., Bastoul, C.: The polyhedral model is more widely applicable than you think. In: Gupta, R. (ed.) CC 2010. LNCS, vol. 6011, pp. 283\u2013303. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11970-5_16"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-319-98521-3_4","volume-title":"Evolving OpenMP for Evolving Architectures","author":"I Bertolacci","year":"2018","unstructured":"Bertolacci, I., Strout, M.M., de Supinski, B.R., Scogland, T.R.W., Davis, E.C., Olschanowsky, C.: Extending OpenMP to facilitate loop optimization. In: de Supinski, B.R., Valero-Lara, P., Martorell, X., Mateo Bellido, S., Labarta, J. (eds.) IWOMP 2018. LNCS, vol. 11128, pp. 53\u201365. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98521-3_4"},{"issue":"6","key":"1_CR15","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1145\/1379022.1375595","volume":"43","author":"U Bondhugula","year":"2008","unstructured":"Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral Parallelizer and locality optimizer. SIGPLAN Not. 43(6), 101\u2013113 (2008). https:\/\/doi.org\/10.1145\/1379022.1375595","journal-title":"SIGPLAN Not."},{"issue":"2","key":"1_CR16","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0012-365X(80)90109-0","volume":"30","author":"FRK Chung","year":"1980","unstructured":"Chung, F.R.K.: On the coverings of graphs. Discret. Math. 30(2), 89\u201393 (1980). https:\/\/doi.org\/10.1016\/0012-365X(80)90109-0","journal-title":"Discret. Math."},{"issue":"11","key":"1_CR17","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1109\/MC.2009.385","volume":"42","author":"C Dave","year":"2009","unstructured":"Dave, C., Bae, H., Min, S., Lee, S., Eigenmann, R., Midkiff, S.P.: Cetus: a source-to-source compiler infrastructure for multicores. Computer 42(11), 36\u201342 (2009). https:\/\/doi.org\/10.1109\/MC.2009.385","journal-title":"Computer"},{"issue":"3","key":"1_CR18","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1145\/24039.24041","volume":"9","author":"J Ferrante","year":"1987","unstructured":"Ferrante, J., Ottenstein, K.J., Warren, J.D.: The program dependence graph and its use in optimization. ACM Trans. Programm. Lang. Syst. 9(3), 319\u2013349 (1987). https:\/\/doi.org\/10.1145\/24039.24041","journal-title":"ACM Trans. Programm. Lang. Syst."},{"key":"1_CR19","unstructured":"gcc.gnu.org git - gcc.git\/blob - gcc\/tree-loop-distribution.c. https:\/\/gcc.gnu.org\/git\/?p=gcc.git;a=blob;f=gcc\/tree-loop- distribution.c;h=65aa1df4abae2c6acf40299f710bc62ee6bacc07;hb=HEAD#l39"},{"key":"1_CR20","unstructured":"Grosser, T.: Enabling Polyhedral Optimizations in LLVM. Master\u2019s thesis, Universit\u00e4t Passau, April 2011. https:\/\/polly.llvm.org\/publications\/grosser-diploma- thesis.pdf"},{"key":"1_CR21","doi-asserted-by":"publisher","unstructured":"Holewinski, J., et al.: Dynamic trace-based analysis of vectorization potential of applications. In: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2012, pp. 371\u2013382. Association for Computing Machinery, New York (2012). https:\/\/doi.org\/10.1145\/2254064.2254108","DOI":"10.1145\/2254064.2254108"},{"key":"1_CR22","unstructured":"Intel: oneTBB documentation (2022). https:\/\/oneapi-src.github.io\/oneTBB\/"},{"key":"1_CR23","unstructured":"Intel Corporation: Intel C++ Compiler Classic Developer Guide and Reference. https:\/\/www.intel.com\/content\/dam\/develop\/external\/us\/en\/ documents\/cpp_compiler_classic.pdf"},{"issue":"3","key":"1_CR24","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/321406.321418","volume":"14","author":"RM Karp","year":"1967","unstructured":"Karp, R.M., Miller, R.E., Winograd, S.: The organization of computations for uniform recurrence equations. J. ACM 14(3), 563\u2013590 (1967). https:\/\/doi.org\/10.1145\/321406.321418","journal-title":"J. ACM"},{"key":"1_CR25","unstructured":"Klemm, M., de Supinski, B.R. (eds.): OpenMP application programming interface specification version 5.2. OpenMP Architecture Review Board, November 2021. https:\/\/www.openmp.org\/wp-content\/uploads\/OpenMP-API- Specification-5-2.pdf"},{"key":"1_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/11494645_33","volume-title":"New Computational Paradigms","author":"L Kristiansen","year":"2005","unstructured":"Kristiansen, L., Jones, N.D.: The flow of data and the complexity of algorithms. In: Cooper, S.B., L\u00f6we, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol. 3526, pp. 263\u2013274. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11494645_33"},{"key":"1_CR27","doi-asserted-by":"publisher","unstructured":"Laird, J., Manzonetto, G., McCusker, G., Pagani, M.: Weighted relational models of typed lambda-calculi. In: LICS, pp. 301\u2013310. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/LICS.2013.36","DOI":"10.1109\/LICS.2013.36"},{"key":"1_CR28","doi-asserted-by":"publisher","unstructured":"Lattner, C., Adve, V.S.: LLVM: a compilation framework for lifelong program analysis & transformation. In: 2nd IEEE \/ ACM International Symposium on Code Generation and Optimization (CGO 2004), 20\u201324 March 2004, San Jose, CA, USA, pp. 75\u201388. IEEE Computer Society (2004). https:\/\/doi.org\/10.1109\/CGO.2004.1281665, https:\/\/ieeexplore.ieee.org\/xpl\/conhome\/9012\/proceeding","DOI":"10.1109\/CGO.2004.1281665"},{"key":"1_CR29","doi-asserted-by":"publisher","unstructured":"Lee, C.S., Jones, N.D., Ben-Amram, A.M.: The size-change principle for program termination. In: Hankin, C., Schmidt, D. (eds.) Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, London, UK, 17\u201319 January 2001, pp. 81\u201392. ACM (2001). https:\/\/doi.org\/10.1145\/360204.360210","DOI":"10.1145\/360204.360210"},{"key":"1_CR30","unstructured":"[loopfission]: Loop fission interference graph (fig). https:\/\/reviews.llvm.org\/D73801"},{"key":"1_CR31","doi-asserted-by":"publisher","unstructured":"Mehta, S., Lin, P., Yew, P.: Revisiting loop fusion in the polyhedral framework. In: Moreira, J.E., Larus, J.R. (eds.) ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2014, Orlando, FL, USA, 15\u201319 February 2014, pp. 233\u2013246. ACM (2014). https:\/\/doi.org\/10.1145\/2555243.2555250","DOI":"10.1145\/2555243.2555250"},{"key":"1_CR32","unstructured":"Microsoft: Parallel patterns library (PPL) (2021). https:\/\/docs.microsoft.com\/en-us\/cpp\/parallel\/concrt\/ parallel-patterns-library-ppl?view=msvc-170"},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-319-68167-2_7","volume-title":"Automated Technology for Verification and Analysis","author":"J-Y Moyen","year":"2017","unstructured":"Moyen, J.-Y., Rubiano, T., Seiller, T.: Loop quasi-invariant chunk detection. In: D\u2019Souza, D., Narayan Kumar, K. (eds.) ATVA 2017. LNCS, vol. 10482, pp. 91\u2013108. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68167-2_7"},{"key":"1_CR34","doi-asserted-by":"publisher","unstructured":"Palkowski, M., Klimek, T., Bielecki, W.: TRACO: an automatic loop nest parallelizer for numerical applications. In: Ganzha, M., Maciaszek, L.A., Paprzycki, M. (eds.) 2015 Federated Conference on Computer Science and Information Systems, FedCSIS 2015, L\u00f3dz, Poland, 13\u201316 September 2015. Annals of Computer Science and Information Systems, vol. 5, pp. 681\u2013686. IEEE (2015). https:\/\/doi.org\/10.15439\/2015F34","DOI":"10.15439\/2015F34"},{"issue":"17","key":"1_CR35","doi-asserted-by":"publisher","first-page":"e5168","DOI":"10.1002\/cpe.5168","volume":"31","author":"S Prema","year":"2019","unstructured":"Prema, S., Nasre, R., Jehadeesan, R., Panigrahi, B.: A study on popular auto-parallelization frameworks. Concurr. Comput. Pract. Exp. 31(17), e5168 (2019). https:\/\/doi.org\/10.1002\/cpe.5168","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"1_CR36","unstructured":"Quinlan, D., et al.: Rose user manual: a tool for building source-to-source translators draft user manual (version 0.9.11.115). https:\/\/rosecompiler.org\/uploads\/ROSE-UserManual.pdf"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Rauchwerger, L., Padua, D.A.: Parallelizing while loops for multiprocessor systems. In: Proceedings of the 9th International Symposium on Parallel Processing, IPPS 1995, pp. 347\u2013356. IEEE Computer Society (1995)","DOI":"10.1109\/IPPS.1995.395955"},{"key":"1_CR38","doi-asserted-by":"publisher","unstructured":"Seiller, T.: Interaction graphs: full linear logic. In: Grohe, M., Koskinen, E., Shankar, N. (eds.) Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2016, New York, NY, USA, 5\u20138 July 2016, pp. 427\u2013436. ACM (2016). https:\/\/doi.org\/10.1145\/2933575.2934568","DOI":"10.1145\/2933575.2934568"},{"key":"1_CR39","doi-asserted-by":"publisher","unstructured":"Vitorovi\u0107, A., Toma\u0161evi\u0107, M.V., Milutinovi\u0107, V.M.: Manual parallelization versus state-of-the-art parallelization techniques. In: Hurson, A. (ed.) Advances in Computers, vol. 92, pp. 203\u2013251. Elsevier (2014). https:\/\/doi.org\/10.1016\/B978-0-12-420232-0.00005-2","DOI":"10.1016\/B978-0-12-420232-0.00005-2"}],"container-title":["Lecture Notes in Computer Science","Verification, Model Checking, and Abstract Interpretation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-24950-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,12]],"date-time":"2024-10-12T09:08:42Z","timestamp":1728724122000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-24950-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031249495","9783031249501"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-24950-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"17 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"VMCAI","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Verification, Model Checking, and Abstract Interpretation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Boston, MA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 January 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 January 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"vmcai2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/vmcai-2023.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"50% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}