US9755992B2ActiveUtilityPatentIndex 50
Distributed online optimization for latency assignment and slicing
Est. expiryJan 8, 2028(~1.5 yrs left)· nominal 20-yr term from priority
G06F 9/5038H04L 47/822H04L 47/83
50
PatentIndex Score
0
Cited by
8
References
18
Claims
Abstract
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 based on latencies in a previous iteration. The new resource price is sent to a task controller that has at least one subtask running at the resource. Each subtask has an initial deadline. New deadlines for the subtasks in a task are determined based on the new resource prices at the task controller. The new deadlines are sent to the resources where at least one subtask in the task is running to improve system performance.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1. A 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; 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. The method as recited in claim 1 , wherein determining new deadlines includes determining an optimal deadline by maximizing an objective function.
11. The method as recited in claim 10 , wherein the objective function is based on utility functions for each task.
12. 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; and
sending the new deadlines to the resources where at least one subtask in the task is running to improve system performance.
13. The computer readable storage medium as recited in claim 12 , wherein computing a new resource price includes computing the new resource price using a gradient projection method.
14. The computer readable storage medium as recited in claim 12 , further comprising computing a path price for each task path of the task controller if there is a critical time specified for the task.
15. The computer readable storage medium as recited in claim 14 , wherein computing a path price for each task path includes computing the path price based upon latencies in a previous iteration.
16. The computer readable storage medium as recited in claim 12 , wherein determining new deadlines includes computing a share of a resource to allocate to a subtask.
17. The computer readable storage medium as recited in claim 12 , wherein determining new deadlines includes determining an optimal deadline by maximizing an objective function.
18. A 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;
sending the new deadlines to the resources where at least one subtask is running; and
iterating to update deadlines.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.