# US 2024/0004707 A1 · Methods and systems for energy-efficient scheduling of periodic tasks on a group of processing devices

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0004707 A1
- Document ID: US20240004707A1
- Status: Published application
- Kind: A1
- Application number: 18/343,304
- Filed: 2023-06-28
- Published: 2024-01-04
- Earliest claimed: 2022-06-29
- Assignees: Orange
- Applicants: Orange
- Inventors: Lan Wang; Lei Yu
- Web page: https://patentgrep.com/patent/US20240004707A1

## CPC

- G06F 9/4893: {taking into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206)}
- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

An energy-efficient assignment of a task set T to a group of M processing devices models the process of deciding the assignment as a combinatorial optimization problem having an objective function optimizing the power consumption of the devices when executing subsets of the tasks, under a constraint that the total utilization of the task subset assigned to each respective processing device is lower than a threshold depending on the number of its processor cores. The objective function may be: min Σi=1M Pi(τi), where τi denotes the subset of tasks allocated to the ith device, and Pi(τi) represents power consumption of the ith device when executing τi, and the constraint Uτi≤Mi/4 for all the devices, where Uτi is the total utilization of τi executing on the ith device, and Mi denotes the number of cores of the ith device. Solving the problem using a MaxMin or genetic algorithm gives good energy efficiency.

## Claims

### Claim 1

A computer-implemented method of scheduling periodic tasks on a group of multi-core processors, the method comprising:
defining as a combinatorial optimization problem a function of assigning, among a group of M processing devices, a set of tasks T for execution, using an objective function optimizing the power consumption of said processing devices when executing subsets of said tasks T, with a constraint that, for each processing device, a total utilization of a task subset assigned to the respective processing device, when executing on said processing device, is lower than a threshold, said threshold depending on the number of processor cores of said respective processing device;
applying a heuristic algorithm to generate a solution to the defined combinatorial optimization problem; and
commanding the scheduling, on each of the processing devices, of the task subset assigned to the respective processing device by the solution generated by the heuristic algorithm.

### Claim 2 (depends on 1)

The method of claim 1, wherein each periodic task comprises subtasks and dependencies capable of representation by a directed acyclic graph, and for a group of M processing devices and a set of tasks T for execution, an ith processing device having a number of processor cores equal to Mi, an objective function of the combinatorial optimization problem is
min
⁢
∑
i
=
1
M
P
i
(
τ
i
)
where τi denotes a subset of tasks, from task set T, which are allocated to the ith processing device, and Pi(τi) represents the power consumption of the i th processing device when executing the task sub-set τi;
wherein said constraint is that, in the solution, the relationship Uτi≤Mi/4 is respected for all the processing devices scheduled to execute tasks, where Uτi is the total utilization of the task sub-set τi when executing on the ith processing device;
and wherein said heuristic algorithm is a heuristic MaxMin algorithm or a meta-heuristic Genetic Algorithm to generate a solution to the defined combinatorial optimization problem.

### Claim 3 (depends on 2)

The method of claim 2, wherein a heuristic MaxMin algorithm is applied to generate a solution to the defined combinatorial optimization problem, and the application of the heuristic MaxMin algorithm comprises:
setting to zero a sum of tasks' utilization on each processing device j of the group;
determining a maximum value and minimum value of average power consumption for each task Ti on each processing device j in a case where no power-saving measures are employed;
for each task, determining a global maximum and global minimum of the average power consumption across the processing devices in the group;
sorting the tasks of the group in a list of tasks in descending order dependent on a difference between the global maximum and global minimum average power consumption for the respective task;
sorting the processing devices of the group in a list of groups in ascending order of minimum value of average power consumption;
for each processing device in the list of groups, determining whether the sum of (i) the existing utilization of the respective processing device j, and (ii) the utilization of the remaining highest-ranked task ThTh, in the list of tasks, is less than or equal to Mj/4; and
upon a determination that said sum is less than or equal to Mj/4, then assigning task Th to processing device j, and increasing the value for utilization of device j to said sum.

### Claim 4 (depends on 2)

The method of claim 2, wherein a meta-heuristic Genetic Algorithm is applied to generate a solution to the defined combinatorial optimization problem, and the application of the heuristic Genetic Algorithm comprises:
designing a chromosome used by the Genetic Algorithm as a vector, each vector location corresponding to a gene location in the Genetic Algorithm and each gene location corresponding to a task to be assigned to a processing device;
setting the possible gene values to correspond to identifiers of the respective processing devices in the group; and
running the Genetic Algorithm with a fitness function min Σi=1M Pi(τi).

### Claim 5 (depends on 1)

The method of claim 1, wherein on each of the processing devices, the scheduling of the assigned task subset is performed using a global earliest deadline first algorithm.

### Claim 6 (depends on 1)

The method of claim 1, wherein, in a preliminary step, a first processing device of the processing devices attempts to schedule the set of tasks for execution on its own processor cores, and upon a determination that the scheduling attempt demonstrates that a resulting workload is too great for the first processing device to execute while respecting timing constraints of the task set that the combinatorial optimization problem is defined and solved to offload tasks to one or more other processing devices in the group.

### Claim 7 (depends on 6)

The method of claim 6, wherein in said preliminary step, the first of the processing devices attempts to schedule the set of tasks for execution on its own processor cores according to a process comprising:
decomposing a task into subtasks according to a directed-acyclic-graph representation of the task;
generating a timing diagram assuming an infinite number of processor cores are available to process subtasks in parallel, said timing diagram representing execution of said subtasks on a schedule respecting the deadlines and dependencies of the subtasks defined by the directed-acyclic-graph;
segmenting the timing diagram based on release times and deadlines of the subtasks, each segment including one or more parallel processing threads for execution, respectively, of at least part of a subtask by a respective processor core;
for each segment, dependent on the workload in the segment, deciding the frequency and/or voltage to be used by the processor core or cores to execute the one or more parallel processing threads of the segment, said decision setting the processor-core frequency and/or voltage to reduce power consumption to an extent that still enables respect of the subtask deadlines; and
scheduling execution of the subtasks of the segments assuming the processor-core frequencies and/or voltages set in the deciding step.

### Claim 8 (depends on 7)

The method of claim 7, wherein in the preliminary step:
the generating of the timing diagram assigns to each segment a first number, m, of processor cores operating at a first speed, s; and
the deciding of processor-core frequency and/or speed in respect of a segment changes the number of processor cores assigned to the segment to a second number m′ and selects a second speed s′ for the second number of processor cores, according to the following process:
determining whether the maximum utilization among the utilizations of the subtasks having portions in the segment is less than or equal to sB/smax′ where smax is the maximal speed of the processor cores and sB is a speed bound defined as
s
B
=
(
P
s
2
⁢
C
)
1
/
3
where Ps and C are constants in the power consumption function of the processor,
determining whether a highest utilization umax is less than or equal to sB/smax′
upon a determination that the highest utilization umax is less than or equal to sB/smax′ deciding the second speed s′ to be equal to sB, and deciding the second number m′ of processor cores to be equal to
⌊
m
×
s
s
B
⌋
,
and
upon a determination that the highest utilization umax is greater than value sB/smax′ decide the second speed s′ to be equal to umax×smax, and decide the second number m′ of processor cores to be equal to
⌊
m
×
s
u
max
×
s
max
⌋
.

### Claim 9 (depends on 6)

The method of claim 6, wherein in the preliminary step the scheduling of execution of the subtasks of the segments is performed using a global earliest deadline first algorithm.

### Claim 10

A scheduling system configured to schedule periodic tasks on a group of multi-core processors, said system comprising a computing apparatus programmed to execute instructions to perform a computer-implemented method of scheduling periodic tasks on a group of multi-core processors, the method comprising:
defining as a combinatorial optimization problem a function of assigning, among a group of M processing devices, a set of tasks T for execution, using an objective function optimizing the power consumption of said processing devices when executing subsets of said tasks T, with a constraint that, for each processing device, a total utilization of a task subset assigned to the respective processing device, when executing on said processing device, is lower than a threshold, said threshold depending on the number of processor cores of said respective processing device;
applying a heuristic algorithm to generate a solution to the defined combinatorial optimization problem; and
commanding the scheduling, on each of the processing devices, of the task subset assigned to the respective processing device by the solution generated by the heuristic algorithm.

### Claim 11 (depends on 10)

An edge server comprising the scheduling system of claim 10.

### Claim 12 (depends on 1)

A non-transitory computer readable medium having stored thereon a computer program which, when the program is executed by a processing unit of a computing apparatus, cause said processing unit to implement the method of claim 1.

### Claim 13 (depends on 1)

A non-transitory computer-readable medium having stored thereon instructions which, when executed by a processor of a computing apparatus, cause the processor to perform the method of claim 1.
