Parallelism in a Region Inference Context
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Parallelism in a Region Inference Context. / Elsman, Martin; Henriksen, Troels.
In: Proceedings of the ACM on Programming Languages, Vol. 7, No. PLDI, 142, 2023, p. 884-906.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Parallelism in a Region Inference Context
AU - Elsman, Martin
AU - Henriksen, Troels
N1 - Publisher Copyright: © 2023 Owner/Author.
PY - 2023
Y1 - 2023
N2 - Region inference is a type-based program analysis that takes a non-Annotated program as input and constructs a program that explicitly manages memory allocation and deallocation by dividing the heap into a stack of regions, each of which can grow and shrink independently from other regions, using constant-Time operations. Whereas region-based memory management has shown useful in the contexts of explicit region-based memory management, and in particular, in combination with parallel execution of code, combining region inference with techniques for higher-order parallel programming has not been investigated. In this paper, we present an implementation of a fork-join parallel construct suitable for a compiler based on region inference. We present a minimal higher-order language incorporating the parallel construct, including typing rules and a dynamic semantics for the language, and demonstrate type soundness. We present a novel effect-based region-protection inference algorithm and discuss benefits and shortcomings of the approach. We also describe an efficient implementation embedded in the MLKit Standard ML compiler. Finally, we evaluate the approach and the implementation based on a number of parallel benchmarks, and thereby demonstrate that the technique effectively utilises multi-core architectures in a higher-order functional setting.
AB - Region inference is a type-based program analysis that takes a non-Annotated program as input and constructs a program that explicitly manages memory allocation and deallocation by dividing the heap into a stack of regions, each of which can grow and shrink independently from other regions, using constant-Time operations. Whereas region-based memory management has shown useful in the contexts of explicit region-based memory management, and in particular, in combination with parallel execution of code, combining region inference with techniques for higher-order parallel programming has not been investigated. In this paper, we present an implementation of a fork-join parallel construct suitable for a compiler based on region inference. We present a minimal higher-order language incorporating the parallel construct, including typing rules and a dynamic semantics for the language, and demonstrate type soundness. We present a novel effect-based region-protection inference algorithm and discuss benefits and shortcomings of the approach. We also describe an efficient implementation embedded in the MLKit Standard ML compiler. Finally, we evaluate the approach and the implementation based on a number of parallel benchmarks, and thereby demonstrate that the technique effectively utilises multi-core architectures in a higher-order functional setting.
KW - Memory Management
KW - Parallelism
KW - Region Inference
U2 - 10.1145/3591256
DO - 10.1145/3591256
M3 - Journal article
AN - SCOPUS:85162055862
VL - 7
SP - 884
EP - 906
JO - Proceedings of the ACM on Programming Languages
JF - Proceedings of the ACM on Programming Languages
SN - 2475-1421
IS - PLDI
M1 - 142
ER -
ID: 358550150