Affinity dispatching load balancer with precise CPU consumption data

• US 20080046895A1
• Filed: 08/15/2006
• Published: 02/21/2008
• Est. Priority Date: 08/15/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dillenberger, Donna N., Schmidt, Donald W., Dyck, Greg A., Su, Gong, Heisig, Stephen J., Pierce, Bernard R.
• Granted Patent: US 7,941,805 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A computer-implemented method for distributing a plurality of tasks over a plurality of processing nodes in a processor network includes the following steps: calculating a task process consumption value for the tasks; calculating a measured node processor consumption value for the nodes; calculating a target node processor consumption value for the nodes, the target node processor consumption value indicating optimal node processor consumption; calculating a load index value as a difference between the calculated node processor consumption value for a node i and the target node processor consumption value for node i; and distributing the tasks among the nodes to balance a processor workload among the nodes, according to the calculated load index value, such that the calculated load index value of each node is substantially zero. The method further embodies a multi-dimensional balancing matrix, each dimension of the matrix representing a node corresponding to a different processor type and each cell representing tasks assigned to multiple nodes.

Claims

1. A computer-implemented method for distributing a plurality of tasks over a plurality of processing nodes in a processor network, the method comprising steps of:

calculating a task processor consumption value for the plurality of tasks;

calculating a measured node processor consumption value for the plurality of nodes;

calculating a target node processor consumption value for the plurality of nodes, the target node processor consumption value indicating optimal node processor consumption;

calculating a load index value as a difference between the measured node processor consumption value for a node i and the target node processor consumption value for node i; and

distributing the tasks among the nodes to balance a processor workload among the nodes according to the calculated load index value of each node, such that the calculated load index value of each node is substantially zero.

2. The method of claim 1, further comprising a step of calculating a load index standard deviation value as a difference of the actual processor workload distribution to a target processor workload distribution where the load index value of all affinity nodes is substantially zero, such that the load index standard deviation is reduced to substantially zero.

3. The method of claim 1, wherein each of the plurality of tasks is distributed only once.

4. The method of claim 1, further comprising the step of determining a processor type for each of the nodes if there is more than one processor type, wherein the processor type determines how the tasks are distributed, such that tasks specified for one type of processor are distributed to that type of processor exclusively.

5. The method of claim 4 further comprising steps of:

creating a multi-dimensional balancing matrix, each dimension of the matrix representing a node corresponding to a particular processor type and each cell representing tasks;

sorting the calculated load index values in order from the highest load index value to the lowest load index value; and

populating the matrix with tasks according to the sorted load index values;

re-arranging the tasks in the cells so as to represent a balance of the processor workload among the nodes;

removing each dimension of the matrix if its corresponding node task list is empty; and

distributing the tasks to the processors according to the matrix representation.

6. The method of claim 5 further comprising steps of:

extending the multi-dimensional balancing, such that each dimension can represent nodes corresponding to multiple processor types; and

re-arranging the tasks in the cells, according to predetermined usage rules, such that the re-arranging of the tasks is asymmetric.

7. The method of claim 1 further comprising a step of calculating a threshold value below which the system is considered to be satisfactorily balanced such that the threshold value represents a load index deviation reduction by a significant amount.

8. The method of claim 7, wherein a task will be redistributed only if the redistribution reduces the load index deviation by more than the threshold value.

9. The method of claim 8, wherein the threshold value varies according to the processor workload.

10. The method of claim 1 further comprising a step of:

keeping track of a plurality of tasks with high processor consumption during each balancer run.

11. The method of claim 10, wherein the plurality of the largest processor consuming tasks are more closely monitored for better processor consumption details when the load index deviation fails to reach below the threshold value.

12. A computer readable medium for distributing a plurality of tasks over a plurality of nodes in a network, the medium comprising program instructions for calculating a task processor consumption value for the plurality of tasks;

calculating a node processor consumption value for the plurality of nodes;

calculating a target node processor consumption value for the plurality of nodes, the target node processor consumption value indicating optimal node processor consumption;

calculating a load index value as a difference between the calculated node processor consumption value for a node i and the target node processor consumption value for node i;

distributing the tasks among the nodes to balance a processor workload among the nodes, according to the calculated load index value of each node, such that the calculated load index value of each node is substantially zero.

13. A system for distributing a plurality of tasks over a plurality of nodes in a network, the system comprising:

a plurality of processors for executing tasks;

a plurality of nodes comprising processors;

a task dispatcher for;

receiving the plurality of tasks;

calculating a task processor consumption value for the plurality of tasks;

calculating a node processor consumption value for the plurality of nodes;

calculating a target node processor consumption value for the plurality of nodes, the target node processor consumption value indicating optimal node processor consumption; and

calculating a load index value as a difference between the calculated node processor consumption value for a node i and the target node processor consumption value for node i;

and

a balancer for distributing the tasks among the nodes to balance a processor workload among the nodes, according to the calculated load index value of each node, such that the calculated load index value of each node is substantially zero.

14. The system of claim 13, wherein the task dispatcher and the balancer are software residing in a computer system.

15. The system of claim 14, wherein the task dispatcher further comprises logic for:

determining a processor type for each of the nodes if there is more than one processor type, wherein the processor type determines how the tasks are distributed.

16. The system of claim 15, wherein the task dispatcher further comprises logic for:

creating a multi-dimensional balancing matrix, each dimension of the matrix representing a node corresponding to a particular processor type and each cell representing tasks;

sorting the calculated load index values in order from the highest load index value to the lowest load index value; and

populating the matrix with tasks according to the sorted load index values;

re-distributing the tasks in the cells so as to balance the processor workload among the nodes;

removing each dimension of the matrix if its corresponding node task list is empty; and

distributing the tasks to the processors according to the balancing matrix representation.

17. The system of claim 13, wherein the task dispatcher further calculates a threshold value such that the threshold value represents a load index deviation reduction by a significant amount;

and a task will be redistributed only if the redistribution reduces the load index deviation by more than the threshold value.

18. The system of claim 17, wherein the threshold value varies according to the processor workload.

19. The system of claim 13, wherein the balancer calculates a load index standard deviation value as a difference of the actual processor workload value to a target processor workload value where the load index value of all affinity nodes is substantially zero, such that the load index standard deviation is reduced to substantially zero.

20. The system of claim 19, wherein if the balancer fails to bring the load index deviation below the threshold value, the balancer will inform a measuring mechanism to start monitoring the several largest processor consuming tasks for better processor consumption details within each task.