Portable Implementations of Work Stealing
Masahiro Yasugi, Tasuku Hiraishi, Chihiro Takeuchi · 2024
Work stealing is a well-known technique for dynamic load balancing; however, manually writing work-stealing protocols is error-prone. We can use the Tascell parallel programming language for the correct and portable implementation of work stealing; the implementation combines polling and adequate mutual exclusion. In Tascell, we can express on-demand concurrency for backtracking-based load balancing where a worker performs a sequential computation with its own execution stack unless it is requested to spawn a task. To spawn a larger task by temporarily backtracking, nested functions can be used for legitimate execution stack access. As nested functions for extended C languages, we can use GCC’s heavyweight implementation with runtime code generation or lightweight implementations by enhancing GCC; however, compiler-based implementations are poor in portability. In this study, we implement and evaluate more portable Tascell frameworks called “Tascell/SC” by using transformation-based portable implementations of nested functions. In addition, we propose Tascell-inspired portable frameworks only in C++ called “Tascell++” by using lambda expressions in C++11 for legitimate execution stack access.