System and method for hierarchical approximation of least...

Details System and method for hierarchical approximation of least... System and method for hierarchical approximation of least...

2006-01-10

2006-01-10

Sparks, Donald (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S113000, C711S128000, C711S130000, C711S134000, C711S135000, C711S136000

Reexamination Certificate

active

06986001

ABSTRACT:
A system for approximating a least recently used (LRU) algorithm for memory replacement in a cache memory. In one system example, the cache memory comprises memory blocks allocated into sets of N memory blocks. The N memory blocks are allocated as M super-ways of N/M memory blocks where N is greater than M. An index identifies the set of N memory blocks. A super-way hit/replacement tracking state machine tracks hits and replacements to each super-way and maintains state corresponding to an order of hits and replacements for each super-way where the super-ways are ordered from the MRU to the LRU. Storage for the state bits is associated with each index entry where the state bits include code bits associated with a memory block to be replaced within a LRU super-way. LRU logic is coupled to the super-way hit/replacement tracking state machine to select an LRU super-way as a function of the super-way hit and replacement history. Block selection logic then selects a memory block to be replaced within the LRU super-way as a function of predefined selection criteria.

REFERENCES:
patent: 5325504 (1994-06-01), Tipley et al.
patent: 5509135 (1996-04-01), Steely, Jr.
patent: 5568632 (1996-10-01), Nelson
patent: 5900011 (1999-05-01), Saulsbury et al.
patent: 6594728 (2003-07-01), Yeager
patent: 2003/0084247 (2003-05-01), Song et al.
Sherwood et al., Jun. 30-Jul 4, 2001, pp. 86-97.

Affiliated with

Also associated with

Rating

System and method for hierarchical approximation of least... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for hierarchical approximation of least..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for hierarchical approximation of least... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3601426