DFVS-Enabled Multiprocessor

A method of executing one or more tasks on one or more processors to reduce overall power consumption, comprising

• formulating the tasks as a graph with dependencies between tasks defined as edges in the graph;
• defining a discrete number of operating frequencies for each processor executing a task in the graph, and determining the power dissipation of the processor executing the task at each such frequency;
• and
• minimizing the sum, over all tasks in the graph and over all allowed frequencies per processor per task, of the product of
• the power consumption of a task on a processor at a frequency,
• the ratio of the cycle count of the task to each allowed frequency, and
• the percentage of cycles of the task executed at each frequency;
• subject to the constraints that
• all the tasks to be executed are in the graph,
• all of the frequencies considered are allowed frequencies for a task on a processor,
• the percentage of cycles of a task executed at a given frequency is between 0 and 100%,
• the sum of the percentages of cycles of a task executed at a plurality of frequencies is 100%, and
• the difference in worst-case start times between tasks i and j is greater than or equal to the sum of
• the number of times one task must execute before the next can begin, times the minimum rate at which a task may be executed and
• the ratio of the cycle count of each task to each allowed frequency, times the percentage of cycles of the task executed at each frequency, this product summed over all allowable frequencies per processor for each task;
• and
• determining a percentage of the cycles for each task to operate on a processor at an allowable frequency to achieve the minimization under the constraints;
• and
• causing each task to execute on each processor at an allowed frequency for the determined percentage of its cycles.