Scheduling DAGs For Minimum Finish Time and Power Consumption on Heterogeneous Processors

Abstract

In the past years, scheduling has always been a hot research area, and with the advancement of processor technologies, there has been an increasing focus on the strategies that allow managing resource allocation in an optimal way. There is a large amount of increase on battery operated devices, and hence low power design is taking a main role in manufacturing most of today's electronics. In a distributed environment, an application is usually decomposed into several independent and/or interdependent sets of co-operating tasks and assigned to a set of available processors for execution. These sets of tasks can be represented by a directed a-cyclic graph (DAG). The set of processors can be homogenous or heterogeneous. Heterogenous processors vary in factors like processor's speed, available memory, operating system, power supply, etc. The role of a good scheduling algorithm is to e±ciently assign each task to a processor sepending on the resources needed such that the communication overhead between related tasks is reduced and the precedence relations among tasks are satisfied. This will minimize the total finish time and total power consumption.

The scheduling algorithm developed in this work to minimizes both total execution time (makespan) and total power consumption of a DAG structured application on heterogeneous processors. This algorithm combines the techniques of heterogeneous earliest finish time (HEFT)[1] and voltage scaling[2] to obtain both minimum makespan and low power consumption. The processors used are considered to be continuously voltage scalable in range of operation. After the initial scheduling is done using HEFT for minimum makespan, the processors are voltage scaled down and/or frequency scaled down, i.e., slowed down, to reduce the power consumption whenever there is an idle time. This voltage scaling is performed without violating the precedence relationships among tasks. The simulation results show power saving of 22.5% over simple HEFT and same makespan as of simple HEFT.