WO2010029694A1 - Cache memory and cache memory system - Google Patents

Abstract

A cache memory (6) includes: a data storage unit (16) having a line containing four words (Word0, Word1, Word2, Word3); and a tag storage unit (14) which stores a tag for identifying each line.  The tag storage unit contains a refill bit (R), dirty bits (D0, D1, D2, D3), and a tag bit (Tag).  If a tag address (AD [31:16]) to be accessed coincides with the address indicated in the tag bit (Tag) and if the refill bit (R) corresponding to the line relating to the access object indicates that refill is in progress, a hit check unit (20) determines that the write access is a write hit.  If the dirty bit corresponding to the word relating to the access object contained in the line indicates dirty, the hit check unit (20) determines that the read access is a read hit.

Description

Cache memory, cache memory system

The present invention relates to a write-back cache memory.

The write-back method is a method in which, when data is written to the cache memory, basically only the cache memory is written, and the main memory is not written at the same time, but is later rewritten appropriately.

In the write-back method, the writing timing to the cache memory and the main memory is shifted, so a Dirty / Clean flag is provided for managing the consistency of the data held by both. Dirty indicates that the data held in the cache memory is updated, etc., and cannot match the data on the main memory, and Clean indicates the opposite. The Dirty / Clean flag can be used to determine whether the target data is dirty or clean. Dirty data must be written back to main memory at an appropriate timing to ensure consistency.

Such a dirty / clean flag is generally managed in units of lines (consisting of several words). Of course, in the case of line units, it is unclear which word out of several words included in a line is Dirty, so unnecessary write back may be performed.

Therefore, in Patent Document 1, it is possible to write back only necessary data and manage unnecessary bus transactions by managing the Dirty / Clean distinction in units smaller than lines (for example, word units). Yes. Other techniques of Patent Documents 2 to 4 are known.

JP 2003-108439 A Japanese Unexamined Patent Publication No. 2006-91995 JP-A-8-16467 JP-A-8-221270

Since the access to the cache memory is faster than the access to the main memory, the improvement of the cache hit rate is generally directly related to the improvement of the performance of the entire computer system.

Generally, in a cache memory that is subject to write allocation control, when a cache miss occurs, a process called refill is performed to bring the data of the target line to the cache. Even during the refill, there is a possibility that there is no problem even if access is permitted by treating the cache hit. However, in the conventional technique, the cache access of the line is not permitted uniformly during the refill. In this case, since a subsequent cache access is awaited, a large overhead occurs in the computer system. In addition, this type of overhead can be expected to be removed in a non-blocking cache or the like, but in general, a non-blocking cache is complicated to control and requires a lot of resources such as a buffer separately.

Under such a background, an object of the present invention is to provide a cache memory having a further improved cache hit rate.

The cache memory according to the present invention includes a plurality of lines each including a plurality of words, a tag indicating an address in the main memory of data stored in the line, and whether or not the line is being refilled for each line. The tag storage unit that stores the refill bit to be indicated and the dirty bit that indicates whether or not the data in the word is dirty for each word, the tag address that is the cache access target, and the address indicated by the tag match When the refill bit of the line indicates refilling, when the cache access is a write access, the write access is determined to be a write hit, and when the cache access is a read access, the read access is related to The dirty bit corresponding to the word contained in the line If shows the I, it is characterized in that it comprises determining the hit judging unit and read hit the read access.

In addition, if the dirty bit corresponding to the word included in the line related to the read access target does not indicate the dirty, the hit determination unit does not permit the read access to the word until the refill of the line including the word is completed. It does not matter.

In addition, when the hit determination unit determines that the write hit occurs, in writing to the word related to the write access, the dirty bit corresponding to the word is asserted, and the dirty bit is dirty when the line is refilled. It is also possible to provide a control unit that permits overwriting of data for words that do not indicate this, and prohibits overwriting of data for words that indicate that the dirty bit is dirty.

The cache memory system according to the present invention is located in a hierarchy between the central processing unit, the cache memory, the central processing unit, the cache memory, and the storage hierarchy, and the central processing unit is transferred to the cache memory. The first write buffer that holds data to be written, the cache memory, the memory to be written back, and the storage hierarchy are located in a hierarchy, and write back from the cache memory to the memory to be written back A second write buffer that holds data to be read, and a read buffer that is positioned between the cache memory, the memory to be written back, and the storage hierarchy and holds data to be read by the cache memory.

The cache memory according to the present invention hits / deletes a flag indicating whether refilling is in progress and a dirty bit for each word that has been used for the purpose of reducing bus transactions to the main memory at the time of write back. Used to determine miss hits.

That is, in the hit determination unit according to the present invention, a write access to a line being refilled is always determined as a write hit, and a read access is determined as a read hit on the condition that the access target word is dirty.

With this configuration, cache access that was not permitted in a situation where the cache access target line is being refilled is permitted under specific conditions, and the cache hit rate can be improved. As a result, it is possible to reduce the overhead of the computer that has occurred due to the fact that cache access is not permitted during refilling.

In addition, a non-blocking cache that is more effective than the conventional one can be constructed together with the write buffer and read buffer prepared in the cache access path.

Configuration diagram of cache memory system 1 The figure which shows the structure of the cache memory 6 Circuit configuration example of hit determination unit 20 FIG. 50 is a table 50 showing determination results output by the hit determination unit 20 of FIG. 3 according to input. Sequence diagram of CPU 2, cache memory 6, and main memory 4 during write access Sequence diagram of CPU 2, cache memory 6, and main memory 4 during read access Diagram explaining the refill of a word (W0, W1, W2, W3) on a line in time series

Hereinafter, embodiments of the present invention will be described with reference to the drawings. In addition, the write-back cache memory according to the present embodiment employs a direct map method, and in the event of a cache write miss hit, the write allocation method (once the data at the address to be accessed for write access is transferred from the main memory to the cache memory In this method, after the data is reflected on the line, a write operation equivalent to that at the time of a write hit is performed on the line.

FIG. 1 is a configuration diagram of the cache memory system 1.

The cache memory system 1 includes a CPU (Central Processing Unit) 2, a main memory 4, a cache memory 6, write buffers 8 and 10, and a read buffer 12.

The CPU 2 is a central processing unit that performs various arithmetic processes.

The main memory 4 is composed of a volatile memory that temporarily stores data such as DRAM.

The cache memory 6 temporarily stores data to be stored in the main memory 4. The access speed is higher than that of the main memory 4 and is interposed between the upper CPU 2 and the lower main memory 4 due to the structure of the storage hierarchy. The cache memory 6 is a write-back method, and the data held therein is written back to the main memory 4 when a cache miss hit occurs.

The cache memory 6 includes a control unit 6a, a storage unit 6b, a hit determination unit 6c, and an arbitration unit 6d.

The control unit (cache memory control unit) 6a controls each functional block, for example, reads / writes data stored in the storage unit 6b and updates tags. Further, data is output to the CPU 2 according to the hit determination result of the hit determination unit 6c.

The storage unit 6b includes a data storage unit that stores data, and a tag storage unit that includes a tag as information for identifying the stored data.

The hit determination unit 6c determines whether or not the data requested to be accessed by the CPU 2 is stored in the storage unit 6b. Details will be described later.

The arbitration unit 6d arbitrates when access to data in the storage unit 6b competes.

FIG. 2 is a diagram showing the configuration of the cache memory 6.

The address 22 in the upper part of FIG. 2 indicates an address output together with a read / write request from the CPU 2 when the CPU 2 tries to access the cache memory 6.

Address (AD [31: 0]) 22 is 32 bits, and the upper 16 bits (AD [31:16]) are used as tag addresses, and 12 bits (AD [15: 4]) from bit 4 to bit 15 are used. As an index address, 2 bits (AD [3: 2]) from bit 2 to bit 3 are used as a word address for specifying a word included in the line. Since the index address is 12 bits, 4096 (= 2 ^ 12) lines can be specified. A line to be accessed is uniquely specified by this index address.

The cache memory 6 includes a tag storage unit 14, a data storage unit 16, a selector 18, and a hit determination unit 20.

The tag storage unit 14 is provided corresponding to 4096 lines in the data storage unit 16, and stores identification information such as data stored in the line.

Specifically, the tag storage unit 14 stores a valid bit (V) indicating whether or not line data is valid, a refill bit (R) indicating whether or not the line is being refilled, and the line. It has a tag bit (Tag) indicating the address of the main data in the main memory.

In addition to this, the tag storage unit 14 includes four dirty bits (D0, D1, D2, D3) respectively provided corresponding to four words (Word0, Word1, Word2, Word3) included in the line. It is out. If the dirty bit is dirty, it has been updated by the write operation from the CPU 2, but it has not yet been written back to the main memory, and it cannot be guaranteed that it matches the data in the main memory. If necessary, it is necessary to write back to the main memory.

The data storage unit 16 holds 4096 lines with four words as one line. The data storage unit 16 includes an SRAM or the like as a memory separate from the tag storage unit 14. The size per word is 32 bits corresponding to the data access width from the CPU 2, and the bit width of the input / output port of the data storage unit 16 is 32 bits (for one word).

The selector 18 selects one word out of four words based on 2 bits (AD [3: 2]) of the address 22.

The hit determination unit 20 has a valid bit (V) of a line specified by a signal indicating Read or Write (Read or Write), a tag address (AD [31:16]), and an index address (AD [15: 4]). , Refill bit (R), dirty bit (D0, D1, D2, D3) for every four words, tag bit (Tag) indicating the address of the data stored in the above line, one of the four words It is determined whether it is a hit or a miss based on 10 inputs of the specified word address (AD [3: 2]).

An example of the circuit configuration of the hit determination unit 20 is shown in FIG.

The hit determination unit 20 includes 2-input 1-output AND circuits 23, 24, 26, 28, and 30, a 3-input 1-output OR circuit 32, NOT circuits 34 and 36, a 4-input 1-output selector 38, and a comparator 40. .

The selector 38 selects and outputs one of four of D0, D1, D2, and D3 based on a 2-bit (AD [3: 2]) input. That is, based on an input (AD [3: 2]) that specifies an access target word included in the line, a dirty bit corresponding to the word is output.

The comparator 40 compares the tag bit (Tag) held in the access target line of the tag storage unit 14 with the tag address (AD [31:16]), and outputs HIGH when the two match.

FIG. 4 is a table 50 showing determination results output by the hit determination unit 20 of FIG. 3 in response to input. In the table, the mark “*” means “Don't Care”.

There are eight cases from (a) to (h) depending on the combination of values input to the hit determination unit 20. Each case will be described in turn. Note that hit determination in cases (a), (b), (d), (e), (f), and (h) that are not being refilled is basically the same as in the prior art. The cases (c) and (g) during refill are characteristic.

In the case of (a): The tag address (AD [31:16]) included in the address 22 of the write access target data matches the tag bit (Tag), and the refill is not in progress (R = 0). This is a case where the valid bit is valid (V = 1) and a write hit occurs. Then, the cache memory 6 writes to the word indicated by the word address (AD [3: 2]) and asserts a dirty bit corresponding to the simultaneously written word.

In the case of (b): Only the place where the valid bit is invalid (V = 0) is different from (a), and since the data is invalid at V = 0, a write miss hit occurs.

Here, the write miss hit data is temporarily held in the write buffer 8 and written to the cache memory 6 after completion of the refill. In particular, in the present embodiment, the write miss hit data is written in the cache memory 6. At the time of writing, the dirty bit for each written word is updated to dirty, and the tag bit (Tag) is updated to the address of the access that caused the write miss hit. Prior to this, a data read request and an address are output to the bus to the main memory 4 in order to refill the write access target line. At this time, if there is no free space in the read buffer 12, it waits until the read request is output or until it is determined that the read buffer 12 is free before the read data is returned from the main memory 4. Wait for read request output.

In the case of (c): The tag bit (Tag) of the write access target data matches the tag address (AD [31:16]) and refilling is in progress (R = 1). Become. Then, the cache memory 6 writes to the word indicated by the word address (AD [3: 2]) and asserts a dirty bit corresponding to the written word.

In the case of (d): The tag bit (Tag) of the data subject to read access matches the tag address (AD [31:16]), not being refilled (R = 0), and the valid bit is valid ( V = 1), which is a read hit. The CPU 2 reads the data of the word indicated by the word address (AD [3: 2]).

In the case of (e): Only when the valid bit is invalid (V = 0) is different from (d). Since the data is invalid at V = 0, a read miss occurs.

In the case of (f): The tag bit (Tag) of the read access target data matches the tag address (AD [31:16]), refilling is in progress (R = 1), and the word address (AD [ 3: 2]) is a case where the dirty bit (D0 in FIG. 4) corresponding to the word (W0 in FIG. 4) is not dirty (clean). In this case, a miss hit occurs, and the control unit 6a of the cache memory 6 notifies the CPU 2 that refilling is in progress. The CPU 2 waits until the notification is no longer being refilled (waits until the refill is completed), and performs a read hit operation (reads the refilled read access target data) as a read hit after the refill is completed, or the missed read Even if the access is not completed, the process proceeds to the subsequent process.

In the case of (g): The tag bit (Tag) of the read access target data matches the tag address (AD [31:16]), refilling is in progress (R = 1), and the word address (AD [ 3: 2]) is a case where the dirty bit (D2 in FIG. 4) corresponding to the word (W2 in FIG. 4) is dirty. In this case, a read hit occurs, and the CPU 2 reads the data of the word indicated by the word address (AD [3: 2]).

In the case of (h): This is a case where the tag bit (Tag) and the tag address (AD [31:16]) do not match. This means that the address of the data to be accessed is different from the address of the data that is actually stored in the data storage unit, so it is not necessary to judge other conditions. It becomes.

As described above, the hit determination unit 20 determines a read hit if the dirty bit corresponding to the read access target word is dirty even if refilling is in progress as in (g). As a result, the read hit rate can be improved.

In addition, since the hit determination unit 20 determines as a write hit even if refilling is in progress as in the case of (c), the write hit rate can be improved as compared with the prior art.

Next, the processing flow of the CPU 2, cache memory 6, and main memory 4 will be described in order for write access and read access.

FIG. 5 is a sequence diagram of the CPU 2, the cache memory 6, and the main memory 4 at the time of write access. In the initial state, it is assumed that the line that is the target of the write access request is not being refilled (R = 0).

The hit determination unit 20 of the cache memory 6 that has received the write access request from the CPU 2 and the tag address (AD [31:16]) of the data address (AD [31: 0]) 22 and the write access request as described above. Hit determination is performed based on comparison with the tag bit (Tag) of the line of the target data or the refill bit (R) of the line.

If it is determined as a write hit (S1: Yes), data is written to the word of the line that is the target of the write access request, and if necessary, the dirty bit corresponding to the word is asserted (S11).

If it is determined that it is a write miss hit (S1: No), the CPU 2 causes the write buffer 8 to temporarily hold the data and the address (AD [31: 0]) 22 that have become a write miss hit. As a result, the CPU 2 can proceed to the subsequent processing without waiting for the completion of the cache write. The data and address (AD [31: 0]) 22 held in the write buffer 8 are used for data writing in step S11.

When it is determined as a write miss hit (S1: No), the cache memory 6 asserts the refill bit of the line (S2: R = 1), and proceeds to the write back process (S3-S8). At this time, the tag bits (Tag) are updated with the tag address (AD [31:16]) of the write access request in which a write miss hit occurs.

In the write back process (S3-S8), if the valid bit is invalid (S3: No, V = 0), the line is invalid and there is no data to be written back.

If the valid bit is valid (S3: Yes, V = 1), only the word in the line where the dirty bit corresponding to the word is dirty (D = 1) is written back to the write buffer 10 (S4, S5). ). The dirty bit corresponding to the word that has been written back is negated cleanly (D = 0) (S6).

The data written back to the write buffer 10 is further written back to the main memory 4 at an appropriate timing such as when the bus is free.

When the processing from S4 to S6 is finished for the four words included in the line (S7: Yes), the valid bit of the line is invalidated (S8: V = 0).

When the write back processing (S3-S8) is completed, the cache memory 6 performs refill / tag update (S9). Specifically, the read buffer 12 overwrites the line of the cache memory 6 with the data of the write access target line that has been read from the main memory 4.

Although it takes time for the read buffer 12 to actually read data from the main memory 4, in this embodiment, cache write access during this period is allowed, and at that time, the dirty bit of the written word is asserted. Therefore, in this refill, only the word of D = 0 is overwritten with the data from the main memory 4.

When the reading from the read buffer 12 is completed (S9), the cache memory 6 validates the line (S10: V = 1), negates the refill bit (S10: R = 0), and ends a series of refills.

FIG. 6 is a sequence diagram of the CPU 2, the cache memory 6, and the main memory 4 at the time of read access. In the initial state, it is assumed that the line that is the target of the read access request is not being refilled (R = 0).

When the CPU 2 requests read access to the cache memory 6 (S20), the cache memory 6 that has received the request performs the hit determination described above in the hit determination unit 20.

If it is determined as a read hit (S21: Yes), the CPU 2 reads data from the word of the line that is the target of the read access request.

If it is determined as a read miss hit (S21: No), the process proceeds to the refill processing from S2 to S10. Since this process is the same as that already described with reference to FIG.

Next, an example when a line in the cache memory 6 is being refilled and there is a write / read access to a word in this line will be described.

FIG. 7 is a diagram for explaining the refill of words (W0, W1, W2, W3) on a certain line in time series. The process at the time of write access will be described using (a), and the process at the time of read access will be described using (b).

At the time of write access, as shown in FIG. 7A, the cache memory 6 completes refilling in the order of W0 → W1 → W2 → W3 at times t0 → t1 → t2 → t3 → t4, respectively. To do. At the start of refill, the refill bit is asserted, and the line tag bit (Tag) is updated to the address of the new line to be refilled.

In the present embodiment, the write access request is received in the middle of refilling and data overwriting is allowed, so that the tag bit (Tag) of the line does not coincide with the tag of the actually overwritten data. As shown in FIG. 7A, the tag is updated at the start of refilling.

First, if there is a write access request to the word W2 between t0 and t2, the hit determination unit 20 determines that it is a write hit as described above, and receives the write access to the word W2 to receive the corresponding dirty. Assert bit (D2). After that, since the dirty bit (D2) of the word W2 is asserted between t2 and t3, the cache memory 6 does not overwrite the word W2 by refilling.

Note that, as a method of not overwriting, for example, a write access is performed but a signal for masking writing to a word is used. Further, the processing may be skipped without performing write access to the word itself.

Next, if there is a write access request to the word W2 between t2 and t3, it is determined as a write hit, and the corresponding dirty bit (D2) is asserted in response to the write access to the word W2. In this case, at the time of a write access request, since the word W2 is being written by refilling, the cache memory 6 arbitrates write control to prevent conflict between them.

If there is a write access request to the word W2 between t3 and t4, it is determined as a write hit, and the corresponding dirty bit (D2) is asserted in response to the write access to the word W2.

At the time of read access, as shown in FIG. 7B, as in FIG. 7A, the cache memory 6 is in the order of W0 → W1 → W2 → W3 at time t0 → t1 → t2 → t3 → t4. It is assumed that refilling is completed in order.

First, if there is a read access request to the word W2 between t0 and t4, if the dirty bit corresponding to the word W2 is asserted, the hit determination unit 20 determines that it is a read hit as described above. , Accepts read access to word W2.

On the other hand, if there is a read access request to the word W2 between t0 and t4 and the dirty bit corresponding to the word W2 is not asserted, the hit determination unit 20 reads the read miss as described above. At the same time as determining the hit, the fact that refilling is in progress is output. In response to this, the CPU 2 postpones execution of this read access until after the refill is completed.

<Supplement>
As mentioned above, although embodiment of this invention was described, this invention is not limited to said content, It can implement also in the various forms for achieving the objective of this invention, its related or incidental object, for example, It may be the following.

(1) In the embodiment, the direct map type cache memory has been described as an example. However, the present invention is not limited to this, and a cache memory adopting a full associative method or a set associative method may be used. In the case of these methods, the line to be refilled at the time of a cache miss hit is not determined as a unique line as in the direct map method, but based on algorithms such as the LRU (Least Recently Used) method and the round robin method Is different.

The present invention is also applied as a method for configuring and controlling a write-back cache memory in a shared memory type cache memory system in which a plurality of cache memories share a single lower layer memory via a shared bus. be able to.

(2) In the embodiment, an example in which only a word whose dirty bit is dirty is written back has been described. However, several words including a dirty word or all words included in a line may be written back. At the time of writing back, the data at the address to be written back is read from the main memory 4 before the data accumulated in the write buffer 10 is written back to the main memory 4 as in a known technique. The entire system can be controlled so that there is no.

(3) In the embodiment, as shown in FIG. 1, write access from the central processing unit to the cache memory is performed by arranging the write buffers 8 and 10 and the read buffer 12 in the path connected to the input / output of the cache memory 6. The write access from the cache memory to the main memory and the write access from the main memory to the cache memory are buffered, so that more flexible cache memory control is possible.

(4) Although no particular details have been described in the embodiment, another approach for reducing overhead on the entire system is conceivable. Specifically, as a response to a write miss, a multi-functional write buffer is placed between the upper layer memory and the cache memory, and writing to the line being refilled is performed once in the write buffer, and the following Reads from the line are read from the write buffer. Then, when data is written by refilling to the cache, the refill data is overwritten with the data in the write buffer. However, this control is very complicated.

On the other hand, in the embodiment, it is possible to reduce overhead to the entire system through simple control of hit determination of the hit determination unit 20.

(5) Although the configuration of the central processing unit, the cache memory, and the main memory is exemplified as the hierarchical memory system, the cache memory may be a deeper hierarchical memory system. For example, the cache memory may be composed of a primary cache memory and a secondary cache memory. In this case, the present embodiment may be applied to a primary cache memory or a secondary cache memory.

The cache memory of the present invention is useful because it can be used as a cache memory existing in a general semiconductor circuit and can improve the cache hit rate.

1 cache memory system 2 CPU
4 Main memory 6 Cache memory 8 Write buffer 10 Write buffer 12 Read buffer 14 Tag storage unit 20 Hit determination unit 22 Address

Claims (4)

Multiple lines, each containing multiple words,
A tag indicating an address in the main memory of data stored in the line;
A refill bit indicating whether the line is being refilled for each line;
A tag storage unit for storing a dirty bit indicating whether or not the data in the word is dirty for each word;
When the refill bit of the line where the tag address that is the cache access target matches the address indicated in the tag indicates that refilling is in progress,
When the cache access is a write access, the write access is determined as a write hit,
When the cache access is a read access, if the dirty bit corresponding to the word included in the line related to the read access indicates dirty, a hit determination unit is provided that determines the read access as a read hit. Characteristic cache memory. If the dirty bit corresponding to the word included in the line related to the read access target does not indicate dirty, the hit determination unit does not permit read access to the word until the refill of the line including the word ends. The cache memory according to claim 1, wherein: When the hit determination unit determines that the write hit occurs, in writing to the word related to the write access, assert a dirty bit corresponding to the word,
When refilling a line
Data overwriting is allowed for words that do not indicate that the dirty bit is dirty,
The cache memory according to claim 1, further comprising a control unit that prohibits overwriting of data with respect to a word indicating that the dirty bit is dirty. A central processing unit;
The cache memory according to claim 1;
A first write buffer located in a hierarchy between the central processing unit and the cache memory and the storage hierarchy, and holding data to be written to the cache memory by the central processing unit;
A second write buffer located in a hierarchy between the cache memory and the memory to be written back and the storage hierarchy, and holding data to be written back from the cache memory to the memory to be written back;
A cache memory system comprising: a read buffer that is located in a hierarchy between the cache memory, the memory to be written back, and a storage hierarchy and holds data to be read by the cache memory.

Images