Apparatus and method for a space saving translation lookaside buffer for content addressable memory

Claim 2

In a computer system comprising a random access memory and a fast cache memory, said cache memory containing frequently referenced data from the random access memory, said system first referencing the cache memory to retrieve data and referencing the random access memory only if the data is not in the cache memory, a method for saving space in address entries of a buffer for the cache memory, each of said address entries comprising a virtual address tag field for virtual address tags, and a level bit field comprising a plurality of bits, said address tag field identifying a virtual address, said level bit field identifying the length of a virtual address tag, said method comprising the steps of: storing data in the cache memory, comprising the steps of; providing an entry in said buffer for data stored in the cache, setting a first level bit for a valid entry, and setting remaining level bits in said level bit field according to a predetermined virtual tag match criteria, said predetermined criteria being based on the length of said virtual address tag in said address tag field; accessing data in the cache memory, comprising the steps of; receiving a virtual address from a processor, reading the status of said first level bit in the address entry in the buffer, if the first level bit is reset, reading a next entry in said buffer, and if the first level bit is set, causing said valid entry to be compared with said virtual address tag from said processor, the length of said virtual address tag in said entry being determined by the status of all level bits according to said predetermined virtual tag match criteria; whereby if the virtual address matches an entry in the buffer, a corresponding physical address is outputted and data is retrieved from the cache.

Claim 3

The method as defined by claim 1 wherein the level bit field is stored in content addressable memory.

Claim 4

The method as defined by claim 2 wherein said buffer is a translation lookaside buffer for said cache memory.

Claim 5

The method as defined by claim 3 wherein said remaining level bits are set according to the predetermined virtual tag match criteria such that one level bit is set to indicate the eight (8) most significant bits of a thirty two (32) bit virtual address, two level bits are set to indicate the fourteen (14) most significant bits in said thirty two (32) bit virtual address, and three level bits are set to indicate the twenty (20) most significant bits of said 32 bit virtual address, respectively, represent the virtual address tag field.

Claim 6

In a computer system comprising a random access memory and a fast cache memory, said cache memory containing frequently referenced data from the random access memory, said system first referencing the cache memory to retrieve data and referencing the random access memory only if the data is not in the cache memory, an apparatus for saving spaced in address entries of a buffer for a cache memory, each of said entries comprising a virtual address tag field for virtual address tags, and a level bit field comprising a plurality of bits, said address tag field identifying a virtual address, said level bit field identifying the length of a virtual address tag, said apparatus comprising: means for storing data in the cache memory, comprising; means for providing an entry in said buffer for data stored in the cache, means for setting a first level bit for a valid entry, and means for setting remaining level bits in said level bit field according to a predetermined virtual tag match criteria, said predetermined criteria being based on the length of said virtual address tag in said address tag field; means for accessing data in the cache memory, comprising; means for receiving a virtual address from a processor, means for reading the status of said first level bit in the address entry in the buffer, if the first level bit is reset, means for reading a next entry in said buffer, if the first level bit is set, means for causing said valid entry to be compared with said virtual address tag from said processor, the length of said virtual address tag in said entry being determined by the status of all level bits according to said predetermined virtual tag match criteria; whereby if the virtual address matches the entry in the buffer, a corresponding physical address is outputted and the data is retrieved from the cache.

Claim 7

In a computer system comprising a random access memory and a fast cache memory, said cache memory containing frequently referenced data from the random access memory, said system first referencing the cache memory to retrieve data and referencing the random access memory only if the data is not in the cache memory, an apparatus for saving spaced in address entries of a buffer for a cache memory, each of said entries comprising a virtual address tag field for virtual address tags, and a level bit field comprising a plurality of bits, said address tag field identifying a virtual address, said level bit field identifying the length of a virtual address tag, said apparatus comprising: means for storing data in the cache memory, comprising; means for providing an entry in said buffer for data stored in the cache, means for setting a first level bit for a valid entry, and means for setting remaining level bits in said level bit field according to a predetermined virtual tag match criteria, said predetermined criteria being based on the length of said virtual address tag in said address tag field; means for accessing data in the cache memory, comprising; means for receiving a virtual address from a processor, means for reading the status of said first level bit in the address entry in the buffer, if the first level bit is reset, means for reading a next entry in said buffer, if the first level bit is set, means for causing said valid entry to be compared with said virtual address tag from said processor, the length of said virtual address tag in said entry being determined by the status of all level bits according to said predetermined virtual tag match criteria; whereby if the virtual address matches the entry in the buffer, a corresponding physical address is outputted and the data is retrieved from the cache.

Claim 8

The apparatus is defined by claim 5 wherein said bit field is stored in content addressable memory.

Claim 9

The apparatus as defined by claim 6 wherein said buffer is a translation lookaside buffer for said cache memory.

Claim 10

The apparatus as defined by claim 7 wherein said remaining level bits are set according to the predetermined virtual tag match criteria such that one level bit is set to indicate the eight (8) most significant bits of a thirty two (32) bit virtual address, two level bits are set to indicate the fourteen (14) most significant bits in said thirty two (32) bit virtual address, and three level bit are set to indicate the twenty (20) most significant bits of said 32 bit virtual address, respectively, represent the virtual address tag field.