Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2002-12-13
2003-09-23
Verbrugge, Kevin (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S133000
Reexamination Certificate
active
06625695
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of computers and computer systems. More particularly, the present invention relates to a cache line replacement policy to avoid memory page thrashing.
BACKGROUND OF THE INVENTION
Since the beginning of computing, processors have been faster than memories. Even though memory technology has evolved and improved over time, so has processor technology. What this means is that processors often have to remain idle for substantial amounts of time while waiting for the memory to respond to a memory request. As a result, system performance can be negatively impacted.
Computer systems have evolved to include memory hierarchies comprising various types of long term storage, main memory, and caches. However, as one moves down the down the memory hierarchy from caches to long term storage, device access times increase dramatically. An ideal solution is to have enough cache memory or fast main memory available to service the currently executing program. But in most systems, such memory is present in only limited amounts or the program demands more memory than is available.
Caches are generally used to keep often used or recently used data close to or within the processor. The idea is that by storing recently used data in close proximity to the processor, the next time a memory request is made for that particular data, a long memory access to main memory or the hard disk drive is not necessary. When a computer starts up, the cache is empty. But over time, the cache continues to fill up until there are no longer any empty entries for new data. This is not a problem as long as invalid entries are available for replacement. But if all existing entries are valid, the cache replacement logic must delete valid entries to make room for incoming data.
In an efficiently designed computer system, the chipset needs to return requested data to the processor with minimum latency in order to provide maximum system performance. A number of factors can influence this latency, including overall system loading and the memory technology deployed. One factor that can become significant is the specific interaction between transactions that are closely related by the time that they are issued to the processor bus. When these transactions cause a conflict or “page miss” in the memory system, read latency seen by the processor can increase dramatically. The impact of these conflicts is often minimized by the inherent randomness of transaction requests. However, certain application access patterns can cause pathological cases where every access is impacted by these page miss cases.
Some of these conflicts are inevitable, as operating system, application, and chipset design details can interact in ways to create vicious cases. On the other hand, a substantial class of conflicts can arise simply from an interaction between the way in which memory controllers are designed and the way in which processor caches are designed. These conflicts can have a significant impact on processor and overall system performance.
REFERENCES:
patent: 5442571 (1995-08-01), Sites
patent: 5630097 (1997-05-01), Orbits et al.
patent: 5752069 (1998-05-01), Roberts et al.
patent: 5752261 (1998-05-01), Cochcroft, Jr.
patent: 6434671 (2002-08-01), Chung
United States Patent Application Publication, “Chung”, Publication Date Aug. 2, 2001 US 2001/0011328 A1.
United States Patent Application Publication, “Morikawa et al.”, Publication Date Oct. 18, 2001 US 2001/0032297 A1.
United States Patent Application Publication, “Chauvel et al.”, Publication Date May 30, 2002 US 2002/0065992 A1.
Lam Peter
Verbrugge Kevin
LandOfFree
Cache line replacement policy enhancement to avoid memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache line replacement policy enhancement to avoid memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache line replacement policy enhancement to avoid memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3090460