Scheduling jobs on multi-processors

A wide variety of research has been done to study the NP-complete optimization problem of multi-processor scheduling. In today’s world, where energy efficiency is gaining importance, the scheduling algorithms need to optimize both performance and energy consumption. This report focuses on scheduling of multiple job sets, using a three-level framework and dynamic speed scaling, with the objective of minimizing the bi-criterion metric of total response time plus energy. A non-clairvoyant setting is assumed, where minimal or zero information is available about the job characteristics. The jobs considered are malleable jobs, which are designed to run on variable number of processors. To exploit their parallelism, emphasis is laid on adaptive scheduling which allows the scheduler to allocate a varying number of processors to the job during its execution. The EQUI scheduler or the DEQ scheduler is used for processor allocation. The performance improvement with increase in number of allocated processors is constrained by the job’s parallelism. Speed is assigned either uniformly or non-uniformly, which determines the total execution rate as well as the total energy consumption. Three algorithms EQUI⨁UEQUI, EQUI⨁NEQUI and EQUI⨁NDEQ are developed for scheduling of multiple job sets. These algorithms are evaluated using a simulator developed in JAVA. It is found that EQUI⨁UEQUI has the worst performance, whereas EQUI⨁NDEQ has the best performance. The experimental results and their detailed analysis are presented.Bachelor of Engineering (Computer Engineering