System and method for balancing a computing load among computing resources in a distributed computing problem

• US 7,590,984 B2
• Filed: 05/29/2003
• Issued: 09/15/2009
• Est. Priority Date: 05/29/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lehman, Tobin Jon, Kaufman, James H.
• Primary Examiner(s): Nguyen; Van H
• Assistant Examiner(s): Wai; Eric C
• Application Number:
  US10/448,625
• Publication Number:
  US 20040244006A1
• Time in Patent Office: 2,301 Days
• Field of Search: 395/675, 709/224, 718105-106
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A distributed parallel computing system actively takes advantage of problem partitioning to balance the computing load among computing resources continually during processing. Variable problem partitions (VPPs) are initially defined as groups of original problem cells (OPCs). VPPs may be redefined and redistributed during execution, if necessary, to optimize performance based on the actual computing agent parameters and costs observed or reported through self-tests. For example, a good rule for efficient execution of a computing problem may be that the time required to perform a computation sequence (iteration) of all OPCs in a VPP should be comparable to the time required to share results via edge OPCs at the VPP collection perimeters. The rules that yield cost-efficient execution may be saved and re-used to generate initial partitionings for subsequent computing problem execution runs.

Claims

1. A method of balancing a computing load among a plurality of computing resources for handling an inter-connected problem in a task, comprising:

determining computing capabilities of a plurality of computers, wherein the computers are heterogeneous, independent, non-dedicated, and connected in a loosely coupled, asynchronous, distributed communications grid for handling the inter-connected problem;

assigning a computing agent role to at least some of the computers for handling the inter-connected problem;

monitoring available resources for the computers that have been assigned a computing agent role;

reassigning original problem cells among the computers that have been assigned a computing agent role, as necessary to balance the computing load for handling the inter-connected problem;

wherein reassigning the original problem cells among the computers includes;

segmenting the computing load into a plurality of fixed sized collections of original program cells based on the complexity of the computing load;

grouping the fixed sized collections of original program cells into a plurality of variable problem partitions;

identifying computing agents having reduced computing resources available;

determining whether any of the computing agents are non-idle and have increased computing resources available;

reassigning variable problem partitions from computing agents having reduced computing resources available to non-idle computing agents having increased computing resources available responsive to identifying computing agents having reduced computing resources available and determining that a computing agent is non-idle and has increased computing resources available; and

dividing the monitored available resources among the respective execution agents, in order to improve computing load manageability.

2. The method of claim 1, wherein upon assignment of the computing agent role, the computers that have been assigned a computing agent role register corresponding computing capabilities in self-profiles comprising at least one of CPU speed, memory size, operating system, or computer type.

3. The method of claim 2, further comprising reviewing the self-profiles of the computers that have been assigned a computing agent role, to determine an overall computing capability.

4. The method of claim 3, further comprising assigning at least some of the original problem cells to the computers that have been assigned a computing agent role based on the overall computing capability.

5. The method of claim 4, further comprising continually monitoring the overall computing capability of the computers that have been assigned a computing agent role.

6. The method of claim 5, further comprising identifying the computers that have been assigned a computing agent role with a current overall computing capability that is less than a prior overall computing capability.

7. The method of claim 5, further comprising identifying the computers that have been assigned a computing agent role with a current overall computing capability that exceeds a prior overall computing capability.

8. The method of claim 1, wherein reassigning the original problem cells from the computers that have been assigned a computing agent role, includes reassigning at least some of the original problem cells from the computers that have been assigned a computing agent role and that have a lower computing capability to the computers that have been assigned a computing agent role and that have a higher computing capability.

9. The method of claim 1, further comprising determining communication bandwidths between the computers;

classifying the computers as any of slower connectivity computers or faster connectivity computers; and

dynamically assigning original problem cells with a high connectivity to the faster connectivity computers, and original problem cells with a low connectivity to the slower connectivity computers.

10. A computer system for balancing a computing load among a plurality of computing resources for handling an inter-connected problem in a task comprising:

means for determining computing capabilities of a plurality of computers, wherein the computers are heterogeneous, independent, non-dedicated, and connected in a loosely coupled, asynchronous, distributed communications grid for handling the inter-connected problem;

means for assigning a computing agent role to at least some of the computers for handling the inter-connected problem;

means for monitoring available resources for the computers that have been assigned a computing agent role;

means for reassigning original problem cells among the computers that have been assigned a computing agent role, as necessary to balance the computing load for handling the inter-connected problem;

wherein the means for reassigning the original problem cells among the computers includes;

a device for segmenting the computing load into a plurality of fixed sized collections of original program cells based on the complexity of the computing load;

a device for grouping the fixed sized collections of original program cells into a plurality of variable problem partitions;

a device for identifying computing agents having reduced computing resources available;

a device for determining whether any of the computing agents are non-idle and have increased computing resources available;

a device for reassigning variable problem partitions from computing agents having reduced computing resources available to non-idle computing agents having increased computing resources available responsive to identifying computing agents having reduced computing resources available and determining that a computing agent is non-idle and has increased computing resources available; and

a device for dividing the monitored available resources among the respective execution agents, in order to improve computing load manageability.

11. The system of claim 10, wherein upon assignment of the computing agent role, the computers that have been assigned a computing agent role register corresponding computing capabilities in self-profiles comprising at least one of CPU speed, memory size, operating system, or computer type.

12. The system of claim 10, further comprising means for reviewing the self-profiles of the computers that have been assigned a computing agent role, to determine an overall computing capability.

13. The system of claim 12, further comprising means for assigning at least some of the original problem cells to the computers that have been assigned a computing agent role, based on the overall computing capability.

14. The system of claim 13, further comprising means for continually monitoring the overall computing capability of the computers that have been assigned a computing agent role.

15. The system of claim 14, further comprising means for identifying the computers that have been assigned a computing agent role with a current overall computing capability that is less than a prior overall computing capability.

16. The system of claim 14, further comprising means for identifying the computers that have been assigned a computing agent role with a current overall computing capability that exceeds a prior overall computing capability.

17. The system of claim 10, wherein the means for reassigning the original problem cells from the computers that have been assigned a computing agent role, includes means for reassignment at least some of the original problem cells from the computers that have been assigned a computing agent role and that have a lower computing capability to the computers that have been assigned a computing agent role and that have a higher computing capability.

18. The system of claim 10, further comprising means for determining communication bandwidths between the computers;

means for classifying the computers as any of slower connectivity computers or faster connectivity computers; and

means for dynamically assigning original problem cells with a high connectivity to the faster connectivity computers, and original problem cells with a low connectivity to the slower connectivity computers.

19. A computer program product having instruction codes stored on a computer readable medium, for balancing a computing load among a plurality of computing resources for handling an inter-connected problem in a task, comprising:

a first set of instruction codes for determining computing capabilities of a plurality of computers, wherein the computers are heterogeneous, independent, non-dedicated, and connected in a loosely coupled, asynchronous, distributed communications grid for handling the inter-connected problem;

a second set of instruction codes for assigning a computing agent role to at least some of the computers for handling the inter-connected problem;

a third set of instruction codes for monitoring available resources for the computers that have been assigned a computing agent role; and

a fourth set of instruction codes for reassigning original problem cells among the computers that have been assigned a computing agent role, as necessary to balance the computing load for handling the inter-connected problem;

wherein the fourth set of instruction codes for reassigning the original problem cells among the computers includes;

a set of instruction codes for segmenting the computing load into a plurality of fixed sized collections of original program cells based on the complexity of the computing load;

a set of instruction codes for grouping the fixed sized collections of original program cells into a plurality of variable problem partitions;

a set of instruction codes for identifying computing agents having reduced computing resources available;

a set of instruction codes for determining whether any of the computing agents are non-idle and have increased computing resources available;

a set of instruction codes for reassigning variable problem partitions from computing agents having reduced computing resources available to non-idle computing agents having increased computing resources available responsive to identifying computing agents having reduced computing resources available and determining that a computing agent is non-idle and has increased computing resources available; and

a set of instruction codes for dividing the monitored available resources among the respective execution agents, in order to improve computing load manageability.

20. The computer program product of claim 19, wherein upon assignment of the computing agent role, the computers that have been assigned a computing agent role register corresponding computing capabilities in self-profiles comprising at least one of CPU speed, memory size, operating system, or computer type.

21. The computer program product of claim 19, further comprising a fifth set of instruction codes for reviewing the self-profiles of the computers that have been assigned a computing agent role, to determine an overall computing capability.

22. The computer program product of claim 21, further comprising a sixth set of instruction codes for assigning at least some of the original problem cells to the computers that have been assigned a computing agent role, based on the overall computing capability.

23. The computer program product of claim 22, wherein the third set of instruction codes continually monitors the overall computing capability of the computers that have been assigned a computing agent role.

24. The computer program product of claim 23, wherein the third set of instruction codes further identifies the computers that have been assigned a computing agent role with a current overall computing capability that is less than a prior overall computing capability.

25. The computer program product of claim 23, wherein the third set of instruction codes further identifies the computers that have been assigned a computing agent role with a current overall computing capability that exceeds a prior overall computing capability.

26. The computer program product of claim 19, wherein the fourth set of instruction codes reassigns at least some of the cells from the original problem computers that have been assigned a computing agent role and that have a lower computing capability to the computers that have been assigned a computing agent role and that have a higher computing capability.

27. The computer program product of claim 19, further comprising a seventh set of instruction codes for determining communication bandwidths between the computers;

an eight set of instruction codes for classifying the computers as any of slower connectivity computers or faster connectivity computers; and

wherein the fourth set of instruction codes dynamically assigns original problem cells with a high connectivity to the faster connectivity computers, and original problem cells with a low connectivity to the slower connectivity computers.