Distributed online optimization for latency assignment and slicing
A system and method for latency assignment in a system having shared resources for performing jobs including computing a new resource price at each resource and sending the new resource price to a task controller in a task path that has at least one job running in the task path. A path price is computed for each task path of the task controller, if there is a critical time specified for the task. New deadlines are determined for the resources in a task path based on the resource price and the path price. The new deadlines are sent to the resources where the at least one job is running to improve system performance.
1. A computer implemented method for latency assignment in a system having shared resources for performing jobs, comprising:
computing a new resource price at each resource based on latencies in a previous iteration;
sending the new resource price to a task controller that has at least one subtask running at the resource, wherein each subtask has an initial deadline;
determining new deadlines for the subtasks in a task based on the new resource prices at the task controller, comprising determining an optimal deadline by maximizing an objective function based on utility functions for each task, wherein the utility functions are based on a percentile of a task latency; and
sending the new deadlines to the resources where at least one subtask in the task is running to improve system performance.
2. The method as recited in claim 1 , wherein computing a new resource price includes computing the new resource price using a gradient projection method.
3. The method as recited in claim 1 , wherein computing a new resource price includes computing the new resource price in accordance with
μ
r
(
t
+
1
)
=
μ
r
(
t
)
-
γ
r
(
B
r
-
∑
s
∈
S
r
share
r
(
s
,
lat
s
)
)
,
where μ r (t) is the price for resource r at a given iteration t, γ r is a step size, B r is a resource availability, S r is a set of subtasks, share r is a share function, and lat s is the worst case latency for a subtask s.
4. The method as recited in claim 3 , wherein computing the new resource price includes adjusting a step size in accordance with resource congestion.
5. The method as recited in claim 1 , further comprising computing a path price for each task path of the task controller if there is a critical time specified for the task.
6. The method as recited in claim 5 , wherein computing a path price for each task path includes computing the path price based upon latencies in a previous iteration.
7. The method as recited in claim 5 , wherein computing a path price for each task path includes computing the path price in accordance with
λ
p
(
t
+
1
)
=
λ
p
(
t
)
-
γ
p
(
1
-
∑
s
∈
S
p
lat
s
C
i
)
,
where λ p (t) is the price for path p at a given iteration t, γ p is a step size, S p is a set of subtasks, lat s is the worst case latency for a subtask s, and C i is a critical time of a task i.
8. The method as recited in claim 7 , wherein computing the path price includes adjusting a step size in accordance with resource congestion.
9. The method as recited in claim 1 , wherein determining new deadlines includes computing a share of a resource to allocate to a subtask.
10. A non-transitory computer readable storage medium comprising a computer readable program for latency assignment in a system having shared resources for performing jobs, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
computing a new resource price at each resource based on latencies in a previous iteration;
sending the new resource price to a task controller that has at least one subtask running at the resource, wherein each subtask has an initial deadline;
determining new deadlines for the subtasks in a task based on the new resource prices at the task controller, comprising determining an optimal deadline by maximizing an objective function based on utility functions for each task, wherein the utility functions are based on a percentile of a task latency; and
sending the new deadlines to the resources where at least one subtask in the task is running to improve system performance.
11. The computer readable storage medium as recited in claim 10 , wherein computing a new resource price includes computing the new resource price using a gradient projection method.
12. The computer readable storage medium as recited in claim 10 , further comprising computing a path price for each task path of the task controller if there is a critical time specified for the task.
13. The computer readable storage medium as recited in claim 12 , wherein computing a path price for each task path includes computing the path price based upon latencies in a previous iteration.
14. The computer readable storage medium as recited in claim 10 , wherein determining new deadlines includes computing a share of a resource to allocate to a subtask.
15. A computer implemented method for latency assignment in a system having shared resources for performing jobs, comprising:
computing a new resource price at each resource based upon latencies in a previous iteration;
sending the new resource price to a task controller that has at least one subtask running at the resource as feedback, wherein each subtask has an initial deadline;
computing a path price for each path of the task at the task controller based upon latencies in the previous iteration;
determining new deadlines for the subtasks in a task based on the resource prices and the path prices at the task controller by maximizing a Lagrangian of a constrained objective function describing subtask latencies, wherein the objective function is based on utility functions for each task and the utility functions are based on a percentile of a task latency;
sending the new deadlines to the resources where at least one subtask is running; and
iterating to update deadlines.