Translation lookaside buffer

Abstract

A translation lookaside buffer (TLB) is disclosed formed using RAM and synthesisable logic circuits. The TLB provides logic within the synthesisable logic for pairing down a number of memory locations that must be searched to find a translation to a physical address from a received virtual address. The logic provides a hashing circuit for hashing the received virtual address and uses the hashed virtual address to index the RAM to locate a line within the RAM that provides the translation.

What is claimed is:  
     
         1 . A translation lookaside buffer (TLB) comprising: 
 at least an input port for receiving a portion of a virtual address;    a random access memory;    a set of registers; and,    synthesisable logic for determining a hash value from the received portion of the virtual address and for comparing the hash value to a stored hash value within the set of registers to determine a potential that a physical address associated with the virtual address is stored within a line within the random access memory and associated with a register, from the set of registers, within which the hash value is stored.    
     
     
         2 . A translation lookaside buffer according to  claim 1 , wherein the synthesisable logic comprises an encoder circuit for receiving at least a page size signal indicative of a page size and for determining from the at least a page size signal at least a mask bit for use in determining the hash value.  
     
     
         3 . A translation lookaside buffer according to  claim 2 , wherein the synthesisable logic comprises a first hashing circuit including an output port and for receiving the received portion of the virtual address and the at least a mask bit, the first hashing circuit for deterministically generating a first hash value from the received portion of the virtual address and the at least a mask bit and for providing the first hash value to the output port thereof.  
     
     
         4 . A translation lookaside buffer according to  claim 3 , wherein the synthesisable logic comprises at least a register ( 409 ) for storing the at least a mask bit.  
     
     
         5 . A translation lookaside buffer according to  claim 4 , wherein the synthesisable logic comprises a second hashing circuit for receiving the portion of the virtual address and at least a stored mask bit from the at least a register, the second hashing circuit for determining the hash value.  
     
     
         6 . A translation lookaside buffer according to  claim 5 , comprising a comparator and wherein the random access memory comprises a translation table stored therein, wherein the line is stored within the translation table and wherein the hash value is compared within the comparator to determine whether the virtual address is present at an associated line within the translation table, a positive indication indicative of a potential match and a negative indication indicative of no potential match for the virtual address within the associated line.  
     
     
         7 . A translation lookaside buffer according to  claim 5 , comprising a third hashing circuit, the third hashing circuit for receiving the portion of the virtual address and at least a stored mask bit from the at least a register, the third hashing circuit for in parallel with the second hashing circuit for determining a hash vector, the hash vector for having stored therein the deterministically generated hash value for at least two lines in the random access memory.  
     
     
         8 . A translation lookaside buffer according to  claim 7 , wherein the first hashing circuit pre-hashes the virtual address and at least a retrieved mask bit to provide a pre-hash value for provision to the second and third hashing circuits.  
     
     
         9 . A translation lookaside buffer according to  claim 8 , comprising at least a second register, the at least a second register for storing a comparison result between the hash value and an associated line within the memory, the comparison result providing a positive indication indicative of a potential match and a negative indication indicative of no potential match for the virtual address within the associated line.  
     
     
         10 . A translation lookaside buffer according to  claim 9 , wherein a plurality of the at least a second register includes a number of registers equal or greater than an amount of lines in memory of the translation lookaside buffer.  
     
     
         11 . A translation lookaside buffer according to  claim 1 , wherein the synthesisable logic comprises a plurality of comparators for comparing a plurality of hash values to a plurality of expected hash values each expected hash value associated with a line in memory to determine a potential that a translation for the virtual address is stored within each associated line in memory, the comparators for, in combination providing a vector including a value associated with each line in memory.  
     
     
         12 . A translation lookaside buffer according to  claim 11 , wherein the synthesisable logic comprises a resolution circuit for resolving between the plurality of values indicative of a potential translation of a line in memory containing the translation.  
     
     
         13 . A translation lookaside buffer according to  claim 1 , comprising a hashing circuit for hashing a virtual address other than a virtual address for which a translation is presently stored to determine a hash value and for storing the hash value in a register in association with an available line in memory, the hashing circuit for storing the virtual address and a translation therefor in the available line in memory.  
     
     
         14 . A translation lookaside buffer comprising: 
 a random access memory;    a first register associated with a line in the memory; and,    a hashing circuit for receiving a virtual address other than a virtual address for which a translation is presently stored in the random access memory, for determining a hash value and for storing the hash value in the first register, the hashing circuit for storing the virtual address and a translation therefor in the line in memory.    
     
     
         15 . A translation lookaside buffer comprising: 
 a RAM; and,    synthesisable logic for determining from a virtual address at least one potential address within the RAM in fixed relation to which to search for a physical address associated with the virtual address, the at least one potential address being other than the one and only known address within the RAM in fixed relation to which the physical address associated with the virtual address is stored.    
     
     
         16 . A translation lookaside buffer according to  claim 15 , wherein the synthesisable logic comprises a hashing circuit for hashing the virtual address to determine a value indicative of a line in the RAM at which to begin searching for a translation for the virtual address.  
     
     
         17 . A translation lookaside buffer according to  claim 16 , wherein the synthesisable logic comprises a lookup resolving circuit for iteratively comparing virtual address data stored within a plurality of lines in the RAM with the virtual address to determine a presence of a translation for the virtual address, the lookup resolving circuit for providing the resolved translation at an output port thereof.  
     
     
         18 . A translation lookaside buffer according to  claim 17 , wherein the lookup resolving circuit includes an incrementing circuit for incrementing an address of the line within the memory by a line between successive comparison operations.  
     
     
         19 . A translation lookaside buffer according to  claim 17 , wherein the lookup resolving circuit includes a hashing circuit for varying an address of the line within the memory by a line between successive comparison operations.  
     
     
         20 . A method of performing a virtual address lookup function for a translation lookaside buffer including RAM and synthesisable logic including the steps of: 
 providing a virtual address to the synthesisable logic;    hashing the provided virtual address to provide a hash result;    based on the hash result determining a memory location within the RAM relative to which is stored a virtual address identifier and a physical address related thereto;    comparing the virtual address to the virtual address identifier to determine if the physical address corresponds to the provided virtual address; and,    when the physical address corresponds to the provided virtual address, providing the physical address as an output value.    
     
     
         21 . A method according to  claim 20 , wherein the step of determining a memory location includes the steps of: 
 comparing the hash result against a known hash result associated with a line in RAM to determine a comparison result;    forming a hit vector including a plurality of values, each value associated with the line in RAM associated with the known hash result and relating to a likelihood that the line in RAM with which the value is associated contains a translation for the virtual address.    
     
     
         22 . A method according to  claim 21 , wherein the step of determining is performed for each line within the RAM.  
     
     
         23 . A method according to  claim 22 , wherein the step of comparing is performed for sequentially for different lines in RAM associated with a value indicative of a potential translation for the virtual address until the line containing the translation is located.  
     
     
         24 . A method according to  claim 20 , wherein the step of determining is performed for each line within the RAM.  
     
     
         25 . A method according to  claim 24 , wherein a line in memory includes a single address translation from a single virtual address to a single corresponding physical address.  
     
     
         26 . A method according to  claim 20 , wherein the step of hashing includes the steps of hashing the virtual address and a stored value associated with each line in memory to determine independently a hash value associated with each line in memory.  
     
     
         27 . A method according to  claim 26 , wherein a line in memory includes a single address translation from a single virtual address to a single corresponding physical address.  
     
     
         28 . A method according to  claim 20 , wherein the step of hashing includes the steps of: 
 pre-hashing the virtual address;    combining the pre-hashed virtual address independently with each of a plurality of stored values, each associated with a line in memory to determine independently a hash value associated with each line in RAM.    
     
     
         29 . A method according to  claim 28 , wherein the step of comparing is performed for sequentially for different lines in RAM associated with a value indicative of a potential translation for the virtual address until the line containing the translation is located.  
     
     
         30 . A method according to  claim 28 , wherein a line in memory includes a single address translation from a single virtual address to a single corresponding physical address.  
     
     
         31 . A method according to  claim 20 , wherein the step of hashing includes the step of hashing the virtual address to determine a value indicative of a line in RAM where a translation for the virtual address is potentially stored.  
     
     
         32 . A method according to  claim 31 , wherein the step of comparing includes the step of iteratively comparing in a known order starting from the line in RAM related to the determined value a plurality of lines in RAM until a translation for the virtual address is located.  
     
     
         33 . A method according to  claim 32 , wherein the known order is incremented by one line between successive comparisons  
     
     
         34 . A method according to  claim 32 , wherein the known order is determined by solving a function based on the determined value.