Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-02-18
2002-12-03
Robertson, David L. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S206000
Reexamination Certificate
active
06490656
ABSTRACT:
TECHNICAL FIELD
The invention relates to digital electronic circuitry. More particularly, the invention relates to digital electronic circuitry implementing a not-recently-used algorithm.
BACKGROUND ART
Typically, a microprocessor's translation look-aside buffer (TLB) does not contain enough entries to map all currently active virtual addresses to their corresponding physical addresses. Instead, the TLB attempts to cache those mappings which are most likely to be used in the near future. When a memory reference misses the TLB and must install a new TLB entry, the TLB must choose which existing entry should be replaced. The system will have fewer total TLB misses (and therefore higher performance) if the TLB always replaces those entries which will not be referenced for the longest time into the future.
Unfortunately, since the TLB cannot know a program's future behavior, its best guess usually comes from the program's recent history. One method which typically exhibits very good behavior is the least-recently-used (LRU) method, in which enough status information is stored so that the TLB always knows which entry was referenced the least recently. By extrapolation, that entry will probably not need to be referenced for the longest time into the future, and so is the best candidate for replacement. However, the LRU method's complexity and storage requirements grow even faster than the number of entries in the TLB; so for large TLBs, the LRU method's cost can be prohibitive.
Other solutions have been devised which are nearly as effective as the LRU method, but have significantly less cost. One such method is the not-recently-used (NRU) method, in which only one bit of status is kept for each TLB entry. When an entry is referenced, it is marked recently used. When all of the TLB entries have been marked recently used, they are all again reset to the not-recently-used state. When a replacement is needed, any one of the not-recently-used entries may be chosen. This method is simpler than the LRU method, its complexity grows only linearly with the size of the TLB, and it typically has good performance. However, searching for a replacement choice across all of the TLB entries can still be difficult in a large TLB. Also, all history is lost whenever all of the entries become recently used, and poor replacement choices (entries very recently used, or even just newly inserted) may be made at those times. This not only has a negative impact on system performance, but can also (in extreme situations) prevent forward progress.
SUMMARY OF INVENTION
In one respect, the invention is a method for improving state information retention when selecting a not-recently-used element in an array of N elements. The array may be one dimensional or multidimensional. The method comprises the steps of subdividing the array of N elements into K groups, selecting a group from among the K groups, selecting an element that is set to a not-recently-used state from the elements in the selected group, and marking the selected element as recently-used. If all the elements in the selected group are marked as recently-used, the method preferably marks all the elements in the selected group, except the selected element, as not-recently-used. Alternately, the method simply marks all the elements in the selected group when all the elements in the selected group are marked as recently-used. The method also preferably cycles through the groups so that a different group is selected each time.
In another respect, the invention is a method which comprises the steps of selecting an element that is marked as not-recently-used from the elements in the array, marking the selected element as recently-used and marking all the elements in the array except the selected element as not-recently-used when all the elements in the array are marked as recently-used.
In yet another respect, the invention is a computer readable medium on which is embedded a program. The embedded program comprises components that execute the above methods.
Those skilled in the art will appreciate these and other advantages and benefits of various embodiments of the invention upon reading the following detailed description of a preferred embodiment with reference to the below-listed drawings.
REFERENCES:
patent: 5539892 (1996-07-01), Reininger et al.
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 5860147 (1999-01-01), Gochman et al.
Wolfe, A., “Patents shed light on Merced's Innards”, Electronic Engineering Times, Feb. 15, 1999.
Hewlett--Packard Company
Robertson David L.
LandOfFree
Retaining state information of an array of elements by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Retaining state information of an array of elements by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Retaining state information of an array of elements by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2966020