US3889243A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Stack mechanism for a data processor
Assignee: International Business Machines Corp
•
Filing: 1973-10-18
•
Granted: 1975-06-10
•
Expires: 1993-10-18
Abstract
Abstract A storage device (hereinafter referred to as a high speed store) includes a plurality of registers or locations and has an access speed compatible with that of its processor. Operand and operator entries are entered into one group of said registers in descending and ascending order from opposite ends thereof (a push operation) and removed therefrom (a pop operation) for processing each entry type in a last-in-first-out order. The group of registers is hereinafter referred to as a high speed stack. The number of entries stored in the stack at any moment can become very large due to the nesting of operators. Since it is not economically feasible to provide a large capacity high speed stack, overflow of the stack into a slower speed storage device (hereinafter called a low speed stack) is provided. ''''Roll out'''' of entries to the low speed stack and ''''roll in'''' of the entries back to the high speed stack is effected as the high speed stack becomes full and empty. When a new entry is to be stored into the high speed stack (a push operation) and the stack is full after the entry is stored therein, the entries are rolled out from the high speed stack to the low speed stack. Pointers (stack addresses), together with their pointer registers, pointer updating circuits and pointer controlled logic, automatically select the stack registers as entries are pushed thereon and popped therefrom. When entries are rolled out, the pointers are rolled out with the entries and the pointer registers are reinitialized. When the entries are subsequently rolled in, their pointers are rolled in and set in the pointer registers. Hardware is provided for reserving some of the high speed stack registers for direct addressing by instructions rather than by the automatic pointer addressing mechanism.
Inventors
- 👤 Edward G Drimak
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-22 20:43
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4482; G06F9/4484; G06F2212/00; G06F2212/45; G06F2212/451
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
281 words
In a data processing system, the combination comprising a stack having a plurality of addressable entry registers having sequential addresses between a predetermined low and high values, means including a first pointer register for storing entries of a first type in the entry registers in ascending address order from said low value, means including a second pointer register for storing entries of a second type in the entry registers in descending address order from said high value, means for removing the entries of each type from the stack for processing in a last-in-first-out order, a store slower in speed than the stack for storing overflow entries from the stack when the latter is full, means responsive to the pointer valueS during the storing of an entry on the stack when the values of the pointers bear a predetermined numeric relationship indicative of a full stack condition for rolling out stack entries and the current first and second pointer values to the slower speed store, means initializing the pointers to said predetermined low and high values after each roll out, means responsive to the pointer values during the attempled removal of an entry from the stack, when the value of one of the pointers indicates that there is no corresponding entry on the stack, for rolling in needed entries and the pointer values from the store to the stack and pointer registers respectively, means for reserving a directly addressable area in the stack for storing one of the last mentioned types of entries, means for directly addressing any one of a plurality of entry registers in said reserved area when the respective pointer value points to the top of said reserved area.
Claim 2
Dependent Claim
281 words
In a data processing system, the combination comprising a stack having a plurality of addressable entry registers having sequential addresses between a predetermined low and high values, means including a first pointer register for storing entries of a first type in the entry registers in ascending address order from said low value, means including a second pointer register for storing entries of a second type in the entry registers in descending address order from said high value, means for removing the entries of each type from the stack for processing in a last-in-first-out order, a store slower in speed than the stack for storing overflow entries from the stack when the latter is full, means responsive to the pointer valueS during the storing of an entry on the stack when the values of the pointers bear a predetermined numeric relationship indicative of a full stack condition for rolling out stack entries and the current first and second pointer values to the slower speed store, means initializing the pointers to said predetermined low and high values after each roll out, means responsive to the pointer values during the attempled removal of an entry from the stack, when the value of one of the pointers indicates that there is no corresponding entry on the stack, for rolling in needed entries and the pointer values from the store to the stack and pointer registers respectively, means for reserving a directly addressable area in the stack for storing one of the last mentioned types of entries, means for directly addressing any one of a plurality of entry registers in said reserved area when the respective pointer value points to the top of said reserved area.
Claim 3
Dependent Claim
30 words
The combination of claim 1 wherein the reserving means comprises means for a changing the value of the pointer corresponding to said one type of entry by a value n.
Claim 4
Dependent Claim
25 words
The combination of claim 2 wherein the direct addressing means comprises means for changing the last-mentioned pointer value by a value between 1 and n.
Claim 5
Dependent Claim
84 words
The combination of claim 1 wherein the means for storing the entries other than said one type of entry further includes means for storing, with each entry of the other type, the current pointer value for the one type of entry when said other type of entry is stored in its entry register, and wherein said removing means further includes means for storing said current pointer value in its pointer register when the corresponding other type of entry is removed from its entry register.
Claim 6
Dependent Claim
266 words
In a data processing system, the combination comprising a stack having a plurality of addressable entry registers having sequential addresses between predetermined low and high values, means including an operator pointer register for storing operator entries in the registers in ascending address order from said low value, means including an operand pointer for storing operand entries in the registers in descending address order from said high value, means for removing the operand and operator entries from the stack for processing, each in a last-in-first-out order, a store slower in speed than the stack for storing overflow entries from the stack when the latter is full, means responsive to the pointer values during the storing of an entry on the stack when the values of the pointers bear a predetermined numeric relationship indicative of a full stack condition for rolling out stack entries and the current pointer values to the slower speed store, means initializing the pointers to said predetermined high and low values after each roll out, means responsive to the pointer values during the attempled removal of an entry from the stack, when the value of one of the pointers indicates that there is no corresponding entry on the stack, for rolling in, needed entries and the pointer values from the store to the stack and pointer registers respectively. means for reserving a directly addressable area in the stack for storing the last mentioned entries, and means for directly addressing any one of a plurality of entry registers in said reserved area when the respective pointer value points to the top of said reserved area.
Claim 7
Dependent Claim
266 words
In a data processing system, the combination comprising a stack having a plurality of addressable entry registers having sequential addresses between predetermined low and high values, means including an operator pointer register for storing operator entries in the registers in ascending address order from said low value, means including an operand pointer for storing operand entries in the registers in descending address order from said high value, means for removing the operand and operator entries from the stack for processing, each in a last-in-first-out order, a store slower in speed than the stack for storing overflow entries from the stack when the latter is full, means responsive to the pointer values during the storing of an entry on the stack when the values of the pointers bear a predetermined numeric relationship indicative of a full stack condition for rolling out stack entries and the current pointer values to the slower speed store, means initializing the pointers to said predetermined high and low values after each roll out, means responsive to the pointer values during the attempled removal of an entry from the stack, when the value of one of the pointers indicates that there is no corresponding entry on the stack, for rolling in, needed entries and the pointer values from the store to the stack and pointer registers respectively. means for reserving a directly addressable area in the stack for storing the last mentioned entries, and means for directly addressing any one of a plurality of entry registers in said reserved area when the respective pointer value points to the top of said reserved area.
References Cited (Backward Citations)
US3047228A
Cited
US3218611A
Cited
US3200379A
Cited
US3401376A
Cited
US3546677A
Cited
US3614746A
Cited
US3601809A
Cited
US3624616A
Cited
US3786432A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1978-06-09 | 1978-12-09 | 1979-06-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1982-06-09 | 1982-12-09 | 1983-06-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1986-06-09 | 1986-12-09 | 1987-06-10 | $7700.00 | Window Closed / Lapsed |