US 10,871,993 B2 · Time-aware method of scheduling application tasks in a green data center

Abstract

A time-aware method of scheduling application tasks in a green data center (GDC) using a task scheduling processor and an energy collecting processor connected to one or more renewable energy sources and a grid power source. The method includes receiving energy data regarding available energy from renewable energy resources such that the renewable energy source is used first then receiving the application tasks and determining a service rate for servers to process the application tasks by using a service rate obtained by solving a profit maximization problem for the GDC by prioritizing and immediately scheduling or removing certain application tasks. The method also includes determining an initial fitness level of each representative application task based on total revenue of the GDC, an energy cost of the GDC, and a penalty associated with violated constraints. The application tasks are formulaically scheduled to be executed in one or more of the servers such that the application tasks maximize a profit in the GDC while guaranteeing delay constraints.

A time-aware method of scheduling application tasks in a green data center (GDC), wherein the GDC comprises a task scheduling processor coupled to one or more queues and an energy collecting processor connected to one or more renewable energy sources and a grid power source, the time-aware method comprising:

receiving, by the task scheduling processor, energy data from the energy collecting processor regarding available energy from renewable energy resources, wherein the resources of the one or more renewable energy sources are used first and when necessary, resources from the grid power source are used;
receiving, from a plurality of electronic devices, a plurality of application tasks into the respective one or more queues, per application, of the GDC;
determining, via the task scheduling processor, a service rate for a plurality of servers to process the plurality of application tasks in the GDC, the service rate representing a rate at which application tasks are removed from the one or more queues and executed, the service rate being obtained by solving a formulated novel profit maximization problem for the GDC, the problem being derived with an M/M/1/Cn/∞ queueing system, wherein a batch of L(1−δ(λτna, μτn))λτna tasks are immediately scheduled and executed in servers in the GDC, and the batch of L(1−δ(λτna, μτn))λτna application tasks are removed immediately from their associated queues for execution in the scheduled one or more servers, and wherein said determining the service rate for the plurality of servers uses a particle swarm optimization technique and a simulated annealing technique that includes:
initializing, via the task scheduling processor, 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,
determining, via the task scheduling processor, 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,
determining, via the task scheduling processor, 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,
initializing, via the task scheduling processor, one or more predetermined task scheduling parameters associated with the simulated annealing technique, a chaotic system, and the particle swarm optimization technique,
updating, via the task scheduling processor, 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,
calculating, via the task scheduling processor, a current fitness level of each representative application task in a current cluster of application tasks,
updating, via the task scheduling processor, a current optimum position of each representative application task and a current optimum position of the cluster of application tasks,
decreasing 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,
calculating, via the task scheduling processor, a chaotic search parameter for an iteration in the chaotic system, the chaotic search parameter being distributed between zero and one,
updating, via the task scheduling processor, the velocity and the position of each representative application task based in part upon the chaotic search parameter, and
determining the 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;
scheduling, via the task scheduling processor, 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 one or more application tasks into the one or more queues and a removal rate for the one or more application tasks from the one or more queues, the number of the one or more application tasks scheduled being based on the determined service rate for the plurality of servers and the accumulated arriving rate for the plurality of application tasks into the one or more queues, and a batch of L(1−δ(λτna, μτn))λτna tasks being immediately scheduled and executed in servers in the GDC;
and
removing immediately the batch of L(1−δ(λτna, μτn))λτna application tasks from their associated queues 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, and
wherein each application task is constrained by the following equations:
Λτ−Bn−1n+λτ−BnnL≤Dτ−1n+(λτ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
,
(
6
)
and
Λ
τ
-
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
)
,
(
6
)
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).

225 more elements

Time-aware method of scheduling application tasks in a green data center

Life of this patent

Time-aware method of scheduling application tasks in a green data center

Life of this patent

Abstract

Claims6