Latency and dependency-aware task scheduling workloads on multicore platforms for energy efficiency

1 . An apparatus of a computing node of a network, the apparatus comprising an interconnect interface to connect the apparatus to one or more components of the computing node, and a processor to:

determine dependencies between sets of tasks of a plurality of tasks to be executed by a plurality of cores of the network;

determine latency deadlines of respective ones of the plurality of tasks;

determine an allocation of individual ones of the plurality of tasks among the plurality of cores to generate an allocation X of the plurality of tasks to the plurality of cores, allocation X being based on the dependencies, on the latency deadlines, and on a minimal energy consumption of the plurality of cores; and

send, to one or more of the one or more components of the computing node and through the interconnect interface, communication to cause the computing node to transmit, to the plurality of cores, information based on allocation X, the information for execution of the plurality of tasks by the plurality of cores wherein the processor is to determine allocation X by using a reinforcement learning (RL) model to:

determine a set of allocations to generate a suggested allocation of the plurality of tasks to the plurality of cores, wherein determination of each individual allocation of the set of allocations comprises:

determining a predicted allocation of a task of the plurality of tasks on a next available one of the plurality of cores based on remaining tasks of the plurality of tasks to be allocated;

for the next available one of the plurality of cores:

sorting corresponding tasks in the predicted allocation based on their latency deadlines and based on their dependencies; and

estimating a total energy to be used by the next available one of the plurality of cores in an execution of the corresponding tasks; and

generate a final reward value for the suggested allocation in response to a determination that dependencies between the sets of tasks and latencies of the respective ones of the plurality of tasks have been satisfied, allocation X dependent on the final reward value.

2 . The apparatus of claim 1 , the processor to:

sort the plurality of tasks based on the dependencies between the sets of tasks and based on the latency deadlines; and

after sorting, store the plurality of tasks in a pool of sorted unallocated tasks in a memory of the network, wherein the processor is to determine the allocation by:

fetching each of the tasks from the memory of the network based on a sorting order thereof in the pool of sorted unallocated tasks;

determining a next available core of the plurality of cores based on one or more core availability criteria;

determining an allocation of said each of the tasks to the next available core; and

repeating fetching, determining the next available core, and determining an allocation of said each of the tasks until at least one set of the plurality of tasks has been allocated; and

sending, to one or more of the one or more components of the computing node, communication to cause the computing node to send to at least some of the plurality of cores information based on the allocation of said each of the tasks the information for execution of the at least one set of the plurality of tasks by the at least some of the plurality of cores.

3 . The apparatus of claim 2 , wherein the processor is to sort the plurality of tasks first in ascending order based on latency deadlines of the tasks, and, within tasks of a same latency deadline, based on average latency cost.

4 . The apparatus of claim 1 , wherein the processor is to use a reinforcement learning (RL) model to generate an intermediate reward value for one or more individual allocations of the set of allocations during a training phase of the RL model, the intermediate reward value based on a determination that at least one task in the one or more individual allocations is to overflow, a determination that an execution of at least one task in the one or more individual allocations is to fail to satisfy a dependency between the sets of tasks, or a determination that at least one task remains unallocated.

5 . The apparatus of claim 4 , wherein the processor is to, during the training phase, determine allocation X by recursively determining training allocations of individual ones of the plurality of tasks, wherein each successive recursion is to be based on a higher intermediate reward value than a prior recursion.

6 . The apparatus of claim 4 , wherein the processor is to generate the intermediate reward value by at least one of:

in response to a determination that a task in the one or more individual allocations is to overflow, generate the intermediate reward value to be based on a ratio of a completion time of the task that is to overflow and a latency deadline of the task that is to overflow; or

in response to a determination that at least one task remains unallocated, generate the intermediate value to equal a positive value.

7 . The apparatus of claim 6 , wherein the intermediate reward value based on the ratio of the completion time of the task that is to overflow and the latency deadline of the task that is to overflow corresponds to

min

i

,

k

⁢

1

-

TC

i

T

k

,

i

,

where i denotes a task number of the task that is to overflow, k denotes task type, T Ci is the completion time and T ki is the latency deadline.

8 . The apparatus of claim 1 , wherein the final reward value is based on a sum of all energy E i consumed by the plurality of cores for all tasks i of the plurality of tasks if all tasks i were to be executed.

9 . The apparatus of claim 8 , wherein the final reward value is given by

β

*

(

1

-

Σ

i

⁢

E

i

E

max

+

λ

*

N

e

N

)

,

where i denotes a task number within the plurality of tasks, β is a final reward amplification factor, N e is number of completely empty cores, N is number of cores, and λ is a factor that corresponds to an empty core reward factor.

10 . The apparatus of claim 1 , wherein the apparatus further comprises a transceiver to provide wireless communication between the apparatus and other edge computing nodes of the network.

11 . One or more computer readable media comprising instructions that, when executed by a machine of a computing node of a network, are to cause the machine to perform operations including:

determine dependencies between sets of tasks of a plurality of tasks to be executed by a plurality of cores of the network;

determine latency deadlines of respective ones of the plurality of tasks;

determine an allocation of individual ones of the plurality of tasks among the plurality of cores to generate an allocation X of the plurality of tasks to the plurality of cores, allocation X being based on the dependencies, on the latency deadlines, and on a minimal energy consumption of the plurality of cores;

send, through an interconnect interface, communication to cause the computing node to transmit, to the plurality of cores, information based on allocation X, the information for execution of the plurality of tasks by the plurality of cores; and

determine allocation X by using a reinforcement learning (RL) model to:

determine a set of allocations to generate a suggested allocation of the plurality of tasks to the plurality of cores, wherein determination of each individual allocation of the set of allocations comprises:

determining a predicted allocation of a task of the plurality of tasks on a next available one of the plurality of cores based on remaining tasks of the plurality of tasks to be allocated;

for the next available one of the plurality of cores:

sorting corresponding tasks in the predicted allocation based on their latency deadlines and based on their dependencies; and

estimating a total energy to be used by the next available one of the plurality of cores in an execution of the corresponding tasks; and

generate a final reward value for the suggested allocation in response to a determination that dependencies between the sets of tasks and latencies of the respective ones of the plurality of tasks have been satisfied, allocation X dependent on the final reward value.

12 . The one or more computer readable media of claim 11 , the operations further including:

sorting the plurality of tasks based on the dependencies between the sets of tasks and based on the latency deadlines; and

after sorting, storing the plurality of tasks in a pool of sorted unallocated tasks in a memory of the network, wherein the operations further include determining the allocation by:

fetching each of the tasks from the memory of the network based on a sorting order thereof in the pool of sorted unallocated tasks;

determining a next available core of the plurality of cores based on one or more core availability criteria;

determining an allocation of said each of the tasks to the next available core; and

repeating fetching, determining the next available core, and determining an allocation of said each of the tasks until at least one set of the plurality of tasks has been allocated; and

sending communication to cause the computing node to send to at least some of the plurality of cores information based on the allocation of said each of the tasks the information for execution of the at least one set of the plurality of tasks by the at least some of the plurality of cores.

13 . The one or more computer readable media of claim 12 , wherein the one or more core availability criteria include whether a worst-case latency cost of said each of the tasks fits within a remaining latency budget of a candidate core of the plurality of cores being evaluated to be the next available core.

14 . The one or more computer readable media of claim 12 , the operations further including using a reinforcement learning (RL) model to generate an intermediate reward value for one or more individual allocations of the set of allocations during a training phase of the RL model, the intermediate reward value based on a determination that at least one task in the one or more individual allocations is to overflow, or a determination that at least one task remains unallocated.

15 . The one or more computer readable media of claim 14 , the operations further including, during the training phase, determining allocation X by recursively determining training allocations of individual ones of the plurality of tasks, wherein each successive recursion is to be based on a higher intermediate reward value than a prior recursion.

16 . A distributed edge computing system comprising:

a central server; and

a plurality of computing nodes communicably coupled to the central server, at least one of the computing nodes including one or more processors and storing instructions that, when executed by the one or more processors, cause the at least one of the computing nodes to perform operations including:

determining dependencies between sets of tasks of a plurality of tasks to be executed by a plurality of cores of the system;

determining latency deadlines of respective ones of the plurality of tasks; and

determining an allocation of individual ones of the plurality of tasks among the plurality of cores to generate an allocation X of the plurality of tasks to the plurality of cores, allocation X being based on the dependencies, on the latency deadlines, and on a minimal energy consumption of the plurality of cores;

sending, through an interconnect interface, communication to cause the computing node to transmit, to the plurality of cores, information based on allocation X, the information for execution of the plurality of tasks by the plurality of cores; and

determining an allocation X by using a reinforcement learning (RL) model to:

determine a set of allocations to generate a suggested allocation of the plurality of tasks to the plurality of cores, wherein determination of each individual allocation of the set of allocations comprises:

determining a predicted allocation of a task of the plurality of tasks on a next available one of the plurality of cores based on remaining tasks of the plurality of tasks to be allocated;

for the next available one of the plurality of cores:

 sorting corresponding tasks in the predicted allocation based on their latency deadlines and based on their dependencies; and

 estimating a total energy to be used by the next available one of the plurality of cores in an execution of the corresponding tasks; and

generate a final reward value for the suggested allocation in response to a determination that dependencies between the sets of tasks and the latencies of the respective ones of the plurality of tasks have been satisfied, allocation X dependent on the final reward value.

17 . The distributed edge computing system of claim 16 , the operations further including:

sorting the plurality of tasks based on the dependencies between the sets of tasks and based on the latency deadlines; and

after sorting, storing the plurality of tasks in a pool of sorted unallocated tasks in a memory of the computing node, wherein the processor is to determine the allocation by:

fetching each of the tasks based on a sorting order thereof in the pool of sorted unallocated tasks;

determining a next available core of the plurality of cores based on one or more core availability criteria;

determining an allocation of said each of the tasks to the next available core; and

repeating fetching, determining the next available core, and determining an allocation of said each of the tasks until at least one set of the plurality of tasks has been allocated; and

sending, to the computing node, communication to cause the computing node to send to at least some of the plurality of cores information based on the allocation of said each of the tasks the information for execution of the at least one set of the plurality of tasks by the at least some of the plurality of cores.

18 . A method to be performed at an apparatus of a computing node in an edge computing environment, the method comprising:

determining dependencies between sets of tasks of a plurality of tasks to be executed by a plurality of cores of a network;

determining latency deadlines of respective ones of the plurality of tasks; and

determining an allocation of individual ones of the plurality of tasks among the plurality of cores to generate an allocation X of the plurality of tasks to the plurality of cores, allocation X being based on the dependencies, on the latency deadlines, and on a minimal energy consumption of the plurality of cores;

sending, through an interconnect interface, communication to cause the computing node to transmit, to the plurality of cores, information based on allocation X, the information for execution of the plurality of tasks by the plurality of cores; and

determining allocation X using a reinforcement learning (RL) model by:

determining a set of allocations to generate a suggested allocation of the plurality of tasks to the plurality of cores, wherein determination of each individual allocation of the set of allocations comprises:

determining a predicted allocation of a task of the plurality of tasks on a next available one of the plurality of cores based on remaining tasks of the plurality of tasks to be allocated; and

for the next available one of the plurality of cores:

sorting corresponding tasks in the predicted allocation based on their latency deadlines and based on their dependencies; and

estimating a total energy to be used by the next available one of the plurality of cores in an execution of the corresponding tasks; and

generating a final reward value for the suggested allocation in response to a determination that dependencies between the sets of tasks and the latencies of the respective ones of the plurality of tasks have been satisfied.

19 . The method of claim 18 , further including:

sorting the plurality of tasks based on the dependencies between the sets of tasks and based on the latency deadlines; and

after sorting, storing the plurality of tasks in a pool of sorted unallocated tasks in a memory of the computing node, wherein determining the allocation includes:

fetching each of the tasks from the memory based on a sorting order thereof in the pool of sorted unallocated tasks;

determining a next available core of the plurality of cores based on one or more core availability criteria;

determining an allocation of said each of the tasks to the next available core; and

repeating fetching, determining the next available core, and determining an allocation of said each of the tasks until at least one set of the plurality of tasks has been allocated; and

sending, through an interconnect interface, a communication to cause the computing node to send to at least some of the plurality of cores information based on the allocation of said each of the tasks the information for execution of the at least one set of the plurality of tasks by the at least some of the plurality of cores.

20 . The method of claim 18 , further including:

using a reinforcement learning (RL) model to generate intermediate reward values for individual allocations of the set of allocations during a training phase of the RL model, each of the intermediate reward values based on a determination that at least one task in said each individual allocation is to overflow, or a determination that at least one task remains unallocated; and

during the training phase, determining allocation X by recursively determining training allocations of individual ones of the plurality of tasks, wherein each successive recursion is to be based on a higher intermediate reward value of the intermediate reward values than a prior recursion.