Abstract:
An intelligent cache memory system and associated method for reducing a central processing unit (CPU) idle time. The system performs prefetches based on data fetching characteristics of the CPU. The system includes cache control logic, a first and a second cache memory, each having a number of cache lines, and a first and a second cache tag array, each having cache tag entries corresponding to the cache lines. The cache tag entries comprise cache tags and valid bits. The cache tag entries of the second cache tag array further comprise interest bits. In addition to their traditional functions, the cache tags and the valid bits, in conjunction with the interest bits, are used to track the data fetching history of the CPU. For each read cycle, the cache control logic returns the data being fetched by the CPU from either the first or the second cache memory or the main memory. Additionally, the cache control logic initiates prefetch and updates the data fetching history conditionally. The data fetched from either the second cache memory or the main memory are also stored in the first cache memory, whereas the data prefetched are stored in the second cache memory. Prefetch is conditioned on the data fetching history, while data fetching history update is conditioned on where the data requested by the CPU are fetched. As a result, CPU idle time is further reduced and system performance is further improved.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to the field of computer systems. More particularly, the present invention relates to cache memory on these computer systems. 
     2. BackGround 
     Typically a central processing unit (CPU) in a computer system operates at a substantially faster speed than a main memory of the computer system. Most computer systems provide cache memory which can operate at a higher speed than the main memory to buffer data and instructions between the main memory and the high speed CPUs. At any particular point in time, the cache memory stores a subset of the data and instructions stored in the main memory. 
     During read cycles, data and instructions are fetched from the cache memory if they are currently stored in the cache memory (read cache hits). Otherwise (read cache misses), they are retrieved from the main memory and stored in the cache memory as well as provided to the CPU. Similarly, during write cycles, data is written into the cache memory if the data is currently stored in the cache memory (write cache hits). Otherwise (write cache misses), the data is either not written into the cache memory (no write allocate) or written into the cache memory after forcing a cache line update (write allocate). Furthermore, data is written into the main memory either immediately (write through) or when a cache line is reallocated (write back). 
     Since the CPU goes idle in the event of a cache miss, the size and operating characteristics of the cache memory are typically optimized to provide a high cache hit rate, thereby reducing CPU idle time and improving system performance. As the speed of CPUs continues to get faster, various performance motivated approaches have also been developed to make cache hits faster or reduce cache miss penalty, thereby further reducing CPU idle time and improving system performance. Well known examples are virtual addressing to make cache hits faster, early restart and out-of-order fetching to reduce read miss penalty, use of write buffer to reduce write miss penalty, and use of two level caches to reduce read/write miss penalty. In the case of the two level cache approach, typically the first level cache is made small enough to match the clock cycle time of the CPU while the second level cache is made large enough to capture many fetches that would otherwise have to go to main memory. 
     However, traditional approaches to reducing CPU idle time and improving system performance seldom take the intrinsic characteristics of the applications that run on the computer systems into consideration, even though it is well known that many applications, due to their inherent nature, cause the CPU to go idle frequently and degrade system performance. For example, in many vector applications, it is quite common for a program to execute a statement like A[i]+B[i]=C[i], for i=1 to N and where N is a large number, and A, B and C are arrays. Assuming the starting addresses for arrays A and B are addr1 and addr2 respectively, the size of the array elements is 32 bytes and data is fetched in 32 byte blocks, the CPU will have to access addr1, addr2, addr1+32, addr2+32, addr1+64, addr2+64, and so forth. After at most n accesses, where n is the number of cache lines which is typically smaller than N, each subsequent access will result in a cache miss requiring access to the main memory. The data last fetched and stored in the cache lines are never used, they just keep getting overlaid. 
     Thus, it is desirable to have a cache memory whose design takes into consideration the inherent nature of some of the more popular applications that affect CPU idle time and system performance. In particular, it is desirable to have the cache memory&#39;s design take into consideration the inherent sequential access nature of vector applications. As will be disclosed, these objects and desired results are among the objects and desired results of the present invention. 
     For further description of cache memory, cache performance problems and improvement techniques, see J. L. Hennessy, and D. A. Patterson, Computer Architecture--A Quantitative Approach, pp. 402-461, (Morgan Kaufmann, 1990). 
     SUMMARY OF THE INVENTION 
     An intelligent cache memory and a method for conditionally prefetching data based on data accessing characteristics of a central processing unit (CPU) are hereby disclosed. The present invention has particular application to computer systems, especially those computer systems intended for vector applications. 
     Under the presently preferred embodiment of the present invention, the cache memory comprises control circuitry, a first and a second cache memory array, and a first and a second corresponding cache tag array. The cache tag entries in the first and second cache tag arrays, in their presently preferred form, comprise address tags and valid bits. Additionally, the cache tag entries in the second cache tag array, in their presently preferred form, further comprise interest bits. 
     The address tags of the first and second cache tag arrays are used for address matching to determine whether the data being accessed by the CPU are currently stored in the corresponding cache memory arrays. The valid bits of the first and second cache tag arrays are used to indicate the validity of the data stored in the corresponding cache lines of the first and second cache memory arrays. The interest bits of the second cache tag array are used to indicate whether the cache memory should prefetch the next data block. Additionally, the address tags of the second cache tag array, in conjunction with their corresponding valid and interest bits, are used for tracking the data fetching history of the application. 
     For each read cycle, the control circuitry fetches the data requested by the CPU from either the first or the second cache memory array or the main memory. Data fetched from either the second cache memory array or the main memory are also stored into the first cache memory array. Additionally, the control circuitry conditionally prefetches the next data block from main memory and stores that data block in the second cache memory array. Prefetching is conditioned on the data fetching history of the CPU. Furthermore, the control circuitry conditionally updates the data fetching history of the CPU. Updating the data fetching history of the CPU is conditioned on where the requested data is fetched. 
     For each write cycle, the control circuitry performs standard write operations. Additionally, the control circuitry conditionally resets the data fetching history of the CPU. Resetting of the data fetching history is conditioned on where the data is written. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The objects, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiment of the invention with references to the drawings in which: FIG. 1 illustrates a computer system which embodies the teachings of the present invention. FIG. 2 illustrates an intelligent cache memory of the present invention. FIGS. 3a-3b illustrate a method of operating the intelligent cache memory of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     An intelligent cache memory and a method for conditionally prefetching data based on data fetching characteristics of a central processing unit (CPU) are hereby disclosed. The present invention has particular applications to computer systems, especially those computer systems intended for vector applications. In the following description for purposes of explanation, specific numbers, materials and configurations are set forth 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 the specific details. In other instances, well known systems are shown in diagrammatical or block diagram form in order not to obscure the present invention unnecessarily. 
     Referring now to FIG. 1, a block diagram illustrating a computer system which embodies the teachings of the present invention is shown. As shown in FIG. 1, the computer system 10 comprises a central processing unit (CPU) 12, a cache memory controller 14 and a hierarchy of cache random access memory (RAM) arrays (or simply cache memory arrays) 16 of the present invention, and a main memory 18. The CPU 12 is coupled to the cache memory controller 14 and the hierarchy of cache memory arrays 16 of the present invention through an address bus 22 and a data bus 24. Additionally, the CPU 12 is coupled to the main memory 18 via a write buffer 20 and a multiplexed data and address bus 26, and the cache memory controller 14 of the present invention is coupled to the main memory 18 via the multiplexed data and address bus 26. 
     However, it will be appreciated that the CPU 12, the cache memory controller 14 and the hierarchy of cache memory arrays 16 of the present invention, and the main memory 18 may be coupled to each other in a variety of other well known manners beside the manner used in the embodiment illustrated by FIG. 1. 
     The cache memory controller 14 and the hierarchy of cache memory arrays 16 of the present invention will be described in further detail later with references to FIGS. 2, 3a and 3b . The CPU 12, the main memory 18, the write buffer 20, the address bus 22, the data bus 24 and the multiplexed data and address bus 26 are intended to be representative of a broad category of well known CPUs, main memory memories, and write buffers, and communication interfaces found in most computer systems, whose basic functions and constitutions are well known and will not be described further. An example of such computer systems is the computer systems manufactured by Sun Microsystems, Inc., of Mountain View, Calif. 
     Referring now to FIG. 2, a block diagram illustrating the intelligent cache memory of the present invention in its presently preferred form is shown. The hierarchy of cache memory arrays 16, in its presently preferred form, comprises a first level cache memory array A 32a, and a second level cache memory array B 32b. In their presently preferred form, the first level cache memory array A 32a comprises a plurality of 32 byte cache lines, and the second level cache memory array B 32b comprises two 32 byte cache lines. 
     In their presently preferred form, the main memory 18 is mapped into the cache lines of the first cache memory array A 32a in a set associative manner, and into the cache lines of the second level cache memory array B 32b in a fully associative manner. Additionally, under the presently preferred embodiment, the second cache memory array B 32b is designed to allow data to be fetched from one of its cache lines and returned to the CPU and the first cache memory array A 32a, while simultaneously allowing data fetched from the main memory to be written into the same cache line. 
     However, it will be appreciated that the second level cache memory array B 32b may comprise more than two cache lines. The cache lines may have line sizes other than 32 bytes. The size of the second level cache memory array B 32b cache lines may be larger than the first level cache memory array A 32a cache lines. Additionally, the main memory 18 may be mapped into the cache lines of the first and second level cache memory arrays 32a and 32b in other well known manners. Furthermore, it will be appreciated that the two levels of cache memory arrays 32a and 32b may be addressed either virtually or physically. 
     The cache controller 14 of the present invention, in its presently preferred form, comprises a cache control logic 28, a cache tag array A 30a , and a cache tag array B 30b . The cache control logic 28 is coupled to the cache tag arrays A and B (30a and 30b). Each cache tag array, A and B (30a and 30b) comprises a plurality of cache tags corresponding to the cache lines of the cache memory array A or B, (32a or 32b). Each cache tag (not shown) in cache tag arrays A and B (30a and 30b) comprises an address tag (not shown) and a valid bit (not shown). Additionally, in its presently preferred form, each cache tag in cache tag array B 30b further comprises an interest bit. 
     The cache control logic 28 comprises circuitry for controlling the operation of the cache memory controller 14. The cache control logic 28 uses the address tags in the cache tag entries of cache tag arrays A and B (30a and 30b), for address matching to determine whether data being fetched by the CPU are currently stored in the corresponding cache lines of the cache memory arrays A and B (32a or 32b). The cache control logic 28 uses the valid bits in the cache tag entries of cache tag array A and B (32a and 30b), to determine whether the data currently stored in the corresponding cache lines of the cache memory arrays A and B (32a and 32b), are valid. 
     Additionally, in its presently preferred form, the cache control logic 28 uses the interest bits of cache tag entry of cache tag array B 30b to indicate whether data should be prefetched. Under the presently preferred embodiment, the cache control logic 28 uses the address tags, the valid bits, and the interest bits of cache tag entries of cache tag array B 30b for tracking data fetching history of the CPU. More specifically, under the preferred embodiment, the cache control logic 28 uses the address tags, the valid bits, and the interest bits in cache tag entries of cache tag array B 30b to track sequential accesses by the CPU and initiate prefetching after the CPU has made two sequential accesses. How the cache control logic 28 uses the address tags, the valid bits and the interest bits to track data fetching history of the CPU, in particular, sequential accesses by the CPU, will be described in further detail below with references to FIG. 3a. 
     However, it will be appreciated that by making minor modifications to the present invention, the cache control circuitry 28 may use the cache tags, the valid bits, and the interest bits to track a variety of data fetching characteristics of the CPU. Furthermore, the cache control circuitry 28 may track data fetching characteristics of the CPU using different but essentially equivalent approaches. 
     Additionally, while the present invention has been described with the first and second level cache sharing the same cache control logic. It will be appreciated from the descriptions to follow that the first and second level caches operate relatively independent of each other, and the present invention may be practiced with the first and second level cache having their own control logic. 
     Furthermore, while the present invention has been described with the first and second level cache control logic, tag array and RAMS located together, it will be appreciated that the present invention may be practiced with these elements located separate from each other, in particular, with the second level cache control logic, tag array and RAM located with the main memory. 
     Referring now to FIGS. 3a and 3b, two block diagrams illustrating the control flow of the cache controller of the present invention are shown. Referring first to FIG. 3a, upon receipt of an address from a CPU during a read cycle, the cache control logic first determines if the address of the data being fetched matches any of the addresses of the data stored in the first level cache memory array using the corresponding cache tag entries in cache tag array A, block 42. If the address of the data being fetched matches one of the addresses of the data stored in the first level cache memory array, the cache control logic further determines if the data with the matching address are valid using the valid bit of the matching cache tag entry, block 44. 
     If the address of data being fetched matches one of the addresses of the data stored in the first level cache memory and the data stored in the first level cache memory is valid, the cache control logic causes the data to be fetched from the first level cache memory array and returned to the CPU, block 46. 
     Continuing to refer to FIG. 3a, if the address of the data being fetched does not match any address of the data stored in the first level cache memory or the data stored in the first level cache memory is invalid, the cache control logic then determines if the address of the data being fetched matches any of the addresses of the data stored in the second level cache memory using the corresponding cache tag entries in cache array B, block 48. Similarly, if the address of the data being fetched matches one of the addresses of the data stored in the second level cache memory, the cache control logic further determines whether the data stored in the second level cache memory is valid using the valid bit of the matching cache tag entry, block 50. Additionally, if the address of the data being fetched matches one of the addresses of the data stored in the second level cache memory array, but the address matching data is invalid, the cache control logic further determines whether the pre-fetch threshold has been reached using the interest bit of the matching cache tag entry, block 52. As will be obvious from the description to follow, the pre-fetch threshold is reached when the interest bit of the matching cache tag entry is set to interested. 
     Still referring to FIG. 3a, if the address of the data being fetched does not match any of the addresses of the data stored in the second level cache memory array, the cache control logic causes the address and a standard fetch size to be sent to the main memory, block 54. In its presently preferred form, the standard fetch size is 32 bytes. Additionally the cache control logic causes the data fetched from main memory to be returned to both the CPU and the first level cache memory, and then updates the address tag and sets the valid bit to valid in the corresponding cache tag entry in cache tag array A, block 56. Furthermore, the cache control logic updates the address tag in a predetermined manner, sets the valid bit to invalid, and sets the interest bit to uninterested in the corresponding cache tag entry in cache tag array B, block 58. 
     In the presently preferred embodiment, a cache tag entry in cache tag array B with the valid bit set to invalid and the interest bit set to uninterested is selected over a cache tag entry in cache tag array B with the valid bit set to invalid and the interest bit set to interested. However, a cache tag entry in cache tag array B with the valid bit set to invalid and the interest bit set to interested is selected over a cache tag entry in cache tag array B with the valid bit set to valid and the interest bit set to interested. If the settings for the valid and interest bits for all cache tag entries in cache tag array B are the same, a cache tag entry is selected arbitrarily. Additionally, under the presently preferred embodiment, the address tag is updated to the address tag of address+32. 
     Still referring to FIG. 3a, if the address of the data being fetched is stored in the second level cache memory, but the data stored in the second level cache memory is invalid, and the prefetch threshold has not been reached, the cache control logic causes the address and standard fetch size (32 bytes in the presently preferred embodiment) to be sent to the main memory, block 60. Similarly, the cache control logic causes the data fetched from main memory to be returned to both the CPU and the first level cache memory, and then updates the address tag and sets the valid bit to valid in the corresponding cache tag entry in cache tag array A, block 62. Furthermore, the cache control logic updates the address tag in a predetermined manner (address tag of address+32 in the preferred embodiment), sets the valid bit to invalid, and sets the interest bit to interested in the corresponding cache tag entry in cache tag array B, block 64. The valid bit of the matching cache tag entry remains set to invalid. 
     Still referring to FIG. 3a, if the address of the data being fetched matches one of the addresses of data stored in the second level cache memory, but the data stored in the second level cache memory is invalid, and the prefetch threshold has been reached, the cache control logic causes the address and the sum of the standard fetch size (32 bytes in the presently preferred embodiment) and the predetermined prefetch size to be sent to the main memory, block 66. In the presently preferred embodiment, the predetermined prefetch size is also 32 bytes. Likewise, the cache control logic causes the data fetched from main memory to be returned to the CPU and the first level cache memory, and then updates the address tag and sets the valid bit to valid in the corresponding cache tag entry in cache tag array A, block 68. Furthermore, the cache control logic causes the data prefetched from memory, i.e. the extra data bytes returned (the second 32 bytes under the presently preferred embodiment), to be returned to the second level cache memory array, and then updates the address tag in a predetermined manner described above (address tag of address+32 under the presently preferred embodiment) and sets to valid bit to valid. The interest bit of the matching cache tag entry remains set to interested. 
     Still referring to FIG. 3a, if the address of the data being fetched matches one of the addresses of the data stored in the second level cache memory array, and the data stored in the second level cache is valid, the cache control logic causes the data to be fetched from the second level memory array and returned to both the first level memory array and the CPU, and then updates the address tag and sets the valid bit to valid in the corresponding cache tag entry in cache tag array A, block 72. Additionally, since the pre-fetch threshold is always reached when the data being fetched are validly stored in the second level of cache memory array, the cache control logic causes the prefetch address, which is generated in the same manner as described above (address+32 under the presently preferred embodiment), and the standard prefetch size (32 bytes under the presently preferred embodiment), to be sent to the main memory, block 74. Similarly, the cache control logic causes the data prefetched from the main memory, i.e. all data bytes returned (all 32 bytes under the presently preferred embodiment), to be returned to the second level cache memory array, and then updates the address tag of the matching cache tag entry to be updated in the same predetermined manner as described above (address tag of address+32 under the presently preferred embodiment. The valid bit and interest bit remain set to valid and interested respectively. 
     Referring now to FIG. 3b, upon receipt of an address from a CPU during a write cycle, the cache control logic causes standard write operations to be performed on the first and second level cache memories, block 82. The standard write operations may be write through or write back, and with or without allocate for write misses. Additionally, if the address is currently cached in the second level of cache memory, the cache control logic updates the address tag in a predetermined manner (address tag of address+32 in the preferred embodiment), sets the valid bit to invalid, and sets the interest bit to uninterested in the corresponding cache tag entry in cache tag array B, block 86. Under the presently preferred embodiment, the address tag is set to null. 
     While the present invention has been described in terms of a presently preferred embodiment, those skilled in the art will recognize that the invention is not limited to the embodiment described. The method and apparatus of the present invention can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of restrictive on the present invention.