JP2002055880A - Cache configuration method and processor system - Google Patents

Abstract

(57) [Summary] [PROBLEMS] In a write-back type multiprocessor system, duplicate tag control of a CPU cache is enabled without additional information from a CPU. SOLUTION: The CPU caches 021 and 121 of the CPUs 020 and 120 are set associatively configured with the number of sets k and the number of ways w.
41 is a set associative configuration in which the number of sets is k and the number of ways is w + α. Then, the CPU caches 021, 1
21 and the CPU cache copy tags 041 and 141 do not match, the CPU-SC interface control unit 0
40 and 140 issue a cache invalidation request to the CPUs 020 and 120.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a shared memory multiprocessor system having a multilevel cache, and more particularly to a cache configuration method suitable for improving coherency request control and a processor system using the same.

[0002]

2. Description of the Related Art In recent years, a so-called memory sharing type multiprocessor system having a plurality of processors (CPUs) each having a cache memory has been widely accepted. In such a system, since a plurality of CPUs store copies of the same data line in their respective cache memories, it is necessary to maintain coherency of data between the cache memories. That is, a problem of cache coherency occurs.

Conventionally, various methods have been proposed to solve the problem of cache coherency, but a method of inquiring all CPU caches by a coherency request is general. In this method, when a cache miss occurs in a certain cache memory and the CPU issues a cache registration request, the cache registration request is broadcast as a coherency request to another CPU via a system connection. Upon receiving the coherency request, the CPU searches its own cache memory to determine a cache hit,
The result is notified to the CPU that issued the cache registration request via the system connection. The issuing CPU of the cache registration request executes a necessary cache registration request according to the result of hit determination of the other CPU cache.

[0004] All CPs by this coherency request
The biggest problem with the method of making an inquiry to the U cache is that the CPU that issues the cache registration request must wait for the result of the inquiry to all the caches before registering data in the cache memory, so that the transaction throughput is large. It will be.
In order to solve the problem of transaction throughput, there is a method of providing a cache replication tag. In this method, when an inquiry to all the CPU caches due to a coherency request occurs, a cache hit determination can be performed by the cache duplication tag before accessing the CPU caches, and the response time to the inquiry is reduced.

[0005] This cache copy tag is described in, for example, Japanese Patent Application Laid-Open No. Hei 9-114735.
This publication discloses a parallel coherent read / write-back in a multiprocessor system in which a transaction throughput is reduced by having a CPU cache duplicated tag memory, particularly also including a write-back buffer for temporarily storing exclusive dirty data to be replaced. A transaction processing system is described. Here, the exclusive dirty data is data different from the data in the shared memory (main memory), and indicates that no other cache has a copy of this data.
This occurs when a cache hit occurs in a write request.

When a cache registration request is issued from the CPU and there is no empty entry in the CPU cache, the CP
Replacement occurs in the U cache. If the replacement target is exclusive dirty data, writing back (write back) to the shared memory must be performed. However, it takes time to execute the cache registration request after waiting for the completion of the writing back of the exclusive data. , The execution of the CPU is hindered. Therefore, the exclusive dirty data is temporarily stored in the write-back buffer, the cache registration request is executed first, and then the data in the write-back buffer is written back to the shared memory at an arbitrary time. As a result, the transaction processing time of the cache registration request can be reduced.

In the system of the above publication, k sets of CPs
For the U cache, k + 1 sets of CPU cache copy tags are provided in the submodule, and
PU cache duplicate tags include "exclusive dirty",
Data states such as "shared dirty", "shared clean", and "invalid" are also held, and the CPU cache copy tag controls the CPU cache by a direct map. As described above, "exclusive dirty" indicates that the cache block contains data different from that of the shared memory, and that a copy of this data is not contained in another cache. "Shared dirty" indicates that the cache block contains data different from that of the shared memory, and that a copy of this data also exists in another cache. “Shared clean” indicates that the cache block contains the same data (clean data) as the shared memory, and that a copy of this data also exists in another cache. “Invalid” indicates that the cache block does not contain valid data.

In the above-mentioned conventional write-back multiprocessor system, the exclusive dirty data to be replaced is temporarily stored in a write-back buffer, and then a cache registration request is sent to a sub-module which holds a CPU cache copy tag. When issued, a flag is set to indicate that there has been a write to the write-back buffer associated with this cache registration request. The submodule reads the tag entry of the corresponding set number of the CPU cache copy tag by the cache registration request, and when the data state is valid and the flag is set in the cache registration request, the tag entry is written to the write-back buffer. And the information of the cache registration request is temporarily stored in the k + 1 set number, and when the write-back processing, which is the expected data write-back request, is completed, the information in the k + 1 set number is replaced with the set number. Transcribe to and control.

When a sub-module that maintains the CPU cache duplicate tag receives a cache registration request that requires coherency request processing from another processor, the sub-module refers to the CPU cache duplicate tag and stores it in the CPU cache. When there is target data (at the time of a cache hit), the cache registration request is
To the U element and inform the cache registration request source of the data state. On the contrary, when there is no cache condition (cache miss), the cache registration request requiring coherency request processing is not sent to the CPU element.
A process of responding a cache miss to the cache registration request source is performed. By this processing, the result can be known from the CPU cache copy tag without waiting for the result of the inquiry from the CPU, and the transaction throughput can be reduced.

[0010]

However, in the above prior art, in order for the CPU cache duplication tag to recognize the existence of the data line in the write back buffer, it is necessary to determine whether or not the write back related to the cache registration request has been issued. Additional information from the CPU for determination is required. Further, at the time of the write-back processing, extra access to the CPU cache copy tag is performed, such as reading to the k + 1 set number and writing back the information in the k + 1 set number to the set number.

A first object of the present invention is to realize a suitable CPU cache duplication tag control which enables tracking of blocks in a CPU cache of a multi-way set associative having a write-back buffer without additional information from the CPU. Is to do. A second object of the present invention is to realize CPU cache copy tag control without extra access to a CPU cache copy tag during write-back processing.

[0012]

According to the present invention, the number of sets in the CPU cache is k (k is an integer of 1 or more and is usually a power of 2) and the w-way set associative (w is 2).
In the case of the above integer, which is usually a power of 2, the configuration of the CPU cache duplication tag is represented by the number of sets k and the number of ways w + α.
(Α is generally 1) is a multiple way set associative.

The CPU cache copy tag entry holds the memory address of the shared memory which is the target of the cache registration request or write-back request issued by the CPU, and the control bit used for the replacement algorithm of the CPU cache copy tag entry. I do.

When a cache registration request is issued from the CPU, the sub-module (CPU-SC interface control unit) holding the CPU cache copy tag reads the corresponding set of the CPU cache copy tag from the cache registration request address. If the tag entry of the read set and the cache registration request address do not match, a cache registration request to the shared main memory is issued.
A PU cache copy tag is registered in the set, and a cache registration request is issued to other CPUs via the system connection (SC) in order to inquire all caches to execute coherency request processing.

When a cache registration request is received from the system connection and the address points to a memory address, coherency request processing must be executed. Therefore, the sub-module reads the corresponding set of CPU cache copy tags, and Search for a tag entry that matches the registration request address. If there is a matching tag entry, since the CPU holds the data at that address, it issues a cache registration request to the CPU, and the CPU executes coherency request processing.
If they do not match, the CPU does not hold the data at that address, so it does not issue a cache registration request to the CPU, and the submodule returns an inquiry result by the coherency request processing to the cache registration request source.

When a write-back request is issued from the CPU, the submodule reads the corresponding set of CPU cache duplicate tags and searches for a tag entry that matches the write-back request address. If there is a matching tag entry, invalidate the tag entry.

[0017]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a block diagram showing a configuration example of a multiprocessor system having a CPU cache duplication tag embodying the present invention. This system is
Processor module 0 including CPUs 020 and 120 and CPU-SC interface control units 040 and 140
10, 110, and the main memory 70 as a shared memory
Are connected via an arbitrary system connection (SC) 60 such as a bus or a crossbar switch. Generally, there are two or more processor modules, and it is not necessary to have one shared memory. CPU
020 and 120 are w-way set associative CPUs in which data on the main memory 70 is temporarily stored.
Caches 021 and 121 and write-back buffer 0
22, 122 are included. CPU cache 211,
Reference numeral 121 denotes a cache data memory and a cache tag memory.
Data in the main memory 70 is stored in the cache data memory, and addresses (tag addresses) of the data in the main memory 70 are stored in the cache tag memory.
A data state, a replacement control bit, and the like are stored.
The CPU-SC interface control units 040 and 140 include CPU cache duplicate tag memories (hereinafter, CPU cache duplicate tags) 041 and 141 which are duplicates of the cache tag memories of the CPU caches 21 and 121. CPU cache duplication tags 041, 141
Stores a tag address, a replacement control bit, a validity bit, and the like, as will be described later.

In the present multiprocessor system, as a method of solving the cache coherency problem, a method of inquiring all caches by a coherency request is adopted. Inquiries to all caches by coherency requests are cache registration requests and cache invalidation requests.

When a desired data block does not exist in the CPU caches 21 and 121, the CPUs 020 and 120 perform a CPU interface 030, 1
Issue a cache registration request via CPU 31
The data corresponding to the cache registration request is received via the C interface control units 040 and 140 and the system connection 60, and the data is transmitted to the CPU cache 0.
21 and 121. At the time of this cache miss, the CPUs 020 and 120 select a replacement target block from the w blocks. If the selected block is exclusive dirty data, the CPUs 020 and 120 temporarily move to the write-back buffers 022 and 122, and At the timing, a write-back request is issued via the CPU interfaces 030 and 130.

The CPUs 020 and 120 have a function of receiving coherency requests such as a cache registration request and a cache invalidation request via the CPU interfaces 030 and 130, and providing an appropriate response. For example, CPU0
20 and 120 are CPU-SC interface control units 0
When a cache registration request or a cache invalidation request is received from any one of the CPU cache 02 and the cache invalidation request 40, 140,
Inspect 1, 121. Then, when the data block of the address is held, the state of the data block is appropriately changed (exclusive dirty, shared clean, exclusive clean, invalid), and in some cases, a write-back request is issued. In this case, the data block is not transferred to the write-back buffers 022 and 122, but is immediately sent to the system connection 60 side.

CPU-SC interface control unit 04
Reference numerals 0 and 140 have a function of appropriately processing a cache registration request, a cache invalidation request, a write-back request, and the like received from the CPUs 020 and 120. For example, CPU
When a cache registration request is received from 020 or 120, the cache registration request is transmitted to the system connection 60 via the SC interface 50, the latest data is received from the system connection 60, and the CPU 02
Data return to 0 and 120. CPU 02
When a write-back request and a cache invalidation write-back request described later are received from 0 and 120, the data is reflected in the main memory 70 via the system connection 60. Further, the CPU-SC interface control unit 0
Each of the functions 40 and 140 has a function of receiving a coherency request such as a cache registration request and a cache invalidation request from the system connection 60 via the SC interface 50, and performing an appropriate response. The processing of the CPU-SC interface control units 040 and 140 will be described later in detail.

The system connection 60 has a function of transmitting a cache registration request, a write-back request, and a cache invalidation write-back request received from the processor modules 010 and 110 to the main memory 70. further,
The system connection 60 has a function of broadcasting a cache registration request and a cache invalidation request to all processor modules as a coherency request.

When the main memory 70 receives a cache registration request from the processor modules 010 and 110 via the system connection 60, the main memory 70 sends the corresponding data block to the SC interface 50 and the system connection It has the function of replying via the 60. Also,
When the main memory 70 receives the write-back request and the cache invalidation write-back request from the processor modules 010 and 110 via the system connection 60, the data block of the write-back request and the cache invalidation write-back request is set as the latest data. Main memory 70
It has a function to update the data above.

FIG. 2 shows the CPU cache duplication tag 04
1 is a diagram illustrating a configuration example of 141. FIG. The CPU caches 021 and 121 have a set associative configuration in which the number of sets is k and the number of ways (the number of blocks) is w. On the other hand, the CPU cache copy tags 041 and 141 are
With the same set number k as the CPU caches 211, 121,
A w + α-way set associative configuration is adopted. C
The tag entry 43 of the PU cache copy tags 041 and 141 includes a tag address 44, a replacement algorithm bit (replacement control bit) 45, and an entry validity (validity bit) 46.

CPU cache copy tags 041, 141
The set number determination method of the CPU caches 021 and 1
21 is the same as the determination of the set number. That is, the index part of the address when accessing the CPU cache duplication tags 041 and 141 is the
This is the same as the index part of the address when accessing the PU caches 021 and 121. The tag address 43 holds a tag portion of the address. Replacement
The algorithm bit 45 is used in the replacement algorithm in the CPU cache copy tags 041 and 141. When the entry valid 46 is “1”, it indicates that the tag entry 42 is valid, and “0”
Is a bit indicating that it is invalid.

Hereinafter, referring to FIG. 3 to FIG.
-The operation of the SC interface control units 040 and 140 will be described. This CPU-SC interface control unit 04
The main control at 0 and 140 is to ensure the consistency of the CPU cache copy tags 041 and 140 with the CPU caches 21 and 121, and to control the CPU cache copy tags
This is a coherency inquiry response using the 140.

FIG. 3 is a flowchart showing the operation when the CPU-SC interface control units 040 and 140 receive a cache registration request from their own CPUs 020 and 120.

When desired data does not exist in the CPU caches 21 and 121 (cache miss) at the time of memory read or memory write, the CPUs 020 and 120 issue a cache registration request.
1, a block to be replaced is selected from the corresponding set of 121, data corresponding to the cache registration request received from the system connection 60 side is stored in the block to be replaced, and a cache registration request to the corresponding cache tag entry is stored. The registration of the tag address and other necessary processing are executed. Also, the CPUs 020 and 12
In the case of 0, when exclusive dirty data exists in the replacement target block, the data is moved to the write-back buffers 022 and 122 in advance and a write-back request is issued at an appropriate timing. CPU-SC interface control unit 040 at the time of this write back request,
The operation of 140 will be described later.

Referring to FIG. 3, CPU-SC interface control units 040 and 141 receiving a cache registration request
Reads the corresponding set of the CPU cache copy tags 041 and 141 using the index part of the address of the cache registration request (step 300). The tag address is compared with the tag part of the address of the cache registration request from the read (w + α) tag entries to find a matching tag entry (step 301). Also,
The entry validity of the (w + α) tag entries is checked to determine whether there is an empty tag entry in the set (step 302). If there is no matching tag entry and there is an empty tag entry, the tag part of the address of the cache registration request is set to the tag address of the empty tag entry, and the entry valid is set to valid (step 304).

If there is a matching tag entry, it is checked whether or not the tag entry is valid (step 303).
No changes are made to this set of zeros. If invalid, step 304 is executed similarly.

On the other hand, if there is no matching tag entry and there is no empty tag entry, the replacement algorithm bits included in the (w + α) tag entries of the set are used, and an appropriate replacement algorithm such as LRU is used. To determine the tag entry to be replaced, and set the entry validity of the tag entry to invalid (step 305). Then, the CPU cache 02 corresponding to the tag entry to be replaced
As a process for invalidating the corresponding entry block 1, 121, an address is generated from the value held in the tag address section of the invalidated tag entry to be replaced, and the CPU interface 030, 130
A cache invalidation request for this address is issued to 20, 20 (step 306).

CPU receiving cache invalidation request
020 and 120 invalidate an entry block corresponding to the cache invalidation request in the CPU caches 21 and 121. At this time, if the data block held in the block is exclusive dirty data, C
The PU 020, 120 sends the cache invalidation write back request together with the data block to the CPU interface 03.
0 and 130 to the CPU-SC interface control units 040 and 140. The CPU-SC interface control units 040 and 140 send this cache invalidation write-back request to the system connection 60.

CPU-SC interface control unit 04
In steps 0 and 140, the tag entry determined to be replenished in step 305 is invalidated and an empty tag entry is created. Therefore, the cache registration request is retried, and the tag address of the cache registration request is added to the tag address of the empty tag entry. The entry is set, and the entry valid is set effectively (step 306).

FIG. 4 is a flowchart showing an operation when the CPU-SC interface control units 040 and 140 receive a cache registration request from the system connection 60.

CPU-SC interface control unit 0 receiving a cache registration request from system connection 60
The CPU cache copy tags 04 and 140 use the index part of the address of the cache registration request.
1 and 141 are read (step 40).
0). From the read (w + α) tag entries, the tag address and the tag part of the address of the cache registration request are compared to find a matching tag entry (step 40).
1). If there is no matching tag entry, the CPU caches 021 and 121 do not hold the address block of the cache registration request, and do not issue the cache registration request to the CPUs 020 and 120 (step 403).
The result of the inquiry to the cache registration request is transmitted to the cache registration request source C via the system connection 60.
Reply to PU020, 120 (step 404). If there is a matching tag entry, it is determined whether the entry validity of the tag entry is valid or invalid (step 402).
Execute 04.

On the other hand, if the comparisons match and the validity of the tag entry is valid in steps 401 and 402, the CPU caches 021 and 121 hold the address of the cache registration request of the inquiry. CPU-SC interface control units 040 and 14
0 issues a cache registration request to the CPUs 020 and 120 (step 405).

CPU-SC interface control unit 04
CPU 02 that has received a cache registration request from 0, 140
0 and 120 check the CPU caches 21 and 120 and issue a write-back request if the data block holds exclusive dirty data. In this case, the exclusive dirty data is written into the write-back buffer 02.
2 and 122, and together with the write-back request, the CPU-SC interface control units 040 and 140
To the system connection 60 side via the Then, the CPUs 020 and 120 execute the CPU cache 211,
The corresponding data block 120 is invalidated.

FIG. 5 is a flowchart showing the operation when the CPU-SC interface control units 040 and 140 receive a cache invalidation request from the CPUs 020 and 120.

The CPUs 020 and 120 perform operations such as initialization of the CPU caches 021, 121 and the like.
When the invalidation factors 1 and 121 occur, a cache invalidation request is issued. In this cache invalidation process, C
The PUs 020 and 120 do not transfer the data to the write-back buffers 022 and 122 for the block in which the exclusive dirty data exists, but issue a cache invalidation write-back request.

CPU-S that has received a cache invalidation request
The C interface control units 040 and 140 use the index part of the address of the cache invalidation request to
The corresponding set of the U cache copy tags 041, 141 is read (step 500). Read (w + α)
The tag address and the tag portion of the address of the cache invalidation request are compared from each other to find a matching tag entry (step 501), and it is determined whether the entry validity of the matching tag entry is valid or invalid (step 501). 502). Then, if there is a tag entry whose comparison matches and the entry validity is valid, the entry validity of the tag entry is invalidated (step 50).
3). No entry matches the tag address, and
Even if they match, if the entry valid of the tag entry is invalid, nothing is done.

FIG. 6 is a flowchart showing the operation when the CPU-SC interface controllers 040 and 140 receive a cache invalidation request from the system connection 60.

The CPU-SC interface control units 040 and 140 that have received the cache invalidation request from the cache connection 60 use the index part of the address of the cache invalidation request to store the corresponding set of the CPU cache copy tags 041 and 141. Read (step 600). (W + α) read tag entries 43
The tag address and the tag part of the address of the cache invalidation request are compared from each other to find a matching tag entry (step 601). If the comparisons do not match, the cache block 211, 121 does not hold the block of the address of the cache invalidation request, so that no cache invalidation request is issued to the CPUs 020, 120 (step 60).
3). If there is a tag entry with a matching tag address, it is determined whether the entry validity of the tag entry is valid or invalid (step 602). If invalid, a cache invalidation request is similarly issued to the CPUs 020 and 120. do not do.

On the other hand, if there is an entry in which the comparison matches and the tag entry valid is valid in steps 601 and 602, the entry valid of the tag entry is invalidated (step 604). Also, CPU cache 0
21 and 121 hold the block of the address of the cache invalidation request.
Issue a cache invalidation request to the client 20 (step 60)
5).

FIG. 7 is a flowchart showing the operation when the CPU-SC interface control units 040 and 140 receive a write-back request from the CPUs 020 and 120.

As described above, the CPUs 020, 120
Issues a cache registration request in response to a cache miss in the CPU caches 21 and 121, and selects a block to be replaced. If this block is exclusive dirty data, the block is moved to the write-back buffers 022 and 122. Then, a write-back request is issued at an appropriate timing. In addition, the CPUs 020 and 120
When a cache registration request for a coherency inquiry is received from another CPU, the CPU caches 021 and 121 are checked, and when the block is exclusive dirty data,
Similarly, a write-back request is issued. In this case, the exclusive dirty data is stored in the write-back buffer 02.
2, 122 without moving to the CPU-SC interface control units 040, 1 along with the write-back request.
The data is transmitted to the system connection 60 via the communication terminal 40.

The CPU-SC interface controllers 040 and 140 that have received the write-back request read the corresponding set of the CPU cache copy tags 041 and 141 using the index part of the address of the write-back request (step 700). The tag address is compared with the tag part of the address of the write-back request from the read (w + α) tag entries, and a matching tag entry is searched (step 701). If there is a tag entry with a matching tag address, it is determined whether the entry valid is valid or invalid (step 702). If there is a tag entry whose comparison matches and the entry validity is valid, the entry validity of the tag entry is invalidated (step 703).

On the other hand, if there is no tag entry with a matching tag address, or if there is a tag entry with a matching tag address but its entry validity is invalid, the CPU cache duplicate tags 041 and 141 can be maintained. Otherwise, an error occurs.

Next, specific transition examples of the CPU cache copy tags 041 and 141 of the present embodiment will be described with reference to FIGS. Here, the CPU cache 021 and the CPU cache copy tag 041 will be described as an example. The number of ways is w = 4, α = 1, and the CPU cache 021 is 4 ways and the CPU cache duplicate tag 041 is 5 ways.

8 to 13, the indexes of the CPU cache 021 and the CPU cache copy tag 041 are read using the same address portion.

FIG. 8 shows an example of a series of operations for setting / resetting the CPU cache copy tag 041 in response to a cache registration / write-back request issued from the CPU 020.

FIG. 8A shows an initial state. In this state, data blocks of tag addresses A, B, C, and D exist in each tag entry of the set number a of the CPU cache 021. Correspondingly, tag addresses A, B, C, and D are set in the tag entries (way 0 to 3) of the set number a of the CPU cache copy tag 041.

FIG. 8B shows a case where a cache registration request E is issued from the CPU 020. Fig. 8 (1)
From the CPU 020 to the CPU cache 021
It is assumed that a cache registration request E of the set number a has been issued due to a cache miss of. In order to secure a storage block for the new cache registration data E, the CPU 020 replaces (replaces) the data block of the tag address A with the set number a, for example. However, the data block A is exclusive dirty data. Therefore, the data is moved (queued) to the write-back buffer 022, and the write-back to the external memory is suppressed. And CPU02
0 outputs the cache registration request E to the CPU-SC interface control unit 040.

CPU-S receiving cache registration request E
The C interface control unit 040 reads the tag entry of the set number a of the CPU cache copy tag 041 (step 300), and the tag addresses A, B, C, and D different from E are set in the ways 0 to 3. And way 4
Is empty, the address of the cache registration request E is set in the empty tag entry of the way 4 (step 3).
04), issue a cache registration request E to the system connection 60;

FIG. 8C shows a case where the CPU 020 issues a write-back request A. From the state of FIG. 8B, the CPU 020 sends the write-back buffer 02
2, the write-back request A of the tag address A in the CPU 2
Issued to the SC interface control unit 040. Upon receiving the write-back request A, the CPU-SC interface control unit 040 reads the set number a of the CPU cache copy tag 041 (step 700), and the tag entry with the same tag address A as the write-back request A and entry validity is valid. Find way 0 (step 70
1, 702), and invalidates the entry validity of the tag entry (step 703).

FIG. 9 shows an example of a series of operations for setting / resetting the CPU cache copy tag 041 in response to a cache registration / write-back request issued from the CPU 020 having a different set number.

FIG. 9A shows an initial state. In this state, data blocks of tag addresses B, C, D, and E exist in the tag entry of the set number a in the CPU cache 022, and data blocks of the tag addresses F, G, H, and I exist in the tag entry of the set number b. Exists. In the write-back buffer 022, there is a data block of the tag address A of the set number a. In the CPU cache copy tag 041, tag addresses A, B, C, D, and E are set in the tag entries of the ways 0 to 4 of the set number a corresponding to the CPU cache 022, and the ways 1 to 4 of the set number b are set. It is assumed that tag addresses F, G, H, and I are set in the tag entry 4.

FIG. 9B shows a case where a cache registration request J is issued from the CPU 020. FIG. 9 (1)
From the CPU 020 to the CPU cache 022
Assume that a cache registration request J of the set number b has occurred due to a cache miss of. In the CPU 020, in order to secure a storage block for new cache registration data J,
The data block of, for example, the tag address I of the set number b is to be replaced. If the data block I is exclusive dirty data, the data block is queued in the write-back buffer 022 and write-back to the external memory is suppressed. . Then, the CPU 020 outputs the cache registration request J to the CPU-SC interface control unit 040.

CPU-S receiving cache registration request J
The C interface control unit 040 reads the tag entry of the set number b of the CPU cache copy tag 041 (step 301), and the tag addresses F, G, H, and I different from J are set in the ways 1 to 4. Since the way 0 is empty, the address of the cache registration request J is set in the empty tag entry of the way 0 (step 30).
4) Issue a cache registration request to the system connection 60.

FIG. 9C shows a case where the CPU 020 issues a write-back request A. From the state of FIG. 9B, the CPU 020 sends the write-back buffer 02
2, the write-back request A of the tag address A in the CPU 2
It is assumed that it has been issued to the SC interface control unit 040.
Upon receiving the write-back request A, the CPU-SC interface control unit 040 sets the CPU cache copy tag 04
A set number a of 1 is read (step 700), a way 0 of a tag entry whose entry validity is valid is found at the same tag address A as the write back request A (steps 701 and 702), and the entry validity of the tag entry is Invalidate (step 703).

FIG. 10 shows a series of operation examples when there is no free space in the tag entry of the corresponding set of the CPU cache copy tag 041 in response to the cache registration request issued from the CPU 020.

FIG. 10A shows an initial state. This state corresponds to the state shown in FIG. The data block of the tag address E corresponding to the set number a exists in the write-back buffer 022, and the CPU cache 021
A, B, C,
There are D data blocks. The tag addresses A, B, C, D, and E are also set in the respective tag entries of the set number a of the CPU cache copy tag 041 corresponding to the CPU cache 21.

FIG. 10B shows a case where a cache registration request F is issued from the CPU 020. FIG.
Assume that a cache registration request F with a set number a has occurred from the CPU 020 due to a cache miss in the CPU cache 021 from the state of (1). In the CPU 020, in order to secure a storage block for the new cache registration data F, the data block of, for example, the tag address C of the set number a is to be replaced.
Is exclusive dirty data, the block C is queued in the write-back buffer 022, and write-back to the external memory is suppressed. Then, the CPU 020
The cache registration request F is output to the CPU-SC interface control unit 040.

CPU-S receiving cache registration request F
The C interface control unit 040 reads the tag entry of the set number a of the CPU cache copy tag 041 (step 300), and since all the ways are set with a tag address different from F, the CPU cache copy tag 041. (Steps 301, 302, and 305). For example, when the tag entry D is selected by the replacement algorithm, the CPU-SC interface control unit 040 invalidates the tag entry D and simultaneously issues a cache invalidation request D to the CPU 020 (step 30).
6).

FIG. 10C shows the issuance of the cache invalidation write-back request D based on the cache invalidation request D. CPU 020 that has received the cache invalidation request D
Invalidates the data block of the tag address D set in the set number a of the CPU cache 021 as a process of the coherency control D. If the data block D is exclusive dirty data, the cache invalidation write A return request D is issued to the system connection 60 via the CPU-SC interface control unit 040, and the exclusive dirty data is sent to the system connection 60. In this case, the CPU 020 does not store the exclusive dirty data D in the write buffer 022. In the system connection 60, the exclusive dirty data sent with the cache invalidation write-back request D is written back to the main memory 70.

FIG. 10D shows the retry operation of the cache registration request F in the CPU-SC interface control unit 040. From the states of FIGS. 10 (2) and (3), C
Since there is a space for a tag entry in the set number a of the PU cache copy tag 041, the CPU-SC interface control unit 040 retries the cache registration request F. That is, the cache registration request F causes the CPU-SC
The interface control unit 040 reads the tag entry of the set number a of the CPU cache copy tag 041, and a tag address that does not match F is set in the ways 0 to 2 and 4, and the tag entry of the way 3 is empty. The tag address of the cache registration request F is set in the tag entry of way 3 and its entry validity is validated (step 307).

FIG. 11 shows an example of a series of operations for resetting the CPU cache copy tag 041 in response to a cache registration request issued from the system connection 60.

FIG. 11A shows an initial state. In this state, data blocks of tag addresses A, B, C, and D exist in each tag entry of the set number a of the CPU cache 021. Correspondingly, tag addresses 44A, B, C, and D are set in the tag entries of ways 0 to 3 of the set number a of the CPU cache copy tag 041.

FIG. 11B shows the system connection 60.
Shows a case where a cache registration request B has been issued from. From the state of FIG.
Assume that a cache registration request B of the set number a has occurred due to a cache miss in the U cache 121. Upon receiving the cache registration request B broadcasted by the system connection 60, the CPU-SC interface control unit 040 reads the tag entry of the set number a of the CPU cache copy tag 041 (step 40).
0), since the way 1 of the valid tag entry is found at the same tag address A as the cache registration request B (steps 401 and 402), the cache registration request B is issued to the CPU 020 (step 405).

FIG. 11C shows execution of the write-back request B. The CPU 020 that has received the cache registration request B from the other CPU 120 performs the coherency control B process. If the data block of the tag address B set in the set number a of the CPU cache 021 is exclusive dirty data, the data B Since this is the latest data, the latest data B is returned to the issuing CPU 120, and the data block B is invalidated in order to write it back to the main memory 70.
The exclusive dirty data B is issued to the PU-SC interface control unit 040 and sent to the CPU-SC interface control unit 040. In this case, CPU020
Writes exclusive dirty data B to write-back buffer 02
2 is not stored. Upon receiving the write-back request B, the CPU-SC interface control unit 040
The set number a of the PU cache copy tag 041 is read (step 700), and a way 1 of a tag entry whose entry validity is valid at the same tag address B as the write-back request B is found (steps 701 and 702). Is invalidated (step 703). Then, the write-back request B is issued to the system connection 60 so as to be reflected in the main memory 70, and the exclusive dirty data B is passed.

In the system connection 60, the exclusive dirty data B is written back to the main memory 70,
The latest data B is transferred to the CPU 120 as a response to the cache registration request B. Note that the system connection 60 notifies the CPU 120 that the CPU 020 has the latest data as a response to the cache registration request B.
20 may access the main memory 70.

FIG. 12 shows an example of a series of operations for resetting the CPU cache copy tag 041 in response to a cache invalidation request issued from the system connection 60.

FIG. 12A shows an initial state. In this state, the tag addresses A,
There are B, C, and D data blocks. Correspondingly, tag addresses A, B, C, and D are set in respective tag entries of ways 0 to 3 of the set number a of the CPU cache copy tag 041.

FIG. 12B shows the system connection 60.
Shows a case where a cache invalidation request C has been issued from. It is assumed that a cache invalidation request C with a set number a has been issued from another CPU 120 from the state of FIG. Upon receiving the cache invalidation request C broadcast by the system connection 60, the CPU-SC interface control unit 040 reads the tag entry of the set number a of the CPU cache copy tag 041 (step 600), and Since the entry valid found a valid tag entry (way 2) at the same tag address 44C (steps 601 and 60)
2), invalidate the entry validity of the tag entry (step 604), and issue a cache invalidation request C to the CPU 020 (step 605).

FIG. 12C shows execution of the cache invalidation write-back request C. Upon receiving the cache invalidation request C from the other CPU 120, the CPU 020 invalidates the data block of the tag address C set in the set number a of the CPU cache 021 as a process of the coherency control C. Issues a cache invalidation write back request C to the system connection 60 via the CPU-SC interface control unit 040, and sends the exclusive dirty data to the system connection 60. The system connection 60 stores dirty data in the main memory 7.
Write back to 0.

FIG. 13 shows a CPU cache copy tag 0 in response to a cache registration request issued from the CPU 020.
41 is another example of a series of operations for setting / resetting 41.

FIG. 13A shows an initial state. In this state, data blocks of tag addresses A, B, C, and D exist in each tag entry of the set number a of the CPU cache 021. Correspondingly, tag addresses A, B, C, and D are set in respective tag entries of ways 0 to 3 of the set number a of the CPU cache copy tag 041.

FIG. 13B shows a case where a cache registration request E is issued from the CPU 020. FIG.
Assume that a cache registration request E of the set number a has occurred from the state of (1) due to a cache miss of the CPU cache 21 from the CPU 020. In order to secure a storage block for new cache registration data E, the CPU 020 replaces (replaces) a data block with a set number a, for example, a tag address A. In this example,
Since the data block A is not exclusive dirty data, the data block A is not moved (queued) to the write-back buffer 22. CPU020
Outputs the cache registration request E to the CPU-SC interface control unit 040.

CPU-S receiving cache registration request E
The C interface control unit 040 reads the tag entry of the set number a of the CPU cache copy tag 041 (step 300), and a tag address not matching E is set in the ways 0 to 3, and the way 4 is empty. The address of the cache registration request E is set in the empty tag entry of this way 4 (steps 301 and 30).
2, 304), and issues a cache registration request to the system connection 60.

FIG. 13C shows a case where the CPU 020 issues a cache registration request F next. Figure 1
Assume that a cache registration request F with a set number a has occurred from the CPU 020 due to a cache miss in the CPU cache 021 from the state of 3 (2). The CPU 020 replaces the data block of the tag address C with the set number a in order to secure a storage block of the new cache registration data F. However, since the data block C is exclusive dirty data, the write-back buffer 0
22 to suppress write-back to the external memory. Then, the CPU 020 outputs the cache registration request F to the CPU-SC interface control unit 040.

CPU-S receiving cache registration request F
The C interface control unit 040 reads the tag entry of the set number a of the CPU cache copy tag 041 (step 301), and the tag addresses that do not match F are set to 0 to 4 in all the ways.
An operation to empty a tag entry from the set number a of the cache copy tag 041 is performed (step 305). CPU-
When, for example, the tag entry A of the way 0 is selected by the replacement algorithm, the SC interface control unit 040 invalidates the entry validity of the tag entry A and simultaneously issues the cache invalidation request A to the CPU 020 (step 306).

FIG. 13D shows execution of the cache invalidation request A. CPU that received cache invalidation request A
Step 020 searches for a data block of the tag address A set in the set number a of the CPU cache 021 as a process of the coherency control A, but terminates without doing anything because this is not an example.

CPU-SC interface control unit 040
Then, the set number a of the CPU cache copy tag 041
Since the tag entry is free, the cache registration request F is retried. That is, in response to the cache registration request F, the CPU-SC interface control unit 040 reads the tag entry of the set number a, and
Since the tag address which does not match the tag address is set and the tag entry of the way 0 is empty, the tag address of the cache registration request F is set to the tag entry of the way 0, and the entry validity is made valid (step 307).

In FIG. 13B, the CPU cache 02
1 and the CPU cache copy tag 041 are not the same, but the tag address A of the set number a in the CPU cache copy tag 041 can be a replacement target that occurs in the CPU cache copy tag 041 anytime.
After that, the processing becomes the same.

Although the embodiments of the present invention have been described above, these embodiments are merely examples, and it goes without saying that the present invention is not limited to these embodiments.

[0085]

As described above, according to the CPU cache duplication tag configuration of the present invention, it is possible to track data blocks in a multi-way set associative cache including a write-back buffer without additional information from the CPU. Thus, a multiprocessor system using a suitable coherence request control method can be realized. Further, it is possible to support a CPU element having a write-back buffer of a plurality of lines, and an effect of improving performance can be obtained.

[Brief description of the drawings]

FIG. 1 is a diagram showing a configuration of a multiprocessor system according to an embodiment of the present invention.

FIG. 2 is a conceptual diagram showing a CPU cache copy tag according to the embodiment of the present invention.

FIG. 3 is a flowchart illustrating an example of an operation of a CPU-SC interface control unit according to the embodiment of the present invention.

FIG. 4 is a flowchart illustrating another example of the operation of the CPU-SC interface control unit according to the embodiment of the present invention.

FIG. 5 is a flowchart illustrating yet another example of the operation of the CPU-SC interface control unit according to the embodiment of the present invention;

FIG. 6 is a flowchart illustrating yet another example of the operation of the CPU-SC interface control unit according to the embodiment of the present invention;

FIG. 7 is a flowchart illustrating yet another example of the operation of the CPU-SC interface control unit according to the embodiment of the present invention; It is a conceptual diagram.

FIG. 8 is a conceptual diagram showing an example of a control operation of a CPU cache copy tag according to the embodiment of the present invention.

FIG. 9 is a conceptual diagram showing another example of the control operation of the CPU cache duplicate tag according to the embodiment of the present invention.

FIG. 10 is a conceptual diagram showing still another example of the control operation of the CPU cache duplicate tag according to the embodiment of the present invention.

FIG. 11 is a conceptual diagram showing still another example of the control operation of the CPU cache duplicate tag according to the embodiment of the present invention.

FIG. 12 is a conceptual diagram showing still another example of the control operation of the CPU cache duplicate tag according to the embodiment of the present invention.

FIG. 13 is a conceptual diagram showing still another example of the control operation of the CPU cache duplicate tag according to the embodiment of the present invention.

[Explanation of symbols]

010, 110 Processor module 020, 120 CPU 211, 121 CP of w-way set associative
U cache 022, 122 Write-back buffer 030, 130 CPU interface 040, 140 CPU-SC interface control unit 041, 141 w + α way set associative CPU cache copy tag 43 Tag entry 44 Tag address 45 Replacement algorithm bit 46 Entry valid 50 SC interface 60 System connection (SC) 70 Shared main memory

──────────────────────────────────────────────────続 き Continued on the front page (51) Int.Cl. ⁷ Identification symbol FI Theme coat ゛ (Reference) G06F 15/177 682 G06F 15/177 682J (72) Inventor Masafumi Shibata 1st Horiyamashita, Hadano-shi, Kanagawa (72) Inventor Kazuyasu Akimoto Kazuyasu Akimoto 1 Horiyamashita, Hadano-shi, Kanagawa F-term in Enterprise Server Division, Hitachi Corporation (Reference) 5B005 JJ11 KK13 MM01 NN31 NN45 PP03 PP11 PP21 TT02 5B045 DD01 DD13

Claims (4)

[Claims] 1. A CPU having a built-in CPU cache and C
CPU-SC with built-in PU cache duplicate tag memory
A plurality of processor modules having an interface control unit and a main memory are connected to a system connection (S
C) a cache configuration method in a multiprocessor system coupled via C), wherein the CPU cache of the CPU is set associative with the number of sets k and the number of ways w, and the CPU cache duplicate tag memory of the CPU-SC interface control unit. Is a set associative with the number of sets k and the number of ways w + α. 2. The cache configuration method according to claim 1, wherein when a cache registration request is issued from the CPU due to a CPU cache miss, the CPU-SC interface control unit sets the address of the cache registration request to the CP.
Register in the empty entry of the U-cache duplicate tag memory,
When there is no empty entry, the replacement target entry is selected, the address of the cache registration request is registered in the selected entry, and an invalidation request of the selected entry block is issued to the CPU. Cache configuration method. 3. The cache configuration method according to claim 1, wherein, when a cache registration request is received from a system connection, the CPU-SC interface control unit checks a CPU cache duplicate tag memory, and A cache configuration method, wherein when the address is held, the cache registration request is sent to the CPU. 4. In a multiprocessor system in which a CPU, a plurality of processor modules each having a CPU-SC interface control unit, and a main memory are connected via a system connection (SC), the number of CPUs is k. A set associative CPU cache having the number of ways w; and the CPU-SC interface control unit including a set associative CPU cache duplicate tag memory having the number of sets k and the number of ways w + α as a copy of the CPU cache. Multiprocessor system.