Multicore scheduling based on learning from optimization models

Scheduling for multicore computer systems is a challenge since subsets of cores may share resources, such as a cache. Performance for workloads may therefore vary depending on which tasks are scheduled to run on the same subset of cores. There is therefore a need for contention-aware scheduling. Our study involves implementation of an optimal multicore scheduler which has perfect prediction of negative consequences of all combinations of tasks scheduled on the hardware platform we are using. It uses an Integer Program. We show that it is indeed optimal for our workloads, supporting its authors' claims. We also implemented a scheduler which uses a combination of a machine learning model (M5 Prime) and Linear Programming to schedule tasks on CPU cores and compared it to a state-of-the-art scheduler known as Distributed Intensity (DI). Some workloads exhibited moderate improvements in unfairness, but not much in runtime. A scheduler based on another machine learning model was implemented, this time a Multilayer Perceptron (MLP). To do this, we had to generate workloads for the Optimal Scheduler, store its decision for various types of workloads, and train a Multilayer Perceptron model on this data. We then implemented a scheduler with the Multilayer Perceptron model, which tries to mimic the decision of the Optimal Scheduler. Our results show that our scheduler is better than DI in 7 out of 9 test workloads (mostly by 10%), and approximately equal to the Optimal Scheduler in 6 out of 9 test workloads (exactly equal in 4). The MLP scheduler is faster than the Optimal Scheduler by a wide margin, and faster than the Linear Programming scheduler.