Variable page size translation lookaside buffer

• US 5,526,504 A
• Filed: 12/15/1993
• Issued: 06/11/1996
• Est. Priority Date: 12/15/1993
• Status: Expired due to Term

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Hsu, Peter Y., Scanlon, Joseph T., Ciavaglia, Steve J.
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US08/168,822
• Time in Patent Office: 909 Days
• Field of Search: 395/400, 395/425, 395/416, 395/417, 395/418, 395/419, 365/49
• US Class Current: 711/207
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/652 Page size control

Abstract

A set associative translation lookaside buffer (TLB) that supports variable sized pages without requiring the use of a separate block TLB. The TLB includes a hashing circuit that creates an index into the TLB for a virtual address using different bits from the virtual address depending on the page size of the address, and a comparator that compares virtual address identifiers or portions of virtual address identifiers stored in the TLB to the current virtual address to determine if a translation to the current virtual address is stored in the TLB.

Claims

1. A translation lookaside buffer for use in a processor that executes instructions from first and second processes, said first process addressing a first virtual memory space comprising a plurality of pages of a first page size and said second process addressing a second virtual memory space comprising a plurality of pages of a second page size, said translation lookaside buffer storing mappings of addresses in said first and second virtual memory spaces to a physical memory space and said translation lookaside buffer comprising:

a memory having a first memory space for storing a plurality of virtual address identifiers and a second memory space for storing a corresponding plurality of physical page identifiers;

indexing means, coupled to said memory, for creating an index address to a specific location in said first memory space for an input virtual address from a subset of bits of said input virtual address;

an index selection circuit, coupled to said indexing means, for selecting said subset to comprise a first subset of bits if said input virtual address is an address in said first virtual memory space and for selecting said subset of bits to comprise a second subset of bits different than said first subset if said input virtual address is an address in said second virtual memory space;

comparing means, coupled to said memory, for comparing a virtual address identifier stored in said first memory space at said index address with said input virtual address and for generating a match signal when said stored virtual address identifier matches said input virtual address, said comparing means comprising masking means for masking, with a first mask, comparisons of a first set of individual bits in said virtual address identifier to corresponding bits of said input virtual address when said input virtual address is an address in said first virtual address space and for masking, with a second mask, comparisons of a second set of individual bits in said virtual address identifier to corresponding bits of said input virtual address when said input virtual address is an address in said second virtual address space; and

output means, coupled to said memory and to said comparing means, for outputting from said second memory space the physical page identifier corresponding to the matching stored virtual address identifier in response to said match signal.

2. The translation lookaside buffer of claim 1 wherein:

said memory is partitioned into a plurality of sets with exactly one entry in each set having an address equal to said index address; and

wherein

said comparing means is coupled to each set of said memory and compares a virtual address identifier from each memory set stored at said index address to said input virtual address.

3. The translation lookaside buffer of claim 1 wherein said comparing means further comprises a mask decoder for creating said first mask when said input virtual address is an address in said first virtual address space and for creating said second mask when said input virtual address is an address in said second virtual address space.

4. The translation lookaside buffer of claim 1 or 2 wherein said memory comprises a first memory for storing said virtual address identifiers in said first memory space and a second memory, coupled to said first memory, for storing said physical address identifiers in said second memory space.

5. A set associative translation lookaside buffer (TLB) for use in a processor that executes instructions from first and second processes, said first process having a first unique process identifier and addressing a first virtual memory space comprising a plurality of pages of a first page size, said second process having a second unique identifier and addressing a second virtual memory space comprising a plurality of pages of a second page size, wherein said first page size may be the same as said second page size, said set associative translation lookaside buffer storing mappings of addresses in said first and second virtual memory address spaces to a physical memory space, said set associative translation lookaside buffer comprising:

a memory comprising a plurality of memory sets, each memory set having a first memory space for storing virtual address identifiers and a second memory space for storing corresponding physical page identifiers;

a first register for storing one of said first and second page sizes;

a second register for storing one of said first and second process identifiers;

an index selection circuit for selecting for output a first and second subset of bits from an input virtual address in accordance with one of said first and second page sizes stored in said first register, said index selection circuit selecting said first subset of bits when said input virtual address is an address tier said first process and selecting said second subset of bits when said input virtual address is an address for said second process; and

hashing means, coupled to said memory, to said index selection circuit, and to said second register, for hashing said first or second subset of bits with said process indentifier stored in said second register to create a randomized index to said TLB, wherein virtual address identifiers that have the same value but are generated by different processes, each process having a unique process indentifier, are stored in different storage locations in said TLB according to said unique process indentifier, thereby reducing thrashing.

6. A set associative translation lookaside buffer for use in a processor that executes instructions from first and second processes, said first process having a first unique process identifier and addressing a first virtual memory space comprising a plurality of pages of a first page size, said second process having a second unique identifier and addressing a second virtual memory space comprising a plurality of pages of a second page size, wherein said first page size may be the same as said second page size, said set associative translation lookaside buffer storing mappings of addresses in said first and second virtual memory address spaces to a physical memory space, said set associative translation lookaside buffer comprising:

a memory comprising a plurality of memory sets, each memory set having a first memory space for storing virtual address identifiers and a second memory space for storing corresponding physical page identifiers;

a first register for storing one of said first and second page sizes;

a second register for storing one of said first and second process identifiers;

an index selection circuit for selecting for output a first and second subset of bits from an input virtual address, said index selection circuit selecting said first subset of bits when said input virtual address is an address for said first process and selecting said second subset of bits when said input virtual address is an address for said second process; and

hashing means, coupled to said memory, to said index selection circuit, and to said second register, for hashing said first or second subset of bits with said process identifier stored in said second register to create a randomized index address to said memory.

7. The set associative lookaside buffer of claim 6 further comprising:

comparing means, coupled to said memory, for comparing a virtual address identifier stored in each of said memory sets at said index address to said input virtual address and for generating a match signal when one of said stored virtual address identifiers matches said input virtual address; and

output means, coupled to said memory and said comparing means, for outputting the physical page identifier corresponding to said matching virtual address identifier in response to said match signal.

8. The set associative buffer claim 6, wherein said hashing means comprises an exclusive-OR circuit.