US5613083A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Translation lookaside buffer that is non-blocking in response to a miss for use within a microprocessor capable of processing speculative instructions
Assignee: Intel Corp
•
Filing: 1994-09-30
•
Granted: 1997-03-18
•
Expires: 2014-09-30
Abstract
Abstract A translation lookaside buffer is described for use with a microprocessor capable of speculative and out-of-order processing of memory instructions. The translation lookaside buffer is non-blocking in response to translation lookaside buffer misses requiring page table walks. Once a translation lookaside buffer miss is detected, a page table walk is initiated to satisfy the miss. During the page table walk, additional memory instructions are processed by the translation lookaside buffer. Any additional instructions which cause translation lookaside buffer hits are merely processed by the translation lookaside buffer. However, instructions causing translation lookaside buffer misses while the page table walk is being performed are blocked pending completion of the page table walk. Once the page table walk is completed the blocked instructions are reawakened and are again processed by the translation lookaside buffer. Global and selective wakeup mechanisms are described. An implementation wherein the non-blocking translation lookaside buffer is provided within a microprocessor capable of speculative and out-of-order processing is also described.
Inventors
- 👤 Andrew F. Glew
- 👤 Haitham Akkary
- 👤 Glenn J. Hinton
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 18:45
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/10; G06F12/1027; G06F2212/00; G06F2212/68; G06F2212/684
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
209 words
In a microprocessor having a translation lookaside buffer and a page miss handler, a method for processing virtual address to physical address translations, said method comprising the steps of: receiving a first instruction having a first virtual address to be translated into a physical address; determining whether the physical address corresponding to the first instruction is stored in the translation lookaside buffer and if not, initiating a page table walk within the page miss hander for determining the physical address, otherwise outputting the physical address corresponding to the first instruction; receiving a second instruction having a second virtual address to be translated into a physical address; determining whether the physical address corresponding to the second instruction is stored in the translation lookaside buffer; if the physical address of the second instruction is not stored in the translation lookaside buffer and the page miss handler is busy completing a page table walk, blocking the second instruction until the page table walk for the first instruction is complete, then re-attempting the address translation for the second instruction; if the physical address for the second instruction is stored in the translation lookaside buffer, outputting the physical address corresponding to the second instruction; and completing the page table walk for the first instruction.
Claim 2
Dependent Claim
209 words
In a microprocessor having a translation lookaside buffer and a page miss handler, a method for processing virtual address to physical address translations, said method comprising the steps of: receiving a first instruction having a first virtual address to be translated into a physical address; determining whether the physical address corresponding to the first instruction is stored in the translation lookaside buffer and if not, initiating a page table walk within the page miss hander for determining the physical address, otherwise outputting the physical address corresponding to the first instruction; receiving a second instruction having a second virtual address to be translated into a physical address; determining whether the physical address corresponding to the second instruction is stored in the translation lookaside buffer; if the physical address of the second instruction is not stored in the translation lookaside buffer and the page miss handler is busy completing a page table walk, blocking the second instruction until the page table walk for the first instruction is complete, then re-attempting the address translation for the second instruction; if the physical address for the second instruction is stored in the translation lookaside buffer, outputting the physical address corresponding to the second instruction; and completing the page table walk for the first instruction.
Claim 3
Dependent Claim
61 words
The method of claim 1, including the further steps of receiving additional instructions to be translated into physical addresses; and determining whether the corresponding physical addresses of the additional instructions are stored in the translation lookaside buffer, and if not and if the page miss handler is busy, blocking each of the additional instructions pending completion of the page table walk.
Claim 4
Dependent Claim
34 words
The method of claim 2, wherein a plurality of second instructions are blocked pending completion of the page table walk and wherein all of the additional instructions are reawakened and instruction translations are reattempted.
Claim 5
Dependent Claim
16 words
The method of claim 3 wherein the additional instructions are reawakened in order of relative age.
Claim 6
Dependent Claim
55 words
The method of claim 3, wherein the additional instructions include a first set of instructions having addresses corresponding to a page currently being accessed by the page table walk and a second set of instructions having addresses corresponding to other pages and wherein said first set of blocked instructions are reawakened before said second set.
Claim 7
Dependent Claim
32 words
The method of claim 5, wherein instructions within said first set of instructions are re-awakened in order of relative age, then instructions of the second set are re-awakened in order of age.
Claim 8
Dependent Claim
144 words
A computer system comprising: means for issuing instructions, some of which are speculative instructions, each of said instructions specifying a virtual address; translation lookaside buffer means for storing physical addresses corresponding to selected virtual addresses; page miss handler means for determining the physical address corresponding to a virtual address for virtual addresses not stored within said translation lookaside buffer means; memory ordering buffer means for reordering and blocking memory instructions; blocking means, operative in response to a translation lookaside buffer means miss, for determining whether the page miss handler means is busy and for controlling the memory ordering buffer means to block an instruction causing the translation lookaside buffer miss until the page miss handler means is no longer busy; and wake up means for awakening instructions blocked by the blocking means and for transmitting the awakened instructions to the translation lookaside buffer means.
Claim 9
Dependent Claim
144 words
A computer system comprising: means for issuing instructions, some of which are speculative instructions, each of said instructions specifying a virtual address; translation lookaside buffer means for storing physical addresses corresponding to selected virtual addresses; page miss handler means for determining the physical address corresponding to a virtual address for virtual addresses not stored within said translation lookaside buffer means; memory ordering buffer means for reordering and blocking memory instructions; blocking means, operative in response to a translation lookaside buffer means miss, for determining whether the page miss handler means is busy and for controlling the memory ordering buffer means to block an instruction causing the translation lookaside buffer miss until the page miss handler means is no longer busy; and wake up means for awakening instructions blocked by the blocking means and for transmitting the awakened instructions to the translation lookaside buffer means.
Claim 10
Dependent Claim
31 words
The computer system of claim 7, wherein said blocking means blocks a plurality of instructions, each causing translation lookaside buffer means misses, until the page miss handler is no longer busy.
Claim 11
Dependent Claim
29 words
The computer system of claim 8, wherein said wake-up means includes means for awaking all blocked instructions and transmitting said awakened instructions to the translation lookaside buffer in sequence.
Claim 12
Dependent Claim
24 words
The computer system of claim 9 wherein said wake-up means transmits the awakened instructions to the translation lookaside buffer means in order of age.
Claim 13
Dependent Claim
73 words
The computer system of claim 9 wherein said blocking means blocks instructions of a first type and a second type wherein instructions of the first type are awaiting page information being retrieved by the pending page table walk and instructions of the second type are merely blocked pending completion of any page table walk and wherein said wake-up means awakens and transmits instructions of the first type before instruction of the second type.
Claim 14
Dependent Claim
41 words
The computer system of claim 11 wherein said wake-up means transmits the awakened instructions of the first type to the translation lookaside buffer means in order of age then transmits the awakened instructions of the second type in order of age.
Claim 15
Dependent Claim
144 words
A computer system comprising: an instruction fetch and issue unit to issue instructions, some of which are speculative instructions, each of said instructions specifying a virtual address; a translation lookaside buffer to store physical addresses corresponding to selected virtual addresses; a page miss handler to determine the physical address corresponding to an instruction for addresses not stored within said translation lookaside buffer; a memory ordering buffer to reorder and block memory instructions; a blocking unit, operative in response to a translation lookaside buffer miss to determine whether the page miss handler means is busy and to control the memory ordering buffer to block an instruction causing the translation lookaside buffer miss until the page miss handler is no longer busy; and a wake up unit to awaken instructions blocked by the blocking unit and to transmit the awakened instructions to the translation lookaside buffer.
Claim 16
Dependent Claim
144 words
A computer system comprising: an instruction fetch and issue unit to issue instructions, some of which are speculative instructions, each of said instructions specifying a virtual address; a translation lookaside buffer to store physical addresses corresponding to selected virtual addresses; a page miss handler to determine the physical address corresponding to an instruction for addresses not stored within said translation lookaside buffer; a memory ordering buffer to reorder and block memory instructions; a blocking unit, operative in response to a translation lookaside buffer miss to determine whether the page miss handler means is busy and to control the memory ordering buffer to block an instruction causing the translation lookaside buffer miss until the page miss handler is no longer busy; and a wake up unit to awaken instructions blocked by the blocking unit and to transmit the awakened instructions to the translation lookaside buffer.
Claim 17
Dependent Claim
32 words
The computer system of claim 13, wherein said blocking unit blocks a plurality of instructions, each causing a translation lookaside buffer means misses, until the page miss handler is no longer busy.
Claim 18
Dependent Claim
27 words
The computer system of claim 14, wherein said wake up unit awakens all blocked instructions and transmits said awakened instructions to the translation lookaside buffer in sequence.
Claim 19
Dependent Claim
24 words
The computer system of claim 15 wherein said wake up unit transmits the awakened instructions to the translation lookaside buffer in order of age.
Claim 20
Dependent Claim
74 words
The computer system of claim 15, wherein said blocking unit blocks instructions of a first type and a second type wherein instructions of the first type are awaiting page information being retrieved by the pending page table walk and instructions of the second type are merely blocked pending completion of any page table walk and wherein said wake up unit awakens and transmits instructions of the first type before instructions of the second type.
Claim 21
Dependent Claim
43 words
The computer system of claim 17 wherein said wake up unit means transmits the awakened instructions of the first type to the translation lookaside buffer means in order of age then transmits the awakened instructions of the second type in order of age.
Claim 22
Dependent Claim
168 words
A computer system comprising: a plurality of microprocessors each having an instruction fetch and issue unit to issue instructions, some of which are speculative instructions, each of said instructions specifying a virtual address; a translation lookaside buffer to store physical addresses corresponding to selected virtual addresses; a page miss handler to determine the physical address corresponding to the virtual address of an instruction not stored within said translation lookaside buffer; a memory ordering buffer for reordering and blocking memory instructions; a blocking unit, operative in response to a translation lookaside buffer miss, to determine whether the page miss handler is busy and to control the memory ordering buffer to block an instruction causing the translation lookaside buffer miss until the page miss handler is no longer busy; a wake up unit to awaken instructions blocked by the blocking unit and to transmit the awakened instructions to the translation lookaside buffer; a memory; an input/output unit; and a system bus interconnecting said microprocessors, said memory and said input/output unit.
Claim 23
Dependent Claim
168 words
A computer system comprising: a plurality of microprocessors each having an instruction fetch and issue unit to issue instructions, some of which are speculative instructions, each of said instructions specifying a virtual address; a translation lookaside buffer to store physical addresses corresponding to selected virtual addresses; a page miss handler to determine the physical address corresponding to the virtual address of an instruction not stored within said translation lookaside buffer; a memory ordering buffer for reordering and blocking memory instructions; a blocking unit, operative in response to a translation lookaside buffer miss, to determine whether the page miss handler is busy and to control the memory ordering buffer to block an instruction causing the translation lookaside buffer miss until the page miss handler is no longer busy; a wake up unit to awaken instructions blocked by the blocking unit and to transmit the awakened instructions to the translation lookaside buffer; a memory; an input/output unit; and a system bus interconnecting said microprocessors, said memory and said input/output unit.
Claim 24
Dependent Claim
31 words
The computer system of claim 19, wherein said blocking unit blocks a plurality of instructions, each causing translation lookaside buffer means misses, until the page miss handler is no longer busy.
Claim 25
Dependent Claim
27 words
The computer system of claim 20, wherein said wake up unit awakens all blocked instructions and transmits said awakened instructions to the translation lookaside buffer in sequence.
Claim 26
Dependent Claim
25 words
The computer system of claim 21 wherein said wake up unit transmits the awakened instructions to the translation lookaside buffer means in order of age.
Claim 27
Dependent Claim
74 words
The computer system of claim 21 wherein said blocking unit blocks instructions of a first type and a second type wherein instructions of the first type are awaiting page information being retrieved by the pending page table walk and instructions of the second type are merely blocked pending completion of any page table walk and wherein said wake up unit awakens and transmits instructions of the first type before instruction of the second type.
Claim 28
Dependent Claim
41 words
The computer system of claim 23 wherein said wake up unit transmits the awakened instructions of the first type to the translation lookaside buffer in order of age then transmits the awakened instructions of the second type in order of age.
Claim 29
Dependent Claim
149 words
A microprocessor comprising: an instruction fetch and issue unit configured to issue instructions, wherein some of said instructions are speculative instructions and each of said instructions specifying a virtual address; a translation lookaside buffer configured to store physical addresses corresponding to selected virtual addresses; a page miss handler configured to determine the physical address corresponding to an instruction for addresses not stored within said translation lookaside buffer; a memory ordering buffer configured to reorder and block memory instructions; a blocking unit, operative in response to a translation lookaside buffer miss, to determine whether the page miss handler is busy and to control the memory ordering buffer to block an instruction causing the translation lookaside buffer miss until the page miss handler is no longer busy; and a wake up unit for awakening instructions blocked by the blocking unit and for transmitting the awakened instructions to the translation lookaside buffer.
Claim 30
Dependent Claim
149 words
A microprocessor comprising: an instruction fetch and issue unit configured to issue instructions, wherein some of said instructions are speculative instructions and each of said instructions specifying a virtual address; a translation lookaside buffer configured to store physical addresses corresponding to selected virtual addresses; a page miss handler configured to determine the physical address corresponding to an instruction for addresses not stored within said translation lookaside buffer; a memory ordering buffer configured to reorder and block memory instructions; a blocking unit, operative in response to a translation lookaside buffer miss, to determine whether the page miss handler is busy and to control the memory ordering buffer to block an instruction causing the translation lookaside buffer miss until the page miss handler is no longer busy; and a wake up unit for awakening instructions blocked by the blocking unit and for transmitting the awakened instructions to the translation lookaside buffer.
Claim 31
Dependent Claim
31 words
The microprocessor of claim 25, wherein said blocking unit blocks a plurality of instructions, each block causing a translation lookaside buffer miss until the page miss handler is no longer busy.
Claim 32
Dependent Claim
25 words
The microprocessor of claim 26, wherein said wake up unit awakens all blocked instructions and transmits awakened instructions to the translation lookaside buffer in sequence.
Claim 33
Dependent Claim
22 words
The microprocessor of claim 27 wherein said wake up unit transmits awakened instructions to the translation lookaside buffer in order of age.
Claim 34
Dependent Claim
73 words
The microprocessor of claim 27 wherein said blocking unit blocks instructions of a first type and a second type, wherein instructions of the first type are awaiting page information being retrieved by the pending page table walk and instructions of the second type are blocked pending completion of any page table walk, and further wherein said wake up unit awakens and transmits instructions of the first type before instructions of the second type.
Claim 35
Dependent Claim
39 words
The microprocessor of claim 29 wherein said wake up unit transmits awakened instructions of the first type to the translation lookaside buffer in order of age and then transmits awakened instructions of the second type in order of age.
References Cited (Backward Citations)
US5455924A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-17 | 2000-09-16 | 2001-03-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-17 | 2004-09-16 | 2005-03-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-17 | 2008-09-16 | 2009-03-18 | $7700.00 | Window Closed / Lapsed |