Programmable data prefetch pacing

Details Programmable data prefetch pacing Programmable data prefetch pacing

2001-10-18

2003-06-10

Elmore, Reba I. (Department: 2186)

Electrical computers and digital processing systems: memory

Address formation

Generating prefetch, look-ahead, jump, or predictive address

C711S137000, C711S204000

Reexamination Certificate

active

06578130

ABSTRACT:

BACKGROUND
The continuing development of computer systems has resulted in efforts to increase performance and maximize efficiency of the computer systems. One solution to this problem has been the creation and utilization of cache systems in a computer. The purpose of a cache system is to bring the speed of accessing computer system memory as close as possible to the speed of the central processing unit (CPU) itself. By making instructions and data available to the CPU at a rapid rate, it is possible to increase the performance rate of the processor. A cache system has access time that approaches that of CPU components, and is often 5 to 10 times faster than the access time of main memory components. When the CPU makes a data request, the data can be found in one of the processor caches, main memory, or in a physical storage system (such as a hard disk). Each level consists of progressively slower components. There are usually several levels of cache. The L
1
cache, which usually exists on the CPU, is the smallest in size. The larger L
2
cache (second-level cache) may also be on the CPU or be implemented off the CPU with SRAM. main memory is much larger and consists of DRAM, and the physical storage system is much larger again but is also much, much slower than the other storage areas. Cache memories are fast memory storage devices. A cache system increases the performance of a computer system by predicting what data will be requested next and having that data already stored in the cache, thus speeding execution. The data search begins in the L
1
cache, then moves out to the L
2
cache, then to DRAM, and then to physical storage.
A process known as “prefetching” is known in the art. Prefetching is used to supply memory data to CPU caches ahead of time to reduce microprocessor access time. By fetching data from a slower storage system and placing it in a faster access location, such as the L
1
or L
2
cache, the data can be retrieved more quickly. Ideally, a system would prefetch the data and instructions that will be needed next far enough in advance that a copy of the data that will be needed by the CPU would always be in the L
1
cache when the CPU needed it. However, prefetching involves a speculative retrieval of data that is anticipated to be needed by the microprocessor in subsequent cycles. Data prefetch mechanisms can be software controlled by means of software instructions, or hardware controlled, using pattern detection hardware. Each of these prefetch mechanisms has certain limitations.
Software prefetch mechanisms typically use instructions such as Data Stream Touch (DST) to prefetch a block of data. Once the prefetch is started by the software command, hardware is used to prefetch the entire block of data into the cache. If the block of data fetched is large relative to the size of the L
1
cache, it is probable that data currently being used by the CPU will be displaced from the L
1
cache. The needed displaced lines will have to be refetched by the CPU, resulting in a slower performance. In addition, software prefetch instructions may be used to generate access patterns which do not efficiently use caches when prefetching larger lines, such as 128 bytes. For example, a DST instruction can specify a starting address, a block size (1 to 32 vectors, where a vector is 16 bytes), a number of blocks to prefetch (1 to 256 blocks), and a signed stride in bytes (−32768 to +32768). An access pattern which specifies blocks which span cache lines and are irregularly spaced, relative to the cache lines, will waste cache space. And, due to the sparse use of the data in the cache line, performance will be lowered. Additionally, large amounts of hardware may required to implement the full scope of the software prefetch instruction.
Hardware mechanisms prefetch a stream of data and generally only prefetch as far ahead as the cache and memories require. Because hardware mechanisms detect a stream, the stream logic has to generate enough prefetched to get the designated number of lines ahead of the actual processor accesses. Once the hardware is far enough ahead, the lines are prefetched at the rate at which the processor consumes them. Often, however, especially when a hardware prefetch is first started, several prefetches may be active at once in order to get enough lines ahead of the actual processor accesses. Prefetching of several streams at once can slow processor speed in general, which can slow access to needed data and processing of that data. These problems are increased in a systems that prefetches data from a plurality of L
1
and L
2
caches, as is becoming more common in larger, faster systems having multiple processors.
With either software or hardware prefetch mechanisms, there is always a performance trade off between utilizing cache resources for the prefetches versus CPU intruction or data requests. Therefore, what is needed is a system and method of efficiently utilizing prefetch logic so as to maximize CPU performance.
SUMMARY
The present invention, accordingly, provides a method and apparatus for controlling utilization of resources in a system for prefetching. By controlling the amount of L
2
resources which can be used by prefetch accesses, the amount of CPU resources being used for prefetch requests and responses is kept at a level that does not exceed cache processing and storage abilities.
A method of the present invention involves prefetching data in a data processing system comprising a plurality of L
1
caches and a plurality of L
2
caches to control utilization of resources. The method comprises defining a maximum number of allowable L
2
cache prefetches, and monitoring the actual number of L
2
cache prefetches. When the system receives a request for an L
2
cache prefetch, it determines if the current actual number of L
2
cache prefetches is less than the defined maximum number of allowable L
2
cache prefetches. If the actual number of L
2
cache prefetches is less than the maximum number of allowable L
2
cache prefetches, the system permits prefetching the requested data to the L
2
cache. If the actual number of L
2
cache prefetches is equal to the defined maximum number of allowable L
2
cache prefetches, the system delays prefetching the requested data to the L
2
cache until at least one prefetch already in the cache has been completed.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and the specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.


REFERENCES:
patent: 5758119 (1998-05-01), Mayfield et al.
patent: 6073215 (2000-06-01), Snyder
patent: 6412046 (2002-06-01), Sharma et al.
patent: 6421762 (2002-07-01), Arimilli et al.
patent: 6446167 (2002-09-01), Mayfield et al.
patent: 6460115 (2002-10-01), Kahle et al.

Affiliated with

Also associated with

Rating

Programmable data prefetch pacing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Programmable data prefetch pacing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable data prefetch pacing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3127729