Cache system and its operating method

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention generally relates to a cache (cache memory) in a microprocessor system, and more particularly to an auxiliary cache device and a method thereof.

【0002】

[Conventional technology]

Memory speeds are becoming more and more important as processor speeds continue to grow at a faster rate than memory speeds. The cache is a buffer type that is smaller and faster than main memory. The cache is located between the processor and main memory. To improve memory speed, the cache stores a copy of instructions and data from main memory that may be next requested by the processor.

【0003】

The cache can use one buffer or many buffers. Many buffers have different speeds or latency. The wait time is the number of clock cycles required to access the data or instruction stored in the memory or cache.

【0004】

Traditionally, microprocessors have been configured with a single-cycle on-chip cache to reduce memory latency. In high-current, high-performance microprocessors, memory standards for instructions and data currently require two-cycle clocks instead of single clock cycles. As a result, the processor's execution unit requires additional state to access memory, which increases the number of hardware and branch disadvantages. Increasing the number of hardware is increasing power and cost. Increasing branch disadvantages are degrading performance.

【0005】

Since performance is important within some processor applications, a buffer between branch prediction and branch achievement was used to reduce branch disadvantages, which led to even more hardware. However, the goal of an embedded processor is a design goal to improve performance per dollar (speed) and performance per watt, instead of coarse performance. Adding many pipeline stages within the execution unit and increasing the number of hardware is not a satisfactory solution to meet the requirements required by the embedded processor.

【0006】

The cache stores instructions copied from main memory in the cache line. The cache line can also store one or many consecutive instructions. Moreover, each cache line has a tag used to confirm the memory address in the copied instruction. In its simplest form, the tag is all addresses. When a cache line stores multiple instructions, not all addresses need to be stored. For example, if the cache line stores 8 bytes, the three least important bits of the address do not need to be stored in the tag.

【0007】

A cache hit occurs when the request instruction is already stored in the cache. A cache miss has occurred when the request instruction was not stored in the cache line. Normally, when a cache miss occurs, the execution unit must wait or stop until the request instruction is retrieved from main memory before continuing to execute the program that reduces processor performance.

【0008】

In general, multi-level caches are cited as L0 cache and L1 cache and have two buffers with different speeds or different memory latency access times. The L1 cache is usually slower than the L0 cache. The L1 cache receives instructions and data from main memory. The L0 cache receives instructions and data from the L1 cache and supplies them to the execution unit.

【0009】

The cache line of the cache includes a direct map type, a full associative type, and a set associative type with respect to a memory address. Full-associative cache does not tie memory addresses to any particular cache line. Instructions and data are located in any cache line. The direct map type cache connects a specific cache line and each memory address, and arranges an instruction or data stored at the specific address only in the specific cache line. The set-associative cache places several sets or groups of continuous cache lines directly at a specific memory location. However, within a set of cache lines, the caches are fully coupled.

【0010】

Direct-mapped caches have the fastest access times, but tend to develop hotspots. Hotspots are repeated mistakes for the same cash line. The full-associative cache has a higher hit rate than the direct-map cache, but has a slower access time than the direct-map cache. In terms of access time, the set-associative cache is between the direct-map cache and the full-associative cache.

【0011】

The victim cache is a full-associative cache that stores cache lines moved from the L0 cache. The Victim cache line is a cache line in the substituted L0 cache. In one cache system, the Victim cache line is copied to the Victim cache on every cache miss. If the victim cache was complete, a new victim cache line would replace the most recently unused cache line in the victim cache. When a cache miss occurs in the L0 and L1 caches, the cache determines whether the request instruction or data was stored in the victim cache, and if so, the cache is instructed from the victim cache to the execution unit. I will provide a.

【0012】

Victim cache improves performance by storing frequently accessed cache lines after at least one cache miss. Moreover, another technique is used to prevent cache misses. The prefetch technique uses a stream buffer to retrieve instructions and data into the cache before a series of cache misses occur. When a mistake occurs, the stream buffer preempts the instruction that started with the instruction that made the mistake into itself. The next cache access compares the request address with the tags in the stream buffer as well as the addresses or tags in the L1 and L0 caches. If the request instruction was in the stream buffer instead of in the L1 or L0 cache, the cache line containing the request instruction is moved from the stream buffer into the L1 or L0 cache. However, the stream buffer uses additional space on the chip, increasing power consumption.

【0013】

Power efficiency is important. Victim caches and stream caches improve performance, but increase hardware complexity, cost and power consumption.

【0014】

[Problems to be Solved by the Invention]

As described above, a cache configuration that solves the problem of giving an acceptable cache hit rate while maintaining the waiting time for single-cycle access is desired. In addition, it is preferred that the proposed cache configuration reduce power consumption and hardware requirements, which are important design constraints for embedded microprocessors.

【0015】

Therefore, an object of the present invention is to provide an improved device for operating a cache and a method thereof.

【0016】

A related object of the present invention is to create an improved device and a method for reducing the power consumption of the cache.

【0017】

[Means for solving problems]

These and other objectives and advantages in the present invention are achieved by using multiple caches with auxiliary caches and auxiliary filters. The auxiliary cache line stores a cache line (victim) moved from the L0 cache and a prefetch cache moved from the L1 cache. In one embodiment, a specific mixture of victim cache lines and prefetch cache lines is embedded in the hardware in the auxiliary cache. In other embodiments, a particular mixture of cash lines is dynamically assigned.

【0018】

More specifically, the L1 cache receives instructions from external memory. The L0 cache has a cache line of the first set number L0 to receive an instruction from the L1 cache. The auxiliary cache has a victim cache and a prefetch cache. The Victim cache has a cache line of a second set number of VCs, and the prefetch cache has a cache line of a third set number of PCs. The Victim cache receives instructions from the L0 cache. The prefetch cache receives instructions from the L1 cache. The Victim filter stores the address of the 4th set number VF, and the 4th set number VF is a function of L0 and the number of cache writes. The number of cache writes to the L0 and victim caches is reduced with respect to using the L0 cache without the auxiliary cache.

【0019】

Other features and advantages of the present invention will be apparent to those skilled in the art who have considered the disclosure of the present invention. Therefore, a detailed description of preferred embodiments of the present invention is provided below with reference to the drawings.

【0020】

BEST MODE FOR CARRYING OUT THE INVENTION

FIG. 1 is a block diagram of a processor and memory suitable for use in the present invention. The processor 10 has a cache system 12 that gives instructions to the execution unit 14. The cache system 12 searches the external memory 16 for instructions. In other embodiments, the memory 16 is on the same chip as the processor 10.

【0021】

With reference to FIG. 2, a detailed block diagram of the caches constituting the cache system 12 of the present invention is shown. Cache system 12 (see Figure 1) includes L1 cache 18, L0 cache 20, and auxiliary cache 22. Auxiliary filter 24 is used with auxiliary cache 22. The multiplexers 26, 28, and 30 connect the L1 cache 18, the L0 cache 20, the auxiliary cache 22, and the execution unit 14 to each other. In a two-clock cycle, the L1 cache 18 is direct-mapped, storing and accessing 16384 (16K) bytes. In other embodiments, the L1 cache 18 is set-associative. The L0 cache 20 stores 256 bytes or 64 cache lines. Auxiliary cache 22 is fully associative, accessible within a single clock cycle, and has four cache lines that store 128 bytes. Alternatively, the auxiliary cache 22 stores 64 bytes in two cache lines or 96 bytes in three cache lines. Preferably, the L1 cache 18, the L0 cache 20, and the auxiliary cache 22 have the same number of bytes in one cache line. In one embodiment, the cache line stores 32 bytes.

【0022】

More specifically, with reference to FIG. 3, a block diagram of the auxiliary cache 22 and the auxiliary filter 24 in FIG. 2 is shown in detail. The auxiliary cache 22 has a Victor cache 32 and a prefetch cache 34. The victim cache 32 includes the first set of cache lines to store the instructions transferred from the L0 cache 20. The prefetch cache 34 includes a second set of cache lines to store the instructions received from the L1 cache 18. The auxiliary filter 24 includes a victim cache 36 and a prefetch cache 38. The victim filter 36 has a victim memory for storing a set of addresses or tags. The execution unit requests an instruction from the request address. The victim cache 32 is responding to the victim filter 36. When the request instruction is not stored in the L0 cache 20 or the auxiliary cache 22, the L0 cache 20 checks the cache line and replaces it in the L0 cache 20 (instead of the victim cache line). The victim filter 36 determines whether or not a part of the request address matches the address stored in the victim filter 36. If part of the request address matches part of the address stored in Victim Filter 36, then Victim Filter 36 is copying the Victim cache line from the L0 cache into Victim Cache 32. Further, the L0 cache 20 reconstructs a part of the address in the victim cache line, and stores the reconstructed address as a cache line tag having the victim cache line in the victim filter 36.

【0023】

When a cache miss occurs before preempting the instruction to store in the prefetch cache, the prefetch filter 38 is used together with the prefetch cache 32 to pass the address. Therefore, the prefetch filter 38 reduces the number of prefetches from the L1 cache and external memory. In other embodiments, the prefetch filter is not used and the instruction is preempted for each cache miss. The prefetch filter 38 significantly reduces the number of memory accesses when compared to prefetch for each mishandling. Therefore, by reducing the number of memory accesses, the prefetch filter 38 reduces power consumption.

【0024】

The dynamic auxiliary cache controller 40 controls the auxiliary cache 22, and dynamically allocates the cache line of the auxiliary cache 22 between the prefetch cache 34 and the victim cache 32. In one embodiment, the application program dynamically allocates the prefetch cache 34 to the victim cache 32 at compile time. In another embodiment, when the processor executes the application program, the prefetch cache 34 is dynamically allocated to the victim cache 32 at the execution time. Dynamic allocation is controlled by special registers containing known configuration information. In this case, the allocation is controlled by one or more bits in the special resist. The instruction prepares the configuration information by writing to a special register. Moreover, there will usually be only one instruction.

【0025】

In other embodiments, the dynamic auxiliary cache controller 40 is not used. The prefetch cache 34 is built into the hardware and is not allocated to the victim cache 32.

【0026】

FIG. 4 shows an address and a data path in the cache system 12 of the present invention, and includes a part of control logic including a cache control block 42 and a dynamic auxiliary cache control device 40. The execution unit 14 has a program counter 44. The program counter 44 stores the address of the next instruction to be searched, that is, the address of the request instruction, and outputs the address on the address bus 15.

【0027】

The L1 cache 18 is connected to the data bus 19 and receives instructions from the external memory. In this embodiment, the L1 cache includes 32-byte cache lines 18a, 18b, 18c, and is a direct-map type 32-Kbyte cache, and has a two-cycle access waiting time. Each cache line 18a, 18b, 18c of the L1 cache 18 stores a tag and a set of instructions. In one embodiment, the tag is the address of the first byte stored in the cache line. Since the cache line stores 32 bytes, the less important 5 bits (bits 4: 0) in the address are not stored in the tag. In the direct map cache, the tag size is further reduced because the cache line position is a function of the address. In particular, since the L1 cache 18 stores 32 Kbytes and each cache line is 32 bytes wide, the L1 cache 18 stores 1024 cache lines and the cache line is 2.¹⁰Is equal to, and is displayed by 10 bits. Therefore, it is not necessary to store 10 bits of the address in the tag. As shown in Figure 4, the address bits (14: 5) are input to the multiplexer 52 and store the instructions and the most important address bits (31:15) in the appropriate cache line.

【0028】

The comparator 54 compares a part of the request address provided by the program counter 44 with the tags stored in each cache line. If a part of the request address is the same as a part of the tag, the comparator 54 outputs a signal called an L1 hit to the cache control block 42, indicating that a hit has occurred in the L1 cache 18. The cache line provided by the cache control block 42 stores the request instruction and is transferred from the L1 cache 18 to the L0 cache 20 via the L1 cache data path 21 and the multiplexer 26. Then, the cache control block 42 transfers the request instruction from the L0 cache 20 to the pipeline in the execution unit 14 via the multiplexer 30.

【0029】

In the present embodiment, the L0 cache 20 includes a 32-byte cache line and is a direct-map type 512-byte cache, and therefore has 16 cache lines. Moreover, the L0 cache 20 stores a tag and a set of instructions on each cache line. Since the L0 cache 20 is a direct map type, the multiplexer 56 uses address bits (8: 5) to store instructions or data inside one of the 16 cache lines. The tag for L0 cache 20 stores the address from 31 bits to 39 bits.

【0030】

The comparator 58 compares a part of the request address (bit (31: 9)) with the tag stored in the L0 cache 20. If part of the request address is the same as part of the tag stored in L0 cache 20, the comparator 58 outputs a signal called an L0 hit to cache control block 42 and a hit occurs in L0 cache 20. It shows that. In the response of the L0 hit signal, the cache control block 42 gives an instruction at the request address and is output from the L0 cache 20 to the pipeline of the execution unit 14 via the multiplexer 30.

【0031】

The auxiliary cache 22 has a 32-byte cache line and is a full-associative 128-byte cache, and therefore has four cache lines. The auxiliary cache 22 stores a tag and a set of instructions on each cache line. The auxiliary cache 22 has three victim cache lines 32a, 32b, 32c and one prefetch cache line 34a. The Victim Cash Line is part of Victim Cash 32. The prefetch cache line 34a is part of the prefetch cache 34. In other embodiments, the prefetch cache 34 has one or more prefetch cache lines. As described above, with respect to FIG. 3, the prefetch cache line 34a can be designated as the victim cache line and included in the victim cache 32. The multiplexer 28 supplies a Victim cache line from the L0 cache 20 stored in the Victim cache 32 and a prefetch cache line from the L1 cache 18 stored in the prefetch cache 34.

【0032】

The multiplexer 62 supplies tags from the Victim cache line of the L0 cache 20 to the appropriate cache line of the Victim cache 32, and also supplies tags from the address bus 15 to the prefetch cache 34. Because the L0 cache tag stores 31: 9 bits and the auxiliary cache tag stores 31: 5 bits, the logic circuit in the L0 cache 20 reconstructs the 8: 5 bits, The L0 cache 20 supplies 31: 5 bits to the multiplexer 62 and stores it in the tag of the appropriate cache line in the victim cache 32.

【0033】

When the cache line is transferred from the L0 cache 20 or the L1 cache 18 to the auxiliary cache 22, the address of the transfer instruction is supplied to the address bus 15 by the program counter 44. The 31: 5 bit of that address is stored as a tag on the transfer cache line in the victim cache 32 or prefetch cache 34 via the multiplexer 62.

【0034】

A set of comparators 72,74,76,78 compares the tags stored in each cache line of the auxiliary cache 22 with the request address output by the program counter 44. If the tag matches the corresponding part of the request address, the comparators 72,74,76,78 output high voltage levels, indicating that a hit has occurred in the cache line of the auxiliary cache 22. The output of the comparators 72,74,76,78 is supplied to the OR gate 80, and a victim hit signal indicating a hit is generated in the victim cache 32 supplied to the cache control block 42.

【0035】

The tag of the prefetch cache line 34a is connected to the comparator 78. When the prefetch cache line 34a is used as the cache line for the victim cache 32, the dynamic auxiliary cache controller 40 is generating a disabled prefetch signal with a high voltage level. When the disable prefetch signal is at a low level, it is supplied to the inverter 82 to generate an enable prefetch signal having a high level. In short, the enable prefetch signal has a high voltage level when the prefetch cache signal is used to preempt instructions. The AND gate 84 generates a prefetch hit signal when the comparator 78 indicates that the enable prefetch signal is at a high voltage level and the prefetch cache 34 matches that voltage level. A prefetch hit signal is supplied to the cache control block 42. AND gates allow interrupts when the prefetch cache line is used as part of the victim cache. When the comparator 78 indicates that the enable prefetch signal is at a low voltage level and the prefetch cache 34 matches that voltage level, the AND gate 86 generates a victim cache line hit signal supplied to the OR gate 80. ..

【0036】

When either the victim hit signal or the prefetch hit signal is at a high voltage level, the OR gate 88 generates an auxiliary hit signal, indicating that a hit has occurred in the auxiliary cache.

【0037】

When either the auxiliary hit signal or the L0 hit signal is at a high voltage level, another OR gate 90 generates a one-cycle access signal, which allows the instruction to be valid and through the pipeline within execution unit 14. ing.

【0038】

The Victim filter 36 has a memory 102 like a FIFO. The memory 102 stores three addresses in entries 102a, 102b, 102c. Entries 102a, 102b, 102c store the last three misaddresses. The entries 102a, 102b, 102c are input to the comparators 104, 106, 108, respectively. Moreover, the request address output by the program counter 44 is supplied to the comparators 104, 106, 108. If any of the addresses stored in entries 102a, 102b, 102c match the request address, the corresponding comparator outputs a high voltage level. The output of the comparators 104, 106, 108 is output to the OR gate 110 to generate a transfer signal of the L0 victim to the auxiliary cache. In response to the transfer signal, the cache control block 42 provides a cache line. The cache line stores the instruction at the matching address of the L0 cache 20, and is transferred from the L0 cache 20 to the victim cache 24 of the auxiliary cache 22.

【0039】

The prefetch filter 38 has an incrementer 112, a multiplexer 114, and a memory 116. The incrementer 112 increases the address output by the program counter 44 up to a preset total number of bits, such as 4 bits for 32 bits. The memory 116 stores the next address to be preempted and is read from the incremental 112. The address bits stored in the memory 116 correspond to the address bits stored in the tag of the auxiliary cache 22. The comparator 118 compares the address stored in the memory 116 of the prefetch filter 38 with the request address, and outputs a high voltage level if both match. The output of the comparator 118 is the L1 request signal to the auxiliary prefetch. The cache control block 42 generates a signal by the request signal, and transfers the cache line from the L1 cache 18 on the L1 data path 21 to the prefetch cache 23 via the multiplexer 62.

【0040】

When the prefetch cache line is dynamically allocated, the prefetch filter 38 is separated from the victim filter 36. Further, even if the prefetch cache 34 is dynamically assigned to the victim cache 32, the prefetch filter 38 is not dynamically assigned to the victim filter 36.

【0041】

The cache control block 42 receives the L1 hit signal, the L0 victim transfer signal to the auxiliary cache, the L1 request signal to the auxiliary prefetch, the prefetch hit signal, the victim hit signal, the auxiliary hit signal, and the one-cycle access signal. Generate a control signal. The control signals include a victim filter control signal, an L1 cache control signal, a prefetch filter control signal, an auxiliary cache control signal, and an L0 cache control signal.

【0042】

A salient feature of the present invention is that the auxiliary cache stores both a moving cache line (victim) from the L0 cache 20 and a prefetch cache line from the L1 cache line 18. In short, on each cycle, the program counter supplies the request address to the address bus 15. The L1 cache 18, the L0 cache 20, the auxiliary cache 24, the victim filter 36, and the prefetch filter 38 compare the stored tags and addresses at the same time as the request address. If a cache hit detects either the L0 cache 20 or the auxiliary cache 22's victim cache line, the request instruction or data stored in the cache line is fed to the processor's execution unit within a single cycle and the instruction or instruction or Data is transferred to L1 cache 20. After the transfer to the L0 cache 20, the allocated prefetch cache line in the auxiliary cache is weakly shown and the prefetch cache line can receive additional prefetch data. If the request address misses in L0 cache 20 and auxiliary cache 22, but hits in L1 cache 18, the instruction is L1 in the next clock cycle, assuming 2 cycles of access to L1 cache 18. The pipeline gets stuck while being read from cache 18.

【0043】

In addition, the L0 cache 20 receives instructions from the L1 cache 18 based on the match within the Victim filter 36. Auxiliary cache 22 receives a new victim from L0 cache 20 and discards the most recently unused cache line of victim cache 32. The victim filter 36 stores a set of missed addresses in the L0 cache 20 and the L1 cache 18. If you make a mistake and the same cache line in L0 cache 20 did not make a mistake before, the victim cache line will not be stored in victim cache 32 and its address will be stored in victim filter 36. .. In this way, power consumption is reduced by reducing the number of writes to the victim cache.

【0044】

FIG. 5 is a flowchart showing one embodiment of the method using the cache system of the present invention. In step 152, an L1 cache, an L0 cache, a victim cache, a prefetch cache, a victim filter, and a prefetch filter are given. L1 cache, L0 cache, victim cache, and prefetch cache store cache lines. Within each cache line, at least a part of the address is stored as an L1 tag, an L0 tag, a victim cache tag, and a prefetch cache tag. The victim filter and the prefetch filter store the victim filter address and the prefetch filter address, respectively. The victim filter stores a preset number of victim filter addresses. The victim filter address is a function of the number of cache lines in the L0 cache and the number of cache writes. The number of cache writes to the L0 and Victor caches is reduced with respect to the use of the L0 cache without using the Victor cache.

【0045】

In step 154, the request address is supplied to the address bus and the request instruction is searched. In step 156, the request address compares the L1 tag, the L0 tag, the victim tag, the prefetch tag, the victim filter address, and the prefetch filter address at the same time. In step 158, if a cache hit is detected in the cache line of the L0 cache, the request instruction stored in the cache line is supplied to the execution unit.

【0046】

In step 160, if a cache hit is detected in the cache line of the victim cache, the request instruction stored in the cache line that generated the hit is supplied to the execution unit. The cache line that stores the request instruction is not transferred from the Victim cache to the L0 cache. Instead, the cash line remains within the Victim cache. Only the prefetch cache line is transferred from the auxiliary cache to the L0 cache.

【0047】

In step 162, if the request address is missed in the L0 cache and the auxiliary cache, but is hit in the L1 cache, each cache line storing the request instruction in the L1 cache is checked. Moreover, the victim cache line in the L0 cache is checked to replace the checked cache line. If the request address matches any of the addresses stored in the victim filter, the victim cache line is stored in the victim cache based on the match to the request address of the victim filter in the agreement step. Victim Cash replaces the least recently used Victim Cash Line with the new Victim Cash Line. The Victim cache line in the L0 cache has been replaced by the confirmed cache line. The request address is stored in the victim filter, and the request instruction is supplied to the execution unit.

【0048】

In step 164, a prefetch address is generated by increasing the request address to the next consecutive address in order to preempt the cache line. The prefetch address is stored in the prefetch filter. If the new request address does not match the prefetch address stored in the prefetch filter, it will be stored. In this method, after making a mistake in consecutive first request addresses and second request addresses, the cache line is preempted from the L1 cache to the prefetch cache using the prefetch filter.

【0049】

In step 166, the prefetch cache is dynamically allocated and becomes part of the victim cache, increasing the number of cache lines stored in the victim cache, but the prefetch filter is not cracked into the victim filter.

【0050】

In general, the Victim cache performs at least the most recently used replacement technique and holds the most frequently replaced cache lines. In addition, performance gains can be achieved by increasing the size of the victim cache. Basically, with increased size, the Victim cache holds many of the most frequently accessed cache lines. However, since the victim cache is a full-associative type, increasing the size of the victim cache increases the execution cost. That is inconsistent with the general design constraints of embedded processors.

【0051】

In one embodiment, the Victim filter is not used and the Victim cache accepts all replacement cache lines. However, in a preferred embodiment, the Victim filter stores the most frequently accessed cache lines in the Victim cache. The Victim filter monitors recent cache misses and determines which cache line to keep and replace by storing a tag for one of the most recently missed cache lines in the L0 and auxiliary caches. In one embodiment, the victim cache filter uses a FIFO buffer to store its address. When a mistake occurs in the L0 cache or the auxiliary cache, the replacement cache line (victim) from the L0 cache is stored in the victim cache only when a hit is detected in the victim filter.

【0052】

FIG. 6 is a graph of the average number of instructions (IPC) per cycle (y-axis) with respect to the number of addresses (x-axis) stored in the victim filter from the simulation results. In the simulation, all caches have a 32-byte cache line. The L1 cache is a direct map type and has 16 Kbytes or 512 cache lines. The auxiliary cache has four cache lines. The number of Victim filter addresses has changed from 1 to 64, and the size of the direct-mapped L0 cache has changed from 128 bytes (4 cache lines) to 1024 bytes (32 cache lines). The simulation results given in FIGS. 6, 7A, 7B, and 8 are obtained by processing the trace files in eight SPEC92 integer benchmarks from the configured MIPS R3000 processor instructions.

【0053】

In the simulation, the L0 cache and the auxiliary cache are accessed within a single cycle, and the L1 cache is accessed within two clock cycles. For each memory criterion, address-tag comparisons are performed simultaneously for the L1 cache, L0 cache, and auxiliary cache. Simultaneous tag comparison improves cache performance because the L1 cache supplied the request instruction or data to the execution unit within the next clock cycle. If a hit is detected in the L0 cache or auxiliary cache, the simulation assumes that the read from the L1 cache is before significant power is consumed, such as when operating a column line or sense amplifier. To be stopped. The simulation model uses a single read / write for each cache. Therefore, if the auxiliary cache is busy reading the Victim from the L0 cache, it will stop preempting from the L1 cache. Published figures for instructions per cycle (IPC) do not include other constructive effects such as branch penalties, branch predictions, data dependencies, buffers, etc., or data flow effects. Moreover, reading instructions and data from external memory requires 16 cycles. Therefore, the published IPC figures impose an upward limit on the performance of the entire system. For simulation, the size of the L0 cache is varied from 32 bytes to 1024 bytes, that is, from one cache line to 32 cache lines. However, in another preferred embodiment, for power efficiency, the practical limit on the size of the L0 cache is 256 bytes or 8 cache lines.

【0054】

In a preferred manner, the size of the L1 cache ranges from 16 Kbytes to 32 Kbytes, and the size of the L0 cache ranges from 128 bytes to 256 bytes. Similarly, if the number of cache lines in the auxiliary cache is changed from 1 to 6, the auxiliary cache actually has 4 or less cache lines.

【0055】

In fact, Figure 6 shows the result of the size of the victim filter stored from one address to six addresses and the result without the victim filter (displayed as "no filter"). The unfiltered result gives an upward limit on the number of times memory can be read and written. The average number of instructions per cycle is virtually independent of the number of cache lines in the Victim filter. However, for the 256-byte L0 cache, the Victim filter that stores three addresses improved the performance by about 1% due to the configuration of the unfiltered cache line.

【0056】

More importantly, the number of cache lines stored within the Victim filter has a substantial effect on the amount of memory traffic. Power consumption correlates with the number of memory activities in the L1 cache, L0 cache, and auxiliary cache, such as the number of writes to the L1 cache, L0 cache, and auxiliary cache. For a rough comparison, reading or writing to either the L0 cache or the auxiliary cache requires 20% of the power required to access the L1 cache.

【0057】

7A and 7B are graphs relating to the number of addresses stored in the victim filter (x-axis) for different sizes of the L0 cache and the total number of writes to the L0 cache and auxiliary cache (y-axis). For each L0 cache size, the total number of writes in FIGS. 7A and 7B is standardized to a basic cache configuration that does not use an auxiliary cache for the size of the L0 cache. For example, results for an L0 cache with an auxiliary cache and a size of 128 bytes are standardized to results for an L0 cache without an auxiliary cache and a size of 128 bytes. Results for an L0 cache with an auxiliary cache and a size of 256 bytes are standardized to results for an L0 cache without an auxiliary cache and a size of 256 bytes.

【0058】

As Figure 7A shows, the smaller the auxiliary cache, the lower the number of write activities with respect to the basic configuration. Therefore, by storing fewer addresses, the Victim filter is very limited, keeping only the most frequently moved cache lines in the auxiliary cache. However, as the number of addresses stored in the victim filter increases, the limit of the victim filter is reduced and the number of memory activities is substantially increased.

【0059】

FIG. 7B shows, in more detail, the results of FIG. 7A for the size of the Victim filter over the range 1-10. A relatively large L0 cache, such as the L0 cache that stores 1024 bytes (32 cache lines), is relatively unaffected by the size of the victim filter compared to the L0 cache that stores 512 bytes or less. When the Victim filter stores 4 or more cache lines, the write activity of 256 bytes (8 cache lines) is significantly increased.

【0060】

Importantly, even if the prefetch cache is dynamically assigned to the victim cache, the prefetch filter is not assigned to the victim filter and remains separate. As can be seen from Figure 7B, if the prefetch filter is dynamically coupled to the victim filter, the number of addresses stored in the victim filter and the number of cache write activities increase. As a result, power consumption is increased, which contradicts one of the objects of the present invention.

【0061】

Figure 8 shows the results of a simulation in which the number of addresses stored in the prefetch filter should be determined. In the simulation, the number of addresses has been changed from 1 to 32, showing unfiltered results. The L0 cache and the L1 cache store 256 bytes (8 cache lines) and 16 Kbytes (512 cache lines), respectively. To isolate the effects of the prefetch filter, the simulation results show achievable performance with all victim cache lines excluded from the auxiliary cache. As shown in Figure 8, when the size of the prefetch filter is increased from 1 to 32, the average number of instructions (IPCs) per cycle remains virtually unchanged. Therefore, the prefetch filter needs to store only one address.

【0062】

When pre-empting without a filter, pre-emption is started for each cache miss or by detecting a hit in the prefetch filter. When each error occurs between the L0 cache line and the auxiliary cache's victim design cache line when preempting with a filter, the next consecutive address is a prefetch filter, such as the address with 1 added. It is stored in. Consecutive mistakes in the L0 cache and auxiliary cache hit in the prefetch filter and start preempting instructions from the L0 cache into the prefetch cache. While preempting, the auxiliary cache first looks into the L1 cache for the request cache line. If the cache line is not in the L1 cache, the auxiliary cache initiates preemption from external memory. In the simulation, external memory access requires 16 cycles.

【0063】

The prefetch filter limits the number of memory activities and therefore power consumption. However, the prefetch filter described above improves performance only if one non-continuous memory access suppresses the memory reference pattern. In another embodiment, for a high performance application, the processor via the cache control block removes the prefetch filter by forcing a hit preemption on all cache accesses.

【0064】

Other features and advantages of the present invention will be apparent to those skilled in the art who have considered the disclosure of the present invention. Therefore, the scope of the present invention may be limited only by claims.

【0065】

[Effect of the invention]

According to the present invention, the cache system has a multi-level cache configuration, and the number of cache writes to the L0 cache and the victim cache is reduced by using the L0 cache without using the auxiliary cache. It solves the problem of giving an acceptable cache hit rate while maintaining cycle access latency, and also addresses key design constraints for embedded microprocessors: power consumption and hardware requirements. It can be reduced.

[Simple explanation of drawings]

[Figure 1]

It is a block diagram of the optimum processor and memory used in the present invention.

[Figure 2]

It is a block diagram of the cache structure in this invention.

[Fig. 3]

It is a detailed block diagram of the auxiliary cache and the auxiliary filter in Fig. 2.

[Fig. 4]

It is a detailed diagram of one embodiment in the cache configuration of FIG.

[Fig. 5]

It is a flowchart of the method using the cache of this invention.

[Fig. 6]

A graph of the number of instructions (IPCs) per cycle as a function of the number of addresses stored in the Victim filter for various sizes of the L0 cache.

[Fig. 7A]

It is a graph of the number of cache writes as a function of the number of addresses stored in the victim filter for various sizes of the L0 cache.

[Fig. 7B]

It is a detailed graph of FIG. 7A for a Victim filter stored from addresses 1 to 10.

[Fig. 8]

The result of the simulation to determine the number of cache lines to be stored in the prefetch filter is shown.

[Explanation of symbols]

10 processors 12 cache system 14 Execution unit 15 address bus 16 External memory 18 L1 cache 19 Data bus 20 L0 cache 21 L1 cache data path 22 Auxiliary cache 24 Auxiliary filter 26,28,30 multiplexer 32 Victim Cash 32a, 32b, 32c prefetch cache line 34 Prefetch cache 34a prefetch cache line 36 Victim Filter 38 Prefetch filter 40 Dynamic auxiliary cache controller 42 Cache control block 44 Program counter 52,56,62 Multiplexer 54,58 Comparator 72,74,76,78 Comparator 80,88,90 OR gate 82 Inverter 84,86 AND gate 102 memory 102a, 102b, 102c entries 104,106,108 Comparator 110 OR gate 112 Incrementa 114 Multiplexer 116 memory 118 Comparator 152,154,156,158,160,162,164,166 steps