JPH09146835A - System for prefetch of data - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce the waiting time for the fetch of the data from a memory in a microprocessor system. SOLUTION: In a data processing system realizing first-order and second-order caches L1 and L2, a stream filter and a buffer, the prefetch of a cache line is progressively executed. In a first mode, the data is not prefetched. In a second mode, two cache lines are prefetched, and the one line is prefetched in the L1 cache and the next line is prefetched in a stream buffer. In a third mode, three cache lines or more are prefetched one time. The prefetches are possible to be performed for a cache mistake or a hit. The cache mistake in a continuous cache line is capable of assigning the stream of the cache line to a stream buffer.

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION This invention relates generally to data processing systems, and more particularly to systems for prefetching data from memory.

[0002]

2. Description of the Prior Art Special high speed memory is sometimes used to improve the processing speed of a data processing system by making the current program and data available to the processor (CPU) at high speed. Such fast memories are known as caches and are sometimes used in large computer systems to compensate for main memory access times and speed differences between processor logic. Processor logic is typically faster than main memory access time, and processing speed is often limited by main memory speed. One technique for compensating for operating speed inconsistencies is CPU
Between the main memory and the main memory, an ultra-fast small memory whose access time is close to the propagation delay of the processor logic circuit is used.
It is used to store the segment of the program currently executing in the CPU, as well as the temporary data often needed in the current computation. Program (command)
Also, the performance of the processor can be improved by making the data available at high speed.

Analysis of a number of routine programs has revealed that memory references in a given time interval are restricted to a few localized regions in memory. This phenomenon is known as the property of "locality of reference". The reason for this property can be understood by considering that normal computer program flow flows linearly and often encounters program loops and subroutine calls. When the program loop is executed,
The CPU repeatedly refers to the instruction set in the memory forming the loop. Each time a given subroutine is called, its instruction set is fetched from memory. Therefore, loops and subroutines tend to localize memory references for instruction fetches. Memory references to data also tend to be localized to a lesser extent. The table lookup procedure repeatedly references the portion of memory where the table is stored. The iterative procedure references a common memory location and an array of numbers is stored in a local portion of memory. The result of these observations is the locality of reference, which means that in a short time interval, the address of an instruction generated by a normal program repeatedly references some localized areas of memory and the remaining memory areas Indicates that access is relatively rare.

When the active portions of the program and data are located in the fast small memory, the average memory access time is reduced, and thus the total program execution time. Such a high speed small memory is referred to as a cache as described above. Cache memory access times are often five to ten times smaller than main memory access times. The cache is the fastest component in the memory hierarchy, close to the speed of the CPU component.

The basic idea of cache organization is to cache the most frequently accessed instructions and data at high speed.
Saving in memory brings the average memory access time closer to the cache access time.
Although the cache is a small fraction of the size of main memory, the majority of memory requirements are found in fast cache memory because of the locality of reference of the program.

The basic operation of the cache is as follows.
When the CPU needs a memory access, the cache is examined. When a word is found in the cache, it is read from fast memory. If the word addressed by the CPU is not found in the cache, main memory is accessed to read the word. The word block containing the word just accessed is then transferred from main memory to cache memory. In this way, certain data will be transferred to the cache and future memory references will find the required word in the fast cache memory.

The average memory access time of a computer system can be greatly improved by the use of caches. Cache memory performance is often measured by a quantity called the "hit rate". When the CPU references memory and finds a word in cache, this is said to have generated a "hit". If the word is not found in cache, it is in main memory and is counted as a "miss". If the hit rate is high enough that most of the time the CPU accesses the cache instead of main memory, the average access time approaches that of the fast cache memory. For example,
100ns cache access time, 1000ns
A computer with a main memory access time of 1 and a hit rate of 0.9 produces an average access time of 200 ns. This is a great improvement over a similar computer that has no cache memory and its access time is 1000 ns.

In modern microprocessors, processor cycle times continue to improve as technology advances. Also, design techniques such as speculative execution, deep pipelines, and more execution elements continue to improve the performance of microprocessors. The improved performance puts a greater burden on the memory interface. This is because the processor requires more data and instructions to be supplied from memory to the microprocessor. Large on-chip cache (L1 or L1 cache) to reduce memory latency
Are implemented, which are often augmented by larger off-chip caches (secondary or L2 caches).

Prefetching techniques are often implemented to pre-populate memory caches with memory data to reduce latency. Ideally, the program pre-fetches data and instructions well enough so that when the processor needs the memory data, its copy always resides in the primary cache.

The problem is that the microprocessor architecture does not provide sufficient a priori information to explicitly determine the address of the data that may be needed in all cases. For example, the address of a data operand in memory is itself in memory,
It must be fetched by the first instruction used by the memory instruction. In such a sequence, the processor does not have an address in advance to perform prefetch.

Prefetching of instructions and / or data is known. However, existing prefetch techniques often prefetch instructions and / or data prematurely. The problem with prefetching instructions and / or data and not using them is that (1) the prefetched data can replace the data needed by the processor, and (2) prefetch memory access , Subsequent processor cache reloads, which can cause prefetch accesses to wait and increase latency of required data. Both of these effects reduce the efficiency of the CPU. Therefore,
What is needed is an improved system for prefetching that reduces the latency of data and instruction access to the primary cache due to cache misses without degrading the performance of the microprocessor.

[0012]

SUMMARY OF THE INVENTION It is an object of the present invention to use stream filters with primary and secondary caches in a microprocessor to provide prefetch data from memory and wait for data in a microprocessor system. It is to reduce the time.

Another object of the present invention is to provide a unique stream filter device capable of simultaneously supporting multiple streams and gradually incrementing the prefetch data to control the prefetch depth.

[0014]

The foregoing description fairly broadly describes the features and technical advantages of the present invention, so that the details of the invention described below will be better understood, and the addition of the present invention The features and advantages of will be described in detail below.

[0015]

DETAILED DESCRIPTION OF THE INVENTION In the following description, numerous specific details are set forth, eg, specific word lengths or byte lengths, in order to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without these specific details. In other instances, known circuits are shown in block diagram form in order not to obscure the present invention with unnecessary details. For the most part, details such as timing are not necessary to an understanding of the invention,
It is omitted as long as it is known to those skilled in the art.

Throughout the drawings, the elements shown are not necessarily to scale, and identical or similar elements are designated by the same reference numbers.

Referring to FIG. 1, a data processing system 100 that advantageously implements the present invention will be described. The multiprocessor system 100 includes a plurality of processing units 106, 108, operatively connected to a system bus 124.
Including 110. Any number of processing units can be used in system 1
00 can be used. Also connected to the system bus 124 is a memory controller 104 that controls access to the system memory 102. The memory controller 104 is also connected to the I / O controller 126, and the I / O controller 126 is connected to the I / O device 128. Processing units 106, 108, 110, I / O control device 12
6, and I / O device 128 are all referred to herein as bus devices. As shown, each processing unit 10
6, 108, 110 may include a processor and L1 (primary) cache 112, 114, 116, respectively.
The L1 cache may be located on the same chip as each processor. Processing units 106, 108, 11
0 to L2 (secondary) caches 118 and 12 respectively.
0 and 122 are connected. These L2 caches are
The system, via each connected processor
It is connected to the bus 124.

Each L1 and L2 cache pair is typically associated in series. L1 cache is store in (st
Larger, slower L2 caches, implemented as ore-in or write-through, can be implemented as write-back caches. L1 and L2 cache controller (not shown)
Both are physically implemented as part of the processing unit and are internally connected to the processing unit via a bus.
The L2 cache controller may be off-chip.

Referring to FIG. 2, a data processing system 200 that may be configured to operate in accordance with the present invention is shown. System 200 is an alternative architecture to system 100. Within system 100 and system 200, the basic operation of processors and caches are similar. Memory controller 104 and node controller 205
The controls and functions of are similar for the present invention.

In system 200, processor 20
1 has an internal L1 cache 202, and the L1 cache 202 is connected to an external L2 cache 203. The processor 201 allows the node control device 20 to operate via the bus 204.
5 is connected. Node controller 205 performs the known basic functions for connecting processor 201 to the remaining elements of system 200. The node controller 205 is connected to the switch 207 by the bus 206. The switch 207 is, for example, a cross point switch,
Other processors and / or I / O devices (not shown)
Are connected to system memory 209 via bus 208. Although the discussion below is with respect to system 200, the discussion of the invention below is also related to and may be implemented in system 100.

The goal of the present invention is to cache these cache lines (data portions or blocks) in the L1 cache 20 so that the processor 201 hits the cache lines in the L1 cache 202 for a considerable amount of time.
2 to provide an efficient and accurate technique for prefetching, thereby minimizing the retrieval of address and data information from the system memory 209 which degrades the performance of the processor 201.

Referring to FIG. 3, stream filters are used to reduce the occurrence of prefetching of unused data. These stream filters are history buffers that contain address and direction information.
The stream filter contains the address of the next higher cache line after the missed cache line in the L1 cache. Access from the processor
When performed on the next higher cache line, the stream condition is detected and the stream buffer is allocated. The stream filter is written with the line address "X + 1" when an access to the line address "X" occurs. While "X + 1" is present in the stream filter, the subsequent access is the address "X +".
When executed for 1 "(filter hit)," X
+1 "is assigned as a stream.

The stream buffer is a prefetch buffer that holds potential cache data.
The idea is that if the program executing in the processor is executing a sequential stream of data / instructions, it may be useful to prefetch additional lines from system memory into the stream buffer.
Therefore, a subsequent cache miss will stream the data.
It can be found in the buffer and the stream buffer feeds the data to the L1 cache and / or the processor.

The stream filter and stream buffer cooperate so that if an L1 cache miss occurs that also misses the stream buffer, the miss address is compared to the address stored in the stream filter. To do. If a hit occurs in the stream filter (meaning there was a sequential access to the sequential data line) then the next line is also likely to be needed in the future.

Referring to FIG. 4, there is shown a detailed view of a system 200 configured in accordance with the present invention, as well as data flow within CPU 201. Variations on data flow are also known, including, for example, the use of separate L1 caches for instructions and data. The L1 cache 202 holds a copy of frequently used data from memory 209, according to any known replacement policy. The large L2 cache 203 holds more data than the L1 cache 202 and normally controls the memory coherence protocol. L1 cache 2
The data in 02 may be a subset of the data in L2 cache 203. L1 cache 202 and L2
The cache 203 is a "store in" cache. Other functional elements (including I / O) use known snoop protocols to compete for data. One form of snooping is disclosed in US patent application Ser. No. 442740.

The boundaries shown to the CPU 201 indicate chip boundaries and functional boundaries, but they do not limit the scope of the invention. PCC404 is a processor
A cache controller that controls fetches (prefetches) and stores from the memory subsystem. P
The CC 404 has other known functions such as creating a directory 410 for the L1 cache 202, converting effective addresses to real addresses, and vice versa. The prefetch buffer (PBFR) 402 is C
Holds several lines of memory data staged in PU 201 and L1 cache 202. PBFR402
Is a stream buffer.

When the PCC 404 fetches data, if the data is in the L1 cache 202 (L1 hit), the data is sent to the PCC 404.
Although it does not exist in the L1 cache 202 (L1 miss),
If it exists in the L2 cache 203 (L2 hit), a line in the L1 cache 202 is replaced by this main data from the L2 cache 203. In this case, the data is L1 cache 202 and PC.
Simultaneously transmitted to C404. If a miss occurs in the L2 cache 203 as well, the data is fetched from the memory 209 to the BIU 401, and the L1 cache 202, the L2 cache 203, and the PCC 404 are fetched.
Loaded at the same time. Variations on this operation are known. The data store operation is similar to the fetch operation except that the data is stored on the L1 line and the operation completes.

In the discussion that follows, various portions of the stream buffer (see FIG. 3) will be located in various portions of system 200. In the present technique, the stream buffer has the ability to store four cache lines, but any number of cache lines may be implemented within the stream buffer. One cache line of the stream buffer is realized in the L1 cache 202. Essentially, one of the cache lines in L1 cache 202 is utilized as a function of one of the stream buffer cache lines. The second cache line of the stream buffer is placed in the PBFR (prefetch buffer) 402. The other two cache lines of the stream buffer are PBFR2 405 and PBFR in the node controller 205.
3 406. The node controller 205 may be arranged on the chip downstream of the CPU 201 along the bus 204. If the architecture of system 100 is used, memory controller 104 may include these stream buffer lines.

As stated in the referenced IEEE Clause, the basic operation of the stream filter and stream buffer is L for request cache lines.
When a cache miss occurs, the address of the cache line is incremented (generally one line address) and this incremented address is stream filter 403.
Is inserted into. Upon occurrence of a subsequent miss of a cache line in the L1 cache 202, the address of this L1 cache miss is the address of the stream filter 40.
3 is compared with the address contained in 3. A stream of cache lines is allocated in the stream buffer if a match with at least one address is observed.

As described above, when a cache miss occurs, the stream filter buffer is written with the address of the next sequential cache line. Stream filters (see FIGS. 3 and 5) include multiple locations that can hold addresses that contain a "history" of such events. These may be replaced on a least recently used (LRU) basis. Each time a cache miss occurs, the stream
The address in the filter is compared to the cache line miss address. If a hit occurs, the filter hit is said to have occurred and the stream is allocated. In stream mode, an extra cache line is expected by the L1 cache 202 as part of the stream, so the stream buffer (eg, L1 cache 202, PBFR 402,
PBFR2 405 and PBFR3 406 lines)
Prefetched to.

FIG. 5 shows a high level functional diagram illustrating the operation of the stream filter and stream buffer according to the present invention. The CPU 201 generates an effective address (EA) according to the architecture used. EA is the requested data address with potential offset.
The converter 503 causes the CPU 201 to generate a translated address or a real address (RA) corresponding to EA. The real address is used by the filter queue 502, but it is within the scope of the invention for the filter queue 502 to use a valid address instead of the real address. RA is filtered by the comparator 504 to the filter queue 50.
If the entry is indiscriminately compared to RA in 2 and the entry is marked valid by its valid bit (V), then the match is called a filter hit.

The filter queue 502 includes a speculative direction indicator for each entry, which indicates that the speculative stream should be incremented or decremented (± 1 or up / down). This will be described later.

Each filter queue entry includes a field that indicates whether or not there is a stream corresponding to that address, and if so, the identifying stream number of that stream (multiple streams can be allocated at one time). Can be).

When a filter hit occurs, a stream is allocated in stream address buffer 501 and a corresponding allocation is made in stream data buffer 506. The stream address entry contains the speculative effective address of the next data line of a particular allocated stream. Again, it is possible here to use the real address instead of the effective address. The stream address entry also contains a valid bit that indicates that the stream is assigned. In addition, there is a state field used to keep track of the state of the stream. Also, a copy of the speculative direction (± or up / down) is kept in the stream buffer. Comparator 505 is an EA issued by the processor
Is compared with the page address and line address contained in the stream address buffer 501. If a match occurs, this is called a stream hit.

The functions shown in FIG. 5 can be implemented by other methods, and these are also included in the scope of the present invention.

The memory space within system memory 209 may be divided into 128 byte lines. Each line may be divided in half such that the even part of the line is at addresses 0-63 and the odd part is at addresses 64-127. As mentioned above, the CPU 201 generates a logical address (EA), which is translated into a real address that points to a cacheable line in memory. The memory is divided into pages of 2N bytes. The page is divided in size into lines that correspond to cache entries. Each time a cache miss occurs, the associated real address is analyzed. If the real address is in the even part of the line, then the latent stream is an incremental stream. The LRU filter queue entry in filter queue 502 is marked with the "up" direction and the line miss RA is incremented by "1" and saved in the entry. RA
If is on the odd side of the line, the RA entry in queue 502 is decremented by 1 and "down" is marked in the entry.

As an alternative technique, it is within the scope of the invention to store the RA in a filter entry upon a miss and then compare subsequent misses to the entry to determine the up or down direction.

It will be apparent that the "next" valid line address is stored in the stream address buffer 501 when a stream is allocated. Buffer 5
01 contains an entry for each active stream.

When a cache miss occurs in the L1 cache 202 and the L2 cache 203, the system
Before accessing the memory 209, an inquiry is made to the stream buffer. Filter queue 5
Combining the 02 circuit and the stream address buffer 501 circuit is also an aspect of the present invention.

Referring to FIGS. 6-9, there is shown a flow diagram of the inventive prefetch mode of the present invention. The present invention enables three progressive prefetch modes and their variants. They are normal, data prefetch,
And Blast. No data is prefetched in normal mode. In data prefetch mode, 2 lines are prefetched and 1 line is L
One line in one cache is prefetched into the stream buffer. In blast mode, three or more lines are prefetched at once. In one aspect of the invention, in blast mode, 4 lines are prefetched, 2 lines are prefetched in data prefetch mode, and 2 additional lines are prefetched into the stream buffer. In any mode, the prefetch buffer may be implemented on the processor chip, cache chip, external chip, and / or memory card. 6 to 9 show examples in which the estimated direction in which the stream flows is the incremental direction. An example for the decremental direction would be obvious as a modification of this example. The flow diagrams of FIGS. 6-9 show how the data prefetch mode and blast mode are entered.

In step 601, the CPU 201 starts data access in the cache line A.
At step 602, it is determined whether cache line A exists in L1 cache 202. If so, the process moves to step 603, where the cache
Line A is returned to CPU 201 and the process ends at step 604.

However, if a miss occurs in cache line A, the process moves to step 605, where the address of cache line A is compared with all the addresses contained in stream filter 403.

If cache line A does not exist in stream filter 403, the process proceeds to step 6.
Moving to 06, the address of cache line A is incremented by 1 and inserted into stream filter 403.
Therefore, in step 607, cache line A is L
It is fetched from the 2-cache 203 or the memory 209 to the L1 cache 202.

The dashed arrow from step 607 to step 608 in FIGS. 6-9 indicates that step 608 does not necessarily occur immediately after step 607. Generally, the more misses occur, the more cache line A +
Address requests in stream filter 403 may occur prior to the request for 1 (step 608).

Eventually, CPU 201 may request cache line A + 1 (step 608). PC again
C404 determines whether cache line A + 1 exists in L1 cache 202 (step 60).
9). If so, then cache line A + 1 is returned to CPU 201 at step 610 and the process ends at step 611. That is, since the cache line A + 1 exists in the L1 cache 202, the comparison with the stream filter 403 is not executed, and A + 1
The entry remains in the filter 403 until it is retired by the filter replacement algorithm. The filter permutation algorithm may be implemented in accordance with the teachings in pending US Patent Application No. 519032. However, L1
When a miss occurs for cache line A + 1 in cache 202, a filter hit occurs (step 637) and the process moves to step 612.
A cache line stream starting with cache line A + 2 is allocated. This is because the address of the requested cache line A + 1 is compared with the address A + 1 existing in the stream filter 403, resulting in a hit in the stream filter 403. Then, in step 613, cache line A + 1 is fetched from L2 cache 203 or memory 209 to L1 cache 202. Also, it is checked whether the cache line A + 2 exists in the L1 cache 202. If not, cache line A + 2 is prefetched from L2 cache 203 or memory 209 to L1 cache 202.

Then, in step 614, the cache
It is determined whether or not the line A + 3 exists in the L2 cache 203. If not, the process moves to step 615 where cache line A + 3 is in memory 2
09, prefetched from prefetch buffer P
It is inserted into BFR402. However, if cache line A + 3 is present in L2 cache 203, the process skips step 615.

Again, steps 615 to 616
The dashed arrow to indicates that step 616 does not necessarily occur immediately after step 615.

At step 616, the processor 201 may request cache line A + 2, in which case an access to line A + 2 will result in L1 cache 202.
Run from At step 613, cache line A + 2 has been fetched into the L1 cache 202, so the L1 cache 202 can supply this cache line to the CPU 201. Step 617
Then, the stream address in the stream address buffer 501 is updated so as to have the address A + 3 at the head of the stream. Then, step 618
So, cache line A + 3 is L1 cache 202
If it does not exist, it is checked whether it exists in
Cache line A + 3 is fetched from L2 cache 203 or PBFR 402 into L1 cache 202. Then, in step 619, cache line A + 4 is fetched into PBFR 402 from L2 cache 203 or memory 209.

Thereafter, if blast mode is not allowed in system 200 (step 620), the process returns to step 616 and as long as CPU 201 continues incrementing cache lines sequentially as shown ("
Referred to as "streaming"), step 616
Through 621. Step 621 then proceeds to step 616 where an L1 cache access to line A + 3 occurs, the stream is updated with address A + 3 at step 617 and step 618.
Indicates that line A + 4 is fetched from L1 cache 202 and that cache line A + 4 is fetched from PBFR 402 at step 619.

The above description shows the data prefetch mode. In step 620, if blast mode is allowed in system 200, the process moves to step 622 and a request is issued from CPU 201 for cache line A + 3. At step 622, PCC 404 searches cache line A + 3 in L1 cache 202 for such a request. Cash line A + 3 is step 61
The cache line A + 3 is returned to the CPU 201 because it exists in the L1 cache 202 due to 8. Then, in step 623, the stream address in stream address buffer 501 is updated to A + 4. At step 624, it is tested whether line A + 4 exists in L1 cache 202. If not present, cache line A + 4 becomes PBFR402.
From the prefetch buffer location in the L1 cache 202.

Then, in step 625, the cache
It is determined whether or not the line A + 5 exists in the L2 cache 203. If so, the process is step 6
26 or 627. This technique requires the node controller 205 to be notified of any stream buffer access. The notification is the next stream
The node controller buffers 405 and 406 temporarily lose synchronization with the processor 201 only when the buffer is not in the L2 cache 203 and therefore needs to be fetched. The advantage of this design trade-off is that steps 626 and 627 are combined to reduce address bus traffic to node controller 205. In the first case, the lines A, A + 1, etc. do not exist in cache 202 prior to prefetching, so cache line A + 5 is typically L.
2 It cannot be expected to exist in the cache 203.

When steps 626 and 627 are combined for the reasons set forth above, the notification of step 627 may be realized by the four control bits added to the prefetch of step 626. The 4 bits include a 1-bit valid prefetch, a 2-bit stream identification, and a 1-bit prefetch direction. Cash line A + 5
From the address of the node and these bits, the node controller 2
05 generates memory requests for cache lines A + 6 and A + 7. As mentioned above, the node controller 205 may be implemented to prefetch any number of cache lines. In step 628, node controller 205 prefetches cache line A + 6 into prefetch buffer PBFR2 405,
Prefetch cache line A + 7 into prefetch buffer PBFR3 406.

The dashed arrow between steps 628 and 629 indicates the CPU for cache line A + 4.
It indicates that the request from 201 does not necessarily occur immediately after step 628.

In step 629, the L1 cache 202 is accessed in response to the cache line A + 4 request by the CPU 201. Cash line A + 4
Has been inserted into the L1 cache 202 in step 624, the cache line A + 4 is returned to the CPU 201. In step 630, the stream address is incremented and led by address A + 5. In step 631, it is checked whether the cache line A + 5 exists in the L1 cache 202, and if not, the cache line A + 5 is transferred from the L2 cache 203 or the buffer 402 to the L1 cache 2
02 is fetched.

Then, in step 632, the cache
Line A + 6 is from PBFR2 405 to PBFR402
Is forwarded to In step 633, cache line A + 7 is from PBFR3 406 to PBFR2 405.
Is forwarded to Then, at step 634, the node controller 205 is notified to prefetch cache line A + 8. In the present technique, step 632
The fetch of the cache line A + 6 in (1) notifies the node controller 205 to prefetch the cache line A + 8 (step 634). In step 635, the node controller 205 determines whether the cache
Prefetch line A + 8 from memory 209 into PBFR3 406.

Thereafter, as long as CPU 201 continues to access the cache line while incrementing it sequentially (ie, CPU 201 continues to access the cache line in the allocated stream), the process is incremental (step 636) and steps Continue looping through 629 through 636.

In the above discussion, bus interface (BIU) 401 performs a cache line fetch from system memory 209.

The node controller 205 can be a port on the switch 207.

Since effective addresses are contiguous across page boundaries and real addresses are not contiguous, it is often advantageous to use effective addresses when comparing two addresses in stream address buffer 501. . Further, a counter may be used to generate the incremental address.

As mentioned above, from BIU 401 to memory 2
On fetch to 09, the control bit is used to direct the node controller 205 to cache line PBFR.
Notify 2405 and PBFR3 406 to prefetch. A one bit may inform node controller 205 that this particular line request requires node controller 205 to perform a prefetch into its buffer. Another two bits may inform the node controller of the stream number associated with the prefetch. Another one bit may indicate the direction of the cache line the address progresses. When the node controller 205 is notified to perform a prefetch, such a prefetch may be performed independently of the operation of the CPU 201.

In the case of including the L1 cache 202 and the L2 cache 203, in the above procedure, the cache line is from the PBFR 402 to the L1 cache 202.
The same cache line will also be included in the L2 cache 203 when transferred to.

The advantage of having one of the stream buffer lines in L1 cache 202 is that when a particular cache line contained within that buffer line in L1 cache 202 is requested by processor 201, A hit occurs in the L1 cache 202 instead of a miss. Technically, a miss will occur even if the requested cache line is contained within another buffer connected to the L1 cache 202. These misses require extra hardware and cycle time to fetch the cache line from the stream buffer line to the CPU 201. Logically, the cache line in L1 cache 202 that acts as one of the stream buffer cache lines is said to be contained within the prefetch stream buffer.

In summary, the following items are disclosed regarding the configuration of the present invention.

(1) A processor, a system memory connected to the processor via a bus, a first cache connected to the processor, a second cache connected to the processor, and the system A stream buffer circuit for storing one or more data lines prefetched from a memory, a stream filter circuit indicating a prefetch state, and a stream filter circuit connected to the stream filter circuit, the first and the second from the system memory A data processing system, comprising: a second cache; and a control circuit that selectively controls fetching and prefetching of data to the stream buffer circuit. (2) A circuit in which the control circuit receives a request for a first cache line from the processor, and a circuit in which it is determined whether the first cache line exists in the first cache. , If the first cache line is not in the first cache and the first cache line is in the second cache, then the first cache line is replaced by the second cache line.
For fetching from the first cache to the first cache, and if the first cache line is not present in the second cache, the first cache
A circuit for fetching a line from the system memory into the first cache; a circuit for incrementing the address of the first cache line to generate a first increment address; and the increment address for the stream filter The circuit according to (1) above, comprising: (3) The second control circuit has the increment address.
A request for a cache line from the processor, a circuit for determining whether the second cache line is in the first cache, and the incremental address in the stream filter. A circuit for determining whether or not there is a second increment address, a circuit for incrementing the increment address to generate a second increment address, a circuit for allocating a stream starting at the second increment address, and the second increment. A circuit for determining whether a third cache line having an address is present in the first cache; the second cache line is present in the second cache; Cache line is not present in the first cache,
A circuit for fetching the second cache line from the second cache to the first cache; and the second cache line if the second cache line is not present in the second cache. A circuit for fetching a line from the system memory into the first cache; and the third cache line with the second cache line.
Of the third cache line and the third cache line is not present in the first cache, the circuit for prefetching the third cache line from the second cache to the first cache. And prefetching the third cache line from the system memory into the first cache if the third cache line is not present in the second cache. ) The system described. (4) Whether a circuit for incrementing the second increment address and generating a third increment address and a fourth cache line having the third increment address are present in the second cache. A circuit for determining whether or not the fourth cache line is present in the second cache, and a circuit for prefetching the fourth cache line from the system memory to the stream buffer circuit. A circuit for receiving a request for the third cache line from the processor;
A cache line from the first cache to the processor;
A circuit for determining whether a line is present in the first cache; and if the fourth cache line is present in the second cache, the fourth cache line is set to the second cache line. Circuit for fetching from the first cache to the first cache;
A circuit for fetching the fourth cache line from the stream buffer circuit to the first cache if the line is not in the second cache; and incrementing the third increment address, A fifth cache line having a fifth cache line having the fourth increment address in the second cache, and a fifth cache line having a fifth cache line having the fourth increment address. Exists in the second cache, a circuit for fetching the fifth cache line from the second cache to the stream buffer circuit; and a fifth cache line for the second cache If not present in the fifth cache,
A circuit for prefetching a line from the system memory into the stream buffer circuit. (5) The system according to (1), wherein one or more cache lines stored in the stream buffer circuit are arranged in the first cache. (6) The system according to (1), wherein one or more cache lines stored in the stream buffer circuit are arranged in a chip including the processor. (7) The system according to (1), wherein one or more cache lines stored in the stream buffer circuit are arranged in a node controller connected to the processor and the system memory. (8) The above-mentioned (1), wherein the first cache is a primary cache arranged on the same chip as the processor, and the second cache is a secondary cache arranged outside the chip. System. (9) The stream filter circuit can track a plurality of streams, each entry in the stream filter circuit tracks one of the plurality of streams, and each entry is tracked by the entry. A first indicator indicating the adequacy of the stream according to the present invention, and a second indicator indicating the increment direction of the address of the entry.
The system according to (1) above. (10) The system according to (1), wherein the stream buffer circuit includes, for each entry, 1) page address, 2) line address, and 3) validity indicator. (11) The system according to (1), wherein the entry in the stream filter circuit has a real address, and the entry in the stream buffer circuit has a valid address. (12) The system according to (1), wherein the processor, the control circuit, the stream filter circuit, the first cache, and part of the stream buffer circuit are arranged on the same chip. (13) A second processor, the system memory connected to the second processor, a third cache connected to the second processor, and a fourth cache connected to the second processor. Second cache connected to the second processor for storing one or more data lines prefetched from the system memory
Stream buffer circuit, a second stream filter circuit connected to the second processor and indicating a prefetch state, and a second stream filter circuit connected to the third stream filter circuit from the system memory. (4) a fourth cache, and a second control circuit for selectively controlling fetching and prefetching of data to the second stream buffer circuit.
The system described. (14) In a data processing system, receiving a request for a first cache line from the processor, and determining whether the first cache line exists in the first cache. The first cache line is not in the first cache and the first cache line is the second cache line;
Fetching the first cache line from the second cache to the first cache if it is present in the second cache, and the first cache line is not present in the second cache If
Fetching the first cache line from the system memory into the first cache;
Incrementing the address of the first cache line to generate a first increment address, and storing the increment address in a stream filter. (15) A second cache having the increment address
Receiving a request for a line from the processor, determining if the second cache line is in the first cache, and the incremental address is in the stream filter. Determining whether or not; incrementing the increment address to generate a second increment address; allocating a stream starting at the second increment address; and having the second increment address. Determining whether a third cache line is present in the first cache; and the second cache line.
A second cache line from the second cache to the first cache if a line exists in the second cache and the second cache line does not exist in the first cache. Fetching the second cache line from the system memory to the first cache if the second cache line is not present in the second cache; A third cache line is present in the second cache, the third cache line
Second cache line is not present in said first cache, said third cache line is said to be said second cache line.
Pre-fetching from said cache to said first cache; and if said third cache line is not present in said second cache, said third cache line from said system memory to said first cache line. Prefetching into a cache, the method according to (14). (16) Incrementing the second increment address to generate a third increment address, and whether a fourth cache line having the third increment address exists in the second cache. Determining if the fourth cache line is not in the second cache and prefetching the fourth cache line from the system memory to the stream buffer circuit. Receiving a request for the third cache line from the processor; sending the third cache line from the first cache to the processor;
Determining whether the fourth cache line is in the first cache; and if the fourth cache line is in the second cache, the fourth cache Fetching a line from the second cache to the first cache; and if the fourth cache line is not present in the second cache, the fourth cache
Fetching a line from the stream buffer circuit into the first cache; incrementing the third increment address to generate a fourth increment address; and a fifth having the fourth increment address. Determining whether a cache line in the second cache is present in the second cache; and if the fifth cache line is in the second cache, the fifth cache line From the second cache to the stream buffer circuit, and if the fifth cache line is not in the second cache, the fifth cache line from the system memory. Prefetching into the stream buffer circuit. (17) 1 stored in the stream buffer circuit
The method of (16) above, wherein one or more cache lines are located within the first cache. (18) The first cache is a primary cache arranged on the same chip as the processor, and the second cache
The method according to (17) above, wherein the cache is a secondary cache located outside the chip. (19) The stream filter circuit can track a plurality of streams, each entry in the stream filter circuit tracks one of the plurality of streams, and each entry is tracked by the entry. A first indicator indicating the adequacy of the stream according to the present invention, and a second indicator indicating the increment direction of the address of the entry.
The method according to (18) above. (20) The method according to (19), wherein the entry in the stream filter circuit has a real address, and the entry in the stream buffer circuit has a valid address.

[Brief description of the drawings]

FIG. 1 illustrates a multiprocessor system configurable according to the present invention.

FIG. 2 is a diagram illustrating a data processing system configurable according to the present invention.

FIG. 3 is a diagram showing a stream filter and a stream buffer.

FIG. 4 is a diagram showing details of the system shown in FIG. 2.

FIG. 5 is a functional diagram according to the present invention.

FIG. 6 is a flow chart of the present invention.

FIG. 7 is a flow chart of the present invention.

FIG. 8 is a flow chart of the present invention.

FIG. 9 is a flow chart of the present invention.

[Explanation of symbols]

 100, 200 data processing system 202 L1 cache 203 L2 cache 204, 206, 208 bus 402 prefetch buffer

 ─────────────────────────────────────────────────── ─── Continued Front Page (72) Inventor Dwain Alan Hicks, USA 78660, Duffons Drive, Pflugerville, Texas 2405 (72) Inventor David Scott Ray United States 78728, Young Ranch, Texas, Young Ranch Road 700 (72) Inventor Shih Shin Stephan Tan 9923 Burbrook Drive, Austin, TX 78726, USA

Claims (20)

[Claims] 1. A processor, a system memory connected to the processor via a bus, a first cache connected to the processor, a second cache connected to the processor, and the system cache. A stream buffer circuit for storing one or more data lines prefetched from a memory; a stream filter circuit indicating a prefetch state; a stream filter circuit connected to the stream filter circuit; And a control circuit that selectively controls fetching and prefetching of data to the stream buffer circuit. 2. The control circuit determines a circuit for receiving a request for a first cache line from the processor, and determining whether the first cache line exists in the first cache. Circuit, if the first cache line is not in the first cache and the first cache line is in the second cache, the first cache line is A circuit for fetching from the second cache to the first cache; and if the first cache line is not present in the second cache, the first cache line from the system memory to the first cache line. And a circuit for incrementing the address of the first cache line to generate a first increment address. Including a circuit for storing said incremental address to the stream filter system of claim 1, wherein. 3. The circuit for the control circuit to receive a request from the processor for a second cache line having the incremental address; and whether the second cache line is in the first cache. A circuit for determining whether or not the increment address is present in the stream filter; a circuit for incrementing the increment address to generate a second increment address; A circuit for allocating a stream starting at a second increment address; a circuit for determining whether a third cache line having the second increment address is present in the first cache; A cache line is present in the second cache, and the second cache line is the first cache line.
Circuit for fetching the second cache line from the second cache to the first cache if not present in the second cache; and the second cache line is not present in the second cache A circuit for fetching the second cache line from the system memory into the first cache; the third cache line being present in the second cache; The line is the first
Circuit for prefetching the third cache line from the second cache to the first cache if not present in the second cache; and the third cache line is not present in the second cache. A system for prefetching the third cache line from the system memory into the first cache, if desired. 4. A circuit for incrementing the second increment address to generate a third increment address; and a fourth cache line having the third increment address in the second cache. A circuit for determining whether or not to do so, and if the fourth cache line is not present in the second cache, prefetch the fourth cache line from the system memory to the stream buffer circuit. A circuit, a circuit for receiving a request for the third cache line from the processor, a circuit for transmitting the third cache line from the first cache to the processor, and a fourth cache line A circuit for determining whether a cache cache is present in the first cache and the fourth cache line is connected to the second cache line. A cache for fetching the fourth cache line from the second cache to the first cache, if present in the cache; and if the fourth cache line is not present in the second cache. A circuit for fetching the fourth cache line from the stream buffer circuit to the first cache; a circuit for incrementing the third increment address to generate a fourth increment address; Circuit for determining whether a fifth cache line having an incremented address of is present in the second cache; and if the fifth cache line is present in the second cache, A circuit for fetching the fifth cache line from the second cache to the stream buffer circuit; and a fifth cache line. 4. The system of claim 3, further comprising: prefetching the fifth cache line from the system memory into the stream buffer circuit if a cache line is not present in the second cache. 5. The system of claim 1, wherein one or more cache lines stored in the stream buffer circuit are located in the first cache. 6. The system of claim 1, wherein one or more cache lines stored in the stream buffer circuit are located in a chip containing the processor. 7. The system of claim 1, wherein one or more cache lines stored in the stream buffer circuit are located in a node controller connected to the processor and the system memory. 8. The first cache is a primary cache located on the same chip as the processor, and the second cache is a secondary cache located outside the chip. The system described. 9. The stream filter circuit is capable of tracking a plurality of streams, each entry in the stream filter circuit tracking one of the plurality of streams, and each entry according to the entry. The system of claim 1 including a first indicator of the validity of the stream being tracked and a second indicator of the incrementing direction of the address of the entry. 10. The stream buffer circuit for each entry: 1) page address and 2) line.
The system of claim 1, including an address and 3) a plausibility indicator. 11. The system of claim 1, wherein the entry in the stream filter circuit has a real address and the entry in the stream buffer circuit has a valid address. 12. The system of claim 1, wherein the processor, the control circuit, the stream filter circuit, the first cache, and a portion of the stream buffer circuit are located on the same chip. 13. A second processor, the system memory connected to the second processor, a third cache connected to the second processor, and connected to the second processor. A fourth cache; a second stream buffer circuit connected to the second processor for storing one or more data lines prefetched from the system memory; connected to the second processor A second stream filter circuit indicating a prefetch state, the third stream filter circuit connected to the second stream filter circuit from the system memory,
And selectively controlling fetching and prefetching of data to the second stream buffer circuit,
The control circuit of claim 1, and the system of claim 1. 14. In a data processing system, receiving a request for a first cache line from the processor, and determining whether the first cache line is in a first cache. And said first cache line is not present in said first cache and said first cache line is present in said second cache, said first cache line is said to be said Fetching from a second cache to the first cache; if the first cache line is not present in the second cache, the first cache line from the system memory to the first cache line; To the first cache line and incrementing the address of the first cache line to increase the first increment And generating an address, and storing the incremented address to the stream filter, the method. 15. A step of receiving a request from the processor for a second cache line having the incremented address, and determining whether the second cache line is in the first cache. Determining whether the increment address is in the stream filter; incrementing the increment address to generate a second increment address; starting with the second increment address Allocating a stream to be processed, determining whether a third cache line having the second increment address is present in the first cache, and the second cache line is Is in a second cache, and the second cache line is the first cache line.
Fetching the second cache line from the second cache to the first cache if not present in the second cache line; and the second cache line is not present in the second cache. If the second cache line is fetched from the system memory into the first cache, the third cache line is in the second cache, and the third cache line is present in the third cache line. The line is the first
Pre-fetching the third cache line from the second cache to the first cache if not present in the second cache, the third cache line not present in the second cache 15. If so, then prefetching the third cache line from the system memory into the first cache. 16. Incrementing the second increment address to increment the third increment address.
Generating an incremental address of the second cache line, determining whether a fourth cache line having the third incremental address is present in the second cache, and the fourth cache line If not present in the second cache, prefetching the fourth cache line from the system memory into the stream buffer circuit; and receiving a request for the third cache line from the processor. Sending the third cache line from the first cache to the processor, and determining whether the fourth cache line is in the first cache. And the fourth cache line resides in the second cache Fetching the fourth cache line from the second cache to the first cache; and if the fourth cache line is not in the second cache, the fourth cache line Fetching a line from the stream buffer circuit into the first cache; incrementing the third increment address to generate a fourth increment address; and a fifth having the fourth increment address. Determining whether a cache line in the second cache exists in the second cache; and if the fifth cache line exists in the second cache, the fifth cache line Fetching from the second cache into the stream buffer circuit, the fifth cache 16. The method of claim 15, comprising pre-fetching the fifth cache line from the system memory into the stream buffer circuit if a cache line is not present in the second cache. 17. The method of claim 16, wherein one or more cache lines stored in the stream buffer circuit are located in the first cache. 18. The first cache is a primary cache arranged on the same chip as the processor, and the second cache is arranged outside the chip.
18. The method of claim 17, which is a next cache. 19. The stream filter circuit is capable of tracking a plurality of streams, each entry in the stream filter circuit tracking one of the plurality of streams, and each entry according to the entry. 19. The method of claim 18, including a first indicator of the validity of the stream being tracked and a second indicator of the incrementing direction of the address of the entry. 20. The method of claim 19, wherein the entry in the stream filter circuit has a real address and the entry in the stream buffer circuit has a valid address.