Patent US5630129A successfully refreshed from Google Patents.
US5630129A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic load balancing of applications
Assignee: National Technology and Engineering Solutions of Sandia LLC
•
Filing: 1993-12-01
•
Granted: 1997-05-13
•
Expires: 2013-12-01
Abstract
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.
Inventors
- 👤 Stephen R. Wheat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 13:18
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5083
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
164 words
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.
Claim 2
Independent Claim
164 words
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.
Claim 3
Dependent Claim
21 words
The method of claim 1 wherein the determining, computing and exporting steps are performed repeatedly until the application has completed execution.
Claim 4
Dependent Claim
17 words
The method of claim 2 wherein global load imbalance is minimized within a finite number of iterations.
Claim 5
Dependent Claim
14 words
The method of claim 1 wherein the application comprises a finite-difference or finite-element application.
Claim 6
Dependent Claim
11 words
The method of claim 4 wherein the data cells are elements.
Claim 7
Dependent Claim
37 words
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.
Claim 8
Dependent Claim
106 words
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.
Claim 9
Dependent Claim
17 words
The method of claim 1 wherein the plurality of data cells are arranged in a two-dimensional grid.
Claim 10
Dependent Claim
17 words
The method of claim 1 wherein the plurality of data cells are arranged in a three-dimensional grid.
Claim 11
Dependent Claim
31 words
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.
Claim 12
Independent Claim
156 words
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.
Claim 13
Independent Claim
156 words
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.
Claim 14
Dependent Claim
25 words
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.
Claim 15
Dependent Claim
17 words
The apparatus of claim 12 wherein global load imbalance is minimized within a finite number of iterations.
Claim 16
Dependent Claim
14 words
The apparatus of claim 11 wherein said application comprises a finite-difference or finite-element application.
Claim 17
Dependent Claim
11 words
The apparatus of claim 14 wherein the data cells are elements.
Claim 18
Dependent Claim
24 words
The apparatus of claim 11 wherein said means for exporting comprises the means for prioritizing data cells to select which data cells to export.
Claim 19
Dependent Claim
107 words
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.
Claim 20
Dependent Claim
17 words
The apparatus of claim 11 wherein the plurality of data cells are arranged in a two-dimensional grid.
Claim 21
Dependent Claim
17 words
The apparatus of claim 11 wherein the plurality of data cells are arranged in a three-dimensional grid.
Claim 22
Dependent Claim
33 words
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.
References Cited (Backward Citations)
US4748558A
Cited
US4670899A
Cited
US5053950A
Cited
US5241677A
Cited
US5115505A
Cited
US5072371A
Cited
US5198979A
Cited
US5283897A
Cited
US5253248A
Cited
US5303383A
Cited
US5321813A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |