Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-05-06
2001-05-01
Yoo, Do Hyun (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S159000, C711S213000, C711S137000, C711S003000
Reexamination Certificate
active
06226715
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a data processing circuit.
BACKGROUND OF THE INVENTION
A cache memory is a well known instrument for bridging the gap between processor speed and main memory speed. Copies of data from main memory are kept in a cache memory, so that to access such copies the processor needs to access only the fast cache memory and not the slow main memory.
U.S. Pat. No. 5,649,144 provides for a cache management unit that prefetches copies of data into the cache before this data is actually read by the processor. The cache management unit makes use of the concept of address streams and prefetches data from the addresses in the streams, either individually or as part of a prefetched block of data. Each stream is described for example by a base address and a stride value, which define a series of addresses obtainable by starting with the base address and incrementing it repeatedly with the stride value. Both the base address and the stride are adjustable; the stride may take values like plus or minus one or plus or minus a larger value.
The idea behind using address streams is that a typical program executed by the processor will contain instructions that read from the addresses defined by the streams. Once data has been accessed at one address from a stream, it may be expected that in the near future the program will need to access data at a new address obtained by adding the stride value to that one address, possibly after reading from other addresses not belonging to the stream. To anticipate the need for data from new addresses the cache management unit prefetches the data from the new address into the cache memory, so that the processor can quickly fetch the data stored at the new address when it is needed.
Between reading one address and the new address from the stream the processor may read from different addresses, which may be part of different streams or unrelated to any stream. The cache management unit keeps track of progress of the execution of the program by the processor and prefetches data from a particular stream each time when the program executed by the processor has advanced so far that it is expected to a new address from the particular stream at short notice.
The cache management unit must also select cache locations for storing any data needed by the processor, which includes both data stored at addresses belonging to the streams and other data. The cache uses a replacement strategy to select cache locations that it makes available for reuse. One popular replacement strategy, for example, is the LRU strategy (Least Recently Used), which selects the cache memory location occupied by the least recently used data item (or block of data).
If a particular cache memory location is made available for reuse then the data previously stored at that particular cache memory location can only be fetched from slow memory. Therefore, the replacement strategy will have an effect on the efficiency of execution of the program and the use of the bus which connects the process or to main memory. The LRU strategy for example may also reduce the efficiency of the processor and bus use in this way.
Amongst others, it is an object of the invention to provide for a data processing circuit according to the preamble in which the processor can use the cache memory more efficiently.
SUMMARY OF THE INVENTION
The data processing circuit according to the invention the address stream is used for selecting cache memory locations that are made available for reuse. When the cache management unit detects that the processor advances a stride along a stream, “old” data in the cache corresponding to that stream is sacrificed for reuse. The cache memory locations may be made available for reuse individually or a block at a time.
Thus the cache memory locations that are made available for reuse are not necessarily the least recently used cache memory locations. For example, when a stream accesses a vast amount of data in quick succession, cache memory locations used for that data may be made available for reuse more quickly than cache memory locations used for other data, which other data is not part of the stream and which other data is used at a much lower frequency than the frequency with which the stream advances. This reduces the number of cache misses if the data from the stream is not accessed after its cache memory location is made available for reuse.
In general dispersed locations in the cache may be made available. For example, when the stride is not plus or minus one, successive locations that are thus made available for use are not adjacent. In principle a cache memory location that is made available for reuse will be generally available: it may be used for the same stream, for another stream or for data which does not belong to any stream.
The technique according to the invention for making cache memory locations available for reuse can be used in combination with any overall replacement strategy for selecting cache memory locations to make them available for reuse (for example if the technique according to the invention does not make sufficient cache memory locations available for reuse for a particular program). Use of the technique according to the invention will reduce the need to use such an overall replacement strategy, because more cache memory locations will be available.
The invention makes the retention of data in the cache dependent on the need of that data in the program. By keeping data for a stream for a specified time it can be promoted that data is not removed from the cache before the program needs that data again. Also, by timely discarding data from a stream when that data is no longer needed, it can be promoted that sufficient space is created for reuse in the cache so that there is less need to remove other data from the cache that may still be used by the processor.
Preferably, the cache management unit keeps data corresponding to a stream in the cache until it is more than a certain number of strides behind the most recently used new address in the stream. Thus, the relation between the cache memory location that is made available for reuse and access to various memory locations is easily adjustable.
When the stride is relatively large, addresses that are very far apart may be kept in cache, whereas if the stride is relatively small, addresses that are quite close to the most recently used address may already be reused. Similarly, if the processor advances relatively infrequently along a stream data from addresses corresponding to that stream may be kept longer than data from addresses corresponding to a stream along which the processor advances relatively frequently.
When the streams are also used for prefetching data, this has the result that data is kept in cache from respective “sliding windows” of addresses, each window belonging to a respective stream.
In an embodiment of the invention, the processor has an instruction for programming the distance over which data is kept in cache independently for each stream. This may be used for example as follows. For a given program it is known how big a surrounding of a local position in a stream is needed for computations, and therefore it can be determined for each stream how much data should be kept in cache for use by the program and at what distance the data can be discarded from the cache. Thus programs can adapt this distance to their needs. The distance may be specified in many ways, for example as a number of strides, or as an address difference; one instruction might specify the distance for one stream, or for several streams etc.
Advancement of the program along a stream may be detected in several ways, for example by detecting whether the processor issues a read instruction with an address corresponding to a next address in the stream, or by explicit instructions in the program, or by detection of execution of an arbitrary instruction located at a specified instruction address. If the addresses in read instructions are used, the instruction handling part of the processor and
Struik Pieter
Van Der Wolf Pieter
Kim Hong
U.S. Philips Corporation
Yoo Do Hyun
LandOfFree
Data processing circuit with cache memory and cache... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing circuit with cache memory and cache..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing circuit with cache memory and cache... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447188