Scheduling method and system, computing grid, and corresponding computer-program product

• US 9,239,734 B2
• Filed: 06/13/2012
• Issued: 01/19/2016
• Est. Priority Date: 06/13/2011
• Status: Active Grant

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Spata, Massimo Orazio
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US13/517,530
• Publication Number:
  US 20120315966A1
• Time in Patent Office: 1,315 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

An embodiment of a method for scheduling execution of jobs with the resources of a Multi-Core system envisages producing a system model based upon agents representing the jobs, said agents being able to implement a strategy for scheduling execution of the jobs with the resources of the Multi-Core system via respective available moves corresponding to the choice of a given resource of the Multi-Core system for execution of a given job. The agents are configured for implementing said strategy as strategy that integrates MiniMax and Nash-equilibrium strategies, for example operating in an iterative way, identifying an optimal solution deriving from the iteration. The strategy can be implemented by maximizing the probability of optimizing the time of completion of a given job for one of the agents.

Claims

1. A method for scheduling the performance of tasks using resources of a Multi-Core system, the method including:

producing a system model based on agents representative of said tasks, said agents configured to implement a scheduling strategy of performing said tasks with the resources of the Multi-Core system via respective available moves corresponding to the choice of a given resource of the Multi-Core system to perform a given task and

wherein said agents are configured to implement said strategy as an integrated MiniMax/Nash Equilibrium strategy.

2. The method of claim 1, wherein said agents are configured to implement in an iterative manner MiniMax and Nash Equilibrium strategies, by identifying an optimal solution deriving from iteration.

3. The method of claim 1, wherein said strategy is implemented by maximizing a probability of optimizing a time of completing a given task for one of said agents.

4. The method of claim 1, including:

identifying for each agent a set of strategies determined by a set of an initial workload on each resource in the Multi-Core system; and

defining a total load on each resource as a sum of performance times of the tasks that select said resource.

5. The method of claim 1, including optimizing results of said integrated MiniMax/Nash Equilibrium strategy with a control game with a MaxiMin solution.

6. The method of claim 1, including:

searching Nash Equilibrium solutions within said system model, selecting the solutions found by a Nash Agent,

in the absence of Nash Equilibrium solutions returning the MiniMax solution for an initial game matrix,

searching MiniMax solutions within said system model, selecting the solutions found by a MiniMax Agent,

playing a new game among all the Agents selected with the Nash and MiniMax solutions found,

for each Nash Agent, comparing its respective solution with a solution of a MiniMax Agent,

if the parameters of the Nash Agent vector correspond to the parameters of the MiniMax Agent vector, and no other solutions exist, returning this solution,

otherwise, for each Nash solution and for each MiniMax solution, iterating the Prisoner'"'"'s Dilemma problem, generating a new 2×

2 matrix with the Nash solution in the first line and the MiniMax solution in the second line,

applying the Nash Equilibrium solution to the new matrix and returning this solution,

optimizing the solution obtained, by playing a new control game between the solution returned and the MaxiMin solution.

7. A scheduler device configured to implement the method of claim 1.

8. A computing grid including a plurality of resources to perform computing tasks, said computing grid including a scheduler according to claim 7.

9. A computer program product, loadable in the memory of at least one computer and including software code portions configured to perform the method of claim 1.

10. An apparatus, comprising:

a first analyzer configured to identify at least one possible first configuration of system nodes according to a first game-theory algorithm;

a second analyzer configured to identify at least one possible second configuration of the system nodes according to a second game-theory algorithm; and

a configuration determiner configured to determine a resulting configuration of the system nodes in response to the identified at least one first and second configurations.

11. The apparatus of claim 10 wherein the system nodes include processing nodes of a computer system;

and the at least one first, at least one second, and resulting configurations include respective assignments of processing tasks to the processing nodes.

12. The apparatus of claim 10 wherein the system nodes include a power-generating node and a power-consuming node of a power grid;

and the at least one first, at least one second, and resulting configurations include respective assignments of a power-generating level to the power-generating node and of a power-consuming level to the power-consuming node.

13. The apparatus of claim 10 wherein one of the first and second gain-theory algorithms includes a Nash-Equilibrium algorithm.

14. The apparatus of claim 10 wherein one of the first and second gain-theory algorithms includes a MiniMax algorithm.

15. The apparatus of claim 10 wherein:

the first analyzer is configured to identify the at least one first configuration of the system nodes as at least one Nash Equilibrium solution;

the second analyzer is configured to identify the at least one second configuration of the system nodes as at least one MiniMax solution; and

the configuration determiner is configured to determine the resulting configuration by

setting the resulting configuration equal to one of the at least one MiniMax solutions if the first analyzer yields no Nash Equilibrium solution, and

if the first analyzer yields at least one Nash Equilibrium solution, then comparing each of the at least one Nash Equilibrium solutions to each of the at least one MiniMax solutions,

if each of the at least one Nash Equilibrium solutions equals a respective one of the at least one MiniMax solutions, and no other solutions exist, then setting the resulting configuration equal to one of the at least one existing solutions,

else, for each respective Nash Equilibrium solution and for each respective MiniMax solution

generating a matrix with the respective Nash Equilibrium solution the respective MiniMax solution,

applying the Nash Equilibrium algorithm to the matrix and returning a resulting solution if a resulting solution exists, and

if the resulting solution exists, then

 

optimizing the resulting solution according to a MaxiMin algorithm, and

 

setting the resulting configuration equal to the resulting solution.

16. A system, comprising:

nodes; and

an apparatus, including

a first analyzer configured to identify at least one possible first configuration of the nodes according to a first game-theory algorithm;

a second analyzer configured to identify at least one possible second configuration of the nodes according to a second game-theory algorithm; and

a configuration determiner configured to determine a resulting configuration of the nodes in response to the identified at least one first and second configurations.

17. The system of claim 16 wherein the nodes include data-processing nodes;

and the at least one first, at least one second, and resulting configurations include respective data to be processed by the data-processing nodes.

18. The system of claim 16 wherein the nodes include a power-generating node and a power-consuming node;

and the at least one first, at least one second, and resulting configurations include respective assignments of a power-generating level to the power-generating node and of a power-consuming level to the power-consuming node.

19. A method, comprising:

identifying at least one possible first configuration of system nodes according to a first game-theory algorithm;

identifying at least one possible second configuration of the system nodes according to a second game-theory algorithm; and

determining a resulting configuration of the system nodes in response to the identified at least one first and second configurations.

20. The method of claim 19, further comprising:

wherein identifying the at least one first configuration of the system nodes includes identifying that at least one first configuration as at least one Nash Equilibrium solution;

wherein identifying the at least one second configuration of the system nodes includes identifying the at least one second configuration as at least one MiniMax solution; and

determining the resulting configuration by

setting the resulting configuration equal to one of the at least one MiniMax solutions if no Nash Equilibrium solution is identified, and

if at least one Nash Equilibrium solution is identified, then

comparing each of the at least one Nash Equilibrium solutions to each of the at least one MiniMax solutions,

if each of the at least one Nash Equilibrium solutions equals a respective one of the at least one MiniMax solutions, and no other solutions exist, then setting the resulting configuration equal to one of the at least one existing solutions,

else, for each respective Nash Equilibrium solution and for each respective MiniMax solution

 

generating a matrix with the respective Nash Equilibrium solution the respective MiniMax solution,

 

applying the Nash Equilibrium algorithm to the matrix and returning a resulting solution if a resulting solution exists, and

 

if the resulting solution exists, then

 

optimizing the resulting solution according to a MaxiMin algorithm, and

 

setting the resulting configuration equal to the resulting solution.

21. A non-transitory computer-readable medium including instructions that, when executed by a computing apparatus, cause the computing apparatus to perform steps comprising:

identifying at least one possible first configuration of system nodes according to a first game-theory algorithm;

identifying at least one possible second configuration of the system nodes according to a second game-theory algorithm; and

determining a resulting configuration of the system nodes in response to the identified at least one first and second configurations.