TY - GEN
T1 - Towards Zero Spawn Overhead
T2 - 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2025
AU - Handleman, Aaron
AU - Singer, Kyle
AU - Schardl, Tao B.
AU - Lee, I. Ting Angelina
N1 - Publisher Copyright:
© 2025 Association for Computing Machinery. All rights reserved.
PY - 2025/7/16
Y1 - 2025/7/16
N2 - In a randomized work-stealing scheduler, parallel speedup depends on the spawn overhead, which workers pay to allow tasks to execute in parallel, and the steal overhead, which thieves pay to start executing new work. The importance of minimizing the spawn overhead in a randomized work-stealing scheduler is first formalized by Frigo et al., coined as the work-first principle [15], which states that one should minimize spawn overhead even at the expense of a larger steal overhead. Since then, many strategies have been proposed to reduce the spawn overhead, which is dominated by maintaining a per-worker double-ended queue, or deque, to keep track of available parallel work. In pursuit of zero spawn overhead, this work considers a strategy that eliminates the use of deques entirely, obviating the need for a worker to perform explicit bookkeeping or set up a deque to enable parallelism. To that end, we propose DLite, a compiler and runtime ABI (Application Binary Interface) that incurs near-zero spawn overhead, empirically measured to be about 6% compared to a regular function invocation. DLite pushes the tradeoffs advocated by the work-first principle to the extreme, which decreases the spawn overhead to almost nil, at the expense of a high steal cost. Specifically, DLite employs a backtracking strategy: When a steal attempt occurs, the victim provides its current stack and base pointers to the thief, and the thief then reconstructs the necessary state to realize the parallel execution. We have implemented Cilk-DLite, which extends the OpenCilk platform [33] to implement DLite. When the application has ample parallelism, Cilk-DLite exhibits similar scalability to OpenCilk with much lower spawn overhead. When the application lacks parallelism, the high steal cost in Cilk-DLite can impede scalability due to slower work distribution. We also implemented variants of Cilk-DLite that make different design choices to evaluate the tradeoffs between spawn overhead and steal cost.
AB - In a randomized work-stealing scheduler, parallel speedup depends on the spawn overhead, which workers pay to allow tasks to execute in parallel, and the steal overhead, which thieves pay to start executing new work. The importance of minimizing the spawn overhead in a randomized work-stealing scheduler is first formalized by Frigo et al., coined as the work-first principle [15], which states that one should minimize spawn overhead even at the expense of a larger steal overhead. Since then, many strategies have been proposed to reduce the spawn overhead, which is dominated by maintaining a per-worker double-ended queue, or deque, to keep track of available parallel work. In pursuit of zero spawn overhead, this work considers a strategy that eliminates the use of deques entirely, obviating the need for a worker to perform explicit bookkeeping or set up a deque to enable parallelism. To that end, we propose DLite, a compiler and runtime ABI (Application Binary Interface) that incurs near-zero spawn overhead, empirically measured to be about 6% compared to a regular function invocation. DLite pushes the tradeoffs advocated by the work-first principle to the extreme, which decreases the spawn overhead to almost nil, at the expense of a high steal cost. Specifically, DLite employs a backtracking strategy: When a steal attempt occurs, the victim provides its current stack and base pointers to the thief, and the thief then reconstructs the necessary state to realize the parallel execution. We have implemented Cilk-DLite, which extends the OpenCilk platform [33] to implement DLite. When the application has ample parallelism, Cilk-DLite exhibits similar scalability to OpenCilk with much lower spawn overhead. When the application lacks parallelism, the high steal cost in Cilk-DLite can impede scalability due to slower work distribution. We also implemented variants of Cilk-DLite that make different design choices to evaluate the tradeoffs between spawn overhead and steal cost.
UR - https://www.scopus.com/pages/publications/105012714068
U2 - 10.1145/3694906.3743349
DO - 10.1145/3694906.3743349
M3 - Conference contribution
AN - SCOPUS:105012714068
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 75
EP - 88
BT - SPAA 2025 - Proceedings of the 2025 37th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
Y2 - 28 July 2025 through 1 August 2025
ER -