Cache memory and control method thereof with cache hit rate

A cache memory comprises a data array that stores a cashed block; a first address array that stores an address of the cached block; a second address array that stores an address of a first block to be removed from the data array when a cache miss occurs; and a control unit that transmits to a processor the first block stored in the data array as a cache hit block, when the address stored in the second address array results in a cache hit during a period before a second block which has caused the cache miss is read from a memory and written into the data array.

REFERENCE TO RELATED APPLICATION

The present application is the National Phase of PCT/JP2010/050907, filed Jan. 25, 2010, which is based upon and claims the benefit of the priority of Japanese Patent Application No. 2009-016224 (filed on Jan. 28, 2009), the disclosure of which is incorporated herein in its entirety by reference.

TECHNICAL FIELD

The present invention relates to a cache memory and a control method of a cache memory. More specifically, the invention relates to a cache memory and a control method of a cache memory accessed by a multi-core or multi-thread processor.

BACKGROUND

Cache memories improve memory access performance of a computer based on temporal locality of access in which once-accessed data is likely to be accessed again and spatial locality of access in which it is highly probable that data close to the once-accessed data will be accessed. The capacity of a cache memory is, however, limited. Accordingly, it is necessary to efficiently utilize the limited capacity to improve a cache hit ratio. A location of the cache memory where a block to be cached is stored differs according to the mapping method of the cache memory.

In a full associative method, each block can be stored in any location of a cache memory. Thus, the cache memory can be efficiently utilized. In the full associative method, however, when searching whether or not there is a block in the cache, all blocks in the cache must be searched. Accordingly, it takes time to perform the search.

A direct mapping method is a method by which a search within a cache memory can be performed most simply. In the direct mapping method, a location where each block is stored is limited to a predetermined portion of the cache memory. In the direct mapping method, however, the location where each block is stored is fixed. Accordingly, a plurality of blocks to be stored in a same location cannot be simultaneously cached in the cache memory.

An N-way set associative method is intermediate between these two methods. In the N-way set associative method, there are N locations for storing a certain block, in a cache memory. That is, N blocks to be stored in a same location in the cache memory can be simultaneously cached. Further, when it is searched whether or not a block has been cached in the cache memory, N locations should be searched.

Patent Document 1 describes a victim cache memory for storing a block targeted for replacement and evicted from a cache memory so as to cache another block when a cache miss has occurred. The victim cache in Patent Document 1 is a cache of a small capacity (of several blocks) using the full associative method, and caches a block evicted from the cache memory. When a block in the victim cache memory has resulted in a cache hit, an evicted block and the block which has resulted in the cache hit are swapped (exchanged) between the cache memory and the victim memory.Patent Document 1: JP Patent Kokai Publication No. JP-A-4-270431

SUMMARY

The entire disclosure of Patent Document listed above is incorporated herein by reference thereto. The following analyses are given by the present invention.

The victim cache memory described in Patent Document 1 has just the capacity of several blocks. Thus, a period of time where a block is held in the victim memory is considered to be short. The technology described in Patent Document 1 is a technology for improving a cache memory hit ratio by using a high likelihood of data that has been cached and evicted being accessed again immediately after the data has been evicted.

On the other hand, due to advancement of multi-core technology and multi-thread technology in a CPU, memory accesses by a plurality of threads may simultaneously occur to a cache memory. These memory accesses are made by the plurality of independent threads, and have no causal relation. A plurality of cache misses may therefore simultaneously occur. Accordingly, compared with the case of a single core or a single thread, the number of the cache misses that simultaneously occur may increase, so that a plurality of memory accesses caused by the cache misses may be simultaneously issued.

In the technology of the victim cache memory described in Patent Document 1, memory accesses from a multi-core or multi-thread CPU in which a plurality of cache misses may simultaneously occur cannot be efficiently processed. The reason for this is as follows. The victim cache memory is the cache memory of the small capacity (of several blocks) using the full associative method. Thus, when a plurality of cache misses have simultaneously occurred, a capacity of blocks which have caused the cache misses exceeds the capacity of the victim cache memory. When the capacity of the victim cache memory is increased so as to accommodate the plurality of cache misses, it is difficult to adopt the full associative method.

Therefore, there is a need in the art to provide a cache memory and a control method of a cache memory that improve a cache hit ratio of memory accesses from a multi-core or multi-thread processor.

According to a first aspect of the present invention, there is provided a cache memory comprising:a data array that stores a cashed block;a first address array that stores an address of the cached block;a second address array that stores an address of a first block to be removed from the data array when a cache miss occurs; anda control unit which transmits to a processor the first block stored in the data array as a cache hit block, when the address stored in the second address array results in a cache hit during a period before a second block that has caused the cache miss is read from a memory and written into the data array.

According to a second aspect of the present invention, there is provided a cache memory comprising:an address array that stores an address of a block to be removed from a data array when a cache miss occurs; anda control unit that transmits to a processor the block stored in the data array as a cache hit block, when the address stored in the address array results in a cache hit during a period before a block that has caused the cache miss is read from a memory and stored in the data array.

According to a third aspect of the present invention, there is provided a control method of a cache memory comprising a data array that stores a cached block, a first address array that stores an address of the cached block, and a second address array, the method comprising:storing in the second address array an address of a first block to be removed from the data array when a cache miss occurs; andtransmitting to a processor the first block stored in the data array as a cache hit block, when the address stored in the second address array results in a cache hit during a period before a second block that has caused the cache miss is read from a memory and written into the data array.

The present invention provides the following advantage, but not restricted thereto. According to the cache memory and the control method of the cache memory of the present invention, a cache hit ratio of memory accesses from a multi-core or multi-thread processor can be improved.

PREFERRED MODES

In the present disclosure, there are various possible modes, which include the following, but not restricted thereto. A cache memory according to an exemplary embodiment will be described with reference to drawings.FIG. 1is a block diagram showing a configuration of the cache memory in the present exemplary embodiment. With reference toFIG. 1, a cache memory10comprises an address array A11, a data array12, an address array B13, and a control unit14. The cache memory10is connected to a memory20and a processor30.

The first address array A11stores the address of a cached block. The data array12stores the cached block. The second address array B13stores the address of a first block which is a block to be evicted from the cache memory when a cache miss occurs.

Before a second block, which is a block that has caused the cache miss, read from the memory20and written into the data array12, the control unit14transmits the first block stored in the data array12to the processor30as a cache hit block when the address stored by the address array B13has resulted in a cache hit.

According to the cache memory in this exemplary embodiment, the block (or the first block) to be evicted due to the cache miss can be processed as the cache hit block during a period where the block (or the second block) that has caused the cache miss is read from the memory20and is then stored in the data array12of the cache memory10. Accordingly, a follow-on access to the block to be evicted due to the cache miss is cache hit for a given period of time. A cache hit ratio can be thereby improved. Further, according to the cache memory in the present exemplary embodiment, even if a lot of cache misses have simultaneously occurred and even if there are a lot of blocks to be evicted, cash hit can be made to occur for a given period of time. A block which has caused a cache miss is defined to be a block that is not stored in the data array12of the cache memory10, and to be read from the memory20and stored in the data array12.

Preferably, the control unit14invalidates the address of the first block stored by the address array B13when writing the second block read from the memory20into the data array12. This operation is performed to allow the control unit14to recognize that the first block has been replaced by the second block in the data array12and the first block is no longer present in the cache memory10.

Preferably, the address array B13stores an identifier for a way of the data array12in which the first block is stored. This operation is performed because the cache memory and a control method of the cache memory according to the present exemplary embodiment can be expanded to an N-way associative method.

Preferably, the address array B13stores a flag indicating whether or not the first block has resulted in the cache hit and has been rewritten. In this case, before the second block is read from the memory20and written into the data array12, the control unit14preferably refers to the flag stored in the address array B13and, if the first block has been rewritten, writes back the first block into the memory20. This operation is performed, because, in doing so, cache coherency (coherency of the cache) can be maintained.

Preferably, an electronic computer comprises the cache memory10described above. The electronic computer may further comprise a multi-core or multi-thread processor. By including the cache memory according to this exemplary embodiment, a cache hit ratio of memory accesses can be improved in the electronic computer including the multi-core or multi-thread processor.

FIRST EXAMPLE

A cache memory according to a first example will be described in detail with reference to drawings.

Referring toFIG. 2, the cache memory in the first example comprises an address register101, an address array102, an eviction block address array103, a data array104, a comparator A105, a comparator B106, and a control unit120.

The address array102is a memory having 2nentries. One entry includes high-order in bits107, which are a part of the address of a block and a status bit string108indicating a status of that block.

The eviction block address array103is a memory having 2nentries. Each entry includes high-order m bits109, which are a part of the address of a block, and a status bit string110indicating a status of that block.

The data array104is a memory having 2nentries. Each entry stores a block111of 2kbytes.

The comparator A105compares the high-order m bits114in the address register with the address of the high-order in bits107of the entry in the address array102accessed using n bits112in the address register101as an offset113. When the m bits114match the high-order m bits107, it means that the entry of the block is already present in the cache memory.

The comparator B106compares the high-order m bits114in the address register with the address of the high-order m bits109of the entry in the eviction block address array103accessed using then bits112in the address register101as the offset113. When the m bits114match the high-order m bits109, it means that the entry of the block is already present in the cache memory.

The control unit120controls the cache memory, based on a comparison result A115from the comparator A105, a comparison result B116from the comparator B106, a instruction type (load or store) from a CPU, the status bit string108in the address array and the status bit string110in the eviction block address array which have been read.

In the following explanation, it is assumed that each address stored in the address register101is composed of 64 bits, k=6 or the size of each block is 64 bytes, n=10 or the number of entries of each of the address array102, eviction block address array103, and the data array104is 1024, and m=48. It is also assumed that the cache memory in the present example is a cache memory using a direct mapping method.

Next, operation of the cache memory inFIG. 2will be described. When an access to the cache memory is made, the address of the access is set in the address register101. The address may be a logical address, or a physical address. It is assumed herein that the address is the physical address translated from a virtual address by some address translation means.

Since the size of each block is 64 bytes, low-order 6 (k) bits118in the address register101constitute the address of the block. Using the 10(n) bits112which are higher-order than the low-order 6 (k) bits118as the offset113, an entry in each of the address array102and the eviction address array103is read.

The comparator A105compares the high-order 48 (m) bits107of the address of the read entry with the high-order 48 (m) bits114in the address register101, and the comparator B106compares the high-order 48 (m) bits109of the address with the high-order 48 (m) bits114in the address register101to determine whether or not the entry of that block is already present in the cache memory.

The comparison result A115and the comparison result B116are supplied to the control unit120together with the instruction type (load, store)117, the status bit string108of the entry read from the address array102and the status bit string110of the entry read from the eviction block address array103to determine the operation of the cache memory. Determination of the operation by the control unit120and details of the operation will be described later in a part of description of the operation.

FIG. 3describes the status bit strings108and110inFIG. 2in detail. Three status bits201in the address array102are composed of three bits which are constituted from a flag V202indicating whether or not the entry of the address array is valid, a flag D203indicating whether or not the block of the data array has been rewritten, and a flag F204indicating whether or not the block of the address array is being read from the memory.

When the entry of the address array102is valid, the flag V202indicates 1. When the entry of the address array102is invalid, the flag V202indicates 0. When the block has been rewritten, the flag D203indicates 1. When the block has not been rewritten, the flag D203indicates 0. When the block of the address array is being read from the memory, the flag F204indicates 1. When the block of the address array is not being read from the memory, the flag F204indicates 0.

Two status bits205of the eviction block address array103includes two bits which are a flag V206indicating whether or not the entry of the eviction block address array is valid and a flag D207indicating whether or not the block of the data array has been rewritten.

When the entry of the eviction block address array103is valid, the flag V206indicates 1. When the entry of the eviction block address array103is invalid, the flag V206indicates 0. When the block has been rewritten, the flag D207indicates 1. When the block has not been rewritten, the flag D207indicates 0.

Next, operation in the first example will be described in detail with reference to the components inFIG. 2and the bit strings inFIG. 3each indicating a status and others.

FIG. 4is a flowchart explaining determination of the operation by the control unit120inFIG. 2and the operation.

An accessed address is stored in the address register101inFIG. 2, and entries in the address array102, the eviction block address array103, and the data array104are accessed using the 10 (n) bits112in the address register101.

Determination of the operation by the control unit120and the operation at this point will be described.

The control unit120determines a process to be performed according to the instruction type117from the CPU (in step S301).

First, when the instruction type117is store (store in step S301), the control unit120determines whether or not a cache hit has occurred (in step S303). The control unit120determines whether or not accessed data has resulted in the cache hit according to the comparison result A115from the comparator A105, the comparison result B116from the comparator B106, the status bit string108in the address array102and the status bit string110in the eviction block address array103(in step S303). When the comparison result A115indicates a match and the flag V202of the status bit string108indicates 1, or when the comparison result B116indicates a Match and the flag V206of the status bit string110indicates 1, the control unit120determines that the accessed data has resulted in the cache hit (Yes in step S303).

On the other hand, when the comparison result S115indicates a mismatch or when the flag V202of the status bit string108indicates 0, the control unit120determines that the accessed data has caused a cache miss when the comparison result B116indicates a mismatch or when the flag V206of the status bit string110indicates 0 (No in step S303).

When the accessed data has resulted in the cache hit (Yes in Step S303), the control unit120determines in which one of the normal address array102and the eviction block address array103the cache hit has occurred, based on whether or not the comparison result A115has indicated the match or the comparison result B116has indicated the match (in step S329).

When the cache hit has occurred in the normal address array (No in step S329), the control unit120determines whether or not the block of the accessed address is being read, based on the flag F204of the status bit string108(in step S323). When the flag F204indicates 1, and then when the control unit120determines that the block is being read (Yes in step S323), the control unit120waits for completion of the reading. When the flag F204indicates 0 and then when the control unit120determines that the block is not being read (No in step S323), the control unit120specifies the word of data in the block, based on low-order 6 (k) bit data (in step S306), and writes write data in the word, and sets the flag D203of the status bit string108to 1 (in step S307).

When the cache hit has occurred in the eviction block address array103(Yes in step329), the control unit120specifies the word of data in the block, based on the data of low-order 6 (k) bits, and writes write data to the word (in step S332). Then, the control unit120sets the flag D207of the status bit string110to 1 (in step S333).

When the accessed data has caused the cache miss (No in step303), the control unit120determines whether or not replacement of a cache block will occur (in step S308). When there is a block which already uses the entry (for which the flag V202of the status bit string108indicates 1), the control unit120determines that the replacement will occur (Yes in step308). On the other hand, when that entry is vacant (or the flag V202of the status bit string108indicates 0), the control unit120determines that the replacement will not occur (No, in step308).

When the control unit120determines that the replacement of the block will not occur (No in step S308), the control unit120stores the high-order m bits114in the address register101in the high-order m bits in the address array102, sets the flag V202and the flag F204of the status bit string108to 1, and reads the block from the memory. Then, when the read block has arrived, the control unit120writes the read block to the block111of the data array104, and sets the flag F204of the status bit string108in the address array102to 0 (in step S311). Then, the control unit writes the data into the block111(in step S306), and sets the flag D203of the status bit string108in the address array102to 1 (in step S307).

When the control unit120determines that the replacement of the block will occur (in step S309), the control unit120performs the replacement of the block and block reading (in step S312). Step S312will be described later, with reference toFIG. 5. After step S312, the control unit120writes the data in the block (in step S306), and sets the flag D203of the status bit string108in the address array102to 1 (in step S307).

Next, when the instruction type117is load (load in step S301), the control unit120determines whether or not a cache hit has occurred (in step S314). The control unit120determines whether or not accessed data has resulted in the cache hit according to the comparison result A115from the comparator A105, the comparison result, B116form the comparator B106, the status bit string108in the address array102and the status bit string110in the eviction block address array103(in step S314).

When the comparison result A115indicates a match and the flag V202of the status bit string108indicates 1, or when the comparison result B116indicates a match and the flag V206of the status bit string110indicates 1, the control unit120determines that the accessed data has resulted in the cache hit (Yes in step S314).

On the other hand, when the comparison result S115indicates a mismatch or when the flag V202of the status bit string108indicates 0, the control unit120determines that the accessed data has caused a cache miss when the comparison result B116indicates a mismatch or when the flag V206of the status bit string110indicates 0 (No in step S314).

When the accessed data has resulted the cache hit (Yes in Step S314), the control unit120determines in which one of the normal address array102and the eviction block address array103the cache hit has occurred, based on whether the comparison result A115indicates the match or the comparison result B116indicates the match (in step S334).

When the cache hit has occurred in the normal address array (No in step S334), the control unit120determines whether or not the block of the accessed data is being read, based on the flag F204of the status bit string108(in step S326). When the flag F204indicates 1, and then when the control unit120determines that the block is being read (Yes in step S326), the control unit120waits for completion of the reading. On the other hand, when the flag F204indicates 0 and then when the control unit120determines that the block is not being read (No in step S326), the control unit120specifies the word of data in the block, based on data of low-order 6 (k) bits, and reads the word from the block111(in step S317).

When the cache hit has occurred in the eviction block address array103(Yes in step334), the control unit120specifies the word of the data in the block, based on the data of low-order 6 (k) bits, and reads the word from the block111(in step S317).

When the accessed data has caused the cache miss (No in step314), the control unit120determines whether or not replacement of a cache block will occur (in step S318). When there is a block which already uses the entry (and for which the flag V202of the status bit string108indicates 1), the control unit120determines that the replacement will occur (Yes in step318). On the other hand, when that entry is vacant (or the flag V202of the status bit string108indicates 0), the control unit120determines that the replacement will not occur (No, in step318).

When the control unit120determines that the replacement of the block will not occur (No in step S318), the control unit120stores the high-order m bits114in the address register101in the high-order m bits in the address array102, sets the flag V202and the flag F204of the status bit string108to 1, and reads the block from the memory. Then, when the read block has arrived, the control unit120writes the read block to the block111of the data array104, and sets the flag F204of the status bit string108of the address array102to 0 (in step S321). Next, the control unit reads the data from the block111(in step S317).

On the other hand, when the control unit120determines that the replacement of the block will occur (Yes in step S318), the control unit120performs the replacement of the block and block reading (in step S322). Step S322will be described later, with reference toFIG. 5. After step S322, the control unit120reads the data from the block (in step S317).

First, the control unit120determines whether or not the entry of the eviction block address array103is vacant (in step S401). When the flag V206of the status bit string110in the eviction block address array103indicates 0, the control unit120determines that the entry is vacant. When the flag V206of the status bit string110in the eviction block address array103indicates 1, the control unit120determines that the entry is not vacant (in step S401).

When the control unit120determines that the entry is not vacant (No in step S401), a cache miss has already occurred, and the block reading from the memory for the replacement is being executed. Thus, the control unit120waits for completion of the block reading (in step S403). After the reading has been completed, the operation returns to step S401.

When the control unit120determines that the entry is vacant (Yes in step S401), the control unit120copies the high-order m bits107in the address array102to be evicted to the high-order m bits109in the eviction block address array103. Then, the control unit120sets the flag V206and the flag D207of the status bit string110to 1 and 0, respectively (in step S404). Next, the control unit120determines whether or not the block to be evicted has been rewritten, based on whether the flag D203of the status bit string108indicates 1 or 0 (in step S405).

Only when the control unit120determines that the block to be evicted has been rewritten (Yes in step S405), the control unit120writes back the block111in the data array104to the address indicated by the high-order m bits107in the address array102(in step S407).

Next, the control unit120copies the high-order m bits114in the address register101to the high-order m bits107in the address array102. Further, the control unit120sets the flag V202and the flag F204of the status bit string108in the address array102to 1, and sets the flag D203of the status bit string108to 0 (in step S409). Then, the control unit120issues to the memory a request for reading the block which has caused the cache miss (in step S410). Next, the control unit120waits for arrival of the block from the memory (in step S411).

During a period before arrival of the block, the block which has been invalid in a related art and will be evicted becomes valid on the eviction block address array. Data in the block which will be evicted remains in the block111of the data array104.

Next, the block which has been read arrives at the cache memory (in step S412). The control unit120sets the flag V206of the status bit string110in the eviction block address array103to 0, for invalidation (in step S413). Next, the control unit120examines the flag D207of the status bit string110of the eviction block address array103to check whether or not the block has been rewritten (in step S414).

Only when the control unit120determines that the block has been rewritten (Yes in step S414), the control unit120writes back the block of the data array104to the address indicated by the high-order m bits109in the eviction block address array103(in step S416). Next, the block which has been read from the memory is written into the block111of the data array104. Then, the control unit120sets the flag F204of the status bit string108in the address array102to 0 (in step S418).

SECOND EXAMPLE

A second example will be described in detail with reference to drawings. Referring toFIG. 6, a cache memory in the second example comprises an address register501, an address array (way 0)502, an address array (way 1)503, an eviction block address array504, a data array (way 0)505, a data array (way 1)506, a comparator A507, a comparator B508, a comparator C509, and a control unit510.

Each of the address arrays502and503is a memory having 2nentries. One entry includes one of high-order m bits511and high-order m bits513, each of which are a part of the address of a block, and one of a status bit string512and a status bit string514each indicating a status of the block.

The eviction block address array504is a memory having 2nentries. One entry includes high-order m bits515, which are a part of the address of a block, a status bit string516indicating a status of the block, and a way number517indicating in which way's data array the block stored in the data array is present.

Each of the data arrays505and506is a memory having 2nentries. One entry stores a block518or519of 2kbytes.

The comparator A507compares high-order m bits522in the address register with the address of the high-order in bits511of the entry in the address array502accessed using n bits520in the address register501as an offset521.

The comparator B508compares the high-order in bits522in the address register501with the address of the high-order m bits513of the entry in the address array503accessed using the n bits520in the address register101as the offset521.

The comparator C509compares the high-order m bits522in the address register501with the address of the high-order m bits515of the entry in the eviction block address array504accessed using the n bits520in the address register101as the offset521.

The control unit510controls the cache memory, based on a comparison result A523from the comparator A507, a comparison result B524from the comparator B508, a comparison result C525from the comparator C509, a instruction type (load or store)528from a CPU, the status bit string512in the address array502, the status bit string514in the address array503, the status bit string516in the eviction block address array504, and the way number517which have been read.

Though not illustrated inFIG. 6, information indicating a (Least Recently Used, LRU) way having a long period of time during which the way is not used is provided for each column in order to determine a way targeted for replacement. Based on the information mentioned above, the way targeted for the replacement is selected.

In the following description, it is assumed that each address stored in the address register101is composed of 64 bits, k=6 or the size of each block is 64 bytes, n=10 or the number of entries of each of the address array502, the address array503, the eviction block address array504, the data array505, and the data array506is 1024, and m=48. Herein, the cache memory using a two-way set associative type is shown as an example. However, the number of ways is arbitrary. Further, the number of eviction block address arrays is set to one. However, the number of the eviction block address arrays is also arbitrary. The number of ways and the number of eviction block address arrays in a set associative method influence the number of address comparators, and the like.

Next, operation of the cache memory inFIG. 6will be described. When an access to the cache memory is made, the address of the access is set in the address register501. The address may be a logical address, or a physical address. It is assumed herein that the address is the physical address translated from a virtual address by some address translation means, and the description will be given.

Since the size of each block is 64 bytes, low-order 6 (k) bits529in the address register101constitute the address of the block. Using 10(n) bits520which are higher-order than the low-order 6 (k) bits529as the offset521, entries in the address array502, the address array503, and the eviction address array504are read. The comparator A507compares the high-order 48 (m) bits522in the address register501with the high-order 48 (m) bits511of the address of the entry read from the address array (way 0)502. The comparator B508compares the high-order 48 (m) bits522in the address register501with the high-order 48 (m) bits513of the address of the entry read from the address array (way 1)503. The comparator C509compares the high-order 48 (m) bits522in the address register501with the high-order 48 (in) bits515of the address of the entry read from the eviction block address array504. The control unit510determines whether or not the entry of that block is already present in the cache memory, based on these comparison results.

The comparison result A523, the comparison result B524, and the comparison result C525are supplied to the control unit510together with the instruction type (load or store)528, the status bit string512of the entry read from the address array502, the status bit string514of the entry read from the address array503, the status bit string516of the entry read from the eviction block address array504to determine the operation of the cache memory. Determination of the operation by the control unit510and details of the operation will be described later in a part of description of the operation.

Each of the status bit string512in the address array502and the status bit string514in the address array503in the second example is the same as the status bit string201in the first example inFIG. 3. Further, the status bit string516in the eviction block address array504in the second example is the same as the status bit string205in the first example inFIG. 3.

Next, operation of the second example will be described in detail with reference to the components inFIG. 6and the bit strings inFIG. 3each indicating a status and others.

FIG. 7is a flowchart for explaining determination of the operation by the control unit510inFIG. 6and the operation.

An accessed address is stored in the address register501inFIG. 6, and entries in the address array502, the address array503the eviction block address array504, the data array505, and the data array506are accessed using the 10 (n) bits520in the address register501. Determination of the operation by the control unit510and the operation at this point will be described.

The control unit510determines a process to be performed according to the instruction type528from a CPU (in step S601).

First, when the instruction type528is store (store in step S601), the control unit510determines whether or not a cache hit has occurred (in step S603). The control unit510determines whether or not accessed data has resulted in the cache hit according to the comparison result A523from the comparator A507, the comparison result B524from the comparator B508, the comparison result C525from the comparator C509, the status bit string512in the address array502, the status bit string514in the address array503, and the status bit string516in the eviction block address array504(in step S603).

When the comparison result A523indicates a match and the flag V202of the status bit string512indicates 1, when the comparison result B524indicates a match and the flag V202of the status bit string514indicates 1, or when the comparison result C525indicates a match and the flag V206of the status bit string516indicates 1, the control unit510determines that the accessed data has resulted in the cache hit (Yes in step S603).

On the other hand, when the comparison result A523indicates a mismatch or the flag V202of the status bit string512indicates 0, and when the comparison result C524indicates a mismatch or the flag V202of the status bit string514indicates 0, the control unit510determines that the accessed data has resulted a cache miss when the comparison result C525indicates a mismatch or the flag V206of the status bit string516indicates 0 (No in step S603).

When the accessed data has resulted in the cache hit (Yes in Step S603), the control unit510determines in which one of the normal address array502, the normal address array503, and the eviction block address array504the cache hit has occurred, based on whether the comparison result A523or the comparison result B524has indicated the match or the comparison result C525has indicated the match (in step S606).

When the cache hit has occurred in the normal address array502or503(No in step S606), the control unit510first updates an LRU (in step S608). Then, the control unit510determines whether or not the block of the accessed data is being read, based on the flag F204of the status bit string512or514(in step S609).

When the flag F204indicates 1, and then when the control unit510determines that the block is being read (Yes in step S609), the control unit510waits for completion of the reading. On the other hand, when the flag F204indicates 0 and then when the control unit510determines that the block is not being read (No in step S609), the control unit510specifies the word of data in the block, based on low-order 6 (k) bit data, and writes write data in the word (in step S612), and sets the flag D203of the status bit string512or514to 1 (in step S613).

When the cache hit has occurred in the eviction block address array504(Yes in step606), the control unit510writes write data to the word of the block518of the data array (way 0) or the block519of the data array506of the way indicated by the way number517(in step S615). The word is specified based on the low-order 6 (k) bit data. Then, the control unit510sets the flag D207of the status bit string516to 1 (in step S616).

When the cache miss has occurred (No in step603), the control unit510determines whether or not replacement of a cache block will occur (in step S617).

When all the ways in the cache memory are used (when the flags V202of the status bit strings512and514indicate 1), the control unit510determines that the replacement will occur (Yes in step617). On the other hand, when there is even one vacant way (when the flag V202of the status bit string512or514indicates 0), the control unit510determines that the replacement will not occur (No in step617).

When the control unit determines that that the replacement of the block will not occur (No in step S617), the control unit510stores the high-order m bits552in the address register501in the high-order m bits511of the address array502or the high-order m bits513of the address array503of the way which is vacant, sets the flag V202and the flag F204of the status bit string512or514to 1, and reads the block from a memory. Then, when the read block has arrived, the control unit510writes the read block to the block518of the data array505or the block519of the data array506, and sets the flag F204of the status bit string512in the address array502or the status bit string514in the address array503to 0 (in step S620). Then, the control unit510writes the data into the block518or519(in step S612), and sets the flag D203in the status bit string512of the address array502or the status bit string514in the address array503to 1 (in step S613).

When the control unit510determines that the replacement of the block will occur (Yes in step S617), the control unit510performs the replacement of the block and block reading (in step S621). Step S621will be described later, with reference toFIG. 6. After step S621, the control unit510writes the data in the read block (in step S612), and sets the flag D203of the status bit string512in the address array502or the status bit string514in the address array503to 1 (in step S613).

Next, when the instruction type528is load (load in step S601), the control unit510determines whether or not a cache hit has occurred (in step S623). The control unit510determines whether or not accessed data has resulted in the cache hit according to the comparison result A523from the comparator A507, the comparison result B524from the comparator B508, the comparison result C525from the comparator C509, the status bit string512in the address array502, the status bit string514in the address array503, and the status bit string516in the eviction block address array504(in step S623).

When the comparison result A523indicates a match and the flag V202of the status bit string512indicates 1, when the comparison result B524indicates a match and the flag V202of the status bit string514indicates 1, or when the comparison result C525indicates a match and the flag V206of the status bit string516indicates 1, the control unit510determines that the accessed data has resulted in the cache hit (Yes in step S623).

On the other hand, when the comparison result A523indicates a mismatch or the flag V202of the status bit string512indicates 0 and when the comparison result B524indicates a mismatch or the flag V202of the status bit string514is 0, the control unit510determines that the accessed data has caused the cache miss when the comparison result C525indicates a mismatch or when the flag V206of the status bit string516indicates 0 (No in step S623).

When the cache hit has occurred (Yes in Step S623), the control unit510determines in which one of the normal address array502, the normal address array503, and the eviction block address array504the cache hit has occurred, based on whether the comparison result A523or the comparison result B524indicates the match or the comparison result C525indicates the match (in step S626).

When the cache hit has occurred in the normal address array502or503(No in step S626), the control unit510first updates the LRU (in step S628). Then, the control unit510determines whether or not the block of the accessed data is being read, based on the flag F204of the status bit string512or514(in step S629). When the flag F204indicates 1, and then when the control unit510determines that the block is being read (Yes in step S629), the control unit510waits for completion of the reading. When the flag F204indicates 0 and the block is not being read (No in step S629), the control unit510specifies the word in the block518or519corresponding to low-order 6 (k) bit data, based on the low-order 6 (k) bit data, and read the word (in step S632).

When the cache hit has occurred in the eviction block address array504(Yes in step626), the control unit510reads the word in the block518of the data array505or the block519of the data array506of the way indicated by the way number517, based on the low-order 6 (k) bit data (in step S634). The word is specified based on the low-order 6 (k) bit data.

When the cache miss has occurred (No in step623), the control unit510determines whether or not replacement of a cache block will occur (in step S635). When all the ways in the cache memory are already used (when the flags V202of the status bit strings512and514indicate 1), the control unit510determines that the replacement will occur (Yes in step635). When there is even one vacant way (when the flag V202of the status bit string512or514indicates 0), the control unit510determines that the replacement will not occur (No in step S635).

When the control unit510determines that the replacement of the block will not occur (No in step S635), the control unit510stores the high-order m bits552in the address register501in the high-order m bits511of the address array502or the high-order m bits513of the address array503of the way which is vacant, sets the flag V202and the flag F204of the status bit string512or514to 1, and reads the block from the memory. Then, when the read block has arrived, the control unit510writes the read block to the block518of the data array505or the block519of the data array506, and sets the flag F204of the status bit string512in the address array502or the status bit string514in the address array503to 0 (in step S638). Then, the control unit510reads the data from the block518or519(in step S632).

When the control unit510determines that the replacement of the block will occur (Yes in step S635), the control unit510performs the replacement of the block and block reading (in step S639). Step S639will be described later, with reference toFIG. 8. After step S639, the control unit510reads the data from the read block (in step S632).

Next, steps S621and S639inFIG. 7will be described, with reference toFIG. 8. First, the control unit510selects the way to be replaced, according to the LRU (in step S701), and updates the LRU.

First, the control unit510determines whether or not the entry of the eviction block address array504is vacant (in step S702). When the flag V206of the status bit string516of the eviction block address array504indicates 0, the control unit510determines that the entry is vacant. When the flag V206of the status bit string516in the eviction block address array103indicates 1, the control unit510determines that the entry is not vacant.

When the control unit510determines that the entry is not vacant (No in step S702), the control unit510determines whether or not the block to be evicted has been rewritten, based on the flag D203of the status bit string512in the address array502or the status bit string514in the address array503(in step S704).

Only when the control unit510determines that the block to be evicted has been rewritten (Yes in step S704), the control unit510writes back the block518of the data array505or the block519of the data array506to the address indicated by the high-order m bits511in the address array502or the high-order in bits513in the address array503(in step S706).

Next, the control unit510copies the high-order m bits522in the address register501to the high-order m bits511in the address array502or the high-order m bits513in the address array503. Further, the control unit510sets the flag V202and the flag F204of the status bit string512of the address array502or the status bit string514of the address array503to 1, and the control unit510sets the flag D203of the status bit string512of the address array502or the status bit string514of the address array503to 0 (in step S708). Then, the control unit510issues to the memory a request for reading the block which has caused the cache miss, and writes the block from the memory into the block518in the data array505or the block519in the data array506(in step S709).

When the control unit510determines that the eviction block address array504is vacant (Yes in step S702), the control unit510copies the high-order m bits511in the address array502for eviction or the high-order m bits513in the address array503for eviction to the high-order m bits515in the eviction block address array504. Then, the control unit510sets the flag V206and the flag D207of the status bit string516to 1 and 0, respectively. Then, the control unit510sets the number for the way to be evicted to the way number517(in step S711).

Next, the control unit510determines whether or not the block to be evicted has been rewritten, based on whether the flag D203of the status bit string in the address array502or503indicated by the way number517is 1 or 0 (in step S712). Only when the control unit510determines that the block to be evicted has been rewritten (Yes in step S712), the control unit510writes back the block518of the data array505or the block519of the data array506indicated by the way number517to the address indicated by the high-order m bits511in the address array502or the high-order in bits512in the address array503for replacement (in step S714).

Next, the control unit510copies the high-order m bits522in the address register501to the high-order m bits511of the address array502or the high-order m bits513of the address array503indicated by the way number517. Then, the control unit510sets the flag V202and the flag F204of the status bit string512or the status bit string514to 1, and sets the flag D203of the status bit string512or the status bit string514to 0 (in step S716). Then, the control unit510issues to the memory a request for reading the block which has caused the cache miss (in step S717). Next, the control unit510waits for arrival of the block from the memory (in step S718).

During a period before arrival of the block, the block which has been invalid in a related art and will be evicted becomes valid on the eviction block address array. Data in the block which will be evicted remains in the block518of the data array505or the block519of the data array506.

Next, the block which has been read arrives at the cache memory (in step S719). The control unit510sets the flag V206of the status bit string516in the eviction block address array504to 0, for invalidation (in step S720). The control unit510examines the flag D207of the status bit string516in the eviction block address array504to check whether or not the block has been rewritten (in step S721).

Only when the control unit510determines that the block has been rewritten (Yes in step S721), the control unit510writes back the block518of the data array505or the block519of the data array506indicated by the way number517to the address of the eviction block address array504indicated by the high-order m bits515(in step S723). Then, the control unit510writes the block read from the memory into the block518of the data array505or the block519of the data array506indicated by the way number517. Then, the control unit510sets the flag F204of the status bit string108in the address array102to 0 (in step S725).

Next, operations of the cache memory in the second example will be described, with reference toFIGS. 9 to 15.

FIG. 9shows a point of time at which data for a different block to be cached in a same column has been loaded in a state where blocks are cached in two ways. First, the column is selected using n bits802in an address register801as an index. Then, entries are read from an address array (way 0)803, an address array (way 1)804, and an eviction block address array805, and are respectively compared with 0x000001cc0003 of high-order m bits806in the address register.

High-order m bits807in the address array (way 0)803are 0x000001cc0001, high-order m bits808in the address array (way 1)804are 0x000001cc0002, and an entry in the eviction block address array is invalid. Consequently, it can be seen that a cache miss has occurred. Since the entries of the address array (way 0)803and the address array (way 1)804are valid, replacement will occur. Then, by referring to an LRU809, a way 0 is targeted for the replacement. Then, the LRU809 is updated to 1.

FIG. 10is a diagram for explaining a process of validating an entry in the eviction block address array. Since the entry in the eviction block address array805is vacant, the high-order m bits807of the way 0 targeted for the replacement are evicted are copied to high-order in bits810of the eviction block address array. Then, a status bit string811is set to 10, and a way number812is set to 0. This makes the entry in the eviction block address array valid.

FIG. 11explains a write back process when a block targeted for the replacement has been rewritten. Since the flag D of a status bit string813in the address array (way 0)803is 1, the block on the data array of the way 0 is written back to the address indicated by the high-order m bits807.

FIG. 12is a diagram for explaining a process of registering a block which has caused a cache miss in the address array, and reading the block which has caused the cache miss from a memory. The high-order in bits806in the address register801are copied to the high-order m bits807in the address array803of the way 0 indicated by the way number812. Then, a flag VDF of the status bit string813is set to101. Thereafter, a request for reading the block which has caused the cache miss from the memory is issued.

FIG. 13shows a state where during reading of the block which has caused the cache miss, a cache hit has occurred in the entry in the eviction block address array at a time of writing. A store instruction to the address in the address register801is executed, and the entries in the address arrays803,804, and805are read, using the n bits802as the index. Then, it is determined that 0x000001cc0001 of the high-order m bits806in the address register801match the high-order in bits810in the eviction block address array805, so that the cache hit has occurred. Then, write data is written into the block of the data array of the way 0 indicated by the way number812. The flag D of the status bit string in the eviction block address array805for storing rewriting becomes 1.

FIG. 14shows a process when the block read from the memory has arrived at the cache memory. First, the flag V of the status bit string811of the eviction block address array805is set to 0, thereby invalidating this entry. Then, it is checked whether or not rewriting has been performed, according to the flag D of the status bit string811. Since the flag D is 1, it means that the rewriting has been performed due to the cache hit in the eviction block address array at the time of writing. Thus, the block of the data array of the way 0 indicated by the way number812is written back to the address indicated by the high-order m bits810.

FIG. 15shows a process of writing the block read from the memory into the data array. The block read from the memory is written into the data array of the way 0 indicated by the way number812, and then the flag F of the status bit string813in the address array803of the way 0 is set to 0.

Variations and adjustments of the exemplary embodiment and the examples may be made within the overall disclosure (including the claims) of the present invention, and based on the technical concept of the present invention. Various combinations and selections of various disclosed elements are possible within the scope of the claims of the present invention. That is, the present invention of course includes various variations and modifications that could be made by those skilled in the art according to the overall disclosure and the technical concept.

The present invention includes inventions according to the following additional modes.

A cache memory according to the first aspect described above.

The cache memory according to mode 1, wherein the control unit invalidates the address of the first block stored in the second address array when writing the second block into the data array.

The cache memory according to mode 1 or 2, wherein the second address array stores an identifier for a way in which the first block is stored.

The cache memory according to any one of modes 1 to 3, wherein the second address array stores a flag indicating whether or not the first block has resulted in a cache hit and has been rewritten.

The cache memory according to mode 4, wherein the control unit, before the second block is read from the memory and written into the data array, refers to the flag stored in the second address array and, if the first memory has been rewritten, writes back the first block to the memory.

A cache memory according to the second aspect described above.

An electronic computer including the cache memory according to any one of modes 1 to 6.

The electronic computer according to mode 7, including a multi-core or multi-thread processor.

A cache memory control method according to the third aspect described above.

The cache memory control method according to mode 9, further comprising invalidating the address of the first block stored in the second address array when writing the second block into the data array.

The cache memory control method according to mode 9 or 10, comprising storing in the second address array an identifier for a way in which the first block is stored.

The cache memory control method according to any one of modes 9 to 11, comprising storing in the second address array a flag indicating whether or not the first block has resulted in the cache hit and has been then rewritten.

The cache memory control method according to mode 12 comprising, before the second block is read from the memory and writing into the data array, referring to the flag stored in the second address array and, if the first block has been rewritten, writing back the first block to the memory.