Electrical computers and digital processing systems: memory – Address formation – Generating prefetch – look-ahead – jump – or predictive address
Reexamination Certificate
2000-04-29
2004-04-06
Nguyen, T. V. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Generating prefetch, look-ahead, jump, or predictive address
C711S118000, C711S137000, C711S204000
Reexamination Certificate
active
06718454
ABSTRACT:
BACKGROUND
In a multiprocessor system, problems arise when more than one processor attempts to access a memory location. While multiple processors have access to a common memory location, if one of those processors attempts to update the information in the memory location without informing the other processors also having access to the memory location, mismatches may occur resulting in a loss of data coherency. This is of particular concern in multiprocessor systems having memory cache associated with each processor, i.e., processor cache. The processor cache stores information most recently accessed by the processor. Processor cache is typically organized out into cache lines of, for example, 64 bits of data. Therefore, when a processor attempts to access a memory location, it first searches its cache to determine if it already has a copy of the information stored in that memory location. If the memory location is not currently stored in the processor cache, the processor attempts to obtain a copy of that memory location from the main memory. Alternatively, if the memory location is already available in the processor cache and is valid, the processor can immediately use the copy of data stored in the cache. Of course, conflict issues arise when multiple processors attempt to access the same memory location.
Regardless of the protocol used, the job of a cache coherency protocol is to make sure that if any caches in a system (especially cache between a processor and a memory or between system input and output in a memory and a processor) has exclusive use of the line, no other cache has a copy of the same exclusive line. Cache coherency protocol can be implemented by processors or by memory.
As previously described, when a processor requires access to a memory location, it first checks its processor cache to determine if the information is available locally. If the information is not present or is invalid, the processor must access the main memory to retrieve the data. This access methodology is not limited to processors. Other devices such as printers which require access to memory may also store data locally or access the main memory. Such a system and method is described, for example, in U.S. Pat. No. 5,829,042 entitled “Prefetch Operation for Network Peripheral Device Having Shared Memory” of Leung and incorporated herein by reference in its entirety. When devices use input/output (I/O) subsystems to access the memory, mismatches between device speed and I/O subsystem speeds can slow the device's access to the memory. The I/O subsystems often have longer memory latency times than that of processors in other devices and often have different access patterns. I/O subsystem transfers tend to be long bursts of data that are linear and sequential in fashion. Prefetch data techniques allow I/O subsystems to request information stored in memory prior to the device's need for that information. By prefetching data ahead of data consumption by the device, data can be continuously sent to the device without interruption thereby enhancing I/O system performance. For example, the amount of time necessary for I/O subsystems to access the memory is called the memory latency. To maximize the efficiency of the device the amount of information which is prefetched is determined by the speed of the device relative to the memory latency. Faster devices benefit from the larger amount of prefetched data (also called deeper prefetches) particularly when memory latency is high. Thus, the information required by the device is retrieved from memory before the device requires the information. This occurs because the prefetch operation requests the data before the device requests the data and allows more time for the memory information to be accessed and provide the data in anticipation of the upcoming request.
However, by their nature prefetch operations are speculative. In other words, since the device has not requested the specific memory location, a prefetch operation anticipates the data that the device will require before it has been requested. Typically a state machine is used to access the information requested by the device. This state machine is also used to prefetch data speculatively. Thus, the speculative prefetch activity consumes resources and time that could be used for fetching data that has been requested by the device. If the data which is speculatively accessed by the prefetched operation is not used, time has been wasted and overall input/output speed has been reduced.
Analogous to the processor's check for the processor cache for requested information, prefetches are checked for the availability of data once a device has requested the data. When the amount of data contained in the prefetch is increased, the overhead necessary to check the prefetch data for the availability of the requested data is increased. Accordingly, a need exists for a device and method of providing prefetch data that minimizes or eliminates the associated overhead required to check the information once a device has requested access to memory. Additionally, a need exists for a prefetch operation that does not compete or interfere with a device's request for access to a memory location.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method which according to one aspect of the invention, a data processing system includes a memory storing data to be retrieved and an I/O controller configured to request data stored in the memory at a plurality of addresses. The I/O may be responsive to an internal or external device requesting such data. A fetch machine provides or initiates retrieval of data stored at the requested address, while a prefetch machine predicts future requests and keeps track of memory requests already initiated and queued. Thus, the prefetch machine is responsive to the plurality addresses to predict others of the addresses and provide or initiate retrieval of data stored thereat. To avoid prefetching information already requested and in a to fetch queue, the prefetch machine includes a memory storing a last one of the addresses subject to prefetching. Finally, to avoid conflicts between currently requested data and prefetch operation, an arbiter resolves memory accesses or data requests initiated by the fetch and prefetch machines.
According to a feature of the invention, the prefetch machine is responsive to addresses of data already supplied to inhibit an inclusion thereof in prefetching the data stored in the memory.
According to another aspect of the invention, a method of retrieving data from a memory is initiated upon receiving a first address of data to be retrieved. A fetch is initiated of data stored at the first address and a prefetch operation is initiated including predicting a first plurality of additional addresses corresponding to first data expected next to be requested. One or more of the predicted additional addresses are stored, for example the latest one of the addresses used to initiate a data request from memory. A prefetch is initiated of the first data expected next to be requested. The method accommodates a subsequent data request upon receiving a next address of data to be retrieved. If a prefetch of the next requested data has already been initiated, then this data is retrieved and provided to the requester. Otherwise, a new fetch is initiated when this second address is not included among the first data expected next to be addressed. The prefetch mechanism also adjusts to an erroneous prediction as indicated by the request not being within the range of data prefetched. Thus, the prefetch operations include selectively (i) continuing to initiate a prefetch of data stored at addresses predicted to follow the one of the additional addresses when the second address is included among the first data expected next to be requested, and (ii) predicting a revised second plurality of additional addresses corresponding to second data expected next to be requested when the second address is not inc
Ebner Sharon M.
Wickeraad John A.
Hewlett--Packard Development Company, L.P.
Nguyen T. V.
LandOfFree
Systems and methods for prefetch operations to reduce... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for prefetch operations to reduce..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for prefetch operations to reduce... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225433