Energy Efficient Scheduling in DVS Processors with Accelerations for Jobs with Multiple Active Intervals

Energy efficient scheduling is considered an important way to extend the lifetime of portable electronic devices like PDAs and sensor nodes which are mainly powered by batteries. Current dynamic voltage scaling (DVS) techniques allow the speed of processors to be set dynamically and therefore make it possible to save energy by scheduling jobs wisely. The associated scheduling problems for DVS techniques can be classified into three categories: ideal model, multiple model and feasible model. In the ideal model, the processor can run at arbitrary speeds and one speed can be changed instantly to another speed, while in the multiple model, only a finite number of speed levels are available. The model which characterizes the real system most accurately is the feasible model, where there is some acceleration constraint on the speed change and at the same time a maximum speed and minimum speed requirement exists. The principal goal of this project is to design algorithms to compute the minimum energy schedule for the feasible model. The researchers also introduce a new type of jobs which have multiple release times and deadlines. Such a job is considered to be completed if it is assigned enough CPU cycles within all of its active intervals. They aim to study the characteristics of the min-energy schedule for the new type of job sets in all the three categories of DVS models. Completing this project will lead to deeper insights in DVS scheduling algorithms and therefore provide useful information for chip designers.