Dynamic load balancing of applications

• US 5,630,129 A
• Filed: 12/01/1993
• Issued: 05/13/1997
• Est. Priority Date: 12/01/1993
• Status: Expired due to Fees

• Current Assignee: Sandia Corporation (Martin Marietta Corporation)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Wheat, Stephen R.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/161,003
• Time in Patent Office: 1,259 Days
• Field of Search: 395/650, 395/700, 395/800
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

An application-level method for dynamically maintaining global load balance on a parallel computer, particularly on massively parallel MIMD computers. Global load balancing is achieved by overlapping neighborhoods of processors, where each neighborhood performs local load balancing. The method supports a large class of finite element and finite difference based applications and provides an automatic element management system to which applications are easily integrated.

Claims

1. A method for dynamically maintaining global load balance in a multiprocessor system that executes an application on a parallel computer, the method comprising the steps of:

a) providing an application for execution to a plurality of processors of the parallel computer for processing the application that is to be executed, the application comprising a plurality of data cells arranged spatially such that each data cell has one or more neighboring data cells;

b) assigning each data cell a processor within the plurality of processors;

c) determining for one or more of the plurality of processors all other processors in one or more corresponding processor neighborhoods;

d) computing work loads for the one or more of the plurality of processors; and

e) for the one or more of the plurality of processors, exporting one or more data cells to another processor in the one or more corresponding processor neighborhoods to achieve a dynamic and global balance of the work load between the plurality of processors.

2. The method of claim 1 wherein the determining, computing and exporting steps are performed repeatedly until the application has completed execution.

3. The method of claim 2 wherein global load imbalance is minimized within a finite number of iterations.

4. The method of claim 1 wherein the application comprises a finite-difference or finite-element application.

5. The method of claim 4 wherein the data cells are elements.

6. The method of claim 1 wherein the step of exporting one or more data cells to another processor in the one or more corresponding processor neighborhoods comprises prioritizing data cells to select which data cells to export.

7. The method of claim 6 wherein the step of prioritizing data cells comprises the steps of:

a) initially assigning a zero priority to all data cells;

b) decreasing a data cell'"'"'s priority by one for each of the one or more neighboring data cells assigned to the same processor as the data cell;

c) increasing a data cell'"'"'s priority by two for each of the one or more neighboring data cells assigned to a processor requesting importation of the data cell; and

d) decreasing a data cell'"'"'s priority by two for each of the one or more neighboring data cells assigned to a concerned partner processor.

8. The method of claim 1 wherein the plurality of data cells are arranged in a two-dimensional grid.

9. The method of claim 1 wherein the plurality of data cells are arranged in a three-dimensional grid.

10. The method of claim 1 wherein the determining step comprises determining for one or more of the plurality of processors all other processors in the one or more corresponding processor neighborhoods.

20. The apparatus of claim 1 wherein said determining means comprises means for determining for one or more of the plurality of processors all other processors in the one or more corresponding processor neighborhoods.

11. An apparatus for dynamically maintaining global load balance in a multiprocessor system that executes an application on a parallel computer, said apparatus comprising:

means for providing an application for execution to a plurality of processors of the parallel computer, the application comprising a plurality of data cells arranged spatially such that each data cell has one or more neighboring data cells;

means for assigning each data cell to a processor within the plurality of processors;

means for determining for one or more of the plurality of processors all other processors in one or more corresponding processor neighborhoods;

means for computing work loads for one or more of the plurality of processors; and

means for exporting, for one or more of the plurality of processors, one or more data cells to another processor in the one or more corresponding processor neighborhoods to achieve a dynamic and global balance of the work load between the plurality of processors.

12. The apparatus of claim 11 wherein said determining, computing and exporting means comprise means for performing such functions repeatedly until the application has completed execution.

13. The apparatus of claim 12 wherein global load imbalance is minimized within a finite number of iterations.

14. The apparatus of claim 11 wherein said application comprises a finite-difference or finite-element application.

15. The apparatus of claim 14 wherein the data cells are elements.

16. The apparatus of claim 11 wherein said means for exporting comprises the means for prioritizing data cells to select which data cells to export.

17. The apparatus of claim 16 wherein said means for prioritizing data cells comprises:

means for initially assigning a zero priority to all data cells;

means for decreasing a data cell'"'"'s priority by one for each of the one or more neighboring data cells assigned to the same processor as the data cell;

means for increasing a data cell'"'"'s priority by two for each of the one or more neighboring data cells assigned to a processor requesting importation of the data cell; and

means for decreasing a data cell'"'"'s priority by two for each of the one or more neighboring data cells assigned to a concerned partner processor.

18. The apparatus of claim 11 wherein the plurality of data cells are arranged in a two-dimensional grid.

19. The apparatus of claim 11 wherein the plurality of data cells are arranged in a three-dimensional grid.