Design and implementation of a NUMA-aware cooperative scheduler

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. Effizientes Scheduling ist entscheidend, um die CPU-Auslastung in parallelen Anwendungen zu maximieren. Eine weit verbreitete Strategie ist das Work-Stealing, bei dem inaktive Threads dynamisch Aufgaben von stark ausgelasteten Threads übernehmen. Moderne Mehrkernsysteme basieren jedoch zunehmend auf NUMA-Architekturen, bei denen die Speicherzugriffszeit von der physischen Nähe des Speichers zu den Prozessorkernen abhängt. In solchen Systemen können traditionelle Work-Stealing-Algorithmen - die hauptsächlich nach Speicherlokalität oder Lastverteilung optimieren - aufgrund von Lastungleichgewichten oderentfernten Speicherzugriffen zu Leistungseinbußen führen. Trotz der entscheidenden Bedeutung von NUMA-Awareness und dynamischer Lastverteilung in modernen Systemen adressieren bestehende Scheduling-Ansätze diese Anforderungen selten gleichzeitig. Die meisten aktuellen Work-Stealing-Scheduler priorisieren entweder die Speicherlokalität oder die Lastverteilung und vernachlässigen dabei die komplexen Wechselwirkungen zwischen Speicherzugriffsmustern und Lastausgleich. Diese Lücke schränkt ihre Effektivität bei der Leistungsoptimierung von NUMA-basierten Workloads ein. Ziel dieser Arbeit ist es, einen Scheduler zu entwerfen und zu implementieren, der die Auswirkungen von nicht-uniformen Speicherzugiffen explizit berücksichtigt und die Performance von Aufgaben in multithreaded Umgebungen optimiert. Dies erfolgt durch die Erweiterung bestehender Scheduling Konzepte um die Integration mehrerer kritischer Parameter - insbesondere NUMA-Awareness und System-Last-Balance - in den Scheduling- und Work-Stealing-Prozess. Im Rahmen dieser Arbeit entwerfen und implementieren wir einen neuartigen hybriden Scheduling Ansatz namens NLHScheduler, der die Stärken zweier moderner Work-Stealing-Strategien kombiniert. Konkret integriert der NLHScheduler die NUMA-Lokalisierungsinformation mit dynamischer System-Last-Balance in jede Scheduling Entscheidung. Erste Experimente zeigten, dass diese beiden Kriterien sich gegenseitig widersprechen können und so suboptimale Scheduliung Entscheidungen hervorrufen können. Zur Lösung priorisiert der NLHScheduler die NUMA-Lokalisierung, da frühere Analysen gezeigt haben, dass Speicherlokalität einen stärkeren Einfluss auf die Leistung hat als die reine Lastverteilung. Zudem wurde der Mechanismus zur initialen Aufgabenverteilung um NUMA-Awareness und Lastsensitivität erweitert, was die Effizienz des Schedulings weiter verbessert. Zur Bewertung der Effektivität der vorgeschlagenen Scheduler wurde ein eigenes Benchmark Framework entwickelt. Mit dieser Benchmark testeten wir verschiedene Workload-Szenarien, darunter balancierte und unbalancierte Aufgabenverteilungen sowie unterschiedliche Skalierungsverhalten durch Variation der Queue-Längen, der Anzahl der Dieb-Coroutinen und der System Nebenläufigkeit. Die Evaluation verglich die medianen Ausführungszeiten, den Systemdurchsatz und die Anzahl erfolgreicher Steal-Operationen verschiedener Scheduler. Alle Work-Stealing-Strategien übertrafen einen Baseline-Round-Robin-Scheduler signifikant und verbesserten die Leistung im Durchschnitt um38,88%. WährenddieeinzelnenStealing-Strategien vergleichbare Ergebnisse erzielten, erreichte der NLHScheduler die größten Verbesserungen, insbesondere durch eine Steigerung der Stabilität der Ausführungszeiten um 40,59%. Diese Arbeit zeigt das Potenzial der Kombination von NUMA-Awareness und dynamischem Lastausgleich in der Aufgabenplanung auf und legt die Grundlage für weiterführende Forschungen zu adaptiven, leistungsorientierten Scheduling-Techniken in NUMA-Architekturen.