US5099415A — Guess mechanism for virtual address translation

Claim 1

Independent Claim 376 words

An apparatus for translating virtual addresses to real addresses in response to a multi-bit signal output by a processor and indicative of an effective address, comprising: a set of Lookaside Tables, each Lookaside Table in said set having a list of address entries therein with the address entries arranged in sets across said set of Lookaside Tables and each address entry comprising a virtual page index and a real frame index; a set of validity registers, each validity register containing bits having values respectively indicative of the validity of each address entry in a respective Lookaside Table of said set of Lookaside Tables; indexing means for receiving multi-bit signals output by a processor including effective address bits and indexing a portion of said effective address bits into said Lookaside Tables to compare said portion of said effective address bits for a match with each set of address entries in said Lookaside Tables means for reading out, in response to a match between said portion of said effective address bits and a set of address entries, the real frame index from each address entry in the matched set of address entries, one of which real frame indexes is used for incorporation in a real address indicative signal register means for containing bits corresponding to each set of address entries, said bits having values respectively indicative of the Lookaside Table in each set of address entries containing the real frame index most recently-used for incorporation in a real address indicative signal; means, using said portion of said effective address bits, for checking said validity registers and said register means to determine the values of the bits therein corresponding to the matched set of address entries; and guess means for producing a signal to select the real frame index, from those real frame indexes read out from the matched set of address entries, to be output for incorporation in a real address indicative signal, said selection signal being in response to 1) the determination of a valid bit in the respective validity register for the address entry containing said selected real frame index and 2) a bit value in said register means indicative of the Lookaside Table in said matched set in which said real frame index is contained.

Claim 2

Independent Claim 376 words

An apparatus for translating virtual addresses to real addresses in response to a multi-bit signal output by a processor and indicative of an effective address, comprising: a set of Lookaside Tables, each Lookaside Table in said set having a list of address entries therein with the address entries arranged in sets across said set of Lookaside Tables and each address entry comprising a virtual page index and a real frame index; a set of validity registers, each validity register containing bits having values respectively indicative of the validity of each address entry in a respective Lookaside Table of said set of Lookaside Tables; indexing means for receiving multi-bit signals output by a processor including effective address bits and indexing a portion of said effective address bits into said Lookaside Tables to compare said portion of said effective address bits for a match with each set of address entries in said Lookaside Tables means for reading out, in response to a match between said portion of said effective address bits and a set of address entries, the real frame index from each address entry in the matched set of address entries, one of which real frame indexes is used for incorporation in a real address indicative signal register means for containing bits corresponding to each set of address entries, said bits having values respectively indicative of the Lookaside Table in each set of address entries containing the real frame index most recently-used for incorporation in a real address indicative signal; means, using said portion of said effective address bits, for checking said validity registers and said register means to determine the values of the bits therein corresponding to the matched set of address entries; and guess means for producing a signal to select the real frame index, from those real frame indexes read out from the matched set of address entries, to be output for incorporation in a real address indicative signal, said selection signal being in response to 1) the determination of a valid bit in the respective validity register for the address entry containing said selected real frame index and 2) a bit value in said register means indicative of the Lookaside Table in said matched set in which said real frame index is contained.

Claim 3

Dependent Claim 44 words

An apparatus as in claim 1, further comprising multiplexing means, responsive to said real-frame-index- selection signals from said guess means, for outputting one of said real frame indexes from said matched set of address entries as part of a real address indicative signal output.

Claim 4

Dependent Claim 84 words

An apparatus as in claim 1, wherein said processor means provides the bits of said effective address in two consecutive cycles, said bits being ordered from higher order bits to lower order bits, with half being higher order bits and half being lower order bits, and the lower order bits being provided during the first cycle and the higher order bits being provided during the second cycle, and said indexing means provides a portion of said lower order bits to index said Lookaside Tables.

Claim 5

Dependent Claim 99 words

An apparatus as in claim 3, further comprising: means for comparing a portion of the higher order bits provided by said processor means during the second cycle, with each of the Lookaside Table address entries in the set of address entries that is matched with said portion of said effective address bits means for producing a hit signal when said higher order bits compare in a match with one of said Lookaside Table address entries; and means for producing a miss signal when said higher order bits compare in a match with none of said Lookaside Table address entries.

Claim 6

Dependent Claim 171 words

An apparatus as in claim 4, further comprising: output means for producing a real address indicative signal output after said first cycle means, responsive to said real-frame-index- selection signals from said guess means, for outputting one of said real frame indexes from among said matched set of address entries for incorporation as part of a real address indicative signal output produced by said output means after said first cycle; and means, responsive to the output of said one of said real frame indexes selected from among said matched set of address entries and to the production of a hit signal, and to the failure of coincidence between the output of said one selected real frame index and the production of a hit signal for said address entry in which said one selected real frame index is contained, for producing a signal after said second cycle to invalidate the output of the real address indicative signal, produced by said output means after said first cycle, incorporating said one selected real frame index.

Claim 7

Dependent Claim 90 words

An apparatus as in claim 5, wherein said means responsive to the failure of coincidence between the output of said one selected real frame index and the production of a hit signal for said address entry in which said one selected real frame index is contained, comprises means, responsive to a signal from said guess means, for producing a signal after said second cycle to invalidate the output of the real address indicative signal, incorporating said one selected real frame index, produced by said output means after said first cycle.

Claim 8

Dependent Claim 40 words

An apparatus as in claim 3, further comprising means for providing the remaining portion of said lower order bits not provided by said indexing means to index said Lookaside Tables for incorporation as part of a real address indicative signal.

Claim 9

Dependent Claim 84 words

An apparatus as in claim 4, wherein each of said Lookaside Table address entries comprise said virtural page index (VPI), said real frame index (RFI), and a segment ID (SID) entry, and said means for comparing provides a portion of the higher order bits for comparison with said SID entries, and the remaining portion of said higher order bits for comparison with said VPI entries, in the set of Lookaside Table address entries that is matched with said portion of said effective address bits.

Claim 10

Dependent Claim 110 words

An apparatus as in claim 4, further comprising: output means for producing a real address indicative signal output after said first cycle means, responsive to said real-frame-index- selection signals from said guess means, for outputting one of said real frame indexes from among said matched set of address entries for incorporation as part of a real address indicative signal output produced by said output means after said first cycle; and means, responsive to a miss signal, for producing a signal after said second cycle to invalidate the output of the real address indicative signal, incorporating said one selected real frame index, produced by said output means after said first cycle.

Claim 11

Independent Claim 356 words

A method for translating virtual addresses in a computer having a set of Lookaside Tables in a buffer with address entries therein arranged in sets across said set of Lookaside Tables and each address entry comprising a virtual page index and a real frame index, comprising the steps of: providing a set of validity registers, each containing bits having values respectively indicative of the validity of each address entry in a respective Lookaside Table of said set of Lookaside Tables in said buffer; providing a multi-bit signal indicative of an effective address; indexing a portion of said effective address bits into said Lookaside Tables to compare said portion of said effective address bits for a match with each set of address entries in said Lookaside Tables, and reading out, in response to a match between said portion of said effective address bits and a set of address entries, a real frame index for each address entry in the matched set of address entries, one of which real frame indexes is used for inclusion in a real address indicative signal providing a register containing bits corresponding to each set of address entries, said bits having values respectively indicative of the Lookaside Table in each set of address entries containing the real frame index most recently used for inclusion in a real address indicative signal using said portion of said effective address bits to check said validity registers and said register containing bits corresponding to each set of address entries, for determining the value of the bits therein corresponding to the matched set of address entries; and producing a guess signal to select the real frame index of the matched set to be output for inclusion in a real address indicative signal, said guess signal selection being in response to the determination of a valid bit in the respective validity register for the address entry containing the selected real frame index and a bit value in said register containing bits corresponding to each set of address entries, indicative of the Table in said matched set in which said address entry containing the selected real frame index is contained.

Claim 12

Independent Claim 356 words

A method for translating virtual addresses in a computer having a set of Lookaside Tables in a buffer with address entries therein arranged in sets across said set of Lookaside Tables and each address entry comprising a virtual page index and a real frame index, comprising the steps of: providing a set of validity registers, each containing bits having values respectively indicative of the validity of each address entry in a respective Lookaside Table of said set of Lookaside Tables in said buffer; providing a multi-bit signal indicative of an effective address; indexing a portion of said effective address bits into said Lookaside Tables to compare said portion of said effective address bits for a match with each set of address entries in said Lookaside Tables, and reading out, in response to a match between said portion of said effective address bits and a set of address entries, a real frame index for each address entry in the matched set of address entries, one of which real frame indexes is used for inclusion in a real address indicative signal providing a register containing bits corresponding to each set of address entries, said bits having values respectively indicative of the Lookaside Table in each set of address entries containing the real frame index most recently used for inclusion in a real address indicative signal using said portion of said effective address bits to check said validity registers and said register containing bits corresponding to each set of address entries, for determining the value of the bits therein corresponding to the matched set of address entries; and producing a guess signal to select the real frame index of the matched set to be output for inclusion in a real address indicative signal, said guess signal selection being in response to the determination of a valid bit in the respective validity register for the address entry containing the selected real frame index and a bit value in said register containing bits corresponding to each set of address entries, indicative of the Table in said matched set in which said address entry containing the selected real frame index is contained.

Claim 13

Dependent Claim 156 words

A method as in claim 10, wherein said set of Lookaside Tables comprises two Tables, TLB (0) and TLB (1), said Tables reading out respective real frame indexes RFI (0) and RFI(1), in response to a match between said portion of said effective address bits and a set of address entries therein said set of validity registers comprises two registers containing valid bits respectively indicative of the validity of each address entry in the respective Tables, TLB(0) and TLB(1) said register containing bits corresponding to each set of address entries, contains MRU bits respectively indicative of the Table containing the real frame index most-recently-used for inclusion in a real address indicative signal and wherein the respective real frame indexes RFI(0) and RFI(1) are selected to be output based on the following relationship: when the MRU bit=0 AND the valid bit for TLB(0)=1, use RFI(0); when the MRU bit=1 AND the valid bit for TLB(1)=l, use RFI(1).

Claim 14

Dependent Claim 33 words

A method as in claim 10, further comprising the step of multiplexing the output of said real frame indexes, in response to said guess signals, for inclusion in a real address indicative signal.

Claim 15

Dependent Claim 87 words

A method as in claim 10, further comprising the steps of providing the bits of said multi-bit signal indicative of an effective address in two consecutive cycles, said bits being ordered from higher order bits to lower order bits, with half being higher order bits and half being lower order bits, and the lower order bits being provided during the first cycle and the higher order bits being provided during the second cycle, and providing a portion of said lower order bits to index said Lookaside Tables.

Claim 16

Dependent Claim 42 words

A method as in claim 13, further comprising the step of providing the remaining portion of said lower order bits not used to index said Lookaside Tables for output with said selected real frame index to form said real address indicative signal.

Claim 17

Dependent Claim 75 words

A method as in claim 13, wherein said Lookaside Table address entries further comprise a segment ID (SID) entry, and further comprising the step of providing a portion of the higher order bits for comparison with said SID entries and the remaining portion of said higher order bits for comparison with said virtual page index entries in the set of Lookaside Table address entries that is matched with said portion of said effective address bits.

Claim 18

Dependent Claim 92 words

A method as in claim 13, further comprising the steps of: comparing a portion of the higher order bits provided during the second cycle, with each of the Lookaside Table address entries in the set of address entries that is matched with said portion of said effective address bits producing a hit signal when said higher order bits compare in a match with one of said Lookaside Table address entries; and producing a miss signal when none of said Lookaside Table address entries compares in a match with said higher order bits.

Claim 19

Dependent Claim 109 words

A method as in claim 16, further comprising the steps of: producing a real address indicative signal output after said first cycle outputting, in response to a guess signal, said selected real frame index as part of a real address indicative signal produced after said first cycle; and in response to the failure of coincidence between the output of the guess signal for said selected real frame index and the production of a hit signal for the entry containing said index, producing a signal after said second cycle to invalidate the output of the real address indicative signal, including said selected real frame index, produced after said first cycle.

Claim 20

Dependent Claim 42 words

A method as in claim 17, wherein the failure of coincidence between said guess signal for said selected real frame index and a hit signal for said entry containing said index is detected by ANDing said guess signal and said hit signal.

Claim 21

Dependent Claim 59 words

A method as in claim 16, wherein said selected real frame index is output in a real address indicative signal after said first cycle, and further comprising the step of producing a signal after said second cycle, in response to a miss signal, to invalidate the output of said real address indicative signal including said selected real frame index.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1995-03-24	1995-09-23	1996-03-24	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1999-03-24	1999-09-23	2000-03-24	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2003-03-24	2003-09-23	2004-03-24	$7700.00	Window Closed / Lapsed

Guess mechanism for virtual address translation

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag