一句话：通过编译器把潜在并行性嵌入调用栈、运行时按需转为并行任务，自动管理并行性并保持 work/span 渐近性质。
在现代体系结构上，线程或任务的创建与管理会给并行带来不可忽视的开销，程序员通常需手动优化与调优来压低这一开销并兼顾性能收益；在支持高阶函数的语言中，由于难以推理并行性的成本与收益，手动调优尤为困难。本文针对带任务并行的 Parallel ML 语言，提出结合静态编译与运行时技术的并行性自动管理方案：编译器 pipeline 将“潜在并行性”直接嵌入调用栈，默认不付出任务创建开销；运行时系统则按需把潜在并行性动态转换为真正的并行任务。作者证明该技术不会渐进地影响并行程序的 work 与 span，从而保持其渐近性质，并在 MPL 编译器上实现，实验表明可在免除手动优化负担的同时取得良好的实际性能。
On any modern computer architecture today, parallelism comes with a modest cost, born from the creation and management of threads or tasks. Today, programmers battle this cost by manually optimizing/tuning their codes to minimize the cost of parallelism without harming its benefit, performance. This is a difficult battle: programmers must reason about architectural constant factors hidden behind layers of software abstractions, including thread schedulers and memory managers, and their impact on performance, also at scale. In languages that support higher-order functions, the battle hardens: higher order functions can make it difficult, if not impossible, to reason about the cost and benefits of parallelism. Motivated by these challenges and the numerous advantages of high-level languages, we believe that it has become essential to manage parallelism automatically so as to minimize its cost and maximize its benefit. This is a challenging problem, even when considered on a case-by-case, application-specific basis. But if a solution were possible, then it could combine the many correctness benefits of high-level languages with performance by managing parallelism without the programmer effort needed to ensure performance. This paper proposes techniques for such automatic management of parallelism by combining static (compilation) and run-time techniques. Specifically, we consider the Parallel ML language with task parallelism, and describe a compiler pipeline that embeds “potential parallelism” directly into the call-stack and avoids the cost of task creation by default. We then pair this compilation pipeline with a run-time system that dynamically converts potential parallelism into actual parallel tasks. Together, the compiler and run-time system guarantee that the cost of parallelism remains low without losing its benefit. We prove that our techniques have no asymptotic impact on the work and span of parallel programs and thus preserve their asymptotic properties. We implement the proposed techniques by extending the MPL compiler for Parallel ML and show that it can eliminate the burden of manual optimization while delivering good practical performance.
@article{paperbot2645,
title = {Automatic Parallelism Management},
author = {Sam Westrick and Matthew Fluet and Mike Rainey and Umut A. Acar},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {POPL},
year = {2024},
doi = {10.1145/3632880}
}