Systems and Methods of Managing Computational Resources

Patent metadata

Field	Value
Publication number	US-2018246766-A1
Application number	US-201715560075-A
Country	US
Kind code	A1
Filing date	Sep 1, 2017
Priority date	Sep 2, 2016
Publication date	Aug 30, 2018
Grant date	—

Abstract

Systems and methods of managing computational resources are provided. In one exemplary embodiment, a method by a controller (305, 407, 500, 600, 700, 1101) for managing computational resources may include dynamically distributing (801) computational resource shares among sequential services that are mapped to one or more processors (303, 403). Further, each sequential service corresponds to an execution step of a remote application (307, 409). Also, a service chain (313-315, 413-415) comprises at least one sequential service. The dynamical distribution is based on estimated and predetermined tail latencies and average execution times of each sequential service in the service chain as well as the service chain such that the latencies are met. In addition, the one or more service chains are executed contemporaneously.

First claim

1 - 40 . (canceled)

41 . A method, performed by a controller, for managing computational resources, the method comprising:
dynamically distributing computational resource shares among sequential services that are mapped to one or more processors, wherein each sequential service corresponds to an execution step of a remote application and wherein a service chain comprises at least one sequential service, based on estimated and predetermined tail latencies and average execution times of each sequential service in the service chain as well as the service chain such that the latencies are met, and wherein the one or more service chains are executed contemporaneously.

42 . The method of claim 41 , wherein the dynamically distributing includes, for each chain:
determining a statistical distribution of a workload for each service of that chain based on computational resource shares and current execution times for the services of that chain for a current execution of that chain; and allocating computational resource shares for the services of that chain for a next execution of that chain based on the statistical distributions and the estimated and predetermined tail latencies of that chain.

43 . The method of claim 42 , wherein the determining the statistical distribution of the workload for each service of that chain is further based on a processing capacity of a corresponding processor.

44 . The method of claim 42 , wherein the statistical distribution of the workload for each service of that chain is represented by P(T i,j,k ≤t) as follows:

P


(

T

i
,
j
,
k

≤
t

)

=

P


(

W

i
,
j

E




Φ

i
,
j
,
k





C
k

≤
t

)

=

F

w

i
,
j



(

t



E




Φ

i
,
j
,
k





C
k

)

,

where T i,j,k is an execution time of the unique sequential service j of the service chain i on processor k, t is time, W i,j is a workload of the service j of the chain i, Φ i,j,k is a computational resource share of the service j of the chain i for processor k, E|Φ i,j,k | is an expected computational resource share of the service j of the chain i for processor k, C k is a processing capacity of processor k, and F W i,j (tE|Φ i,j,k |C k ) represents a cumulative density function of T i,j,k expressed by the corresponding workload W i,j .

45 . The method of claim 42 , wherein the allocating includes:
determining candidate computational resource shares of available computational resource shares for the services of that chain based on the statistical distributions; determining the estimated tail latency of that chain based on the candidate shares of that chain and an average execution time of that chain; and evaluating whether to use the candidate shares of that chain as the next shares for that chain based on the estimated and predetermined tail latencies of that chain.

46 . The method of claim 45 , wherein the allocating further includes:
determining the average execution time of that chain and each sequential service in that chain based on an idle time and a probability that such chain is idle; and wherein the evaluating is also based on the average execution time of that chain.

47 . The method of claim 46 , wherein the average execution time of that chain is represented by E|T i | as follows:

E




T
i



=

λ
i

-
1



1
-

p

idle
,
i

p

idle
,
i

,

where E|T i | is an average execution time of chain i, λ i −1 is an idle time of cha

Assignees

• Ericsson Telefon Ab L M

Inventors

• Holmberg Torgny
• Eker Johan
• Persson Joakim

Classifications

• G06F9/5038 Primary

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title