Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-03-31
2003-09-23
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S204000, C711S213000
Reexamination Certificate
active
06625696
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to a method and apparatus for adaptively caching data for peripheral devices capable of initiating requests for data from a storage device.
ART BACKGROUND
Computer systems commonly have one or more storage devices, devices requiring large quantities of data from storage devices, and busses that can be used to transfer data from storage devices to other devices. Commonly used storage devices such as dynamic random access memory (DRAM) and various forms of disk drives impose considerable latencies on each access made to either read or write data.
A common approach to overcoming these latencies is the use of a cache system, a smaller, but much faster storage device. Cache systems attempt to reduce latencies when reading data from slower storage devices by reading more data than is necessary to fill a request by a processor. This is based on the assumption that the data requested by the processor at some future time will be among the extra data read by the cache system, and that the cache system will be able to fill that future request for data more quickly.
Cache systems typically intercept requests for data from a storage device, and supply the data if the requested data is stored within the cache. If some or all of the data is not in the cache, then the data not already in the cache is requested from the storage device. In cases where data must be requested from the storage device, the cache system will often request what is often referred to as a “block” of data large enough to fill one or more cache lines of the cache. Where possible, the effects of the latencies of the storage device are often minimized by supplying data needed to fill the original request for data from the storage device at the same time that data is read from the storage device to fill one or more cache lines.
Such cache systems have proven to be effective for processors in many systems due to common patterns in the amount and quantities a processor typically requires in requests for data. However, peripheral devices within a computer system often have very different patterns of access, and often require much larger and highly variable quantities of data when requesting data from a storage device.
SUMMARY OF THE INVENTION
An apparatus and method for predicting quantities of data required by requesting devices in future requests for data from storage devices, in which patterns of quantities requested in past requests for such data are monitored. Predictions are made based on those patterns, then associated with a pattern, and then used to make requests for data from storage devices, and are selectively modified if they prove to be inaccurate.
REFERENCES:
patent: 5146578 (1992-09-01), Zangenehpour
patent: 5778436 (1998-07-01), Kedem et al.
patent: 5815662 (1998-09-01), Ong
patent: 5838945 (1998-11-01), Emberson
patent: 6003115 (1999-12-01), Spear et al.
patent: 6012106 (2000-01-01), Schumann et al.
patent: 6134643 (2000-10-01), Kedem et al.
patent: 6195735 (2001-02-01), Krueger et al.
patent: 6311260 (2001-10-01), Stone et al.
patent: 6321312 (2001-11-01), Davis et al.
patent: 6381554 (2002-04-01), Matsuo et al.
Chen et al., “A Performance Study of Software and Hardware Data Prefetching Schemes,” pp 223-232. IEEE, 1994.*
Saavedra et al., “Improving the Effectiveness of Software Prefetching With Adaptive Execution,” pp 68-78. IEEE, 1996.
Blakely , Sokoloff, Taylor & Zafman LLP
Elmore Stephen
Kim Matthew
LandOfFree
Method and apparatus to adaptively predict data quantities... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus to adaptively predict data quantities..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to adaptively predict data quantities... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3010770