US4920487A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of up-front load balancing for local memory parallel processors
Assignee: National Aeronautics and Space Administration
•
Filing: 1988-12-12
•
Granted: 1990-04-24
•
Expires: 2008-12-12
Abstract
Abstract In a parallel processing computer system with multiple processing units and shared memory, a method is disclosed for uniformly balancing the aggregate computational load in, and utilizing a minimal memory by, a network having identical computations to be executed at each connection therein. Read-only and read-write memory are subdivided into a plurality of partitions, and the computational load is subdivided into a plurality of process sets, which function like artificial processing units. Said plurality of process sets is iteratively merged and reduced to the number of processing units without exceeding the balance load. Merger is based upon the value of a partition threshold, which is a measure of the memory utilization. The turnaround time and memory savings of the instant method are functions of the number of processing units available and the number of partitions into which memory is subdivided.
Inventors
- 👤 Paul T. Baffes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 00:18
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5011; G06F9/5016; G06F9/5061; G06F9/5066
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
206 words
In a parallel processing computer system including a plurality of processing units and shared memory, and containing a network having identical computations to be executed at each connection therein, and said network further having a constant aggregate computational load, a method of up-front, load balancing comprising generating a first signal representative of said plurality of processing units in said network, generating a first plurality of signals with each such signal representing a corresponding one of said identical computations in said network, generating in response to said first signal and said first plurality of signals a second signal representing a balance load in said network, generating a second plurality of signals functionally establishing a preselected plurality of partitions of said memory, generating in response to said first and second pluralities of signals, a first sequence of signals functionally dividing said computational load into a plurality of process sets, generating in response to said second signal and said first sequence of signals, a second sequence of signals functionally allocating said process sets among said memory partitions, and generating in response to said second sequence of signals, a third sequence of signals functionally merging said process sets until they are equal in number to said plurality of processing units.
Claim 2
Dependent Claim
206 words
In a parallel processing computer system including a plurality of processing units and shared memory, and containing a network having identical computations to be executed at each connection therein, and said network further having a constant aggregate computational load, a method of up-front, load balancing comprising generating a first signal representative of said plurality of processing units in said network, generating a first plurality of signals with each such signal representing a corresponding one of said identical computations in said network, generating in response to said first signal and said first plurality of signals a second signal representing a balance load in said network, generating a second plurality of signals functionally establishing a preselected plurality of partitions of said memory, generating in response to said first and second pluralities of signals, a first sequence of signals functionally dividing said computational load into a plurality of process sets, generating in response to said second signal and said first sequence of signals, a second sequence of signals functionally allocating said process sets among said memory partitions, and generating in response to said second sequence of signals, a third sequence of signals functionally merging said process sets until they are equal in number to said plurality of processing units.
Claim 3
Dependent Claim
35 words
The method described in claim 1, wherein said merging of said process sets includes comparing each signal of said third sequence of signals to said second signal to detect whether said balance load is exceeded.
Claim 4
Dependent Claim
25 words
The method described in claim 2 wherein said merging of said process sets includes generating a third signal functionally related to a preselected partition threshold.
Claim 5
Dependent Claim
31 words
The method described in claim 3, wherein said merging of said process sets includes generating in response to said third signal, a fourth signal functionally related to a current partition threshold.
Claim 6
Dependent Claim
45 words
The method described in claim 4, where said merging of said process sets further includes generating a fifth signal functionally related to the difference between said third signal and said fourth signal to detect whether said preselected partition threshold differs from said current partition threshold.
Claim 7
Dependent Claim
35 words
The method described in claim 5, wherein said merging of said process sets includes increasing in magnitude said fourth signal by an amount functionally related to incrementing said current partition threshold by a preselected amount.
Claim 8
Dependent Claim
24 words
The method described in claim 1 including generating a fourth sequence of signals functionally ordering said plurality of process sets by ascending computational load.
Claim 9
Dependent Claim
30 words
The method described in claim 7 further including comparing said fourth sequence of signals to said third and fourth pluralities of signals functionally ascertaining which computational loads to merge together.
References Cited (Backward Citations)
US4590555A
Cited
US4400768A
Cited
US4495570A
Cited
US4410944A
Cited
US4491932A
Cited
US4468736A
Cited
US4633387A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-04-23 | 1993-10-23 | 1994-04-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-04-23 | 1997-10-23 | 1998-04-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-04-23 | 2001-10-23 | 2002-04-24 | $7700.00 | Window Closed / Lapsed |