This Is AuburnElectronic Theses and Dissertations

Show simple item record

Dynamic Task Scheduling onto Heterogeneous Machines Using Support Vector Machine


Metadata FieldValueLanguage
dc.contributor.advisorBaskiyar, Sanjeev
dc.contributor.advisorUmphress, Daviden_US
dc.contributor.advisorYilmaz, Leventen_US
dc.contributor.authorPark, Yongen_US
dc.date.accessioned2008-09-09T22:34:05Z
dc.date.available2008-09-09T22:34:05Z
dc.date.issued2008-05-15en_US
dc.identifier.urihttp://hdl.handle.net/10415/1047
dc.description.abstractDistributed 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.en_US
dc.language.isoen_USen_US
dc.subjectComputer Science and Software Engineeringen_US
dc.titleDynamic Task Scheduling onto Heterogeneous Machines Using Support Vector Machineen_US
dc.typeThesisen_US
dc.embargo.lengthNO_RESTRICTIONen_US
dc.embargo.statusNOT_EMBARGOEDen_US

Files in this item

Show simple item record