Adaptive scheduling on heterogeneous systems using support vector machine

In heterogeneous computing systems consisting of a multitude of autonomous computers, a mechanism that can harness the computing resources efficiently is essential to maximizing system performance. The general problem of mapping tasks onto machines is known to be NP-complete, as such, many good heuristics have been developed. However, the performance of most heuristics is susceptible to the dynamic environment, and affected by various system variables. Such susceptibility makes it difficult to choose an appropriate heuristic. Furthermore, an adaptable scheduler has been elusive to researchers. In this research, we show that using a support vector machine (SVM), an elegant meta-scheduler can be constructed which is capable of making heuristic selections dynamically and which adapts to the environment as well. To the best of our knowledge, this research is the first use of SVM to perform schedule selections in heterogeneous computing. We call the novel meta-scheduler, support vector scheduler (SVS). Once trained, the SVS can perform the schedule selections in O(n) complexity, where n is the number of tasks. Using simulations, we evaluated the effectiveness of SVS in making the best heuristic selection. We find that the average improvement of SVS over random selection is 29  %, and over worst selection is 49  %. Indeed, SVS is only 5  % worse than the theoretical best selection. Since SVS contains a structural generalization of the system, the heuristic selections are adaptive to the dynamic environment in terms of task heterogeneity and machine heterogeneity. Furthermore, our simulations show that the SVS is scalable with number of tasks as well as number of machines.