Set associative cache memory device

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a semiconductor storage device, and more particularly to a set-associative type cache memory device.

【0002】

[Conventional technology]

Figure 7 shows the structure of the set-associative type instruction cache memory device according to the conventional example. Cache memory consists of several sets. Here, 16 sets are used for explanation, but usually more sets are used. Each set consists of a small number (about 2 to 16) of lines and tags. The number of pairs of lines and tags included in one set is called the set associativity. Here, we assume a set associative cache memory with a set associativity of 4, that is, a 4-way set associative cache memory that has 4 sets of tags and lines per set. Lines are sometimes called blocks, but in the following explanation, they will be unified as lines. Each line stores a small copy of the contents of main memory (command sequence). When copying a part of the contents of the main memory to the cache memory, it is always done in line units. Here, it is assumed that the size per line, that is, the line length is 16 words. Each tag stores a part of the memory address in order to identify which part of the main memory is stored in the corresponding line. It is assumed that the instruction length is one word and the memory address is assigned to each word. In the set associative type cache memory device, the correspondence, that is, the mapping of which line on the cache memory the contents of one line (16 words in this case) in the main memory is copied is performed as follows.

【0003】

The address of the main memory is decomposed into three parts: in-line offset (offset), set number (set no.), And tag (tag). The in-line offset is information indicating which of the lines the content of the desired address is in the line. In the example of FIG. 7, one word is identified from the 16 words included in one line. Therefore, the lower 4 bits of the address are used. Set number (set no.) Is information indicating a set that may contain the contents of the desired address. In the example of FIG. 7, one set is identified from 16 sets, so 4 bits in the address. To use. This 4 bit is usually next to the lower 4 bits used for in-line offset, that is, the 5th to 8th bits from the bottom. The tag is information indicating which part of the main memory is copied to each line, and the rest of the address excluding the bit used as the offset in the line and the set number is used. Here, 4 bits are used as the in-line offset and 4 bits are used as the set number, so assuming that the address is 20 bits wide, 12 bits (= 20-4-4) are used as the tag. After all, as for the address of the main memory, the upper 12 bits are used as a tag, the next 4 bits are used as a set number, and the lower 4 bits are used as an in-line offset. The controller (14) controls the reading and writing of the contents of each tag and line, and the contents output from the tag (tag) are input to the comparison mechanism (10-13) and output from the line (line). The content is output via the selector (15). In addition, each comparison mechanism (10-13) compares whether or not the tag information requested from the processor core matches the contents stored in the cache memory tag.

【0004】

A case where the cache hits, that is, the contents of the desired address can be found in the cache memory will be described with reference to FIG. For example, consider a case where the contents of address 5AC83 (hexameric) of the main memory are searched from the cache memory in response to a request from the processor core. First, the address of the main memory is decomposed into three parts: tag, set number, and offset in line. As mentioned above, the tag is "5AC" because it is the upper 12 bits (3 digits in hexadecimal) of the address of the main memory, the set number is "8" because it is the next 4 bits (1 digit in hexadecimal), and the offset in the line is the lower 4 Since it is a bit (1 hexadecimal digit), it is "3". Next, the set whose set number is "8" (set) 8), read the tag and line. Since it is assumed that each set has 4 sets of tags and lines, 4 tags and lines will be read out. Here, it is assumed that the value of each tag is "D4B", "5AC", "A19", and "4F6". Subsequently, the read tag group is compared with the tag calculated from the address. Here, the second tag from the left matches. From this, it can be seen that the second line from the left contains the contents of the desired address 5AC83. To be precise, this line contains 16 words from address 5AC80 to address 5AC8F. Finally, take out the contents (1 word) of address 5AC83 from this line. Since the offset in the line is "3", the fourth word in the line is taken out and passed to the processor core.

【0005】

Next, with reference to FIG. 9, the operation when the cache makes a mistake, that is, the contents of the desired address are not in the cache memory will be described. For example, consider a case where the contents of address C1B59 of the main memory are searched from the cache memory. First, the address "C1B59" of the main memory is decomposed into the tag "C1B", the set number "5", and the offset "9" in the line. Next, the set whose set number is "5" (set) Read 4 sets of tags and lines from 5). Here, it is assumed that the value of each tag is "99D", "101", "2FF", and "B0C". Comparing the four tags read out with the tag "C1B" obtained from the address of the main memory, it can be seen that the cache does not contain the contents of the desired address C1B59 because there is no matching tag. In this case, it is necessary to actually refer to the main memory and read the contents of address C1B59. To be precise, the contents of one line including C1B59, that is, 16 words from C1B50 to C1B5F will be read together. The contents read from the main memory are stored in the cache memory for future reference. The storage is in the form of replacing the contents of one set of four sets of tags and lines included in the set number "5", but which set is dynamically determined by a determined algorithm. The algorithm.

【0006】

The LRU algorithm is generally used as this method. In the LRU algorithm, the longest unreferenced pair is chosen as the tag and line to be replaced. Assuming that the rightmost tag and line have not been referenced for the longest time, the content of this tag is rewritten from "B0C" to "C1B", and the content of the corresponding line is "B0C50 to B0C5F". "Contents of" is rewritten to "Contents of address C1B5F from address C1B50". Next, from this line, one word whose in-line offset is "9", that is, the tenth word is taken out and passed to the processor core as the content of the desired address C1B59.

【0007】

[Problems to be Solved by the Invention]

As can be seen from the above, in the conventional method, in order to search for the desired word for each reference, it is necessary to read all the tags included in the set corresponding to the address and execute the comparison operation, so that a large amount of power is required. There was a problem of consuming it. Furthermore, if the contents of the line are read after the comparison result is obtained, the processing time will be long. Therefore, the line is usually read in parallel with the reading of the tag, so that the problem of power consumption is larger. It becomes. As described above, when the contents of the main memory are copied to the cache memory due to a cache error, the set including the lines to be copied can be specified from the address, but which line in the set is stored is dynamically determined. At the time of each reference, which line of the set is included or not included in any line can be determined until the comparison operation between each read tag in the set and the tag calculated from the address is performed. Absent. This is why all the tags and lines in the set have to be processed. In the conventional method, the operation when a continuous area having a memory is intensively and repeatedly referred to will be described with reference to FIG. FIG. 10 shows the operation of the cache memory having the configuration shown in FIG. 7 when the 126-word instruction from address 8CB47 to address 8CBC4 is repeatedly executed. It seems that most of the references will be cache misses in the first iteration, but when the first iteration is completed, the contents of the cache memory will be as shown in Fig. 10, and all the references in the second and subsequent iterations will be cache hits. This is a perfect condition in terms of processing speed, but it is not attractive in terms of power consumption. If you look closely at Figure 10, you will notice that during repetitive execution, only specific tags and lines in each set will be cache hits, but in the conventional method, which tags and lines will be hits? Since each set will be different, in the end, it will be necessary to always check all the tags and lines in the set corresponding to the address, and a large amount of power will be consumed.

【0008】

The present invention has been made in view of the above problems, and an object of the present invention is to provide a set-associative cache memory device capable of significantly reducing power consumption without lowering the hit rate of the cache memory.

【0009】

[Means for solving problems]

According to the present invention, in a set associative cache memory device having a plurality of sets and having two or more sets of tags and lines per set, one or more sets of tags and lines are grouped together for all sets by executing a dedicated instruction. It is characterized by having a mechanism for prohibiting its use. In addition, there are a plurality of sets, two or more sets of tags and lines per set, a control device that controls writing and reading of the contents of the tags and lines, a register whose value can be set by a dedicated instruction, and the above. It is characterized by including a gating mechanism for gating a read control signal supplied from the control device to the tag and the line by the register. Further, only one of the register and the gating mechanism is provided, and one or more sets of the tag table and the line table can be used, and one or more sets are prohibited. Further, the register and the gating mechanism are provided for each set of the tag table and the line line table, and are characterized in that they can be used independently and the use-prohibited state is set.

【0010】

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, examples of the present invention will be described with reference to the drawings. FIG. 1 is a diagram showing a configuration of a set-associative cache memory device according to a first embodiment of the present invention. The cache memory has a plurality of sets as in the conventional example, and each set is composed of two or more sets of tag tables and line tables. Also, whether the tag information requested from the controller (14) that controls reading and writing of the contents of each tag and line and the processor core matches the contents stored in the tag (tag) of the cache memory. It has a comparison mechanism (10-13) and a selector (15) to compare the two. Further, as compared with the cache memory device of the conventional example, only one specific set (for example, the leftmost set) among the sets of tags and lines included in each line is used as a dedicated instruction. A gating mechanism (16) and a register (17) for temporarily stopping by execution have been added. Specifically, a 1-bit register (17) (mask_cache_register) is introduced, and the value of this register (17) gates the read control signal to the key of 3 sets of tags and lines excluding the leftmost one. Will be done. As dedicated instructions, the value of mask_cache_register is set to 0, and only one set in each set can be operated (called the mask_cache_on instruction), and the value of mask_cache_register is set to 1, and all sets are set. An instruction to enable operation (called a mask_cache_off instruction) is prepared, and when an instruction at a certain consecutive address is repeatedly executed, the mask_cache_on instruction is inserted immediately before it and the mask_cache_off instruction is inserted immediately after that. deep. Then, the set associative type cache memory device shown in FIG. 1 behaves like a cache memory having a set association degree of 1, that is, a direct map type cache memory only during repeated execution.

【0011】

In the following, for convenience of explanation, each set (set 0-set) The set of tags and lines at the same position in F) is called a way. Further, a plurality of tags and a plurality of lines in the same way are collectively referred to as a tag table and a line table, respectively. For example, the set of tags (tag table) and the set of lines (line table) on the leftmost side of each set is called way0, and the set of tags and lines second from the left is called way1 and so on. According to this, the 4-way set associative cache memory device includes four ways from way0 to way3, and in the method shown in FIG. 1, three of the four ways are temporarily stopped. It will be a thing. In setting the way of suspension of use, in the above description, reading is first prohibited by gating the reading signal. Writes are not used unless selected (ie, if the corresponding write signal is negative). The control of the write signal is as follows. With the conventional LRU replacement algorithm, the read signal gating may rewrite the decommissioned way as having not been accessed for the longest time. In general, the LRU replacement algorithm chooses the least accessed way "among all ways", but in the present invention it is necessary to choose the longest unaccessed way "among the available ways". Therefore, in the present invention, the value of the enable / disable register (17) (mask_cache_register) of the way is referred to by the controller (14), thereby making the write signal of the way to be deactivated negative. ..

【0012】

The operation of the set-associative cache memory device of the first embodiment shown in FIG. 1 will be described with reference to FIG. Similar to the conventional example shown in FIG. 10, consider the case where the 126-word instruction from address 8CB47 to address 8CBC4 is repeatedly executed. For the sake of simplicity, assuming that the iterative execution always starts with the instruction execution at address 8CB47 and always ends with the instruction execution at address 8CBC4, the mask_cache_on instruction is immediately applied to the instruction sequence 8CB46 immediately before the instruction sequence to be repeatedly executed. Insert the mask_cache_off instruction at address 8CBC5. During repeated execution, after executing the mask_cache_on instruction, for all references, only the leftmost tag and line (way0) of each set in the cache memory are searched and replaced when a cache miss occurs. Become. Therefore, when the first iteration is completed, as shown in FIG. 2, the contents of the cache memory are all the instruction sequences of the iterative execution portion stored in way0. In the second and subsequent repetitions, a cache hit will occur in the only searched way0. The cache memory of the proposed method behaves in the same way as the conventional method in that almost all memory references become cache misses in the first time of repeated execution and all cache hits occur in the second and subsequent times. Therefore, the processing speed is almost the same between the conventional method and the first embodiment. To be precise, the processing time of the proposed method is longer than that of the conventional method by 2 instructions for executing the mask_cache_on instruction and the mask_cache_off instruction, but during repeated execution, a large number of instructions, generally hundreds to tens of thousands, are generally executed. Is executed, so the increase of 2 instructions before and after repeated execution can be ignored. In the method of the first embodiment, the execution speed is hardly reduced, but most of the cache memory (three-quarters in this embodiment) is stopped during the long process of repeated execution, so that the execution speed is significantly reduced. Power consumption can be saved.

【0013】

A supplementary note is given to the instruction sequence that is repeatedly executed. Examples of the instruction sequence to be repeatedly executed include loop processing and recursive procedure, but in this embodiment, it is premised that all the instruction sequences of the iterative part can be stored with only one way. Therefore, the size of the repeating portion needs to be less than or equal to the product of the number of sets and the line length. In the example used in this example, it is 256 words (= 16 sets x 16 words), but as I refused at the beginning, the number of sets is much smaller than the realistic value for convenience of explanation. Since the number of sets is 256, etc., which is a realistic value, the method of this embodiment can be applied to the repeated execution of a considerably long instruction sequence such as 4096 words (= 256 sets x 16 words). Is. Further, in the method of this embodiment, since the cache memory behaves as a direct map type cache memory during repeated execution, it is not preferable that the instruction sequence to be repeatedly executed includes a call of another procedure (recursive call). Is no problem). This is because the line containing the instruction sequence of the repeating part and the line containing the instruction sequence of the procedure called from the repeating part may be mapped to the same set in the cache memory. However, this can be easily solved by inlining the procedure call from the instruction sequence of the repeating part.

【0014】

Next, a second embodiment of the present invention will be described with reference to FIGS. 3 to 5. FIG. 3 is a diagram showing a configuration of a set-associative cache memory device according to a second embodiment of the present invention. The configuration of the tag table and line table, the controller (14) that controls reading and writing of the contents of each tag and line, the tag information requested by the processor core, and the information stored in the cache memory tag (tag). The comparison mechanism (10-13) and the selector (15) for comparing whether or not the contents match are the same as those in the first embodiment described above. The cache memory device of this embodiment is provided with a register (mask_cache_register) (30-33) and a gating mechanism (20-23) having a number of bits equal to the set associativity, and each bit of the register (bit 0-bit3) is provided. ) Is each way There is a one-to-one correspondence with 0-way3). Ways whose corresponding bit of mask_cache_register is 1 are searched and replaced. Similar to the first embodiment, the control of read stop is determined by the output of the gating mechanism (20-23), and the control of write stop is the value of the register (30-33) by the controller (14). It is done by referencing and thereby making the write signal of the way to deactivate it negative.

【0015】

Normally, all bits are 1, and the entire cache memory operates, but in the repetitive execution part, the value of mask_cache_register is rewritten by executing a dedicated instruction, and only some ways operate as targets for search and replacement. Will be done. For example, in the case of a 4-way set associative cache, the value of mask_cache_register is usually "1111" in binary, but when the value of mask_cache_register is changed to "0010", only way2 is searched and replaced. And the remaining three ways stop. When the iterative execution part ends, the value of mask_cache_register is returned to "1111" by executing the dedicated instruction, and all four ways are searched and replaced again. In this embodiment as well, as in the first embodiment, when a relatively short instruction sequence is repeatedly executed as in loop processing or recursive procedure, the set associativity is temporarily lowered and included in each set. Only a part of the tags and lines can be referred to and updated, and the power consumption can be significantly saved without lowering the hit rate of the cache memory. Further, for the execution of a program whose optimum cache size is known in advance, it is possible to reduce the power consumption without deteriorating the performance by lowering the set associativity until the optimum cache size is obtained. Further, it is particularly effective when it is desired to reduce power consumption even if the performance is slightly lowered, such as the "power saving mode" often seen in notebook computers.

【0016】

Even when the two instruction sequences A and B are repeatedly executed, the value of mask_cache_register is set to "1000" immediately before the instruction sequence A, "0100" is set immediately before the instruction sequence B, and so on. Therefore, it is possible to use different ways for the instruction sequence A and the instruction sequence B, and it is possible to avoid the situation where the copy of the instruction sequence of the other party stored in the cache memory is replaced. For example, assuming that the instruction sequence A is an instruction sequence from A2860 to A28EF and the instruction sequence B is an instruction sequence from B9E10 to B9ECF, the operation of the cache memory according to this embodiment is as shown in FIG. FIG. 4 is a diagram showing an execution state for explaining the operation when two sets of relatively short instruction sequences (instruction sequence A and instruction sequence B) are repeatedly executed alternately. A copy of instruction sequence A is stored in way0 and a copy of instruction sequence B is stored in way1, but since the value of mask_cache_register is set to "1000" during execution of instruction sequence A, only way0 is searched and replaced. In this example, the instruction at address A28A5 is found from way0. While the instruction sequence B is being executed, the value of the mask_cache_register shown in Fig. 5 is set to "0100", so only way1 is searched and replaced. In this example, the instruction at address B9E64 is found from way1. ing. When executing instruction sequence A again, simply set the value of mask_cache_register to "1000", and the copy of instruction sequence A previously stored in the cache memory can be used as it is. The same applies to the command sequence B.

【0017】

When repeatedly executing a relatively long instruction sequence that does not fit in one way, set the value of mask_cache_register to "0011" etc. to use two ways or set it to "1101" etc. It is possible to respond flexibly by using three ways depending on the situation. For example, FIG. 6 shows the state of the cache memory according to this embodiment while repeatedly executing the instruction sequence from CC140 to CC2CF. The value of mask_cache_register is set to "0011", only way2 and way3 are searched and replaced. In this example, the instruction at address CC256 is found in way3. Which way to execute each of the instruction sequences to be repeatedly executed is a dedicated instruction that changes the value of mask_cache_register, and even if it is decided in advance in the form of an instruction argument, for example, "mask_cache 0100". Alternatively, it may be determined dynamically according to an algorithm such as LRU by referring to the record of repeated executions executed in each way in the past.

【0018】

[Effect of the invention]

In the set-associative cache memory device of the present invention, when a relatively short instruction sequence is repeatedly executed as in loop processing or recursive procedure, the set associativity is temporarily lowered and included in each set. Only part of the tags and lines can be referenced and updated. Therefore, the power consumption can be significantly saved without lowering the hit rate of the cache memory.

[Simple explanation of drawings]

[Figure 1]

It is a figure which shows the structure of the set associative type cache memory apparatus which concerns on 1st Example of this invention.

[Figure 2]

It is a figure explaining the operation at the time of repeatedly executing a relatively short instruction sequence of the set associative type cache memory apparatus which concerns on 1st Embodiment of this invention.

[Fig. 3]

It is a figure which shows the structure of the set associative type cache memory apparatus which concerns on the 2nd Example of this invention.

[Fig. 4]

It is a figure explaining the operation when the iterative execution of two sets of relatively short instruction sequences is performed alternately of the set associative type cache memory apparatus which concerns on 2nd Embodiment of this invention.

[Fig. 5]

It is a figure explaining the operation when the iterative execution of two sets of relatively short instruction sequences is performed alternately of the set associative type cache memory apparatus which concerns on 2nd Embodiment of this invention.

[Fig. 6]

It is a figure explaining the operation at the time of repeatedly executing a relatively long instruction sequence of the set associative type cache memory apparatus which concerns on 2nd Embodiment of this invention.

[Fig. 7]

It is a figure which shows the structure of the set associative type cache memory apparatus which concerns on a prior art example.

[Fig. 8]

It is a figure explaining the operation at the time of a cache hit of the set associative type cache memory apparatus which concerns on a conventional example.

[Fig. 9]

It is a figure explaining the operation at the time of a cache miss of the set associative type cache memory apparatus which concerns on a conventional example.

[Fig. 10]

It is a figure explaining the operation at the time of repeatedly executing a relatively short instruction sequence of the set associative type cache memory apparatus which concerns on a prior art example.

[Explanation of symbols]

10, 11, 12, 13 comparison mechanism 14 controller 15 Selector 16, 20, 21, 22, 23 Gating mechanism 17, 30, 31, 32, 33 registers tag tag line line