ASSOCIATIVE MAP WITH LEAST RECENTLY USED (LRU) REPLACEMENT

摘要

A least recently used associative map is described for translating virtual memory addresses to real memory addresses. The map includes a stack of storage devices each with a comparator. The storage devices are arranged in a push down stack with an input storage device to receive the incoming virtual address and store the corresponding real address and the other storage devices coupled to the output of the previous higher storage devices and with storage devices storing the translation of virtual address and real address in order of recent use with the last or bottom storage device storing the least recently used address. When the comparator detects a compare that real address is provided out and that translation is applied to the input storage device as the most recently used translation and the other translations are shifted down the stack to replace in the storage device that had the compare with the translation from the previous storage device. If there is not a compare a new translation is entered at the input storage device and the other translations are shifted down with the least recently used being shifted out if the storage devices are full.