Multi-Core Software

Process Scheduling Challenges in the Era of Multi-Core Processors

RESEARCH WORK

Quite a bit of recent research in the process scheduler area is to do with trying to address multi-core scheduling challenges. For example, Micro Architectural Scheduling Assist [2] talks about tracking the shared resource usage with performance-monitoring counters and using this information for effective distribution of shared resource load. Another body of work in this area is the cache-fair algorithm [4] that tries to address the application performance variability that depends on the other co-scheduled threads in the same multi-core package. This algorithm uses an analytical model to estimate the L2 cache miss rate a thread would have if the cache were shared equally among all the threads, i.e., the fair miss rate. The algorithm then adjusts the thread's share of CPU cycles in proportion to its deviation from its fair miss rate. This algorithm showed a reduction of the effect of the schedule-dependent miss rate variability on the thread's runtime. The L2-conscious scheduling algorithm [5] separates all runnable threads into groups, such that the combined working set of each group fits in the cache. By scheduling a group at a time and making sure that the working set of each scheduled group fits in the cache, this algorithm reduces the cache miss ratios.

While the research shows promising results, it is far from being implementation ready and from inclusion in commercial operating systems. The main challenges of these algorithms include the dependency of the performance-monitoring counters (which are not designed primarily for process scheduling and which vary from processor generation to processor generation), the different algorithm phases (data collection phase and usage phase), applicability of mathematical models to wide heterogeneous workloads, and above all, incorporating this knowledge into the traditional process scheduler that works across wide multi-core topologies and platforms. One of the current focus areas is to turn this research into reality.

Most of the software algorithms exploit the differences in the individual task characteristics and their resource usages. Scenarios such as those in which all the tasks in the system have similar characteristics and resource requirements cannot be addressed by software alone with the current generation of multi-core hardware. CQoS [3] presents a new cache management framework for improving shared cache efficiency and improving system performance. It proposes options for priority classification, priority assignment, and priority enforcement to heterogeneous memory access streams. Hardware solutions like these help maximize resource utilization and minimize the impact on performance in the presence of shared resource contention.

As more logic gets integrated into the processor die, future work in this area will focus on the increasing shared resources between cores on the die and their interactions with the system software; the process scheduler in particular. In the area of multi-core processor power management, one of the areas that is making rapid progress is the reduction of idle processor power. In future platforms, as the power consumed by idle cores decreases and becomes independent of the busy cores in the packages, scheduling mechanisms for power savings need to be revisited.

Back to Top