Claims:
1. A method of reducing power consumption in real-time heterogeneous computing systems during task scheduling, the method comprising:
creating an initial schedule having a plurality of tasks;
determining a critical path from the plurality of tasks;
estimating a completion time required for execution of the plurality of tasks from the critical path;
determining a slack time for execution of the plurality of tasks by comparing the estimated completion time with a timeline provided by the user; and
decreasing the execution time of the tasks based on the slack time thereby executing the plurality of tasks with less energy consumption.

2. The method of claim 1, wherein the initial schedule is created using a Directed Acrylic graph (DAG), where the DAG comprises of the plurality of tasks represented in the form of nodes.

3. The method of claim 1, wherein the DAG is created based on a precedence constraint and deadline constraint of the plurality of tasks.

4. The method of claim 1, wherein the critical path in DAG is the one consisting of nodes which enables to prioritize the plurality of tasks to determine a time required for completion of execution.

5. The method of claim 1, wherein estimating a completion time required for execution of the plurality of tasks comprises of:
increasing the slack time by preparing the initial schedule using the DAG;
calculating the overall completion time of the plurality of tasks in different paths in the graph;
utilizing the extra time in the different paths for adding more value to the slack; and
relaxing the overall schedule by utilizing the slack.

6. The method of claim 1, further comprising:
assigning a processor to the selected tasks for scheduling; and
selecting a voltage level according to the processor speed for execution of the selected task;
wherein the voltage level is selected using a Dynamic Voltage Scaling (DVs) technique to substantially minimize energy consumption and completion time of the selected task.

7. The method of claim 6, wherein the processor is assigned by comparing an earliest start time of the task and an avail parameter of the processor to determine availability of the processor.

8. The method of claim 1, wherein the plurality of tasks are executed based on a Precedence constraint and deadline constraint.

9. The method of claim 1, wherein heterogeneous computing system is a multi-processor computing system.

10. The method according to claim 1, wherein the tasks are heterogeneous.

11. A heterogeneous computing system, comprising a scheduling module, a processor unit comprising one or more processors, each enabled to operate on different voltage supply levels, wherein the scheduling module is adapted for:
creating an initial schedule having a plurality of tasks;
determining a critical path from the plurality of tasks;
estimating a completion time required for execution of the plurality of tasks from the critical path;
determining a slack time for execution of the plurality of tasks by comparing the estimated completion time with a timeline provided by the user; and
decreasing the execution time of the tasks based on the slack time thereby executing the plurality of tasks with less energy consumption.

12. The system of claim 11, wherein each processor of processor unit use a Dynamic Voltage Scaling (DVS) technique to adjust the voltage level dynamically according to the processor speed.

13. The system of claim 11, further comprises:
a voltage controller unit to regulate the voltage supplied to the one or more processors for execution of the scheduled tasks. , Description:FIELD OF THE INVENTION
The present invention generally relates to power optimization in heterogeneous computing systems and embedded systems. More particularly the present invention relates to slack management for real-time computing and embedded systems to reduce energy consumption while scheduling tasks on processing units and available resources dynamically.

BACKGROUND OF THE INVENTION
Today in the era of fast emerging computing technologies, heterogeneous systems and embedded computing systems have proliferated in almost all areas of technology and applications. There has been phenomenal demand on small factor devices during the past decade. Their application spans from stand-alone battery operated devices such as cellular phones, digital cameras, MP3 players, Personal Digital Assistances (PDAs), laptops medical monitoring devices, to real-time distributed systems used in sensor networks, remote robotic clusters, avionics, and defense systems and all the low end and high end devices which consists of heterogeneous processors, storage nodes, underlying network and resources. Some of these devices have strict deadlines for the completion of execution of all tasks while others have some flexibility. But the problem of energy consumption of these systems have become a major issue as they consume a considerable amount of energy. This also leads to increasing costs.

Heterogeneity of processing elements provides for a tighter bound on the flexibility of reschedule necessary for exploiting runtime variations than homogenous processing elements. Scheduling problem in these systems is especially challenging, so an efficient and cost-effective way is required to meet the high increasing cost. Various scheduling techniques have been proposed but they lack in one performance parameter or the other (that includes makespan, cost, energy consumption, performance). Further the Directed Acyclic Graph (DAG) used for scheduling of the tasks requires that the precedence and deadline constraints should be satisfied while scheduling.

Thus, there is a need for providing an efficient mechanism for reducing power consumption in real-time heterogeneous computing systems during task scheduling.

The above mentioned shortcomings, disadvantages and problems are addressed herein and which will be understood by reading and studying the following specification.

SUMMARY OF THE INVENTION

The various embodiments herein disclose a method for reducing power consumption in real-time heterogeneous computing systems during task scheduling. The method comprises of creating an initial schedule having a plurality of tasks, determining a critical path from the plurality of tasks, estimating a completion time required for execution of the plurality of tasks from the critical path, determining a slack time for execution of the plurality of tasks by comparing the estimated completion time with a timeline provided by the user and decreasing the execution time of the tasks based on the slack time thereby executing the plurality of tasks with less energy consumption.

According to an embodiment of the present invention, the initial schedule is created using a Directed Acrylic graph (DAG), where the DAG comprises of the plurality of tasks represented in the form of nodes.

According to an embodment of the present invention, the DAG is created based on a precedence constraint and deadline constraint of the plurality of tasks. The critical path in DAG is the one consisting of nodes which enables to prioritize the plurality of tasks to determine a time required for completion of execution.

According to an embodiment of the present invention, the method of estimating a completion time required for execution of the plurality of tasks comprises of increasing the slack time by preparing the initial schedule using the DAG, calculating the overall completion time of the plurality of tasks in different paths in the graph, utilizing the extra time in the different paths for adding more value to the slack and relaxing the overall schedule by utilizing the slack.

According to an embodiment of the present invention, the method further comprises of assigning a processor to the selected tasks for scheduling and selecting a voltage level according to the processor speed for execution of the selected task. The voltage level is selected using a Dynamic Voltage Scaling (DVs) technique to substantially minimize energy consumption and completion time of the selected task.

According to an embodiment of the present invention, the processor is assigned by comparing an earliest start time of the task and an avail parameter of the processor to determine availability of the processor.

According to an embodiment of the present invention, the plurality of tasks are executed based on a Precedence constraint and deadline constraint. The heterogeneous computing system is a multi-processor computing system and the plurality of tasks are heterogenous.
Embodiments herein further disclose a heterogeneous computing system, comprising a scheduling module, a processor unit comprising one or more processors, each enabled to operate on different voltage supply levels. The scheduling module is adapted for creating an initial schedule having a plurality of tasks, determining a critical path from the plurality of tasks, estimating a completion time required for execution of the plurality of tasks from the critical path, determining a slack time for execution of the plurality of tasks by comparing the estimated completion time with a timeline provided by the user and decreasing the execution time of the tasks based on the slack time thereby executing the plurality of tasks with less energy consumption. Each processor of processor unit use a Dynamic Voltage Scaling (DVS) technique to adjust the voltage level dynamically according to the processor speed. The system further comprises a voltage controller unit to regulate the voltage supplied to the one or more processors for execution of the scheduled tasks.

The foregoing has outlined, in general, the various aspects of the invention and is to serve as an aid to better understanding the more complete detailed description which is to follow. In reference to such, there is to be a clear understanding that the present invention is not limited to the method or application of use described and illustrated herein. It is intended that any other advantages and objects of the present invention that become apparent or obvious from the detailed description or illustrations contained herein are within the scope of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

The other objects, features and advantages will occur to those skilled in the art from the following description of the preferred embodiment and the accompanying drawings in which:

Figure 1 is a schematic diagram illustrating overall workflow of a heterogeneous computing system, according to an embodiment of the present invention.

Figure 2 is a schematic flow diagram illustrating a Directed Acyclic graph illustrating the schedule of the plurality of tasks, according to an embodiment of the present invention.

Figure 3 is a block diagram illustrating the functional components of a real-time heterogeneous computing system adapted for executing the method as described in Figure. 1.

Although specific features of the present invention are shown in some drawings and not in others. This is done for convenience only as each feature may be combined with any or all of the other features in accordance with the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention provides a method to schedule the tasks in a way that helps in minimizing the power consumed, enhanced availability of processors and work in the dynamic environment in addition to fulfilling the deadline constraint and the precedence constraint. In the following detailed description of the embodiments of the invention, reference is made to the accompanying drawings that form a part hereof, and in which are shown by way of illustration specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that changes may be made without departing from the scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.

The specification may refer to “an”, “one” or “some” embodiment(s) in several locations. This does not necessarily imply that each such reference is to the same embodiment(s), or that the feature only applies to a single embodiment. Single features of different embodiments may also be combined to provide other embodiments.

As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless expressly stated otherwise. It will be further understood that the terms “includes”, “comprises”, “including” and/or “comprising” when used in this specification, specify the presence of stated features, integers, steps, operations, elements and/or components, but do not preclude the presence or addition of one or more other features integers, steps, operations, elements, components, and/or groups thereof. As used herein, the term “and/or” includes any and all combinations and arrangements of one or more of the associated listed items.

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosure pertains. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.

The various embodiments herein describes a method to prepare the Directed Acyclic Graph (DAG) taking care of precedence and deadline constraints out of the available tasks and compute the Slack. The slack then determines the overall completion time of the plurality of tasks in the system and the extra time available in the same given deadline, which can be utilized further during the parallel execution of multiple tasks at the same time.

The embodiments herein create an initial schedule having a plurality of tasks represented in the form of nodes in a Directed Acyclic Graph (DAG). A critical path for task execution is then determined from the DAG, where the critical path consists of nodes which help in finding the time when the plurality of tasks complete their execution. This time is them compared with the deadline provided by the user to determine the additional time left after the schedule, which is utilized for relaxing the initial schedule. The execution time of the plurality of tasks can then be increased, so that they can execute with less energy consumption. Further a DVS technique is used to adjust the voltage of processor dynamically as required by the processors to execute the tasks.

According to an embodiment of the present invention, the system herein is divided into three modes called as task model, system model and power model. The task model comprises of a Directed Acyclic Graph G (V, E), where V is the set of vertices or nodes in the graph and E is the set of edges connecting these nodes. The nodes in the DAG represents the plurality of tasks to be scheduled. An edge exists in the graph only if precedence constraints are satisfied i.e. the first task should complete its execution before the beginning of the next task. The graph comprises of an entry node and exit node. The entry node is the node which has zero in degree, which means it does not have any parent node and the exit node is one which has zero out degree, that is no decedent nodes. The exit node exists as the leaf node in the graph.

The system model comprises of a plurality of processors P= {Pi | i=1, 2, m} and each processor can use a Dynamic Voltage Scaling (DVS) technique to adjust the voltage level dynamically according to the processor’s speed. Some discrete v voltage levels V = {Vj | j=1, 2, v} have been recorded and according to these voltage levels, the processor will adjust its voltage. The voltage levels have been decided taken into consideration the normal voltages used for these processors at the different speeds. It can be formulated as:
V = min {VP | Sp = stack}

Here V is the voltage level maintained in the system, stack is the speed at which the task is executing, Sp is the minimum speed at which processor runs so as to schedule the task in a suitable way, V is the voltage maintained by the processor corresponding to the speed of the processor.

The embodiment herein considers different voltages corresponding to four different speeds. Table 1 shows one such example of different values of speed for processing at different voltage levels.
TABLE 1. Voltage Levels
Voltage (Vp) Speed (sp)
0.9 0.4
1.1 0.6
1.3 0.8
1.5 1.0

The power consumed by a processor can be found as the sum of static energy and dynamic energy. Each processor consumes some constant power which depend on the internal design, architecture and the capacitance. This factor can be denoted as ß. The dynamic power is dependent on the frequency and voltage at which the processor is operating; which can be expressed as:
P = ß + CV2f

This frequency varies since the system model functions through Dynamic voltage scaling.

According to an embodiment of the present invention the Real-time heterogeneous systems includes the embedded systems varying from emerging laptops, printers, mobile devices and others, all the low end and high end devices which consists of heterogeneous processors, storage nodes, underlying network and resources. Some of them have strict deadlines for the completion of execution of all tasks while others have some flexibility.

Here scheduling in real-time heterogeneous computing systems refers to the selection and execution of lowest level tasks in the processing units. The critical path is the path in the Directed Acyclic Graph that consists of nodes starting from the root node to the leaf node with the maximum sum of computation time and communication time. Makespan refers to the overall completion time for the execution of all the tasks on the processing units. Slack is the unused time left in the task scheduling as compared to the given deadline. Utilization is the rate at which tasks are being executed on the processing units according to the given deadline.

Figure 1 is a schematic diagram illustrating overall workflow of a heterogeneous computing system, according to an embodiment of the present invention. According to an embodiment herein, the task scheduling herein is the process of allocating a set of N tasks to a set of P processors without violating precedence constraints aiming to minimize makespan with energy consumption as low as possible. The user inputs a plurality of tasks (1-10) which needs to be executed by the computing system at step 102. The plurality of tasks (1-10) inputted by the user are represented in the form of nodes in a Directed Acyclic Graph (DAG) at step 104. Further a critical path in the DAG is determined, where the critical path is the one consisting of nodes which enables the system to determine a time required by the plurality of tasks to complete their execution. Then a slack time required for execution of the plurality of tasks is determined by comparing the estimated completion time with a timeline provided by the user. Further the extra time calculated in all these different paths are then utilized for adding more valued to the slack and the slack is then utilized for relaxing the overall schedule at step 106.

Further task selection is initiated at step 108. For selecting the order in which the plurality of tasks are to be executed, the Critical Path in the DAG is utilized. The selection is started from the root node and then move level by level until the last level is reached. Firstly selecting the node in the Critical Path at each level, then scheduling the other nodes by their order. This schedule is based on Level-based scheduling but enhancing it by the use of Critical Path.

After selecting the node, the processor is selected for allocation to the task for scheduling at step 110. For selecting the appropriate processor, a parameter termed as avail is used. This parameter is used to keep record when a processor is available for the scheduling of the tasks. Initially for the first processor, avail is zero till no task has been assigned to it. It is calculated as the sum of Earliest Time and the Execution Time of the task.

For a task i, the avail can be expressed as
avail[i] = EST[i] + ET[i]

According to an embodiment of the present invention, the availability of the processor is checked when a particular task is to be scheduled by comparing the Earliest Start Time of task and Avail parameter of the processor. If EST [taski] = avail, only then that task can be scheduled on that processor, otherwise check for the availability of next processor in the processor list. When a processor has been allocated for a task i, the avail of the processor is accordingly changed.

The processors are initially arranged on the basis of their energy consumption. The processor which consumes the least energy while executing a task is the most efficient processor and is thus kept in the starting of the processor’s list to be considered firstly for the allocation of tasks. The processor list is thus prepared which contains the processors in the increasing order of the energy consumption working in a dynamic environment.

Further the method comprises of dynamically selecting voltage level using DVS (dynamic voltage scaling) technique to these processors at step 112. Any task i will execute at a speed which is equal to the utilization. The processor on which the task is being executing must operate at a minimum speed si so that it can execute a task running at a speed sk, otherwise the task cannot be scheduled properly. Thus the suitable voltage vi can be found when the processing speed of the processor is known.

Due to the changing and the dynamic nature of the grid, the DVS technique is used to alter the voltage and frequency. To decide on the appropriate voltage level, firstly the utilization is determined and then the processor speed is computed with the help of utilization.

Accordingly, the embodiments herein reduces an average of 15-20% power consumed in the scheduling of tasks in real-time heterogeneous computing systems. Further the system does assign the resources to the tasks at the run time. It applies the slack to the computation of tasks while scheduling and adds value in the efficient use of resources.

Figure 2 is a schematic flow diagram illustrating a Directed Acyclic graph illustrating the schedule of the plurality of tasks, according to an embodiment of the present invention. A DAG, consists of a set of nodes and a set of edges. A DAG is also called a task graph or macro-dataflow graph. The nodes 1-11 represent tasks partitioned from an application, the edges 10- 60 represents precedence constraints. An edge 10 between task 1 and task 2 also represents inter-task communication. In other words, the output of task 1 has to be transmitted to task 2 in order for task 2 to start its execution. A task with no predecessors is called an entry task, whereas an exit task, is one that does not have any successors. Among the predecessors of a task, the predecessor which completes the communication at the latest time is called the most influential parent (MIP) of the task. The longest path of a task graph is the critical path (CP), which is the edge 60 according to Figure 2. The priority of each task may be based on computation and communication costs of each task respectively along the longest path (critical path) of precedence constrained tasks that the task is a part of.

Figure 3 is a block diagram illustrating the functional components of a real-time heterogeneous computing system adapted for executing the method as described in Figure. 1. The system comprises of a scheduling module 302, a processing unit 304, a voltage controller unit 306 and a memory unit 308.

The scheduling module 302 is adapted for creating a DAG illustrating the schedule of a plurality of tasks, determining a critical path of the DAG, estimating a completion time required for execution of the plurality of tasks from the critical path, determining a slack time for execution of the plurality of tasks by comparing the estimated completion time with a timeline provided by the user and decreasing the execution time of the tasks based on the slack time thereby executing the plurality of tasks with less energy consumption.

The processor unit 304 comprises of a plurality of processors, each enabled to operate at different voltage supply levels for execution of the scheduled tasks. Each processor use a Dynamic voltage scaling technique to adjust the voltage level according to the processors speed.
The voltage control unit 306 is adapted to provide a suitable voltage level to the processors that substantially minimizes energy consumption and completion time for performing that task.

The embodiments herein is able to take account of the different capacities of the processors that form part of the heterogeneous network to assign, in priority order, tasks to the processors at a particular voltage level in a way that balances both completion time and energy consumption.

Although the embodiments herein are described with various specific embodiments, it will be obvious for a person skilled in the art to practice the invention with modifications. However, all such modifications are deemed to be within the scope of the claims. It is also to be understood that the following claims are intended to cover all of the generic and specific features of the embodiments described herein and all the statements of the scope of the embodiments which as a matter of language might be said to fall there between.