Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-08-26
2002-09-10
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S138000, C711S154000, C712S205000
Reexamination Certificate
active
06449698
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
The present invention provides a method and system for bypassing a prefetch data path. Each transaction within a system is tagged, and as transactions are issued for retrieving data, the system has a data prefetch unit for prefetching data from a processor, a memory subsystem, or an I/O agent into a prefetch data buffer. A prefetch data buffer entry is allocated for a data prefetch transaction, and the data prefetch transaction is issued. While the prefetch transaction is pending, a read transaction is received from a transaction requestor. The address for the read transaction is compared with the addresses of the pending data prefetch transactions, and in response to an address match, the prefetch data buffer entry for the matching prefetch transaction is checked to determine whether data has been received for the data prefetch transaction. In response to a determination that data has not been received for the data prefetch transaction, the prefetch data buffer entry is deallocated, and the transaction tag for the data prefetch transaction is stored in a table for bypassing a prefetch data path. When data for a data prefetch transaction is received, its transaction tag is compared with transaction tags in the table for bypassing the prefetch data path, and in response to a transaction tag match, the received data is sent to the transaction requestor.
REFERENCES:
patent: 5257359 (1993-10-01), Blasco et al.
patent: 5357618 (1994-10-01), Mirza et al.
patent: 5659712 (1997-08-01), Divivier et al.
patent: 5680564 (1997-10-01), Divivier et al.
patent: 6311260 (2001-10-01), Stone 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
Reddy Praveen S.
Chace Christian P.
Kim Matthew
Salys Casimer K.
Yee Duke W.
LandOfFree
Method and system for bypass prefetch data path 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 bypass prefetch data path, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for bypass prefetch data path will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896116