Computer memory address control apparatus utilizing hashed address tags in page tables which are compared to a combined address tag and index which are longer than the basic data width of the associated computer

• US 5,724,538 A
• Filed: 02/27/1996
• Issued: 03/03/1998
• Est. Priority Date: 04/08/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Morris, Dale C., Bryg, William R., Huck, Jerome C.
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US08/607,622
• Time in Patent Office: 735 Days
• Field of Search: 395/416, 395/417, 395/418
• US Class Current: 711/206
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables

Abstract

The present invention relates to the design of computer systems incorporating virtual memory where a virtual page number is longer than the inherent basic data width of the designed computer system. Instead of storing an entire tag in page table entries, a reduced tag is stored. The reduced tag is sized to be no greater in length than the basic computer data width and therefore a single compare operation will ascertain whether there is a match between the reduced tag and the tag stored in a page table entry. To maintain uniqueness of the page table entries, any bits removed from the virtual address to form the reduced tag are used to form an index into the page table.

Claims

1. A computer apparatus having a basic data width, incorporating virtual memory to physical memory translation apparatus of the type having a TLB and a page table, comprising:

a first storage means storing a virtual tag wherein the number of bits in the virtual tag exceeds the basic data width of the computer;

the virtual tag having a reduced tag section wherein the number of bits in the reduced tag section is equal to, or less than, the basic data width of the computer;

the virtual tag having an index section including the virtual tag bits excluded from the reduced tag section;

a hash function operative to produce an output string of bits from the reduced tag bits;

a page table index including said output string bits combined with said index section bits; and

a page table including a reduced tag entry, where the reduced tag entry is a reduced tag, and an associated physical page address;

wherein after a TLB miss, the page table points to a page table reduced tag entry which is compared to the reduced tag entry of the virtual tag.

2. An apparatus as in claim 1 wherein the page table includes 2^I reduced tag entries where "I" equals the number of bits in the index section.

3. An apparatus as in claim 1 wherein the page table also includes a pointer entry which points to a chain of entries and the chain of entries includes a reduced tag entry.

4. A computer apparatus for updating information in a translation look-aside buffer (TLB) comprising:

a first storage means storing a virtual address wherein the virtual address includes a reduced tag field, an index field and a physical offset field;

a hash function means for hashing the information in the reduced tag field and producing a tag index output;

a page table index including the tag index and the information in the index field where the page table index points to a reduced tag entry in a page table;

a comparator that compares the information in the reduced tag entry to the information in the reduced tag field and if the information in the reduced tag entry and the reduced tag field match, the physical page entry associated with the reduced tag entry and the virtual address associated with the reduced tag entry are stored in the TLB; and

wherein the reduced tag field and the size of the reduced tag entry are equal to, or less than, a basic data width of the associated computer and the reduced tag field plus the index field is larger than the basic data width of the associated computer.

5. An apparatus as in claim 4 wherein:

the page table index includes the tag index and an output from a second hash function; and

a first input to the second hash function includes all the information in the index field and a second input to the second hash function includes 1 bit of information from the reduced tag field.

6. A computer-based apparatus for handling translation lookaside buffer (TLB) misses, the apparatus comprising:

a physical memory means for storing pages of data, the pages of data accessed via a virtual address;

a TLB for storing address translation information for translating the virtual addresses to physical addresses of the data in the physical memory;

a TLB miss handler, coupled to the TLB, adapted to hash information in a first field within the virtual address, where this first field is equal to, or less than, a basic data width of the associated computer, to form a tag index and this tag index is combined with information in a separate second field within the virtual address to form an offset pointer into a page table, wherein said separate second field comprises virtual bits of said virtual address excluded from said first field; and

the TLB handler is further adapted to compare page table information pointed to by the offset pointer with the information in the first field within the virtual address and if there is a match, then the TLB miss handler causes information from the page table to be stored in the TLB.

7. An apparatus as in claim 6 wherein the TLB miss handler is further adapted to hash the information in the separate second field plus one bit of information from the first field and thereby form a hash index output which is combined with the tag index to form the offset pointer.

8. An apparatus as in claim 7 wherein the page table includes 2^I translation entries where "I" equals the number of bits in the hash index output.

9. A computer apparatus for updating information in a translation look-aside buffer (TLB) comprising:

a first storage means storing a virtual address wherein the virtual address includes a reduced tag field, an index field and a physical offset field;

a first hash function for hashing the reduced tag field and producing a tag index output;

a page table index including the tag index and the index field where the page table index points to a hashed tag entry in a page table;

a second hash function for hashing the virtual address and thereby producing a hash result; and

a comparator that compares the hashed tag entry to the hash result and if the hashed tag and hash result match, the physical page entry associated with the hashed tag entry is stored in the TLB.

10. An apparatus as in claim 9 wherein the page table includes 2^I hashed tag entries where "I" equals the number of bits in the index section.

11. An apparatus as in claim 9 wherein the hashed tag is equal to a basic data width of a computer the hashed tag is associated with.