Virtual address to physical address translation cache that supports multiple page sizes

A method for translating a first virtual address to a physical address, the method comprising the steps of:

• receiving the first virtual address, the first virtual address comprising a virtual page offset and a virtual page number, the first virtual address being mapped by an unknown page size, the unknown page size being one of L different page sizes where L is a positive integer greater than one;
• then, for each of the L page sizes, selecting a different one of the L page sizes to be a test page size,
• (i) calculating a pointer into a translation storage buffer, the pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the test page size, the pointer pointing to a candidate translation table entry of the translation storage buffer, the candidate translation table entry comprising a candidate tag and candidate data, the candidate tag identifying a particular virtual address and the candidate data identifying a particular physical address corresponding to the particular virtual address,
• (ii) extracting a virtual address target tag from the first virtual address, the virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the test page size,
• (iii) comparing the target tag to the candidate tag, and
• (iv) if the target tag matches the candidate tag, providing the candidate data as the physical address translation corresponding to the first virtual address,
• wherein the translation steerage buffer is comprised of sub translation storage buffers, each sub translation storage buffer corresponding to a page size and is comprised of a positive integral power of two translation table entries and each translation table entry is M words in size where M is a positive integer, and the step of calculating the pointer includes the steps of:
• forming a translation storage buffer index by extracting N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the test page size where N is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the test page size;
• and
• adding the product of the translation storage buffer index and M to a base address to form the pointer, the base address corresponding to the test page size, the base address being one of L base addresses.

A method for translating a first virtual address to a physical address, the method comprising the steps of:

• receiving the first virtual address to be translated, the first virtual address comprising a virtual page offset and a virtual page number, the first virtual address being mapped by an unknown page size, the unknown page size being a first or second page size, the first page size not equal to the second page size;
• calculating first and second pointers into a translation storage buffer, the first pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the first page size, the first pointer pointing to a first candidate translation table entry of the translation storage buffer, the first candidate translation table entry comprising a first candidate tag and first candidate data, the first candidate tag identifying a first particular virtual address and the first candidate data identifying a first particular physical address corresponding to the first particular virtual address, the second pointer being calculated from the virtual address to be translated by assuming that the first virtual address corresponds to a mapping of the second page size, the second pointer pointing to a second candidate translation table entry of the translation storage buffer, the second candidate translation table entry comprising a second candidate tag and second candidate data, the second candidate tag identifying a second particular virtual address and the second candidate data identifying a second particular physical address corresponding to the second particular virtual address;
• extracting first and second virtual address target tags from the first virtual address, the first virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the first page size, the second virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the second page size;
• comparing the first target tag to the first candidate tag;
• if the first target tag matches the first candidate tag, providing the first candidate data as the physical address translation corresponding to the first virtual address;
• comparing the second target tag to the second candidate tag;
• if the second target tag matches the second candidate tag, providing the second candidate data as the physical address translation corresponding to the first virtual address,
• wherein the translation storage buffer is comprised of sub translation storage buffers, each sub translation storage buffer corresponding to a page size of the first and second page sizes and is comprised of a positive integral power of two translation table entries and each translation table entry is M words in size where M is a positive integer, the step of calculating the first and second pointers includes the steps of:
• forming a first translation storage buffer index by extracting N1 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size where N1 is the base two logarithm of the number of translation-table entries of the sub translation storage buffer corresponding to the first page size;
• adding the product of the first translation storage buffer index and M to a first base address to form the first pointer;
• forming a second translation storage buffer index by extracting N2 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the second page size where N2 is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the second page size;
• and
• adding the product of the second translation storage buffer index and M to a second base address to form the second pointer.

An apparatus for translating a first virtual address to a physical address, the apparatus comprising:

• a receiver adapted to receiving the first virtual address, the virtual address comprising a virtual page offset and a virtual page number, the first virtual address being mapped by an unknown page size, the unknown page size being a first or second page size, the first page size not equal to the second page size;
• a calculator adapted to calculating first and second pointers into a translation storage buffer, the calculator coupled to the receiver, the first pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the first page size, the first pointer pointing to a first candidate translation table entry of the translation storage buffers, the first candidate translation table entry comprising a first candidate tag and first candidate data, the first candidate tag identifying a first particular virtual address and the first candidate data identifying a first particular physical address corresponding to the first particular virtual address, the second pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the second page size, the second pointer pointing to a second candidate translation table entry of the translation storage buffer, the second candidate translation table entry comprising a second candidate tag and second candidate data, the second candidate tag identifying a second particular virtual address and the second candidate data identifying a second particular physical address corresponding to the second particular virtual address;
• an extractor adapted to extracting first and second virtual address target tags from the first virtual address, the extractor coupled to the receiver, the first virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the first page size, the second virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the second page size;
• a first comparator coupled to the calculator and the extractor, the first comparator adapted to comparing the first target tag to the first candidate tag;
• a first provider coupled to the first comparator, the first provider adapted to providing the first candidate data as the physical address translation corresponding to the first virtual address if the first target tag matches the first candidate tag;
• a second comparator coupled to the calculator and the extractor, the second comparator adapted to comparing the second target tag to the second candidate tag;
• a second provider coupled to the second comparator, the second provider adapted to providing the second candidate data as the physical address translation corresponding to the first virtual address if the second target tag matches the second candidate tag,
• wherein the translation storage buffer is comprised of sub translation storage buffers, each sub translation storage buffer corresponds to a page size of the first and second page sizes and is comprised of an integral power of two translation table entries and each translation table entry is M words in size where M is a positive integer, the calculator comprising:
• a first indexer adapted to forming a first translation storage buffer index by extracting N1 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size where N1 is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the first page size;
• a first pointer calculator adapted to adding the product of the first translation storage buffer index and M to a first base address to form the first pointer;
• a second indexer adapted to forming a second translation storage buffer index by extracting N2 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the second page size where N2 is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the second page size;
• and
• a second pointer calculator adapted to adding the product of the second translation storage buffer index and M to a second base address to form the second pointer.