{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T17:43:48Z","timestamp":1785001428200,"version":"3.55.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T00:00:00Z","timestamp":1590796800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T00:00:00Z","timestamp":1590796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["01|H13004A"],"award-info":[{"award-number":["01|H13004A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Priority Programme 1648"],"award-info":[{"award-number":["Priority Programme 1648"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The need for parallel task execution has been steadily growing in recent years since manufacturers mainly improve processor performance by increasing the number of installed cores instead of scaling the processor\u2019s frequency. To make use of this potential, an essential technique to increase the parallelism of a program is to parallelize loops. Several<jats:italic>automatic loop nest parallelizers<\/jats:italic>have been developed in the past such as PluTo. The main restriction of these tools is that the loops must be statically analyzable which, among other things, disallows function calls within the loops. In this article, we present a seemingly simple extension to the C programming language which marks functions without side-effects. These functions can then basically be ignored when the automatic parallelizer checks the parallelizability of loops. We integrated the approach into the GCC compiler toolchain and evaluated it by running several real-world applications. Our experiments show that the C extension helps to identify additional parallelization opportunities and, thus, to significantly increase the performance of applications.<\/jats:p>","DOI":"10.1007\/s10766-020-00660-4","type":"journal-article","created":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T04:26:27Z","timestamp":1590812787000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Pure Functions in C: A Small Keyword for Automatic Parallelization"],"prefix":"10.1007","volume":"49","author":[{"given":"Tim","family":"S\u00fc\u00df","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lars","family":"Nagel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc-Andr\u00e9","family":"Vef","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9","family":"Brinkmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dustin","family":"Feld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Soddemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,30]]},"reference":[{"issue":"2","key":"660_CR1","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1145\/3282307","volume":"62","author":"JL Hennessy","year":"2019","unstructured":"Hennessy, J.L., Patterson, D.A.: A new golden age for computer architecture. Commun. ACM 62(2), 48\u201360 (2019). https:\/\/doi.org\/10.1145\/3282307","journal-title":"Commun. ACM"},{"issue":"1","key":"660_CR2","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/99.660313","volume":"5","author":"L Dagum","year":"1998","unstructured":"Dagum, L., Menon, R.: Openmp: an industry-standard API for shared-memory programming. IEEE Comput. Sci. Eng. 5(1), 46\u201355 (1998)","journal-title":"IEEE Comput. Sci. Eng."},{"key":"660_CR3","unstructured":"The OpenACC Application Program Interface. Version 2.5 (2012). http:\/\/www.openacc-standard.org\/"},{"key":"660_CR4","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E.: The cilk++ concurrency platform. In: Proceedings of the 46th Annual Design Automation Conference, DAC \u201909, pp. 522\u2013527 (2009)","DOI":"10.1145\/1629911.1630048"},{"key":"660_CR5","unstructured":"SILKAN: HPC project. Par4All automatic parallelization (2012). http:\/\/www.par4all.org"},{"key":"660_CR6","unstructured":"Amini, M., Ancourt, C., Coelho, F., Creusillet, B., Guelton, S., Irigoin, F., Jouvelot, P., Keryell, R., Villalon, P.: PIPS is not (just) polyhedral software adding GPU code generation in PIPS. In: First Int. Workshop on Polyhedral Compilation Techniques (IMPACT 2011) in Conjonction with CGO 2011 (2011)"},{"key":"660_CR7","doi-asserted-by":"crossref","unstructured":"Bondhugula, U., Ramanujam, J., Sadayappan, P.: Pluto: a practical and fully automatic polyhedral parallelizer and locality optimizer. Tech. Rep. OSU-CISRC-10\/07-TR70, The Ohio State University (2007)","DOI":"10.1145\/1375581.1375595"},{"issue":"4","key":"660_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2400682.2400713","volume":"9","author":"S Verdoolaege","year":"2013","unstructured":"Verdoolaege, S., Juega, J.C., Cohen, A., G\u00f3mez, J.I., Tenllado, C., Catthoor, F.: Polyhedral parallel code generation for CUDA. ACM Trans. Archit. Code Optim. 9(4), 1\u201323 (2013). https:\/\/doi.org\/10.1145\/2400682.2400713. (Selected for presentation at the HiPEAC 2013 Conf)","journal-title":"ACM Trans. Archit. Code Optim."},{"key":"660_CR9","unstructured":"Feld, D., Soddemann, T., J\u00fcnger, M., Mallach, S.: Facilitate SIMD-code-generation in the polyhedral model by hardware-aware automatic code-transformation. In: Gr\u00f6\u00dfliger, A., Pouchet, L.N. (eds.) Proceedings of the 3rd International Workshop on Polyhedral Compilation Techniques, pp. 45\u201354 (2013)"},{"key":"660_CR10","doi-asserted-by":"publisher","unstructured":"Feld, D., Soddemann, T., J\u00fcnger, M., Mallach, S.: Hardware-aware automatic code-transformation to support compilers in exploiting the multi-level parallel potential of modern cpus. In: Proceedings of the 2015 International Workshop on Code Optimisation for Multi and Many Cores, COSMIC \u201915, San Francisco Bay Area, 8 Feb 2015, pp. 2:1\u20132:10 (2015). https:\/\/doi.org\/10.1145\/2723772.2723776","DOI":"10.1145\/2723772.2723776"},{"key":"660_CR11","doi-asserted-by":"crossref","unstructured":"Strout, M.M., Georg, G., Olschanowsky, C.: Set and relation manipulation for the sparse polyhedral framework. In: Kasahara, H., Kimura, K. (eds.) Languages and Compilers for Parallel Computing: 25th International Workshop, LCPC 2012, pp. 61\u201375 (2013)","DOI":"10.1007\/978-3-642-37658-0_5"},{"key":"660_CR12","doi-asserted-by":"crossref","unstructured":"Bastoul, C., Cohen, A., Girbal, S., Sharma, S., Temam, O.: Putting polyhedral loop transformations to work. In: 16th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2003, pp. 209\u2013225 (2003)","DOI":"10.1007\/978-3-540-24644-2_14"},{"issue":"9","key":"660_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/2544174.2500605","volume":"48","author":"L Petersen","year":"2013","unstructured":"Petersen, L., Orchard, D., Glew, N.: Automatic simd vectorization for haskell. SIGPLAN Not. 48(9), 25\u201336 (2013)","journal-title":"SIGPLAN Not."},{"issue":"9","key":"660_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/1631687.1596563","volume":"44","author":"S Marlow","year":"2009","unstructured":"Marlow, S., Peyton Jones, S., Singh, S.: Runtime support for multicore haskell. SIGPLAN Not. 44(9), 65\u201378 (2009)","journal-title":"SIGPLAN Not."},{"key":"660_CR15","doi-asserted-by":"crossref","unstructured":"Gill, A., Runciman, C.: Haskell program coverage. In: Proceedings of the ACM SIGPLAN Workshop on Haskell Workshop, Haskell \u201907, pp. 1\u201312 (2007)","DOI":"10.1145\/1291201.1291203"},{"key":"660_CR16","unstructured":"Corporation, I.: Intel Fortran language reference. Document number: 253261-002 (2001)"},{"issue":"2","key":"660_CR17","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1080399.1080400","volume":"24","author":"RW Numrich","year":"2005","unstructured":"Numrich, R.W., Reid, J.: Co-arrays in the next fortran standard. SIGPLAN Fortran Forum 24(2), 4\u201317 (2005)","journal-title":"SIGPLAN Fortran Forum"},{"issue":"1","key":"660_CR18","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/2754942.2754944","volume":"34","author":"A Shterenlikht","year":"2015","unstructured":"Shterenlikht, A., Margetts, L., Cebamanos, L., Henty, D.: Fortran 2008 coarrays. SIGPLAN Fortran Forum 34(1), 10\u201330 (2015)","journal-title":"SIGPLAN Fortran Forum"},{"key":"660_CR19","unstructured":"ARM compiler toolchain compiler reference\u2014compiler-specific features (2015). http:\/\/infocenter.arm.com\/help\/topic\/com.arm.doc.dui0491c\/CHDFIJAE.html"},{"issue":"11","key":"660_CR20","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/2018396.2018415","volume":"54","author":"K Kennedy","year":"2011","unstructured":"Kennedy, K., Koelbel, C., Zima, H.: The rise and fall of high performance fortran. Commun. ACM 54(11), 74\u201382 (2011)","journal-title":"Commun. ACM"},{"key":"660_CR21","doi-asserted-by":"crossref","unstructured":"Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer. In: Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation (PLDI), pp. 101\u2013113 (2008)","DOI":"10.1145\/1379022.1375595"},{"issue":"12","key":"660_CR22","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.J., Lee, S., Eigenmann, R., Midkiff, S.: Cetus: a source-to-source compiler infrastructure for multicores. Computer 42(12), 36\u201342 (2009). https:\/\/doi.org\/10.1109\/MC.2009.385","journal-title":"Computer"},{"key":"660_CR23","doi-asserted-by":"crossref","unstructured":"Schordan, M., Quinlan, D.J.: A source-to-source architecture for user-defined optimizations. In: JMLC, pp. 214\u2013223 (2003)","DOI":"10.1007\/978-3-540-45213-3_27"},{"key":"660_CR24","unstructured":"Bastoul, C.: Extracting polyhedral representation from high level languages. LRI, Paris-Sud University, Tech. rep. (2008)"},{"key":"660_CR25","unstructured":"Bastoul, C.: Openscop: a specification and a library for data exchange in polyhedral compilation tools. Paris-Sud University, France, Tech. rep. (2011)"},{"key":"660_CR26","unstructured":"Bastoul, C.: Generating loops for scanning polyhedra. Tech. Rep. 2002\/23, PRiSM, Versailles University (2002)"},{"key":"660_CR27","doi-asserted-by":"publisher","unstructured":"Verdoolaege, S.: isl: an integer set library for the polyhedral model. In: Fukuda, K., van\u00a0der Hoeven, J., Joswig, M., Takayama, N. (eds.) Lecture Notes in Computer Science, pp. 299\u2013302 (2010). https:\/\/doi.org\/10.1007\/978-3-642-15582-6_49. https:\/\/lirias.kuleuven.be\/handle\/123456789\/270231","DOI":"10.1007\/978-3-642-15582-6_49"},{"key":"660_CR28","unstructured":"Polylib\u2013a library of polyhedral functions. (1012). http:\/\/www.irisa.fr\/polylib\/"},{"key":"660_CR29","unstructured":"Feautrier, P., Collard, J., Bastoul, C.: Solving systems of affine (in)equalities. PRiSM, Versailles University, Tech. rep. (2002)"},{"key":"660_CR30","unstructured":"Grosser, T., Zheng, H., Aloor, R., Simb\u00fcrger, A., Gr\u00f6sslinger, A., Pouchet, L.N.: Polly-polyhedral optimization in LLVM. In: First International Workshop on Polyhedral Compilation Techniques (IMPACT\u201911) (2011)"},{"key":"660_CR31","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF01407835","volume":"21","author":"P Feautrier","year":"1992","unstructured":"Feautrier, P.: Some efficient solutions to the affine scheduling problem: I. One-dimensional time. Int. J. Parallel Program. 21, 313\u2013348 (1992). https:\/\/doi.org\/10.1007\/BF01407835","journal-title":"Int. J. Parallel Program."},{"key":"660_CR32","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10766-006-0012-3","volume":"34","author":"S Girbal","year":"2006","unstructured":"Girbal, S., Vasilache, N., Bastoul, C., Cohen, A., Parello, D., Sigler, M., Temam, O.: Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies. Int. J. Parallel Program. 34, 261\u2013317 (2006)","journal-title":"Int. J. Parallel Program."},{"key":"660_CR33","volume-title":"Automatic Parallelization of Loop Programs for Distributed Memory Architectures","author":"M Griebl","year":"2004","unstructured":"Griebl, M.: Automatic Parallelization of Loop Programs for Distributed Memory Architectures. University Passau, Habilitation (2004)"},{"key":"660_CR34","doi-asserted-by":"crossref","unstructured":"Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer. In: Proc. 2008 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI \u201908, pp. 101\u2013113. ACM (2008)","DOI":"10.1145\/1375581.1375595"},{"key":"660_CR35","series-title":"Kluwer Int. Series in Engineering and Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4337-4","volume-title":"Loop Tiling for Parallelism","author":"J Xue","year":"2000","unstructured":"Xue, J.: Loop Tiling for Parallelism. Kluwer Int. Series in Engineering and Computer Science. Kluwer Academic, New York (2000)"},{"key":"660_CR36","doi-asserted-by":"crossref","unstructured":"Heintze, N., Tardieu, O.: Ultra-fast aliasing analysis using CLA: A million lines of c code in a second. In: Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI \u201901, pp. 254\u2013263 (2001)","DOI":"10.1145\/378795.378855"},{"key":"660_CR37","doi-asserted-by":"crossref","unstructured":"Xu, Z., Kremenek, T., Zhang, J.: Leveraging Applications of Formal Methods, Verification, and Validation: 4th International Symposium on Leveraging Applications, ISoLA 2010, chap. A Memory Model for Static Analysis of C Programs, pp. 535\u2013548 (2010)","DOI":"10.1007\/978-3-642-16558-0_44"},{"key":"660_CR38","doi-asserted-by":"crossref","unstructured":"Gad, R., S\u00fc\u00df, T., Brinkmann, A.: Compiler driven automatic kernel context migration for heterogeneous computing. In: 34th International Conference on Distributed Computing Systems (ICDCS) (2014)","DOI":"10.1109\/ICDCS.2014.47"},{"issue":"2\u20133","key":"660_CR39","first-page":"211","volume":"28","author":"J Kraus","year":"2013","unstructured":"Kraus, J., F\u00f6rster, M., Brandes, T., Soddemann, T.: Using lama for efficient amg on hybrid clusters. Comput. Sci. R&D 28(2\u20133), 211\u2013220 (2013)","journal-title":"Comput. Sci. R&D"},{"issue":"3","key":"660_CR40","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1080\/01431161.2011.577832","volume":"33","author":"Y Wang","year":"2012","unstructured":"Wang, Y., Xue, Y., Li, Y., Guang, J., Mei, L., Xu, H., Ai, J.: Prior knowledge-supported aerosol optical depth retrieval over land surfaces at 500 m spatial resolution with modis data. Int. J. Remote Sens. 33(3), 674\u2013691 (2012). https:\/\/doi.org\/10.1080\/01431161.2011.577832","journal-title":"Int. J. Remote Sens."},{"issue":"5","key":"660_CR41","doi-asserted-by":"publisher","first-page":"2306","DOI":"10.1109\/JSTARS.2015.2438893","volume":"8","author":"J Liu","year":"2015","unstructured":"Liu, J., Feld, D., Xue, Y., Garcke, J., Soddemann, T.: Multicore processors and graphics processing unit accelerators for parallel retrieval of aerosol optical depth from satellite data: implementation, performance, and energy efficiency. IEEE J. Sel. Top. Appl. Earth Observ. Remote Sens. 8(5), 2306\u20132317 (2015). https:\/\/doi.org\/10.1109\/JSTARS.2015.2438893","journal-title":"IEEE J. Sel. Top. Appl. Earth Observ. Remote Sens."},{"key":"660_CR42","unstructured":"Stallman, R.M., DeveloperCommunity, G.: Using the GNU Compiler Collection: A GNU Manual for GCC Version 4.4.7. CreateSpace, Paramount, CA (2009)"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-020-00660-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-020-00660-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-020-00660-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T18:24:56Z","timestamp":1696184696000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-020-00660-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,30]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["660"],"URL":"https:\/\/doi.org\/10.1007\/s10766-020-00660-4","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,30]]},"assertion":[{"value":"8 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}