JPH0228738A - Method for substituting block of multi-hierarchy cache memory - Google Patents

Abstract

PURPOSE:To store new blocks in an order which is requested from a processor in a low-level cache memory by segmenting the blocks of the low-level cache memory in accordance with the storage state of the low-level cache memory. CONSTITUTION:When a block request is given to a cache memory 3 in level '1' as the cache memory of the low-level, a cache memory 2 in level '0' as the cache memory of a high-level simultaneously gives the notice of a block which is to be substituted by said block. Thus, the blocks can be segmented to these stored in the memory 2, and those which are not stored in the memory 3. When the blocks are substituted, the memory 3 sets only the blocks which are not included in the memory 2 to be the object of substitution, and stores the new blocks in the order which the processor has requested. Consequently, the blocks are substituted in the memory 3 in the same way as a case when there is not memory 2, and the new block which the processor has requested can be taken priority and stored in an internal part.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a cache memory block replacement method in an information processing device configured with a multi-layered cache memory.

[Conventional technology]

FIG. 4 shows a configuration example of a multi-tiered cache memory for explaining a conventional block replacement method.

This is located between processor 1 and main memory 4 at level 0.
This is an example in which a two-level cache memory is arranged, consisting of a cache memory 2 (upper level) and a cache memory 3 (level 1 (lower level)). In FIG. 4, the capacity of level 1 cache memory 3 is equal to the capacity of level 0 cache memory 2.
The capacity of the memory 4 is twice the capacity of the level 1 cache memory 3. 5 indicates one block, and each memory has the same capacity.

The level O cache memory 2, the level 1 cache memory 3, and the main memory 4 are divided into a plurality of columns (four columns in FIG. 4), and blocks 5 included in the same column of the main memory 4 are divided into level O The level 1 cache memory 2 and the level 1 cache memory 3 are stored in the same column. Furthermore, in each column of the cache memory 2 at level ○ and the cache memory 3 at level 1, each block is stored in the order in which the blocks were requested in the past.

In Figure 4, this is shown as new←old.

Hereinafter, conventional block replacement processing for the configuration example shown in FIG. 4 will be explained with reference to FIGS. 5 and 6.

Now, in the initial state, blocks are stored in the level O cache memory 2 and the level 1 cache memory 3 as shown in FIG. 6(a) for the block group of the main memory 4 shown in FIG. , processor 1 requests data in each block in the order of blocks 01, 02, 01.03, and 04.

First, when data in block 01 is requested from processor 1, block 0 is stored in cache memory 2 at level O.
1 exists, so when the level O cache memory 2 transfers the data in block 01 to the processor 1, it immediately rearranges the blocks stored in the 0th column in the order requested by the processor 1 ( Step 5 in Figure 5
01°502, 5], 2. 513).

After processing when block 01 is requested from processor 1, cache memory 2 at level O and cache memory at level 1
The state of the cache memory 3 is as shown in FIG. 6(b).

Next, when the processor 1 requests the data in block 02, the cache memory 2 at level 0 does not store block 02 internally, so it requests block 02 from the cache memory 3 at level 1, and Among the blocks in the 0th column, the block O0 for which the oldest request from the processor was made is selected as the block to be replaced by block 02 (steps 501, 502, 5 in FIG. 5).
03.504. ).

Level 1 cache memory 3 has block 02, so level 0 cache memory 2 has block 0.
2 is transferred (block transfer).

\Moreover, the blocks stored in the 0th column are set to level O.
from the cache memory 2 in the requested order (steps 505, 509, and 510 in FIG. 5). The cache memory 2 at level 0 is block OO in the 0th column.
is replaced with block 02 transferred from the level 1 cache memory 3 (step 511 in FIG. 5). Thereafter, the level O cache memory 2 is stored in the processor 1.
When the data in block 02 is transferred, the blocks stored in the 0th column are rearranged in the order requested by processor 1 (512 and 513 in FIG. 5).

After processing when block 02 is requested from processor 1, cache memory 2 at level O and cache memory 2 at level 1
The state of the cache memory 3 is as shown in FIG. 6(c).

Next, when processor 1 requests the data in block 01 again, since block 01 exists in level 0 cache memory 2, level 0 cache memory 2
transfers the data in block 01 to processor 1, and 2 also rearranges the blocks stored in the 0th column in the order requested by processor 1 (steps 5.1, 502.512 in Figure 5). .503).

After processing when block 01 is requested again from processor 1, the states of level 0 cache memory 2 and level 1 cache memory 3 become as shown in FIG. 6(d).

Next, when data in block 03 is requested from processor 1, cache memory 2 at level 0
3 is not stored internally, and the level 1 cache memory 3 stores block 03. The process at this time is
This is similar to the case where the data in block 02 was requested. That is, block 03 is transferred from level 1 cache memory 3 to level O cache memory 2, and level 0 cache memory 2 transfers block 0 to the block in the 0th column for which the request from processor 1 was made the earliest.
2 is replaced with block 03 and the data in block 03 is transferred to processor 1. At the same time, the blocks stored in the 0th column are rearranged in the order requested by processor 1.

On the other hand, the level 1 cache memory 3 rearranges the blocks stored in the 0th column in the requested order from the level 0 cache memory 2.

After processing when block 03 is requested from this processor 1, cache memory 2 at level O and cache memory 2 at level 1
The state of the cache memory is as shown in FIG. 6(e).

Next, when processor 1 requests data in block 04, cache memory 2 at level 0 does not store block 4 internally, so when requesting block o4 from cache memory 3 at level 1, data in block 04 is also requested. Then, among the blocks in the 0th column, block 01, for which the request from processor 1 was made the oldest, is selected as the replacement block (
Steps 501, 502, 503, 504 in FIG.

On the other hand, block 04 also exists in level 1 cache memory 3.
Since there is no cache memory 3 at level 1,
When block 04 is requested from main memory 4, block 01, which has been requested from level O cache memory 2 the oldest among the blocks in the 0th column, is selected as the block to be replaced with block 04. (Steps 505, 506, 507 in FIG. 5). When block 04 is transferred from main memory 4 (block transfer), level 1 cache memory 3 replaces block 01 in the 0th column with block 04 transferred from main memory 4 (as shown in FIG. 5). Step 508). After that, when the level 1 cache memory 3 transfers the block 04 to the level 0 cache memory 2,
The blocks stored in the column are rearranged from the level O cache memory 2 in the requested order (steps 509 and 510 in FIG. 5).

The level O cache memory 2 replaces the block 01 in the 0th column with the block 4 transferred from the level 1 cache memory 3 (step 511 in FIG. 5).

Thereafter, when the cache memory 2 at level 0 transfers the data in block 04 to the processor 1,
The blocks stored in the columns are rearranged in the order requested by processor 1 (steps 512 and 513 in FIG. 5).

After processing when block 04 is requested from processor 1, cache memory 2 at level O and cache memory 2 at level 1
The state of the cache memory 3 is as shown in FIG. 6(f).

[Problem to be solved by the invention]

Generally, the more recent a block is requested by the processor, the higher the probability that it will be requested again by the processor.
It must be stored in cache memory. but,
In the conventional block replacement method, as described above, the lower level cache memory uses only the information of the block requested from the upper level cache memory, and the accesses made to the upper level cache memory from the processor Because blocks were replaced independently from the processor, the lower level cache memory had the drawback that new blocks were not necessarily stored in the order requested by the processor. In the example of FIG. 6, although processor 1 requests data in blocks in the order of blocks 01, 02, 01, 03, and 04, processor 5 requests data in the third order. New block 01 is level 1 cache memory 3
Not stored in .

SUMMARY OF THE INVENTION An object of the present invention is to provide a block replacement method that allows a lower level cache memory to store a new block in the order requested by a processor in a multi-level cache memory.

[Means to solve the problem]

In order to achieve the above object, in the multi-level cache memory block replacement method of the present invention, blocks in the lower level cache memory are divided into blocks stored in the upper level cache memory and blocks not stored in the upper level cache memory. , when a block is replaced in a lower level cache memory, a block that is not stored in an upper level cache memory is targeted for replacement.

[For production]

When the upper level cache memory issues a block request to the lower level cache memory, it also notifies the block to be replaced by the block at the same time. This results in
In the lower level cache memory, blocks can be divided into blocks stored in the higher level cache memory and blocks not stored in the higher level cache memory.

When replacing blocks, the lower level cache memory replaces only blocks that are not included in the upper level cache memory, and stores new blocks in the order requested by the processor. As a result, blocks in the lower-level cache memory are replaced in the same way as if there was no upper-level cache memory, and new blocks requested by the processor can be given priority and stored internally. .

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram for explaining an embodiment of the block replacement method of the present invention, in which 1 is a processor, 2 is a level 0 cache memory, 3 is a level 1 cache memory,
4 is the main memory.

The configuration in Figure 1 is basically the same as the configuration in Figure 4,
Level O cache memory 2, level 1 cache memory 3, and main memory 4 are divided into four columns, and the capacity of level cache memory 3 is twice the capacity of level O cache memory 2, and the capacity of main memory 4 is It is assumed that the capacity is twice that of the level 1 cache memory 3. 5 indicates one block, and each memory has the same capacity.

Blocks included in the same column of main memory 4 are stored in the same column of level 0 cache memory 2 and level 1 cache memory 3. In this case, for each column of the cache memory 2 at level O, blocks are stored in the order in which requests are made from the processor 1 as in the past, but for each column of the cache memory 3 at level 1, blocks are stored at level O. Blocks stored in the cache memory 2 of level O]1 are divided into blocks b that are not stored in the cache memory 2 of level O, and blocks b that are not stored in the cache memory 2 of level O are are stored in the order in which they were stored in the level O cache memory 2. In FIG. 1, the replaced order is shown as new←old.

An example of block replacement processing according to the present invention will be described below with reference to FIGS. 2 and 3 for the configuration example shown in FIG. 1.

Now, as an initial state, blocks are stored in the level O cache memory 2 and the level 1 cache memory 3 as shown in FIG. 3(a) for the block group of the main memory 4 shown in FIG. shall be. In this state, processor 1 blocks blocks 01, 02, 01, 03.
, 04 will be described below.

First, when data in block 01 is requested from processor l, block 0 is stored in cache memory 2 at level O.
1 exists, so when the level O cache memory 2 transfers the data in block 01 to the processor 1, it immediately rearranges the blocks stored in the 0th column in the order requested by the processor 1 ( Step 2 in Figure 2
01°202.212,213).

After processing when block 01 is requested from processor 1, cache memory 2 of level 0 and cache memory 2 of level 1
The state of the cache memory 3 is as shown in FIG. 2(b). This is the same as FIG. 6(b).

Next, when processor 1 requests data in block 02, cache memory 2 at level O does not store block o2 internally, so the request from processor 1 is the most requested among the blocks in the 0th column. The old block OO is selected as the block to be replaced with block 02, and block 0 is selected for level 1 cache memory 3.
When a request is made to transfer block 02, it is notified that block OO will be replaced with block 02 (steps 201, 202, 203, and 204 in FIG. 2).

Since block O2 exists in level 1 cache memory 3, level O cache memory 2 has block 0.
2 (steps 205 and 209 in FIG. 2). After that, the cache memory 3 at level 1 will have block 00
When the storage position of block 02 is swapped, the blocks b that are not stored in the 0th column of the level 0 cache memory 2 are rearranged in the order in which they were stored in the level 0 cache memory 2 (Fig. 2). step 210).

The level O cache memory 2 replaces the block OO in the 0th column with the block 02 transferred from the level 1 cache memory 3 (step 211 in FIG. 2).
. After that, the level O cache memory 2 transfers the data in block 02 to the processor 1, and at the same time rearranges the blocks stored in the 0th column in the order requested by the processor 1 (see Figure 2). 212, 213)
.

After processing when block 02 is requested from processor 1, cache memory 2 at level 0 and cache memory 2 at level 1
The state of the cache memory 3 is as shown in FIG. 2(c). In contrast to Fig. 6(c), in Fig. 2(C), level 1
In the cache memory 3, the locations of block OO and block 01 are swapped.

Next, when processor 1 requests the data in block 01 again, since block 01 exists in level 0 cache memory 2, level O cache memory 2
transfers the data in block 01 to processor 1, and at the same time rearranges the blocks stored in the 0th column in the order requested by processor 1 (steps 20, 202, 212, 213 in Figure 2). ).

After processing when block 01 is requested again from processor 1, the states of level 0 cache memory 2 and level 1 cache memory 3 are as shown in FIG. 2(d).

Next, when data in block 03 is requested from processor 1, cache memory 2 at level O
3 is not stored internally, and the level 1 cache memory 3 stores block 03. The process at this time is
This is similar to the case where the data in block 02 was requested. In other words, since the cache memory 2 at level O does not store block 03 internally, it requests block 03 from the cache memory 3 at level 1, but at the same time it requests block 03 from the cache memory 3 at level 1.
Notification is made that block 02, which was the oldest block in the column for which a request was made from processor 1, will be replaced with block 03. Level 1 cache memory 3 is level O
The block 03 is transferred to the level O cache memory 2, and the level O cache memory 2 transfers the block 02 to the block 0.
3 and transfers the data in block 03 to processor 1, the blocks stored in the 0th column are rearranged in the order requested by processor 1. On the other hand, in the level 1 cache memory 3, when the storage locations of blocks 02 and 03 are swapped, block b, which is not stored in the 0th column of the level O cache memory 2, is transferred to the level O cache memory 2. Rearrange them in the order in which they were stored.

After processing when the block 03 is requested from the processor 1 at 1, the state of the level O cache memory 2 and the level 1 cache memory becomes as shown in FIG. 3(e).

Next, when processor 1 requests data in block 04, cache memory 2 at level 0 does not store block 04 internally, so the request from processor 1 is the most requested among the blocks in the 0th column. If you select block 01, which was executed in the past, as a replacement block and request block 04 from level 1 cache memory 3,\
also informs that block 01 is to be replaced with block 04 (steps 201, 202, 203 . in FIG. 2).
204).

On the other hand, block 04 also exists in level 1 cache memory 3.
Since there is no cache memory 3 at level 1,
When block 04 is requested from the main memory 4, block 00, which is the oldest to no longer be stored in the level 0 cache memory 2 among the blocks in the 0th column, is selected as the block to be replaced with block 04. Steps 205, 206, 207 in Figure 2). When the block 04 is transferred from the main memory I74 (block transfer), the level 1 cache memory 3 replaces the block 04 in the 0th column with the block 04 transferred from the main memory 4, and the level 0 cache Transfer block 04 to memory 2 (steps 208 and 20 in FIG.
9). Thereafter, the level 1 cache memory 3
When the storage positions of block 01 and block 04 in the column are swapped, block b in the 0th column, which is not stored in the level O cache memory 2, is changed to the order in which it was stored in the level 0 cache memory 2. Reorder (step 210 in FIG. 2).

The level O cache memory 2 replaces the block 01 in the 0th column with the block 4 transferred from the level 1 cache memory 3 (step 211 in FIG. 2).

Thereafter, when the cache memory 2 at level O transfers the data in block o4 to processor 1,
The blocks stored in the columns are rearranged in the order requested by processor 1 (steps 212 and 213 in FIG. 2).

After processing when block 04 is requested from this processor 1, cache memory 2 of level ○ and cache memory 1 of level 1
The state of the cache memory 3 is as shown in FIG. 3(f).

In the example shown in FIG. 3, processor 1 requests data in blocks in the order of blocks 01, 02, 01゜03.04, and then requests new blocks 01, 02゜03 in the order requested by processor 1. .04 is stored in the level 1 cache memory 3. As a result, block replacement in the lower level cache memory 3 is
This is done in the same way as when there is no upper-level cache memory 2, and it becomes possible to preferentially store new blocks requested by the processor 1 internally.

〔Effect of the invention〕

As described above, according to the present invention, in a multi-tiered cache memory, information on blocks stored in the upper level cache memory is transmitted to the lower level cache memory, and when a block is replaced in the upper level cache memory. By replacing blocks that are not included in the upper level cache memory, it is possible to preferentially store new blocks in the order requested by the processor. In general, the higher the level of cache memory, the shorter the access time from the processor, and the more recently the block is requested by the processor, the higher the probability that it will be requested again by the processor. By correctly storing data in the cache memory, it is possible to shorten the access time from the processor to the memory.

In addition, in the cache memory of a multiprocessor system, the cache memory and main memory are connected to prevent the processor from executing incorrect processing by storing main memory data that has been rewritten by another processor in the cache memory. It is necessary to control data consistency.

By using the present invention, it is possible to determine whether an arbitrary block (a block containing data rewritten by another processor) is stored in the upper level cache memory from the information in the lower level cache memory. , performs matching control sequentially from the lower level, and if it is determined that the upper level does not store a block containing data that has been rewritten by another processor, matching control for the upper level cache memory is no longer necessary, and the cache There is an advantage in that it is possible to reduce access conflicts between processors and co-controllers in memory.

[Brief explanation of the drawing]

FIG. 1 is a block diagram for explaining an embodiment of the block replacement method of the present invention, FIG. 2 is a flowchart of an example of block replacement processing according to the present invention, and FIG. 3 is a concrete process of the configuration of FIG. 1. A diagram showing an example, FIG. 4 is a block diagram for explaining the conventional block replacement method, FIG. 5 is a flowchart of the conventional block replacement process, and FIG. 6 shows a specific processing example of the configuration of FIG. 4. It is a diagram. DESCRIPTION OF SYMBOLS 1... Processor, 2... Level O cache memory, 3... Level 1 cache memory, 4...
・Main memory, 5...Block, a...Block stored in level O cache memory,
b: Blocks not stored in level O cache memory. 3rd row) Nepya my state, (g) 7' Lomph 01 meeting is 7"L (!LLI41
((,(su7°”lots702ケ♂2゛(line 1 method, (
d) 7'o7701tノ'e, ;ok'R*or4'
lj-shihe"le0I71 7-1, 2+1%7ki11 Shihele1combw,,, = --/F II (e)7"C1y703%'i#k,-ttae4:'
Kl, ζ子) 7. 口, ri. 4 饅H light f11 组悠, 6yan 麺く yt7 to f7shiLX't diagram (αbo?l Kanjobachi (to27pa07〕O decrease 1゛(dai 1+jlr'fi- (c, + ]゛'[777'2 j North is "'f9q" lj
``'B(d) Film 077 Q - #Akako to 'tfu husband lI 仄' J3- MV7 to 1 mesek? 1st 2nd year ∆゛ru O raheyatsu 1A-ru 1's home〉 Meri Ce)7"Otsuyo3j:eHk-Lf'i,,*"l
K'g(su)7°'Dso)o4 tQafF--Lf'
1qLF'j3, ILOQ to Jin Heyasoshini x 7υ L to ゛le 19 Aya V=-Yu〆9 Mhair 0 x 6 to Fujimeri L "Look A Yafushie〆-J

Claims (1)

[Claims] (1) In an information processing device that has multiple cache memories arranged between a processor and main memory, the lower the level, the larger the capacity, the lower level cache memory blocks are stored in the upper level cache memory. A block of a multi-layered cache memory characterized in that the blocks are divided into blocks and blocks that are not stored, and when blocks are replaced in a lower level cache memory, blocks that are not stored in an upper level cache memory are targeted for replacement. Replacement method.