The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Modular divide-and-conquer parallelization of nested loops
Abstract
We propose a methodology for automatic generation of divide-and-conquer parallel implementations of sequential nested loops. We focus on a class of loops that traverse read-only multidimensional collections (lists or arrays) and compute a function over these collections. Our approach is modular, in that, the inner loop nest is abstracted away to produce a simpler loop nest for parallelization. The summarized version of the loop nest is then parallelized. The main challenge addressed by this paper is that to perform the code transformations necessary in each step, the loop nest may have to be augmented (automatically) with extra computation to make possible the abstraction and/or the parallelization tasks. We present theoretical results to justify the correctness of our modular approach, and algorithmic solutions for automation. Experimental results demonstrate that our approach can parallelize highly non-trivial loop nests efficiently.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Other research works with a complete characterization of the semantics of the original sequential computation [7, 8].”
From Automatic synthesis of parallel unix commands and pipelines with KumQuat (2022) · cites this paper as [8]
Citations
Cites
Dafny: An Automatic Program Verifier for Functional Correctness
Leino, K. R. M. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17511-4_20 · Cited by 940 · cited 1×
“To have correctness over all inputs, we use the same scheme as [11] to produce correctness proofs verified through Dafny [27].”
MethodAlur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656
Synthesis of divide and conquer parallelism for loops
Farzan, A., & Nicolet, V. (2017) · Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3062341.3062355 · Cited by 25
Self-citation
Research works printed but not linked: 37
- 10.1145/197405.197406 · DOI
- 10.5555/1025127.1025992 · DOI
- 10.1109/71.899937 · DOI
- Guy E Blelloch . 1993. Prefix sums and their applications . In Synthesis of Parallel Algorithms ( 1 st ed.). Morgan Kaufmann Publishers Inc . Guy E Blelloch. 1993. Prefix sums and their applications. In Synthesis of Parallel Algorithms (1st ed.). Morgan Kaufmann Publishers Inc.
- 10.1145/2145816.2145840 · DOI
- 10.1109/2.546612 · DOI
- 10.1109/IISWC.2008.4636091 · DOI
- 10.1109/CGO.2009.17 · DOI
- 10.1109/99.660313 · DOI
- Azadeh Farzan and Victor Nicolet. 2019. Modular Synthesis of Divide-and-Conquer Parallelism for Nested Loops (Extended Version). arXiv: cs.PL/1904.01031 Azadeh Farzan and Victor Nicolet. 2019. Modular Synthesis of Divide-and-Conquer Parallelism for Nested Loops (Extended Version). arXiv: cs.PL/1904.01031
- 10.1145/3062341.3062382 · DOI
- 10.1145/178243.178255 · DOI
- 10.5555/647709.734948 · DOI
- 10.1017/S0956796800001908 · DOI
- 10.5555/646451.692925 · DOI
- 10.1016/S0167-6423(97)00014-2 · DOI
- 10.1109/RTSS.2006.12 · DOI
- 10.5555/645609.662492 · DOI
- 10.1145/7902.7903 · DOI
- 10.1145/2983990.2983993 · DOI
- 10.1145/2908080.2908117 · DOI
- Emanuel Kitzelmann and Ute Schmid . 2006 . Inductive synthesis of functional programs: An explanation based generalization approach . Journal of Machine Learning Research 7 , Feb (2006), 429 – 454 . Emanuel Kitzelmann and Ute Schmid. 2006. Inductive synthesis of functional programs: An explanation based generalization approach. Journal of Machine Learning Research 7, Feb (2006), 429–454.
- 10.1145/322217.322232 · DOI
- 10.5555/1939141.1939161 · DOI
- 10.5555/647197.720999 · DOI
- 10.1007/978-3-642-12251-4_23 · DOI
- 10.1145/1250734.1250752 · DOI
- 10.5555/111853.111889 · DOI
- 10.1145/1401132.1401152 · DOI
- 10.5555/1352079.1352134 · DOI
- 10.1145/1993498.1993501 · DOI
- 10.1145/2660193.2660228 · DOI
- 10.1145/2815400.2815418 · DOI
- 10.1006/jagm.1999.1044 · DOI
- 10.1145/2908080.2908102 · DOI · Paper page
- YN Srikant and Priti Shankar . 2002. The compiler design handbook: optimizations and machine code generation . CRC Press . YN Srikant and Priti Shankar. 2002. The compiler design handbook: optimizations and machine code generation. CRC Press.
- 10.1007/11688839_16 · DOI
Cited by
Sorted by citations
An order-aware dataflow model for parallel Unix pipelines
Handa, S., Kallas, K., Vasilakis, N., & Rinard, M. C. (2021) · Proceedings of the ACM on Programming Languages · doi:10.1145/3473570 · Cited by 4
“Divide and Conquer Decomposition : Prior work has shown the possibility of decomposing programs or program fragments using divide-and-conquer techniques [Farzan and Nicolet 2017, 2019; Rugina and Rinard 1999; Smith and Albarghouthi 2016].”
BackgroundMethodAutomatic synthesis of parallel unix commands and pipelines with KumQuat
Shen, J., Rinard, M., & Vasilakis, N. (2022) · Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/3503221.3508400 · Cited by 4
Metadata
- Authors
- Farzan, A., & Nicolet, V.
- Affiliations
- University of Toronto (CA)
- Venue
- Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation
- Publisher
- ACM
- Published
- 2019-06-08
- Pages
- 610-624
- ISSN
- 1531-7102 (ISSN-L)
- OpenAlex
- W2954733970
- Cited by
- 16
- References
- 3
- Citations by year
- 2025: 2 · 2024: 2 · 2023: 3 · 2021: 5 · 2020: 3 · 2019: 1
- FWCI
- 1.77
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Keywords
- nested loops, automatic parallelization, multidimensional arrays, program transformation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Modular divide-and-conquer parallelization of nested loops. https://app.cochat.ai/papers/10.1145/3314221.3314612
- The paper
- Farzan, A., & Nicolet, V. (2019). Modular divide-and-conquer parallelization of nested loops. Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. https://doi.org/10.1145/3314221.3314612
