US5237685A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Linear recurrence dispersal structure and method for parallel processors
Assignee: International Business Machines Corp
•
Filing: 1992-04-02
•
Granted: 1993-08-17
•
Expires: 2012-04-02
Abstract
Abstract A substantial savings in computational time is realized by the use of plural parallel processing elements, each element having vector processing capabilities. The plurality of vector processor elements will concurrently perform calculations for a number of a groups of equations. The system determines the values of recurrent variables in a set of equations which define a linear recurrence in any order under program control by dividing said set of equations into groups of consecutive equations, determining temporary (or partial) values of the recurrence variables for each group with those recurrence variables which are derived in the equation in the next preceding group being set to zero, determining for each equation values of coefficients for those recurrence variables which were set to zero, and determining the final values of previously unsolved recurrence variables.
Inventors
- 👤 Edward V. Toney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 13:31
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/11; G06F17/12
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
347 words
A multiprocessor data processing system comprising: a) a plurality of processor elements, each one of said processor elements having a coupling interface means through which data is communicated to and from each processor element; b) a plurality of first storage elements having coupling interfaces through which data is communicated to and from said storage elements, said storage elements being accessible to each of said processor elements; c) first control means for dividing a set of equations into groups of consecutive equations and further allocating processing of said groups between said plurality of processor elements; d) second control means operating at one of said plurality of processor elements concurrently with at least one other of said plurality of processor elements, said processor elements including at least one pair of parallel vector processing elements further including a multiplier logic element having two inputs and an output coupled to a first input of an addition logic element which has a second input, each processing element determining temporary values of recurrence variables of said groups of consecutive equations by setting those recurrence variables which are derived from equations in a next preceding group to zero; e) third control means operating at one of said plurality of processor elements concurrently with at least one other of said plurality of processor elements, said processor elements including at least one pair of parallel vector processing elements further including an addition logic element which has two inputs and one output, each processing element determining for each equation, values of coefficient for those recurrence variables which were set to zero; f) fourth control means operating at one of said plurality of processor elements to determine final values of recurrence variables which were set to zero; g) fifth control means operating at one of said plurality of processor elements concurrently with at least one other of said plurality of processor elements, each processing element determining the final values of previously unsolved recurrence variables; and h) second storage means for storing each of the temporary values and final values as determined by the first through fifth control means.
Claim 2
Dependent Claim
347 words
A multiprocessor data processing system comprising: a) a plurality of processor elements, each one of said processor elements having a coupling interface means through which data is communicated to and from each processor element; b) a plurality of first storage elements having coupling interfaces through which data is communicated to and from said storage elements, said storage elements being accessible to each of said processor elements; c) first control means for dividing a set of equations into groups of consecutive equations and further allocating processing of said groups between said plurality of processor elements; d) second control means operating at one of said plurality of processor elements concurrently with at least one other of said plurality of processor elements, said processor elements including at least one pair of parallel vector processing elements further including a multiplier logic element having two inputs and an output coupled to a first input of an addition logic element which has a second input, each processing element determining temporary values of recurrence variables of said groups of consecutive equations by setting those recurrence variables which are derived from equations in a next preceding group to zero; e) third control means operating at one of said plurality of processor elements concurrently with at least one other of said plurality of processor elements, said processor elements including at least one pair of parallel vector processing elements further including an addition logic element which has two inputs and one output, each processing element determining for each equation, values of coefficient for those recurrence variables which were set to zero; f) fourth control means operating at one of said plurality of processor elements to determine final values of recurrence variables which were set to zero; g) fifth control means operating at one of said plurality of processor elements concurrently with at least one other of said plurality of processor elements, each processing element determining the final values of previously unsolved recurrence variables; and h) second storage means for storing each of the temporary values and final values as determined by the first through fifth control means.
Claim 3
Dependent Claim
14 words
The multiprocessor data processing system of claim 1 wherein said first storage elements are
Claim 4
Dependent Claim
92 words
The multiprocessor data processing system of claim 1 wherein said first control means includes means for arranging the groups of consecutive equations into subsets of groups of consecutive equations and wherein said second control means includes means for determining temporary values of recurrence variables for each subset of groups, operating stride S, in a sequence in which the temporary values of the first equations in each group of the subset are calculated in sequence followed by the temporary values of the second, then the following equations in each group of the subset.
Claim 5
Dependent Claim
30 words
The multiprocessor data processor system of claim 3 wherein said vector processing elements perform the temporary value determinations of said subsets of groups of consecutive equations concurrently with each other.
Claim 6
Dependent Claim
87 words
The multiprocessor data processing system of claim 3, wherein said first control means includes means for arranging the groups of consecutive equations into subsets of groups of consecutive equations and wherein said third control means includes means for determining said coefficient values for each of said subsets in a sequence in which the coefficient values of the first equations in each group of the subset are calculated in sequence followed by the coefficient values of the second, then the following equations in each group of the subset.
Claim 7
Dependent Claim
30 words
The multiprocessor data processing system of claim 5 wherein said vector processing elements perform the coefficient value determinations of said subsets of groups of consecutive equations concurrently with each other.
Claim 8
Independent Claim
186 words
A method of operating a data processing system having a plurality of processing elements and a system memory for more efficiently determining values of recurrence variables in a set of equations which define a linear recurrence of any order comprising the steps of: (a) separating said set of equations into groups of consecutive equations, (b) determining concurrently in separate processors, temporary values, for each group, of recurrence variables by setting recurrence variables which are derived from equations in a next preceding group to zero, one said processor being assigned to determine temporary values of recurrence variables for each said group of consecutive equations. (c) determining concurrently in separate processors, coefficient values, for each equation in each group, of those recurrence variables which were set to zero, one said processor being assigned to determine coefficient values for each equation in each group of consecutive equations, (d) determining final values of said recurrence variables which were set to zero, (e) determining final values of previously unsolved recurrence variables, and (f) storing each of the determined temporary and final values in the system memory after each respective determining step.
Claim 9
Independent Claim
186 words
A method of operating a data processing system having a plurality of processing elements and a system memory for more efficiently determining values of recurrence variables in a set of equations which define a linear recurrence of any order comprising the steps of: (a) separating said set of equations into groups of consecutive equations, (b) determining concurrently in separate processors, temporary values, for each group, of recurrence variables by setting recurrence variables which are derived from equations in a next preceding group to zero, one said processor being assigned to determine temporary values of recurrence variables for each said group of consecutive equations. (c) determining concurrently in separate processors, coefficient values, for each equation in each group, of those recurrence variables which were set to zero, one said processor being assigned to determine coefficient values for each equation in each group of consecutive equations, (d) determining final values of said recurrence variables which were set to zero, (e) determining final values of previously unsolved recurrence variables, and (f) storing each of the determined temporary and final values in the system memory after each respective determining step.
Claim 10
Dependent Claim
79 words
The method of claim 7 wherein consecutive equations are arranged in subsets of consecutive groups of consecutive equations, and wherein memory is addressed stride S for performing said temporary value determinations of each subset of groups in a sequence in which temporary values of first equations in each group of a subset are calculated in sequence followed by temporary values of second equations in each group, then remaining in sequence, equations in each group of the subset being calculated.
Claim 11
Dependent Claim
16 words
The method of claim 8 wherein S coincides with the number of equations in a group.
Claim 12
Dependent Claim
77 words
The method of claim 7 wherein consecutive equations are arranged in subsets of consecutive groups of consecutive equations, and wherein said coefficient value determinations for each of said subsets are performed by a processor element in a sequence in which the coefficient values of the first equations in each group of the subset are calculated in sequence followed by the coefficient values of the second, then the remaining, in sequence, equations in each group of the subset.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-08-16 | 1997-02-15 | 1997-08-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-08-16 | 2001-02-15 | 2001-08-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-08-16 | 2005-02-15 | 2005-08-17 | $7700.00 | Window Closed / Lapsed |