Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-08-26
2001-11-13
Ellis, Kevin L. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S213000
Reexamination Certificate
active
06317811
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to an improved data processing system and, in particular, to a method and system for improving data throughput within a data processing system. Specifically, the present invention relates to a method and system for improving performance of storage access and control using prefetch.
2. Description of Related Art
Rapid advances in integrated circuit technology and in computer architecture have resulted in an increasing “memory reference delay gap” between relatively fast processing units and relatively slow memory. High performance processors with high throughput are available as commercial products, and multiprocessor systems using these processors are also available. However, in order to run at their peak speeds, these high performance systems require memory systems that are able to send data to the processor as fast as the processor requires, otherwise the processor stalls while it is waiting for data to be delivered. Such memory systems may be complex and/or expensive. As a result, the performance bottleneck of many current high performance computer systems is not the speed of the processor but rather the efficiency of the memory system.
In order to overcome the problem of an increasingly large memory reference delay gap between fast processing units and slow memory, cache or buffer memories are used. Buffer memory is a small, high speed memory between a processor or processors and a memory subsystem of a computer system. Its primary purpose is to provide high speed data/instruction accesses without the associated cost of an entire memory that uses high speed technology. This is achieved by keeping data and/or instructions that are expected to be referenced in the near future in the buffer.
When the required data for a requested memory transaction exists in the buffer, a “buffer hit” is said to occur, and the required data does not need to be fetched from slower, main memory. In contrast, when the required data for a requested memory transaction does not exist in the buffer, a “buffer miss” is said to occur, and the required data must be fetched from slower, main memory. Buffer misses are problematic because the amount of data that can be processed is limited to the speed at which data can be fetched from main memory. In general, system designers attempt to improve the buffer hit ratio so that the number of buffer misses are reduced and better performance can be obtained. As used herein, the term “buffer hit ratio” is defined as the probability that a data item requested by a processor unit will be found in the buffer, and the “buffer miss penalty” is defined as the time that the processing unit is required to wait for the requested data item to arrive when a buffer miss occurs.
In current buffer designs, instruction buffers are usually given a higher priority than data buffers for implementation and optimization. This is due to the current level of understanding of instruction reference behavior and data reference behavior and to the accuracy of current buffer models for instructions and for data. Since instruction references have a strong sequential reference characteristic, the prior art teaches a technique known as prefetching in which references are brought into the buffer memory before they are actually needed. If the prefetching is correct, memory reference delay times can be overlapped with program execution, at least partially overlapped and preferably completely overlapped. For non-sequential instruction references due to branch or jump instructions, “branch target prediction” may be used to predict the manner in which a program may execute. Together with the buffer prefetching technique, the number of buffer misses can be reduced if the prediction is correct.
Data reference behavior is generally considered random compared to instruction reference behavior. As a result, those buffering techniques that can improve instruction buffer performance might become ineffective when they are applied to data buffer performance. Since data reference behavior has been much less predictable than instruction reference behavior, buffer space may be wasted to store prefetched, non-referenced data, and data items in the buffer that are going to be referenced shortly might be replaced by non-referenced data. Branch technique prediction and the use of a branch target buffer are not applicable to data buffers as the distinction of branch references from sequential references in instruction references is not applicable to data references. Thus, it is much more difficult to improve the performance of data buffer designs than the performance of instruction buffer designs.
Therefore, it would be advantageous to have a method and system for improving the efficiency of a data buffer. It would be further advantageous to have a method and system for improving the efficiency of a data buffer through the use of enhanced buffer prefetching techniques.
SUMMARY OF THE INVENTION
A method and system for reissuing load requests in a multi-stream prefetch engine of a data processing system is provided. A read transaction is received from a transaction requester, and the read transaction has a base address and a prefetch stream identifier. The received read transaction is issued to a prefetch stream associated with a data prefetch buffer identified by the prefetch stream identifier as the prefetch stream is one of a set of prefetch streams, each of which has an associated prefetch buffer. The read transaction is issued to a prefetch stream associated with a data prefetch buffer, and a set of prefetch addresses are generated, each prefetch address in the set of prefetch addresses being proximate to the base address. A determination is made as to whether the data prefetch buffer has unallocated prefetch buffer entries, and a comparison is made between each prefetch address in the set of prefetch addresses and all prefetch addresses in each data prefetch buffer to determine whether a prefetch address in the set of prefetch addresses collides with a prefetch address in a data prefetch buffer. In response to a determination of an absence of an address collision and a determination that the data prefetch buffer does not have an unallocated prefetch buffer entry, the base address is held for data prefetch reissuance.
REFERENCES:
patent: 5317718 (1994-05-01), Jouppi
patent: 5452418 (1995-09-01), Tatosian et al.
patent: 5490113 (1996-02-01), Tatosian et al.
patent: 5652858 (1997-07-01), Okada et al.
patent: 5737568 (1998-04-01), Mayfield
patent: 5758119 (1998-05-01), Mayfield
patent: 5761706 (1998-06-01), Kessler et al.
patent: 5958040 (1999-09-01), Jouppi
patent: 6085291 (2000-07-01), Hicks et al.
patent: 6253306 (2001-06-01), Ben-Meir et al.
IBM Technical Disclosure Bulletin; M-Way Set Associative Prefetch/Stream Buffer Design; vol. 40, No. 12, Dec. 1997, pp. 129 -131.
Deshpande Sanjay Raghunath
Mui David
Ellis Kevin L.
International Business Machines - Corporation
Salys Casimer K.
Yee Duke W.
LandOfFree
Method and system for reissuing load requests in a... 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 system for reissuing load requests in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for reissuing load requests in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2577755