Page address translation cache replacement algorithm with improved testability
First Claim
1. In a memory management unit which translates each of a plurality of logical addresses into a corresponding physical address using a respective one of a plurality of resident logical-to-physical translation descriptors, during a translation cycle, and which retrieves a replacement descriptor from an external memory, during a replacement cycle, a replacement method for determining which of said plurality of resident logical-to-physical translation descriptors to replace comprising the steps of:
- shifting a single data bit through a circular shift register, in response to a shift clock signal, when a valid bit contained in a first one of said translation descriptors is a first logic value, thereby advancing a shift register pointer from said first one of said plurality of translation descriptors to a next one of said plurality of translation descriptors, after each translation cycle;
reading said valid bit contained in said next one of said plurality of translation descriptors, and shifting said shift register pointer to a subsequent one of said plurality of translation descriptors, if said valid bit of said next one of said plurality of translation descriptors is said first logic value;
disabling advancement of said circular shift register pointer if any of the following conditions occur;
said circular shift register pointer points to an invalid translation descriptor, wherein said valid bit is a second logic value;
orsaid circular shift register pointer points to a valid translation descriptor and an address translation miss occurs in said memory management unit;
whereby if said address translation miss occurs when said circular shift register pointer is disabled, said replacement descriptor replaces said invalid translation descriptor pointed to by said circular shift register pointer, and if said address translation miss occurs while said circular shift register pointer is enabled then said replacement descriptor replaces said valid translation descriptor pointed to by said shift register pointer.
1 Assignment
0 Petitions
Accused Products
Abstract
A replacement method is provided for improving the hit rate and testability of a page address translation cache (PATC). The replacement scheme uses a modified FIFO replacement algorithm. A circular shift register has a pointer which points to each of a predetermined number of translation descriptors stored in the PATC. The shift register pointer has an input for receiving the logic state of a valid bit associated with each of the translation descriptors stored in the PATC. The shift register is advanced after every translation cycle, until the logic state of the valid bit indicates that the denoted translation descriptor is invalid, or until a read/write control signal indicates a PATC write is in progress. Upon detecting an invalid translation descriptor, the circular shift register is disabled, and remains disabled until an address translation "miss" occurs, and a replacement entry is loaded into the PATC. If, however, an address translation miss occurs while the circular shift register is enabled (i.e. before an invalid descriptor is located, or when all descriptors are valid), then the translation descriptor the shift register points to is replaced by a new valid translation descriptor.
49 Citations
12 Claims
-
1. In a memory management unit which translates each of a plurality of logical addresses into a corresponding physical address using a respective one of a plurality of resident logical-to-physical translation descriptors, during a translation cycle, and which retrieves a replacement descriptor from an external memory, during a replacement cycle, a replacement method for determining which of said plurality of resident logical-to-physical translation descriptors to replace comprising the steps of:
-
shifting a single data bit through a circular shift register, in response to a shift clock signal, when a valid bit contained in a first one of said translation descriptors is a first logic value, thereby advancing a shift register pointer from said first one of said plurality of translation descriptors to a next one of said plurality of translation descriptors, after each translation cycle; reading said valid bit contained in said next one of said plurality of translation descriptors, and shifting said shift register pointer to a subsequent one of said plurality of translation descriptors, if said valid bit of said next one of said plurality of translation descriptors is said first logic value; disabling advancement of said circular shift register pointer if any of the following conditions occur; said circular shift register pointer points to an invalid translation descriptor, wherein said valid bit is a second logic value;
orsaid circular shift register pointer points to a valid translation descriptor and an address translation miss occurs in said memory management unit; whereby if said address translation miss occurs when said circular shift register pointer is disabled, said replacement descriptor replaces said invalid translation descriptor pointed to by said circular shift register pointer, and if said address translation miss occurs while said circular shift register pointer is enabled then said replacement descriptor replaces said valid translation descriptor pointed to by said shift register pointer. - View Dependent Claims (2, 3)
-
-
4. In a memory management unit having means for translating each of a plurality of logical addresses into a corresponding physical address using a respective one of a plurality of resident logical-to-physical translation descriptors, during a translation cycle, and for retrieving a replacement descriptor from an external memory, during a replacement cycle, a circuit for determining which one of said plurality of resident logical-to-physical translation descriptors is replaced by said replacement descriptor, said circuit comprising:
-
first means for shifting a single data bit through n-stages of a circular shift register, in response to a shift clock signal, when a valid bit contained in a first one of said translation descriptors is a first logic value thereby simultaneously advancing a shift register pointer from said first one of said plurality of translation descriptors to a next one of said plurality of translation descriptors, after each translation cycle; second means for reading said valid bit contained in said next one of said plurality of translation descriptors, and for advancing said circular shift register pointer to a subsequent translation descriptor, if said valid bit of said next one of said plurality of translation descriptors is said first logic value; and third means for disabling advancement of said shift register if any of the following conditions occur; said circular shift register pointer points to an invalid translation descriptor, wherein said valid bit is a second logic value;
orsaid circular shift register pointer points to a valid translation descriptor and an address translation miss occurs in said memory management unit; wherein if said address translation miss occurs when said circular shift register is disabled, said replacement descriptor replaces said invalid translation descriptor pointed to by said circular shift register pointer, and if said address translation miss occurs while said shift register is enabled then said replacement descriptor replaces said valid translation descriptor pointed to by said circular shift register pointer. - View Dependent Claims (5, 6, 7, 8, 9)
-
-
10. In a memory management unit having means for translating each of a plurality of logical addresses into a corresponding physical address using a respective one of a plurality of resident logical-to-physical translation descriptors, during a translation cycle, and for retrieving a replacement descriptor from an external memory, during a replacement cycle, a circuit for determining which one of said plurality of resident logical-to-physical translation descriptors is replaced by said replacement descriptor, said circuit comprising:
-
first means for shifting a single data bit through n-stages of a circular shift register, in response to a shift clock signal, when a valid bit contained in a first one of said translation descriptors is a first logic value, thereby simultaneously advancing a shift register pointer from said first one of said plurality of translation descriptors to a next one of said plurality of translation descriptors, said first means comprising an n-bit circular shift register, wherein a first bit of said n-bits is set to a logic "1" value, in response to an initialization signal, and said logic "1" is shifted through said circular shift register after, each translation cycle, and provided as an output, said output being coupled to an input to said circular shift register; selection logic means coupled to each bit of said n-bit circular register, said selection logic means pointing to said first translation descriptor, in response to said initialization signal, and said selection logic means reading a valid bit contained in said first translation entry, and advancing said shift register pointer to a subsequent translation descriptor, after said translation cycle, if said valid bit of said first translation descriptor indicates is a first logic value; and enable means coupled to said first means and said selection logic means for enabling advancement of said shift register pointer until said selection logic means detects an invalid translation descriptor or an address translation miss occurs;
whereby if said address translation miss occurs when said first means is disabled, said replacement descriptors replaces said invalid translation descriptor pointed to by said circular shift register pointer, and if said address translation miss occurs while said first means is enabled then said replacement descriptor replaces a valid translation descriptor pointed to by said circular shift register pointer. - View Dependent Claims (11, 12)
-
Specification