US 11,531,568 B2 · Time-aware application task scheduling system

Abstract

A time-aware application task scheduling system for a green data center (GDC) that includes a task scheduling processor coupled to one or more queue processors and an energy collecting processor connected to one or more renewable energy sources and a grid power source. The systems is capable of determining a service rate for a plurality of servers to process a plurality of application tasks in the GDC and scheduling, via processing circuitry, one or more of the application tasks to be executed in one or more of the servers at a rate according to a difference in an accumulated arriving rate for the plurality of application tasks into the one or more queues and a removal rate for the plurality of application tasks from the one or more queues. The system is further capable of removing the one or more application tasks from their associated queues for execution in the scheduled one or more servers.

A time-aware application task scheduling system for a green data center (GDC), the GDC having a task scheduling processor coupled to one or more queue processors and an energy collecting processor connected to one or more renewable energy sources and a grid power source, wherein the task scheduling processor is configured to periodically receive energy data from the energy collecting processor, regarding available energy from renewable energy resources, wherein the resources of the renewable energy source are used first and then-when necessary, resources from the grid power source are used, and wherein the one or more queue processors are configured to receive a plurality of application tasks from a plurality of electronic devices into the one or more queue processors of the application task scheduling system, per application, of the GDC,

the time-aware application task scheduling system, comprising:
a plurality of servers configured to process the plurality of application tasks;
and
the task scheduling processor configured to:
determine a task service rate for each of the plurality of servers to schedule the plurality of application tasks received from the plurality of electronic devices, each of said task service rate being determined according to a difference in an accumulated arriving rate for the plurality of application tasks in a respective time interval into the one or more queue processors and a removal rate for the plurality of application tasks in the respective time interval for removing immediately a batch of L(1−δ(λτna,μτn))λτna application tasks from their associated queue processors for execution in the scheduled one or more servers, the number of the application tasks scheduled being based on the determined task service rate for the plurality of servers and the accumulated arriving rate into the one or more queue processors using a particle swarm optimization technique and a simulated annealing technique that solves a formulated novel profit maximization problem for a GDC, the profit maximization problem is derived with an M/M/1/Cn/∞ queueing system, the task service rate representing a rate at which the application tasks are removed from the one or more queue processors and executed,
the task scheduling processor further configured to:
initialize a random velocity and a random position for a plurality of representative application tasks in a cluster of application tasks representing an initial swarm for the service rate,
determine an initial fitness level of each representative application task in the cluster of application tasks, the initial fitness level representing a profit of the green data center based on a total revenue of the GDC for the initial swarm, an energy cost of the GDC, and a penalty associated with violated constraints,
determine an initial optimum position of each representative application task and an initial optimum position of the cluster of application tasks, the position of each of the application tasks, which is represented by a particle, contains decision variables including μτn and {tilde over (μ)}τ+bn,
initialize one or more predetermined task scheduling parameters associated with the particle swarm optimization technique,
update a velocity and a position of each representative application task based upon the initialized task scheduling parameters using a Metropolis acceptance criterion, and based upon the initialized task scheduling parameters associated with the chaotic system, wherein said updating includes, for each said application task, if a new position of the application task is better than a current position thereof, the new position is accepted, otherwise, the new position is conditionally accepted only if the Metropolis acceptance criterion is met,
calculate a current fitness level of each representative application task in a current cluster of application tasks,
update a current optimum position of each representative application task and a current optimum position of the cluster of application tasks,
decrease a temperature by a temperature cooling rate of each representative application task and an inertia weight of each representative application task from an upper bound inertia weight to a lower bound inertia weight,
calculate a chaotic search parameter for an iteration in a chaotic system, the chaotic search parameter being distributed between zero and one,
update the velocity and the position of each representative application task based in part upon the chaotic search parameter, and
determine the task service rate for the plurality of servers based on the updated velocity and the updated position of each representative application task, the updated position including μτn and {tilde over (μ)}τ+bn,
schedule, via the task scheduling processor, one or more of the plurality of application tasks to be executed in one or more of the plurality of servers at a rate determined according to a difference in an accumulated arriving rate for the one or more application tasks into the one or more queue processors and a removal rate for the one or more application tasks from the one or more queue processors, the number of the one or more application tasks scheduled being based on the determined task service rate for the plurality of servers and the accumulated arriving rate for the plurality of application tasks into the one or more queue processors, and a batch of L(1−δ(λτna,μτn))λτna tasks being immediately scheduled and executed in plurality of servers in the GDC;
and
remove immediately the batch of L(1−δ(λτna,μτn))λτna application tasks from their associated queue processors for execution in the scheduled one or more servers,
wherein the one or more application tasks are scheduled to maximize a profit in the GDC while guaranteeing delay constraints of each application,
wherein each application task is constrained by the following equations:
Λ
τ
-
B
n
-
1
n
+
λ
τ
-
B
n
n
⁢
L
≤
D
τ
-
1
n
+
(
λ
τ
na
(
1
-
δ
⁡
(
λ
τ
na
,
μ
τ
n
)
)
⁢
L
)
(
5
)
Λ
τ
-
B
n
-
1
n
+
∑
u
=
τ
-
B
n
τ
-
B
n
+
b
(
λ
u
n
⁢
L
)
≤
D
τ
-
1
n
+
(
λ
τ
na
(
1
-
δ
⁡
(
λ
τ
na
,
μ
τ
n
)
)
⁢
L
)
+
∑
u
=
τ
+
1
τ
+
b
(
λ
~
u
na
(
1
-
δ
⁡
(
λ
~
u
na
,
μ
~
u
n
)
)
⁢
L
)
,
1
≤
b
≤
B
n
,
and
(
6
)
Λ
τ
-
B
n
-
1
n
+
∑
u
=
τ
-
B
n
τ
❘
(
λ
u
n
⁢
L
)
=
D
τ
-
1
n
+
(
λ
τ
na
(
1
-
δ
⁡
(
λ
τ
na
,
μ
τ
n
)
)
⁢
L
)
+
∑
u
=
τ
+
1
τ
+
B
n
(
λ
~
u
na
(
1
-
δ
⁡
(
λ
~
u
na
,
μ
~
u
n
)
)
⁢
L
)
,
(
9
)
where Λτn is the number of already-arrived tasks, Bn is the delay constraint, μτn is the arriving rate of its task in a time interval τ, L is length of each interval, Dτn is number of tasks scheduled in τ intervals, λτna is the accumulated arriving rate of tasks of application n in interval τ, μτn is the rate at which tasks of application n are removed from the queue, δ(λτna,μτn) is the loss possibility of tasks of application n in interval τ, and b is a time interval (1≤b≤Bn),
wherein the servers associated with each said application task are homogeneous, and
wherein the servers across the application tasks are heterogeneous.

270 more elements

Time-aware application task scheduling system

Life of this patent

Time-aware application task scheduling system

Life of this patent

Abstract

Claims7