Design and Implementation of a Nonblocking Randomized Work Stealing Scheduler

Abstract

This thesis presents FLCN (Free of Locks, Cilk is Now), a nonblocking work-stealing runtime scheduler that supports Cilk multithreaded programming. The existing OpenCilk runtime system uses lock-based synchronization and thus suffers from lock contention, does not provide progress guarantees, and can experience performance degradation with high worker counts and in multiprogrammed scenarios. FLCN leverages the existing runtime system’s provably efficient scheduling algorithm and introduces several new data structures and concurrency protocols to form a correct and performant lock-free system. In addition to enabling fork-join task parallelism, FLCN supports other Cilk features such as reducer hyperobjects. Through analyzing the performance of FLCN on various canonical benchmark programs, I find that for programs with low amounts of work, FLCN performs worse than the existing runtime. However, for most programs, I find that FLCN is either competitive with or marginally outperforms the existing runtime. Additionally, FLCN consistently exhibits higher scalability than the existing runtime, performing especially better when using hyperthreads and in multiprogrammed environments. I also outline future work that could make FLCN a more comprehensive and performant system, including ideas for improving FLCN’s work efficiency that would in turn better its performance on programs with low amounts of work.