US5442767A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Address prediction to avoid address generation interlocks in computer systems
Assignee: International Business Machines Corp
•
Filing: 1992-10-23
•
Granted: 1995-08-15
•
Expires: 2012-10-23
Abstract
Abstract A computer system predicts an address required to execute a current iteration of a program instruction based on addresses required to execute previous iterations of the same program instruction. The system stores an address required to execute the previous iteration of the program instruction, and determines differences between addresses required to execute successive iterations of the program instruction prior to the current iteration. The system also determines and stores a current value of a delta, and predicts the address required to execute the current iteration of the program instruction based on the address required to execute the previous iteration of the program instruction plus the current value of the delta. The system sets the delta at one time equal to a difference between two addresses required to execute two successive iterations of the program instruction and updates delta when two actual differences between three addresses required to execute three successive iterations of the program instruction are equal to each other and different than delta. Thus, the system predicts constantly spaced addresses unless two successive addresses have a different spacing than the previous address. This is particularly advantageous when the program instruction adds data stored as elements of rows of one or more matrices. While the prediction will be incorrect for the first element in each row (and the first two elements in the first row) of each matrix, the prediction will be correct for all other elements in the rows, even if the inter-element spacings in rows of the different matrices are different than each other. For each of some predictions for successive iterations of the program instruction, the system negates the current value of the delta, whereby the predictions alternate between two addresses for multiple iterations of the program instruction.
Inventors
- 👤 Richard J. Eickemeyer
- 👤 Stamatis Vassiliadis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 18:10
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/32; G06F9/322; G06F9/325; G06F9/34; G06F9/345; G06F9/38; G06F9/3824; G06F9/383; G06F9/3832
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
155 words
A system for predicting an address required to execute a current iteration of a program instruction, said system comprising: means for storing an address required to execute a preceding iteration of said program instruction; means for determining differences between addresses required to execute successive iterations of said program instruction prior to said current iteration; means for predicting the address required to execute the current iteration of said program instruction based on the address required to execute the preceding iteration of said program instruction plus a current value of an increment; and means for setting said increment before said current iteration equal to a difference between two addresses required to execute two successive iterations of said program instruction and updating said increment when two actual differences between three addresses required to execute three successive iterations of said program instruction are equal to each other and different than the set increment, said update being said actual difference.
Claim 2
Independent Claim
155 words
A system for predicting an address required to execute a current iteration of a program instruction, said system comprising: means for storing an address required to execute a preceding iteration of said program instruction; means for determining differences between addresses required to execute successive iterations of said program instruction prior to said current iteration; means for predicting the address required to execute the current iteration of said program instruction based on the address required to execute the preceding iteration of said program instruction plus a current value of an increment; and means for setting said increment before said current iteration equal to a difference between two addresses required to execute two successive iterations of said program instruction and updating said increment when two actual differences between three addresses required to execute three successive iterations of said program instruction are equal to each other and different than the set increment, said update being said actual difference.
Claim 3
Dependent Claim
107 words
A system as set forth in claim 1 further comprising: means for storing the difference between the address required to execute the current iteration of said program instruction and the preceding iteration of said program instruction; and means for updating the current value of said increment to a difference between an address required to execute a next iteration of said program instruction and the current iteration of said program instruction when the difference equals a difference between the addresses required to execute the current iteration of said program instruction and the preceding iteration of said program instruction but does not equal the current value of said increment.
Claim 4
Dependent Claim
45 words
A system as set forth in claim 1 wherein, for each of some predictions for successive iterations of said program instruction, the updating means negatives the current value of said increment, whereby the predictions alternate between two addresses for multiple iterations of said program instruction.
Claim 5
Dependent Claim
73 words
A system as set forth in claim 3 wherein said prediction means makes said some predictions when a difference between the addresses required for the current iteration of said program instruction and the preceding iteration of said program instruction is different than a difference between addresses required for said preceding iteration of said program instruction and an iteration preceding said preceding iteration of said program instruction and the current value of said increment.
Claim 6
Independent Claim
153 words
A method for predicting an address required to execute a current iteration of a program instruction, said method comprising the following steps performed by computer hardware: storing an address required to execute a preceding iteration of said program instruction; determining differences between addresses required to execute successive iterations of said program instruction prior to said current iteration; predicting the address required to execute the current iteration of said program instruction based on an address required to execute the preceding iteration of said program instruction plus a current value of an increment; setting said increment before said current iteration equal to a difference between two addresses required to execute two successive iterations of said program instruction; and updating said increment when two actual differences between three addresses required to execute three successive iterations of said program instruction are equal to each other and different than the set increment, said update being said actual difference.
Claim 7
Independent Claim
153 words
A method for predicting an address required to execute a current iteration of a program instruction, said method comprising the following steps performed by computer hardware: storing an address required to execute a preceding iteration of said program instruction; determining differences between addresses required to execute successive iterations of said program instruction prior to said current iteration; predicting the address required to execute the current iteration of said program instruction based on an address required to execute the preceding iteration of said program instruction plus a current value of an increment; setting said increment before said current iteration equal to a difference between two addresses required to execute two successive iterations of said program instruction; and updating said increment when two actual differences between three addresses required to execute three successive iterations of said program instruction are equal to each other and different than the set increment, said update being said actual difference.
Claim 8
Dependent Claim
103 words
A method as set forth in claim 5 further comprising the steps of: storing a difference between the addresses required to execute the current iteration of said program instruction and the preceding iteration of said program instruction; and updating the current value of said increment when a difference between an address required to execute a next iteration of said program instruction and the current iteration of said program instruction equals a difference between the address required to execute the current iteration of said program instruction and the preceding iteration of said program instruction but does not equal the current value of said increment.
Claim 9
Dependent Claim
56 words
A method as set forth in claim 6 wherein, for each of some predictions for successive iterations of said program instruction, the step of updating the current value of said increment comprises the step of negativing the current value of said increment, whereby the predictions alternate between two addresses for multiple iterations of said program instruction.
Claim 10
Dependent Claim
86 words
A method as set forth in claim 7 wherein said step of updating the current value of said increment comprises the step of negativing the current value of said increment when a difference between addresses required for the current iteration of said program instruction and the preceding iteration of said program instruction is different than the difference between addresses required for said preceding iteration of said program instruction and an iteration preceding said preceding iteration of said program instruction and the current value of said increment.
References Cited (Backward Citations)
US4594659A
Cited
US4583162A
Cited
US4729092A
Cited
US4760520A
Cited
US5007011A
Cited
US4853840A
Cited
US4991080A
Cited
US4888689A
Cited
US5121473A
Cited
US4984772A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-14 | 1999-02-13 | 1999-08-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-14 | 2003-02-13 | 2003-08-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-14 | 2007-02-13 | 2007-08-15 | $7700.00 | Window Closed / Lapsed |