Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2002-08-20
2004-09-07
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S213000, C711S217000
Reexamination Certificate
active
06789171
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention relates to memory accesses in computer systems, and more particularly to memory read ahead operations within computer systems.
2. Description of the Related Art
Computer systems often include various mechanisms to enhance the speed of processing. Not only is the speed of the processor itself important, but storage performance may be equally important to enhancing the overall processing speed of a computer system. Storage performance may involve accesses to cache memory, main memory, and/or secondary memory such as disk, optical drives, etc.
The expanding gap between processor speed and storage speed has furthered the need to develop techniques designed to reduce or mitigate the amount of time it takes to complete file accesses. One technique known as file prefetching or file read-ahead reduces file access time by transferring data from secondary memory such as a disk to the computer system's main memory before the data is actually requested by an application. If data is correctly prefetched into the computer system's main memory, overall latencies may be reduced since execution of the application need not wait on the transfers to main memory from secondary storage.
Various systems have been proposed that perform operations to prefetch blocks of data in anticipation that the block may be later requested by the application. For example, one simple file read-ahead mechanism prefetches sequential blocks of data based on the assumption that file blocks will be accessed sequentially. While such mechanisms have generally been successful in improving overall performance for applications that regularly perform sequential accesses, overall performance may not be improved (and may in fact be degraded) for applications in which blocks of a file are regularly accessed on a non-sequential basis.
Other mechanisms have therefore been developed that attempt to prefetch data on a non-sequential basis by searching for distinct file usage patterns and exploiting such detected patterns. For example, various stride-based read-ahead mechanisms are known that detect a pattern of regularly spaced, non-sequential accesses and that prefetch blocks of data based upon such strided accesses. A stride-based read-ahead mechanism may, for instance, detect a set of consecutive single block accesses to block locations
3
,
5
and then
7
of a given file. When such an access pattern is detected, the mechanism may prefetch block
9
(and possibly additional blocks consistent with the pattern such as blocks
11
,
13
and so on). Prefetching on this basis continues until a file request is received that falls outside of the pattern. In this manner, for as long as file requests are performed in accordance with the detected stride pattern, the needed blocks may have already been prefetched into the system's main memory. Accordingly, overall latency in fulfilling a request from the time when it is initiated by an application may be reduced.
Implementations of stride-based read-ahead mechanisms may be somewhat more complicated in multi-threaded systems. In multi-threaded systems, requests from multiple threads may be received in an overlapping fashion by the file system. Thus, although each thread may be performing requests according to a respective, independent stride pattern, when the requests are combined and viewed as a whole, the respective stride pattern of each thread may be obscured. Additionally, the requests of the different threads may interfere with one another in such a manner that a stride pattern may be erroneously detected (i.e., it may appear to the detection mechanism that a thread is performing strided accesses, when in fact, no such strided access pattern is occurring).
Therefore, to correctly identify stride based patters in the requests of differing threads, some systems store a history of file requests to determine which requests correspond to a strided pattern. Such implementations may be somewhat computationally intensive and may require relatively large amounts of storage. Furthermore, such implementations may still be prone to interference between threads.
In addition, while various stride-based read-ahead mechanisms are known that operate upon fixed-size block requests, such mechanisms may not be configured to operate upon requests having variable sizes. Still further, such mechanisms may be incapable of detecting stride patterns formed by a series of sequential accesses, followed by a skip to a non-sequential location, and then another (equal length) series of sequential accesses and an equal skip. In various applications, this form of stride based pattern may be common.
SUMMARY OF THE INVENTION
A computer system and method for implementing a stride prediction read ahead algorithm are disclosed. In one embodiment, a computer system includes a read ahead engine that receives a sequence of read requests and performs read ahead operations in accordance with various patterns detected within the sequence of read requests. The prefetch engine may implement the method of storing a first run value indicative of the run size of a first plurality of sequential read requests, and storing a first skip value indicative of a non-sequential skip associated with a subsequent read request. The method may further include determining whether a second run value indicative of the sequential run size of a second plurality of read requests equals the first run value, and whether a second skip value indicative of another non-sequential skip associated with an additional read request equals the first skip value. If the first run value equals the second run value, and the first skip value equals the second skip value, a stride pattern is indicated, and one or more read ahead operations according to the detected stride pattern may be initiated.
REFERENCES:
patent: 5357618 (1994-10-01), Mirza et al.
patent: 6070230 (2000-05-01), Capps
patent: 6138212 (2000-10-01), Chiacchia et al.
patent: 6275918 (2001-08-01), Burky et al.
patent: 6430680 (2002-08-01), Burky et al.
Parallel-I/O Biblography, Ninth Edition, Feb. 22, 1997.
Colgrove John
Desai Samir
Varadarajan Ganesh
Kim Matthew
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Patel H. B.
Veritas Operating Corporation
LandOfFree
Computer system implementing a multi-threaded stride... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer system implementing a multi-threaded stride..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer system implementing a multi-threaded stride... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220974