Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-04-14
2003-06-03
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S122000, C711S213000, C712S207000
Reexamination Certificate
active
06574712
ABSTRACT:
TECHNICAL FIELD
The present invention relates in general to data processing systems, and in particular, to a system and method for implementing prefetching of data with respect to a plurality of cache levels.
BACKGROUND INFORMATION
A special very high-speed memory is sometimes used to increase the speed of processing within a data processing system by making current programs and data available to a processor (“CPU”) at a rapid rate. Such a high-speed memory is known as a cache and is sometimes employed in large computer systems to compensate for the speed differential between main memory access time and processor logic. Processor logic is usually faster than main memory access time with a result that processing speed is mostly limited by the speed of main memory. A technique used to compensate for the mismatch in operating speeds is to employ one or more extremely fast, small memory arrays between the CPU and main memory whose access time is close to processor logic propagation delays. It is used to store segments of programs currently being executed in the CPU and temporary data frequently needed in the present calculations. By making programs (instructions) and data available at a rapid rate, it is possible to increase the performance rate of the processor.
Analysis of a large number of programs has shown that the references to memory at any given interval of time tend to be confined within a few localized areas in memory. This phenomenon is known as the property of “locality of reference.” The reason for this property may be understood considering that a typical computer program flows in a straight-line fashion with program loops and subroutine calls encountered frequently. When a program loop is executed, the CPU repeatedly refers to the set of instructions in memory that constitute the loop. Every time a given subroutine is called, its set of instructions are fetched from memory. Thus, loops and subroutines tend to localize the reference to memory for fetching instructions. To a lesser degree, memory references to data also tend to be localized. Table look-up procedures repeatedly refer to that portion in memory where the table is stored. Iterative procedures refer to common memory locations and arrays of numbers are confined within a local portion of memory. The result of all these observations is the locality of reference property, which states that, over a short interval of time, the addresses of instructions generated by a typical program refer to a few localized areas of memory repeatedly while the remainder of memory is accessed relatively infrequently.
If the active portions of the program and data are placed in a fast small memory such as a cache, the average memory access time can be reduced, thus reducing the total execution time of the program. The cache memory access time is less than the access time of main memory often by a factor of five to ten. The cache is the fastest component in the memory hierarchy and approaches the speed of CPU components.
The fundamental idea of cache organization is that by keeping the most frequently accessed instructions and data in one or more fast cache memory arrays, the average memory access time will approach the access time of the cache. Although the cache is only a small fraction of the size of main memory, a large fraction of memory requests will be found in the fast cache memory because of the locality of reference property of programs.
The basic operation of the cache is as follows. When the CPU needs to access memory, the cache is examined. If the word is found in the cache, it is read from the fast memory. If the word addressed by the CPU is not found in the cache, the main memory is accessed to read the word. A block of words containing the one just accessed is then transferred (prefetched) from main memory to cache memory. In this manner, some data is transferred to cache so that future references to memory find the required words in the fast cache memory.
The average memory access time of the computer system can be improved considerably by use of a cache. The performance of cache memory is frequently measured in terms of a quantity called “hit ratio.” When the CPU refers to memory and finds the word in cache, it is said to produce a “hit.” If the word is not found in cache, then it is in main memory and it counts as a “miss.” If the hit ratio is high enough so that most of the time the CPU accesses the cache instead of main memory, the average access time is closer to the access time of the fast cache memory. For example, a computer with cache access time of 10 ns, a main memory access time of 300 ns, and a hit ratio of 0.9 produces an average access time of 39 ns. This is a considerable improvement over a similar computer without a cache memory, whose access time is 300 ns.
In modern microprocessors, the processor cycle time continues to improve with technology evolution. Also, design techniques of speculative execution, deeper pipelines, more execution elements and the like continue to improve the performance of the microprocessor. The improved performance puts a heavier burden on the memory interface since the processors demand more data and instructions from memory to feed the microprocessor. Large on-chip caches (L1 or primary caches) are implemented to help reduce the memory latency, and they are often augmented by larger off-chip caches (L2 or secondary caches or even L3 caches).
Prefetching techniques are often implemented to try to supply memory data to the L1 cache ahead of time to reduce latency. Ideally, a program would prefetch data and instructions far enough in advance that a copy of the memory data would always be in the L1 cache when it was needed by the processor.
One of the problems with existing prefetching mechanisms is that they operate on one cache level or one prefetch buffer. With ever increasing memory latencies associated with increasing processor speeds, a prefetch mechanism that operates on multiple cache levels is required. Therefore, what is need in the art is an improved prefetch mechanism, which alleviates such problems.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing need by providing a centralized hardware prefetch mechanism, which treats the L1, L2, and L3 cache levels as a three-level prefetch buffer, appropriately compensating for the different latencies and block sizes of each cache level. A private prefetching bus is used to carry extra prefetch requests made to the L2 (secondary) cache. The result is that prefetching for the lower memory hierarchy within a multilevel cache system is performed without burdening the data busses with such prefetch traffic.
More specifically, the present invention is implemented in a multiprocessor environment whereby two processor cores share an L2 cache. Each processor core implements a prefetcher mechanism for controlling prefetching of data into the first (L1), second (L2), or third level (L3) caches. Prefetching to the second and third level caches is performed by signaling the second level cache over a private (dedicated) prefetch bus. Such prefetch signaling does not increase the traffic on the fetch busses between the first level cache and the second level cache, since these requests are prefetched to the L2 and L3 cache levels, not the L1 cache. A second processor core would have its own fetch and private prefetch busses. It should be noted, however, that the present invention is not limited to implementation with two processor cores sharing a second level cache, but could be expanded to the sharing of a second level cache by any number of processor cores, including one processor core.
In one embodiment of the present invention, a software instruction is used to override the normal functioning of the hardware prefetch engine to accelerate the prefetching of a stream into the various cache levels. The number of cache lines prefetched is determined by the software instruction so that only the cache lines required are prefetched.
The foregoing has outlined rather broadly the features and technical advantages of the
Kahle James Allan
Mayfield Michael John
O'Connell Francis Patrick
Ray David Scott
Silha Edward John
Bataille Pierre-Miche
International Business Machines - Corporation
Kim Matthew
Kordzik Kelly K.
Salys Casimer K.
LandOfFree
Software prefetch system and method for predetermining... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Software prefetch system and method for predetermining..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software prefetch system and method for predetermining... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3110903