Page address translation cache replacement algorithm with improved

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.