公开(公告)号：US06408364B1

公开(公告)日：2002-06-18

申请号：US09528041

申请日：2000-03-17

申请人： Teik-Chang Tan ,  Leonel Lozano ,  Benjamin T. Sander

发明人： Teik-Chang Tan ,  Leonel Lozano ,  Benjamin T. Sander

IPC分类号： G06F1200

CPC分类号： G06F12/123

摘要： A least recently used (LRU) cache replacement algorithm is implemented with a set of N pointer registers that point to respective ways of an N-way set of memory blocks. One of the pointer registers is an LRU pointer, pointing to a least recently used way and another of the pointer registers is a most recently used (MRU) pointer, pointing to a most recently used way. For a cache fill operation in which a new memory block is written to one of the N ways, the new memory block is written into the way (wayn), pointed to by the LRU pointer. All the pointers except the MRU pointer are promoted to point to a way pointed to by respective newer neighboring pointers, the newer neighboring pointers being neighbors towards the MRU pointer. The MRU pointer is updated to point to the wayn in which the new memory block was written. For a cache hit in which one of the memory blocks in the set, waym, is accessed for a write or read operation, all the pointers waym and newer, except for the MRU pointer, are promoted to point to a way pointed to by a newer neighboring pointer. The MRU pointer is changed to point to waym. For an invalidate operation in which one of the ways, wayk is invalidated, all the pointers pointing to wayk and older are demoted, except for the LRU pointer. The LRU pointer is pointed to the invalidated way.

摘要翻译： 使用指向N路存储器块集合的各个方式的一组N个指针寄存器来实现最近最少使用（LRU）高速缓存替换算法。 指针寄存器之一是LRU指针，指向最近最少使用的方式，另一个指针寄存器是最近使用的（MRU）指针，指向最近使用的方式。 对于其中将新的存储器块写入N个路径中的一个的高速缓存填充操作，新的存储器块被写入由LRU指针指向的方式（wayn）。 除了MRU指针之外的所有指针被提升以指向相应较新的相邻指针指向的方式，较新的相邻指针是朝向MRU指针的邻居。 更新MRU指针以指向写入新内存块的方式。 对于缓存命中，其中访问集合（waym）中的一个存储器块用于写入或读取操作，除了MRU指针之外，所有指向waym和更新的指针都被提升为指向一个 较新的相邻指针 MRU指针更改为指向waym。 对于无效操作，其中一种方式，wayk无效，除了LRU指针之外，所有指向wayk和old的指针都将被降级。 LRU指针指向无效的方式。