Software Engineering Institute | Carnegie Mellon University
Software Engineering Institute | Carnegie Mellon University

Multicore Scheduling

While scheduling in multiprocessor real-time systems is an old problem, multicore processors have brought a renewed interest, along with new dimensions, to the challenge. For instance, there is a need to tradeoff different levels of migration cost, different degrees of inter-core hardware sharing (e.g. memory bandwidth), and so on. Our research is aimed at providing new knobs to perform these tradeoffs with additional application information.

Beyond real-time systems, general-purpose systems are now faced with the fact that they need to parallelize their work in order to get the expected performance increment from additional cores in the new processors. However, partitioning the work into parallel pieces is a necessary but not sufficient condition. Equally important is the allocation of CPU cycles to these parallel pieces (tasks). In the extreme, if we run all the tasks of the parallel pieces in the same core, such parallelism is completely wiped out. Hence, the task-to-core allocation and the scheduling of hardware resources between core (e.g., cache, memory bandwidth) can change completely the performance of these systems. We are working on new ways to take advantage of application knowledge to use them as parameter in the scheduling algorithms at all levels of the computer system.

Inter-core Memory Interference in Multicore Processors

Multicore processors are quite different from multi-processors. This is due to the fact that cores within a processor share resources. One of the most critical shared resources is the memory system. This includes both shared cache and shared RAM memory. The effect of the memory interference that one task running on one core has on another running on a different core can be highly significant. We have seen extreme cases of 12X increases in the execution time due to memory interference (as the figure below illustrates), and some practitioners have observed 3X increases. This 3X basically means that in a dual core processor I am better off shutting down a core to avoid a decrease in the execution speed.

Illustrates inter-core memory interference in multicore processors

Once we solve the interference problem we have another challenge. Due to shared resources, we must support new tasks with parallelized jobs that require more than one core to complete before the deadline. New scheduling algorithms are necessary to schedule these tasks and must be combined with memory partitions to maximize their utilization and guarantee their time predictability.

At the SEI, we have been working with the CMU Real-Time and Multimedia Systems Laboratory to address the shared memory challenge by creating partitioning mechanisms to eliminate or reduce interference, along with analysis algorithms to take into account residual effects.