Distributing and Parallelizing Non-canonical Loops

Clément Aubert, Thomas Rubiano, Neea Rusch, Thomas Seiller

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This work leverages an original dependency analysis to parallelize loops regardless of their form in imperative programs. Our algorithm distributes a loop into multiple parallelizable loops, resulting in gains in execution time comparable to state-of-the-art automatic source-to-source code transformers when both are applicable. Our graph-based algorithm is intuitive, language-agnostic, proven correct, and applicable to all types of loops. Importantly, it can be applied even if the loop iteration space is unknown statically or at compile time, or more generally if the loop is not in canonical form or contains loop-carried dependency. As contributions we deliver the computational technique, proof of its preservation of semantic correctness, and experimental results to quantify the expected performance gains. We also show that many comparable tools cannot distribute the loops we optimize, and that our technique can be seamlessly integrated into compiler passes or other automatic parallelization suites.

Original languageEnglish (US)
Title of host publicationVerification, Model Checking, and Abstract Interpretation - 24th International Conference, VMCAI 2023, Proceedings
EditorsCezara Dragoi, Michael Emmi, Jingbo Wang
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages24
ISBN (Print)9783031249495
StatePublished - 2023
Event24th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2023 - Boston, United States
Duration: Jan 16 2023Jan 17 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13881 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2023
Country/TerritoryUnited States


  • Abstract interpretation
  • Automatic parallelization
  • Dependency analysis
  • Loop optimization
  • Program analysis
  • Program transformation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Distributing and Parallelizing Non-canonical Loops'. Together they form a unique fingerprint.

Cite this