Bachelor Thesis BCLR-2025-65

BibliographyKrieg, Jonas: Design and implementation of a NUMA-aware cooperative scheduler.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 65 (2025).
71 pages, english.
Abstract

Efficient task scheduling is essential for maximizing computational processing unit (CPU) utilization in parallel applications. A widely adopted strategy is work-stealing, where idle threads dynamically steal tasks from busy ones. However, modern multi-core systems are increasingly based on Non Uniform Memory Access (NUMA) architectures, in which memory access latency varies depending on the physical proximity of memory to processor cores. In such systems, traditional work-stealing algorithms-which primarily optimize for memory locality or load distribution-can lead to performance degradation due to load imbalance or remote memory accesses. Despite this critical need for both NUMA-awareness and dynamic load balancing in modern systems, existing scheduling approaches rarely address these requirements simultaneously. Most current work-stealing schedulers prioritize either memory locality or load distribution, failing to capture the complex interactions between memory access patterns and workload balancing. This oversight limits their effectiveness in optimizing performance for real-world, NUMA-based workloads. The goal of this thesis is to design and implement a scheduling system that explicitly considers the effects of Non-Uniform Memory Access and aims to optimize task execution performance in multi-threaded environments. This is done by extending existing scheduling concepts by integrating multiple critical parameters-specifically NUMA-awareness and system load balance-into the scheduling and work-stealing process. In this work, we design and implement a novel hybrid scheduling approach, called NUMA-Load Aware Hybrid Scheduler (NLHScheduler), which combines the strengths of two state-of-the-art work-stealing strategies. Specifically, the NLHScheduler integrates NUMA-locality awareness with dynamic system workload balancing in every scheduling decision. Initial experiments revealed that these two criteria can sometimes conflict, leading to suboptimal scheduling decisions. To address this, the NLHScheduler prioritizes NUMA-locality, as previous analyses have shown that memory locality has a greater impact on performance than load balancing alone. Additionally, we enhanced the initial task assignment mechanism to be both NUMA-aware and load-sensitive, further improving scheduling efficiency. To evaluate the effectiveness of the proposed schedulers, a custom benchmark framework was developed. With this benchmark we tested various workload scenarios, including balanced and imbalanced task distributions, as well as different scaling behaviors by varying queue lengths, the number of thief coroutines, and the system’s concurrency level. The evaluation comparedmedianexecutiontimes, systemthroughput, andsuccessful steal operations across different schedulers. All work-stealing strategies significantly outperformed a baseline round-robin scheduler, improving performance by an average of 38.88%. While the individual stealing strategies showed similar results, the NLHScheduler achieved the greatest gains, especially by improving execution time stability by 40.59%. This work highlights the potential of combining NUMA-awareness and dynamic workload balancing in task scheduling, and lays a foundation for further research into adaptive, performance-oriented scheduling techniques in NUMA architectures.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Becker, Prof. Christian, König, Simon
Entry dateNovember 10, 2025
   Publ. Institute   Publ. Computer Science