DFVS-enabled multiprocessor
View Patent ↗One or more tasks to be executed on one or more processors are formulated into a graph, with dependencies between the tasks defined as edges in the graph. In the case of a Radio Access Technology (RAT) application, the graph is iterative, whereby each task may be activated a number of times that may be unknown at compile time. A discrete number of allowable frequencies for processors while executing tasks are defined, and the power dissipation of the processors at those frequencies determined. A linear programming problem is then formulated and solved, which minimizes the overall power dissipation across all processors executing all tasks, subject to several constraints that guarantee complete and proper functionality. The switching of processors executing the tasks between operating points (frequency, voltage) may be controlled by embedding instructions into the tasks at design or compile time, or by a local supervisor monitoring execution of the tasks.
1. 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 a 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 negative of the number of times one task must execute before the next can begin, times a 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.
2. The method of claim 1 wherein causing each task to execute on each processor at an allowed frequency for the determined percentage of its cycles comprises embedding instructions in each task operative to force a processor executing the task to do so at a predetermined operating point defined by frequency and supply voltage level.
3. The method of claim 1 wherein causing each task to execute on each processor at an allowed frequency for the determined percentage of its cycles comprises monitoring each task by a supervisor function operative to control the processor to operate at a predetermined operating point defined by frequency and supply voltage level.
4. The method of claim 1 wherein the minimization is achieved by formulating and solving a linear programming problem as:
minimize
∑
i
∈
V
×
∑
f
∈
F
(
π
(
i
)
)
P
(
π
(
i
)
,
f
)
×
cc
(
i
)
f
×
α
(
f
,
i
)
and
wherein the constraints are formulated as
∀(i,j)εE,
s
(
j
)
-
s
(
i
)
≥
-
d
(
i
,
j
)
×
μ
d
+
∑
f
∈
F
(
π
(
i
)
)
cc
(
i
)
f
×
α
(
f
,
i
)
,
∀iεV,
∑
f
∈
F
(
π
(
i
)
)
α
(
f
,
i
)
=
1
,
∀fεF(π(i)),
∀iεV, s(i)≧0
0≦α(f,i)≦1, where
V is a set of tasks in a graph,
E is a set of edges in the graph, each edge (i,j) representing a data dependency between a producer task i generating data and a consumer task j consuming the data,
d(i,j) represents an iteration distance between tasks i and j, such that the kth execution of task j is dependent on the (k−d(i,j)) execution of task i,
f is a frequency allowed for a processor,
F(p) is a set of frequency points allowed for processor p,
π(i) is a processor to which task i is mapped,
P(p,f) is a power dissipation of processor p at frequency f,
cc(i) is a cycle count of task i,
α(f,i) is a percentage of the cycles of a task that are executed at frequency f, such that the sum of alphas for a given task is equal to one,
μ d is a minimum rate at which a task must be executed, and
s(i) is a free variable indicating the worst-case start time of task i.
5. The method of claim 4 further comprising including into the linear programming problem one or more latency requirements formulated as
s(j)−s(i)≦(the latency between each activation of task i and subsequent activation of task j).
6. The method of claim 4 further comprising defining static ordering of tasks within a processor by adding edges with d(i,j)=0 delays from each preceding task i in the ordering to its succeeding task j in the ordering, subject to the constraint that an edge with d=1 is placed between the last task in the order and the first task in the order.
7. The method of claim 4 further comprising adding edges to represent buffer sizes between tasks, wherein the buffer size represents the dependence of a producer task on the availability of space to store data in the buffer for a consuming task.
8. The method of claim 7 wherein the linear programming problem is further constrained by a buffer constraint edge (j,i) being added for each inter-task buffer, with the constraint that d(j,i)=(size_of_buffer−d(i,j)).
9. A method of executing one or more tasks on one or more processors to reduce overall power consumption, comprising:
formulating a set of tasks, each comprising a predetermined set of instructions, as a graph V;
defining a set of edges E in the graph, each edge (i,j) representing a data dependency between a producer task i generating data and a consumer task j consuming the data;
defining an iteration distance d(i,j) between tasks i and j such that the kth execution of task j is dependent on the (k−d(i,j)) execution of task i;
determining one or more frequencies f allowed for a processor;
defining a set of frequencies F(p) allowed for processor p;
identifying a processor π(i) to which task i is mapped;
determining a power dissipation P(p,f) of processor p at frequency f;
determining a cycle count cc(i) of task i;
determining a percentage α(f,i) of the cycles of a task i that are executed at frequency f, such that the sum of all α(f,i) for a given task is equal to one;
determining a minimum rate μ d at which a task must be executed;
determining a free variable s(i) indicating a worst-case start time of task i; and
formulating a linear programming problem as
minimize
∑
i
∈
V
×
∑
f
∈
F
(
π
(
i
)
)
P
(
π
(
i
)
,
f
)
×
cc
(
i
)
f
×
α
(
f
,
i
)
,
subject to the constraints
∀(i,j)εE,
s
(
j
)
-
s
(
i
)
≥
-
d
(
i
,
j
)
×
μ
d
+
∑
f
∈
F
(
π
(
i
)
)
cc
(
i
)
f
×
α
(
f
,
i
)
,
∀iεV,
∑
f
∈
F
(
π
(
i
)
)
α
(
f
,
i
)
=
1
,
∀fεF(π(i)),
∀iεV, s(i)≧0, and
0≧α(f,i)≧1.
10. The method of claim 9 wherein the linear programming problem further includes the constraint that s(j)−s(i)≦(the latency of each activation of task i and subsequent activation of task j).
11. The method of claim 9 wherein static ordering of tasks within a processor is represented by adding edges with d(i,j)=0 delays from each preceding task i in the ordering to its succeeding task j in the ordering, subject to the constraint that an edge having d−1 must be placed between the last task in the order and the first task in the order.
12. The method of claim 11 further comprising adding edges to represent buffer sizes between tasks, wherein the buffer size represents the dependence of a producer task on the availability of space to store data in the buffer for a consuming task.
13. The method of claim 12 wherein the linear programming problem is further constrained by a buffer constraint edge (j,i) being added for each inter-task buffer, with the constraint that d(j,i)=(size_of_buffer−d(i,j)).