Dynamic Task Scheduling onto Heterogeneous Machines Using Support Vector Machine

Abstract

Distributed computing has been used to overcome the limitations of single computer use. However, the benefit of parallelizing computations may substantially reduce, if there is no well constructed mechanism to coordinate them. In this respect, the task matching problem of mapping a class of independent tasks on heterogeneous computers is critical to increase system performance, especially if the purpose is to reduce the total completion time of tasks. Mapping tasks to non-identical machines is a known NP-complete problem. Many heuristic algorithms have been used to minimize the total completion time in parallel systems. In this thesis, we take a novel approach by using Support Vector Machine (SVM) to dynamically schedule independent tasks to heterogeneous machines to minimize schedule length. SVM learns from a set of input workload patterns or samples. It maps each sample to a predefined label. Most learning samples of real world problems are non-separable in multi-dimensional input space. In our SVM, Radial Basis Function (RBF) Kernel is used to transform non-separable samples in multi-dimensional input space into high-dimensional feature space, where the samples are separable. The SVM constructs a hyperplane with maximal margin between the positive and negative samples in the high dimensional feature space. This hyperplane is used to classify future mappings. We constructed a Support Vector Scheduler (SVS), which uses the SVM to map tasks to machines. Using simulations we compared our algorithm against Early Fast (EF), Light Least (LL), and Round Robin (RR). We found that the performance using SVM was similar to EF and better than LL and RR. However, SVM is superior since it can dynamically adapt to changing inputs and machine characteristics.