US3868644A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Stack mechanism for a data processor
Assignee: International Business Machines Corp
•
Filing: 1973-06-26
•
Granted: 1975-02-25
•
Expires: 1993-06-26
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. Operands and/or operators are entered into one group of said registers hereinafter referred to as a high speed stack (a push operation) and removed therefrom (a pop operation) for processing in a lastin-first-out order. 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. A backup register in the non-stack portion of the high speed store permits delay of roll out operations until the last possible moment. When a new entry is to be stored into the high speed stack (a push operation) and the stack is full, the new entry is put into the backup register, entries are rolled out from the high speed stack to the low speed stack and the new entry is then transferred from the backup register to the high speed stack. By means of pointers (stack addresses), pointer updating circuits and pointer controlled logic, entries rolled out to the low speed stack are still valid and available in the high speed stack for processing until they are either popped out or overlaid by new entries. This significantly reduces the number and frequency of roll out and roll in operations.
Inventors
- 👤 Robert A Healey
- 👤 Everett M Shimp
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 11:16
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4482; G06F9/4484
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
123 words
In a system having means including a stack and a slower speed store for directly executing algorithmic type problem programs of the type in which means transfers data entries into and removes entries from the stack for processing in a last-in-first-out order and in which means roll overflow entries out to the slower speed store when the stack is full and roll overflow entries into the stack when the stack is empty, the combination with the stack and slower speed store of means including pointer registers for permitting the removal of each entry in the stack from the stack for processing after a copy of said entry has been rolled out to the slower speed store but not rolled back to the stack.
Claim 2
Dependent Claim
123 words
In a system having means including a stack and a slower speed store for directly executing algorithmic type problem programs of the type in which means transfers data entries into and removes entries from the stack for processing in a last-in-first-out order and in which means roll overflow entries out to the slower speed store when the stack is full and roll overflow entries into the stack when the stack is empty, the combination with the stack and slower speed store of means including pointer registers for permitting the removal of each entry in the stack from the stack for processing after a copy of said entry has been rolled out to the slower speed store but not rolled back to the stack.
Claim 3
Dependent Claim
35 words
The combination of claim 1 together with additional means including said registers for permitting a new entry to overlay one of said entries in the stack which has a copy in the slower speed store.
Claim 4
Dependent Claim
211 words
In a data processing system for directly executing algorithmic type problem programs, the combination comprising a stack having registers for storing entries, first means for transferring entries into the stack and for removing them from the stack for processing in last-in-first-out order, a store operable at a slower speed than the stack for storing overflow copies of said entries from the stack, second means for rolling out all entries in the stack from the stack to the slower speed store only when all of the stack registers are full of entries having no copies in the slower speed store, and third means for rolling in copies of said rolled out entries from the slower speed store to the stack only when the stack registers are (1) empty of entries with copies in the slower speed store and (2) empty of entries without copies in the slower speed store, program responsive means for rendering said first means effective to remove a stack entry from the stack for processing when said latter entry has a copy in the slower speed store, and program responsive means rendering said first means effective to overlay an entry in the stack with a new entry when the latter entry has a copy in the slower speed store.
Claim 5
Dependent Claim
211 words
In a data processing system for directly executing algorithmic type problem programs, the combination comprising a stack having registers for storing entries, first means for transferring entries into the stack and for removing them from the stack for processing in last-in-first-out order, a store operable at a slower speed than the stack for storing overflow copies of said entries from the stack, second means for rolling out all entries in the stack from the stack to the slower speed store only when all of the stack registers are full of entries having no copies in the slower speed store, and third means for rolling in copies of said rolled out entries from the slower speed store to the stack only when the stack registers are (1) empty of entries with copies in the slower speed store and (2) empty of entries without copies in the slower speed store, program responsive means for rendering said first means effective to remove a stack entry from the stack for processing when said latter entry has a copy in the slower speed store, and program responsive means rendering said first means effective to overlay an entry in the stack with a new entry when the latter entry has a copy in the slower speed store.
Claim 6
Dependent Claim
72 words
The combination of claim 3 wherein the second means further comprises first and second registers respectively storing stack address indicia pointing to the most recently received entry in the stack and to the least recently received entry in the stack having no copy in the store, And means for initiating roll out if the address indicia in the registers become equal when a new entry is received for transfer to the stack.
Claim 7
Dependent Claim
59 words
The combination of claim 4 wherein the third means further comprises said first register, a third register storing stack address indicia pointing to the least recently received entry in the stack, and means for initiating roll in when the address indicia in the first and third registers are equal and said least recently received entry is removed for processing.
Claim 8
Dependent Claim
43 words
The combination of claim 5 further comprising means storing status bit information, and said second and third means including store address calculation means responsive to said status information for determining which of two address groups to use during roll out and roll in.
Claim 9
Dependent Claim
240 words
In a data processing system having a processor and a stack for storing operand and/or operator entries immediately preceding processing of the entries, the combination with said processor and stack of first means for transferring the entries into the stack and for transferring the entries from the stack directly to the processor for processing in a last-in-first-out sequence, a store operable at a slower speed than the stack for storing overflow entries from the stack, second means for rolling out said overflow entries from the stack to the slower speed store when the stack is full and for rolling in said overflow entries from the store to the stack when the stack becomes empty, means for overlaying entries stored in the stack with new entries only when the stored entries have copies in the slower speed store, pointer registers, means for maintaining in the pointer registers address indicia pointing to the stack addresses storing the last received entry in the stack, the earliest received entry which is valid in the stack, and the earliest received entry in the stack for which there is no copy in the slower speed store, and means controlled by said address indicia for maintaining all overflow entries in the stack valid and available for processing after a copy of the last-mentioned entries has been rolled out to the store until the said last-mentioned entries are either transferred to the processor or overlaid by new entries.
Claim 10
Dependent Claim
240 words
In a data processing system having a processor and a stack for storing operand and/or operator entries immediately preceding processing of the entries, the combination with said processor and stack of first means for transferring the entries into the stack and for transferring the entries from the stack directly to the processor for processing in a last-in-first-out sequence, a store operable at a slower speed than the stack for storing overflow entries from the stack, second means for rolling out said overflow entries from the stack to the slower speed store when the stack is full and for rolling in said overflow entries from the store to the stack when the stack becomes empty, means for overlaying entries stored in the stack with new entries only when the stored entries have copies in the slower speed store, pointer registers, means for maintaining in the pointer registers address indicia pointing to the stack addresses storing the last received entry in the stack, the earliest received entry which is valid in the stack, and the earliest received entry in the stack for which there is no copy in the slower speed store, and means controlled by said address indicia for maintaining all overflow entries in the stack valid and available for processing after a copy of the last-mentioned entries has been rolled out to the store until the said last-mentioned entries are either transferred to the processor or overlaid by new entries.
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) | 1978-02-24 | 1978-08-26 | 1979-02-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1982-02-24 | 1982-08-26 | 1983-02-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1986-02-24 | 1986-08-26 | 1987-02-25 | $7700.00 | Window Closed / Lapsed |