KR0138585B1 - Shared memory multiprocessor using spilt transaction bus - Google Patents

Abstract

A write-invalidate cache system for a multiprocessor system using a separate transaction bus has been presented.

The multiprocessor system includes at least one memory module; A system bus operating under a separate transaction protocol; And a plurality of processor modules each having a processor, a cache, and a state information storage device. The state information storage device provides for each block stored in its processor module as to whether or not an updated copy of that block exists in the memory module when that block is invalidated by another processor module.

Accordingly, when a processor module receives an access request for a block from a processor, the block is invalidated by another processor module, and if the most recently updated copy of the block does not exist in the memory module, By accessing the most recently updated copy of s by communicating with the processor modules, unnecessary memory access is reduced, thus reducing the actual memory access time.

Description

Shared memory multiprocessor with separate transaction bus

Figure 1 illustrates a typical shared memory multiprocessor.

Figure 2 illustrates a typical shared memory multiprocessor with a cache included in each processor module.

3 is a diagram of a conventional shared memory multiprocessor, illustrating a problem when a conventional write invalidation cache coherency maintaining scheme is used under a multiprocessor environment using a separate transaction bus.

Figure 4 illustrates a shared memory multiprocessor including an improved write-validating cache system of the present invention.

5 is a block diagram illustrating an improved write-invalidate cache system of the present invention.

* Explanation of symbols for the main parts of the drawings

100: memory module 200, 200 ': processor module

300: Detachable transaction bus 400,400 ': Processor

500,500 ': cache 510: processor tag cache

511: comparator 520: bus monitor tag cache

521: Comparator 530: status information cache

540: data cache 550: cache controller

560: bus interface

The present invention relates to a multiprocessor, and more particularly, to an improved write-invalidate cache system for a shared memory multiprocessor using a split transaction bus. will be.

Multiprocessing is a common way to increase system computing power by overcoming the limitations of existing single processor technology. In multiple processors, a plurality of instruction streams are performed in parallel, and communication and synchronization between processor modules is accomplished by sharing messages or sharing memory modules.

Shared memory multiprocessors are a very economical way to increase system computing power and speed, largely due to the fact that low-cost, high-performance microprocessors can be economically interconnected via shared memory modules and a common bus. . Figure 1 illustrates a typical shared memory multiprocessor architecture in which multiple processor modules are coupled with multiple shared memory modules by a common bus.

However, there are two fundamental problems in this system configuration: bus contention and multiple processor modules that occur when multiple processor modules try to access a common bus at the same time. Memory contention occurs when trying to access memory modules at the same time. These problems increase memory access time, which in turn reduces the execution speed of multiple processors.

One way to reduce the number of access collisions on a common bus is to have the common bus transmit as much information as possible without unnecessary rest. For example, use a non-split transaction bus that occupies the common bus from when the processor module sends an access request to the memory module over the common bus until it receives a response. Rather, it separates the access request transfer process and the response transfer process from the memory module so that another processor module or memory module can use the common bus while not using the common bus between the access request transfer process and the response process of the memory module. The use of split transaction buses can help reduce the number of access conflicts on the common bus. A more detailed description of the separate transaction bus is described, for example, in US Pat. No. 5,067,071 to D. J. Schanin et al.

Even if the bandwidth of the common bus increases, one memory module can handle one memory access request at a time, resulting in memory conflicts that occur when multiple processor modules attempt to access one memory module at the same time. System degradation due to the present still exists. Therefore, it is important to reduce the traffic between the processor module and the memory module as much as possible.

Processor modules reduce the number of access requests to common buses and memory modules by storing blocks of memory modules that the processor is expected to use frequently in its own cache, which provides less access than memory modules but provides faster access times. Can be. FIG. 2 illustrates a multiprocessor configuration in which all processor modules have caches.

However, in the case of multiple processors, each processor module uses its own cache, so if one processor module writes to a block stored in its own cache, the result of that write is itself in all other processor modules. There is a so-called cache coherence problem that must be reflected in the corresponding blocks stored in the cache. In order to solve this cache coherence problem, various cache coherency methods have been proposed to reduce the number of bus and memory access requests of the processor module. Among these schemes, one of the most widely used is the write-invalidate cache coherence scheme.

In this write-invalidate cache coherence scheme, the cache in the processor module maintains state information for each block stored therein, which state information is stored in at least three possible cache block states (i.e., MODIFIED, INVALID, and SHARED). Express one. The MODIFIED state means that the block has been changed most recently in the cache, but the memory module has not yet been updated. If a block in the MODIFIED state is replaced by a new block according to block replacement, which will be described later, the block must be copied-back to the corresponding memory module. The INVALID state means that the block has been invalidated by another processor module. The SHARED state means that the block has not been modified in the cache, invalidated by another processor module, and is consistent in content with the block stored in the memory module. The cache coherence scheme generally operates as follows for a block access request from a processor in a processor module.

Read hit—a case in which the cache in the processor module holds a block that has been requested to be read in a SHARED or MODIFIED state, wherein the processor module performs a read operation on the block.

Read miss—if the cache in the processor module does not hold a block that has been requested to read (cache failed) or if the block that has been read is held in an INVALID state (invalid invalidation), the processor module Sends a broadcast read request for the block to the module and another processor module. If any one of the other processor modules holds the requested block in the MODIFIED state, the processor module provides the block for the broadcast read request. If another processor module does not hold the requested block in the MODIFIED state, the memory module holding the requested block provides that block for the broadcast read request. Accordingly, the processor module receives the requested block, performs a read operation, and maintains the state of the block in the SHARED state.

Write-hit—a cache in the processor module holds a block that has been requested to be written in the SHARED or MODIFIED state. If the cache is held in the MODIFIED state, the processor module performs a write operation on the block. . If the cache in the processor module holds the requested block in the SHARED state, the processor module sends an invalidation request for that block to another processor module so that all other processor modules are stored in their cache. Invalidate a copy of a block, perform a write operation on the requested block stored in its own cache, and change the state of the block to MODIFIED.

Write miss—when the cache in the processor module does not hold a block that has been requested to write (cache failed), or has a block that has been requested to write in an INVALID state (invalidation failure), the processor module may Send a broadcast read with invalidation request to the memory module and other processor modules, including the invalidation request for the block, at the same time that all other processor modules invalidate copies of the requested block stored in their cache, If one of the other processor modules holds the requested block in the MODIFIED state, the processor module causes the block to be provided in accordance with the broadcast read request containing the invalidation request. Alternatively, if no processor module holds the requested block in the MODIFIED state, the memory module holding the requested block provides the block in response to the broadcast read request containing the invalidation request. Accordingly, the processor module receives the requested block, changes its state to MODIFIED state, and performs a write operation.

Various variations of the write-invalidate cache coherence scheme described above are described, for example, in Per Stensterom's A Survey of Cache Coherence Schemes for Multiprocessors (IEEE Computer, June 1990, pp. 12-24); A Low Overhead Coherence Solution for Multiprocessors with Private Cache Memories (11th ISCA, 1984, pp. 348-354) from Paramarcos, M. and Patel, J .; R. H. Katz et al. Implementing A Cache Consistency Protocol (12th ISCA, 1985, pp. 276-283); And The Symmetry Multiprocessor System (1988 ICPP, Vol. I, August 1988, pp. 303-310) by Tom Lovett and Shreekant Thakkar.

Such conventional write-invalidate cache coherency maintaining schemes generate inefficiencies as described below in a multiprocessor environment using a separate transaction bus, unlike in a multiprocessor environment using a non-separable transaction bus.

As described above, in the conventional write-invalidate cache coherence maintaining scheme, the processor module sends a broadcast read request (including an invalidation request) to a memory module and another processor module whenever an invalidation failure occurs. In addition, the detached transaction bus releases the bus between the memory access request and the corresponding response, allowing the bus to be used by another module during that period.

Under this situation, as shown in the example of FIG. 3, if an invalidation failure occurs for block X in processor module 1, and then a cache failure for another block Y occurs in processor module 2, (memory module is one and Assuming that this memory module has one request buffer, processor module 1 sends a broadcast read request for block X (including an invalidation request), and processor module 2 sends an invalidation request for block Y. Sends a broadcast read request to the memory module and another processor module, thereby causing the memory module to perform a memory read operation on block X for a broadcast read request (including an invalidation request) to block X. But, since the memory module can handle one memory access request at a time, it implies an invalidation request for block Y 1) The broadcast read request is stored in the request buffer, so that processing of a request from processor module 2 completes a response to a request from processor module 1, or holds block X in MODIFIED state. It is delayed until another processor module that is doing (i.e., holding an updated copy of block X) sends information to the memory module that it will provide block X on behalf of the memory module.

However, if one of the other processor modules can know in advance that it has block X in MODIFIED state, processor module 1 sends a broadcast read request for block X (including an invalidation request) only to the other processor modules. Unnecessary memory access can be reduced, and thus the memory module can process the response to broadcast read requests (including invalidation requests) for block Y without delay, thereby reducing the actual memory access time.

It is therefore a primary object of the present invention to provide an improved write-invalidate cache system for a multiprocessor system using a separate transaction bus, thereby solving the problem of maintaining cache coherency and reducing the actual memory access time.

In order to achieve the above object of the present invention and other objects not specifically stated, the present invention is directed to a system bus operating under a split transaction protocol, at least one memory module coupled to the system bus ( A shared memory multiprocessor having a momory module and a plurality of processor modules each coupled to the system bus, each shared processor multiprocessor comprising: a processor; A cache coupled between the processor and the system bus to store blocks; And status information associated with the cache, the status information indicating whether the at least one memory module holds an updated copy of each block when the respective blocks are invalidated for each of the blocks. Including a storage device, when each processor module receives an access request for each block from the processor, the status information indicates that any memory module of the at least one or more memory modules receives the updated copy. If not, it provides a shared momory multiprocessor that accesses the updated copy only by communicating with the plurality of processor modules via the system bus.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

Referring first to FIG. 4, an exemplary block diagram of a shared memory multiprocessor using the improved write-invalidate cache system of the present invention is shown. As shown, at least one or more memory modules 100 and at least two or more processor modules 200 and 200 ′ are coupled to a shared memory multiprocessor by a separate transaction bus 300. Each processor module 200 or 200 'includes a processor 400 or 400' and a cache 500 or 500 '.

In the memory module 100 and the cache 500 or 500 ', data is divided into blocks of the same size and stored. Access to a block stored in cache 500 or 500 'is initiated by passing the block's physical address along with a request for access to the block from processor 400 or 400'. (Caches 500, 500 'all have the same structure and function, and therefore, only cache 500 will be described in detail below. In addition, in the following description of embodiments of the present invention, the cache 500 will be described as follows. A case of using a direct mapping method will be described. However, the present invention provides a method in which the cache 500 has another mapping method, for example, 2-way set-associative maping (Mano, MM, Computer Engineering, Prentice Hall). It should be understood that the same applies to the case of using the same method.

Given the physical address of a block is n bits, for example, the lower k bits are used to access a block in cache 500, and the n bit address is used to access a block in memory module 100. . This lower k bit portion is called a block address, and the remaining upper n-k bit portions are called a tag address. Each block in cache 500 consists of data and tag addresses associated with it. Therefore, when one block is newly stored in the cache 500, the data and the tag address are stored together. In this case, when the physical address of the block arrives at the cache 500 together with an access request for one block from the processor 400 or 400 ', the block address portion of the physical address of the block is cached. The tag address portion of the block's physical address is used to access the block in the block and the tag address portion in the block accessed by the block address portion stored in the cache 500. If the tag address portion and the tag addresser bits from the cache match, it means that the cache 500 holds the block.

In addition, the cache 500 according to the present invention maintains cache block state information indicating the current state of the block for each stored block.

As described above, according to the conventional write-invalidate cache coherence maintaining scheme, when an invalidation failure for one block occurs in a processor module, a read request (including an invalidation request) is transmitted to a memory module and another processor module. This can adversely affect the performance of shared memory multiprocessors. However, as in the present invention, if another processor module knows that the block is in the MODIFIED state, i.e., stores an updated copy of the block, then the read request (which contains an invalidation request) may be executed. Is sent only to the memory module and is excluded from the transaction for the read request (including the invalidation request), thereby eliminating unnecessary memory accesses, thus reducing the actual memory access time.

However, to achieve this improvement, the cache system 500 of the present invention must maintain the INVALID state in at least two cache block states, for example, the NON-COPYBACK-INVALID state and the COPYBACK-INVALID state.

Both the NON-COPYBACK-INVALID state and the COPYBACK-INVALID state mean that the block has been invalidated by another processor module in the shared memory multiprocessor. However, the NON-COPY BACK-INVALID status indicates that the processor module that most recently invalidated the block did not copy back an updated copy of the block it owns to memory module 100, The COPYBACK-INVALID state means that the processor module that most recently invalidated the block has evicted the updated copy of the block it holds to the memory module 100 in accordance with block replacement, which will be described in more detail later.

In addition, according to an embodiment of the present invention, the cache 500 of the present invention may include five additional cache block states as follows. That is, there are five cache block states, MODIFIED-SHARED, MODIFIED, EXCLUSIVE, SHARED-SOURCE, and SHARED, all of which are valid (i.e. not invalidated by other processor modules in the shared memory multiprocessor). Means status.

The MODIFIED-SHARED and MODIFIED states are consistent with those in memory module 100, where the block was most recently updated in cache 500 (that is, cache 500 holds an updated copy of that block). It means not to. The MODIFIED state also means that the block does not exist in a valid state in the other cache 500 '.

The EXCLUSIVE state indicates that the block matches that in the memory module 100, and that the block does not exist in a valid state in the other cache 500 '.

The SHARED-SOURCE state indicates that the block matches that of memory module 100, the most recent read failure for that block occurred in cache 500, and the other cache 500 'indicates that the block is MODIFIED-SHARED. Or it does not exist in the MODIFIED state. Also, the SHARED state indicates that the state of the block does not belong to any of the above states but is only valid.

According to an embodiment of the present invention, a processor module holding a block in a state of MODIFIED-SHARED, MODIFIED, EXCLUSIVE, SHARED-SOURCE becomes the owner of the block, and thus receives an access request for the block from another processor module. It is your responsibility to respond.

Referring now to FIG. 5, an embodiment of a cache 500 in accordance with one embodiment of the present invention is shown in block diagram form. As shown, the cache 500 includes a processor tag cache 510 and a bus monitor tag chche 520 each holding a tag address of a block stored in the cache 500; Two comparators 511, 521 coupled to the processor tag cache 510 and the bus monitor tag cache 520, respectively; A state information cache 530 for storing cache block state information indicating one of the seven cache block states as described above, for each cache block stored; A data cache 540 for storing cache blocks; Cache controller 550; And a bus interface 560 that connects the processor 400 and the cache 500 to the system bus 100 under the control of the cache controller 550.

When the processor 400 transmits an access request for one block and the physical address of the block to the cache 500, the portion of the physical address represented by the block address is the processor tag cache 510 and the status information cache 530. ) And data cache 540. The comparator 511 receives a tag address from the processor tag cache 510 and another part of the physical address expressed as a tag address as input and performs a comparison operation. If these two inputs in the comparator 511 match, it means that the cache 500 holds the requested block.

Bus watching operations are handled using the bus monitor tag cache 520, so bus monitoring operations may be performed in parallel with the operation of the processor 400 accessing the cache. That is, if a bus-oriented command is received from the bus 300 in the cache 500 with the physical address of the desired block, the block address portion of the physical address is the bus monitor tag cache 520, status information. Used to access cache 530 and data cache 540. The comparator 521 receives a tag address from the bus monitor tag cache 520 and a tag address portion of the physical address as an input to perform a comparison operation. If these two inputs in the comparator 521 match, it means that the cache 500 holds the desired block.

The cache controller 550 is provided with information regarding whether the above inputs match, and in response to a request from the processor 400 and / or an instruction from the system bus 300, status information for the block. Check / change, check / change COMMAND, VALID, DIRTY, MEMORY-INHIBIT and SOURCE-ID and DESTINATION-ID lines as described below, and control and synchronize the overall operation of cache 500.

Referring back to FIG. 4, communication between major elements of the shared memory multiprocessor is on system bus 300. As shown in FIG. The system bus 300 includes three buses, an addresser bus, a data bus and a control bus, and uses a separate transaction protocol as described above. The control bus may also include COMMAND, VALID, DIRTY, MEMORY-INHIBIT, SOURCE-ID and DSESTINATION-ID lines.

The COMMAND line includes a broadcast read request, cache-to-caches read request, which will be described in more detail later between the memory module 100 and the processor module 200, 200 '. Invalidation request commands that include a broadcast read with invalidation request that contains an invalidation request, and a cache-to-caches read with invalidation request that contains an invalidation request. send.

The VALID, DIRTY, and MEMORY-INHIBIT lines are used for broadcast read requests (including invalidation requests). For example, if processor module 200 sends a broadcast read request to memory module 100 and another processor module 200 'due to a cache failure for a block, the other processor module 200' The signal is asserted on the VALID, DIRTY, and MEMORY-INHIBIT lines according to the state information of the corresponding block. Thereafter, the processor module 200 may examine the VALID line to determine whether the block exists in another state of the EXCLUSIVE, SHARED-SOURCE, or SHARED state in another processor module, and the block may be MODIFIED by examining the DIRTY line. You can determine whether it exists in SHARED or MODIFIED state. In addition, the memory module 100 may stop the processing of the broadcast read request (including the invalidation request) when the MEMORY-INHIBIT signal is applied by checking the MEMORY-INHIBIT line.

The SOURCE-ID line identifies the source processor module that sent the instruction, such as a broadcast read request (including an invalidation request), a cache-caches read request (including an invalidation request), or an invalidation request. The DESTINATION-ID line may be used to identify the processor module that will receive the instruction or receive the requested block.

Hereinafter, exemplary operations of processor modules 200 and 200 'including caches 500 and 500' in accordance with one embodiment of the present invention are described for each case of read hits, read failures, write hits and write failures. Will be. In each case it is assumed that processor 400 in processor module 200 of FIG. 4 generated a request to access a block with cache 500. In addition, in describing exemplary operations of the processor modules 200 and 200 ′, block replacement refers to a block to be replaced in the cache when the cache failure occurs in the MODIFIED-SHARED or MODIFIED state. Eject the block (i.e., an updated copy of that block) to that memory module and, for example, a COMMAND line to all other processor modules that hold the block in its cache in the NON-COPYBACK-INVALID state. The task is to send a signal through to change the state of the copy of the block they hold to the COPYBACK-INVALID state.

If the cache 500 in the read hit-processor module 200 holds a block that has been requested for reading in any of the following states: MODIFIED-SHARED, MODIFIED, EXCLUSIVE, SHARED-SOURCE, or SHARED, the cache 500 Deliver the block to the processor 400.

Read failure—the cache 500 in the processor module 200 does not hold a block that has been requested to read, or holds in a cache 500 in a COPYBACK-INVALID or NON-COPYBACK-INVALID state. If not, processor module 200 performs block replacement and sends a broadcast read request for the block to memory module 100 and other processor module 200 ′. On the other hand, if the cache 500 holds the requested block in the COPYBACK-INVALID state, the processor module 200 reads the broadcast for the block to the memory module 100 and the other processor module 200 'without replacing the block. Send the request.

If any one of the other processor modules 200 'holds the requested block in the EXCLUSIVE or SHARED-SOURCE state, the processor module 200' applies the VALID and MEMORY-INHIBIT signals to the corresponding line and reads the read line. Respond to the request by providing a copy of the block stored in its own cache 500 'and change the state of the block stored in its own cache 500' to the SHARED state. If any one of the other processor modules 200 'holds the requested block in the MODIFIED -SHARED or MODIFIED state, the processor module 200' applies the DIRTY and MEMORY-INHIBIT signals to the corresponding line and reads the read line. It responds to the request by providing a copy of the block stored in the stall cache 500 'and maintains / changes the state of the block stored in its cache 500' to the MODIFIED-SHARED state. If another processor module 200 'holds the requested block in the SHARED state, the processor module 200' applies a VALID signal to the VALID line.

The memory module 100 examines the MEMORY-INHIBIT line during this transaction and provides a copy of the block for the read request if the MEMORY-INHIBIT signal is not applied.

When the processor module 200 receives a valid copy of the requested block from any one of the memory module 100 or the other processor module 200 'through the above-described process, the VALID line and the DIRTY line are examined to check the received block. It stores in its own cache 500 in the following state, and performs the read operation. When the DIRTY signal is applied, the processor module 200 stores the received block in the cache 500 in the SHARED state; When the VALID signal is applied but the DIRTY signal is not applied, the processor module 200 stores the received block in the cache 500 in the SHARED-SOURCE state; When neither the VALID signal nor the DIRTY signal is applied, the processor module 200 stores the received block in the cache 500 in an EXCLUSIVE state.

However, when the cache 500 in the processor module 200 holds the requested block in the NON-COPYBACK-INVALID state, the processor module 200 (in the conventional cache coherence scheme, memory broadcast read request is memory). Instead of sending to module 100 and another processor module 200 '), a cache-caches read request for that block is sent only to the other processor module 200'.

Accordingly, the processor module 200 ', which has recently invalidated the requested block, and therefore holds the block in its cache 500' in the MODIFIED or MODIFIED-SHARED state, is stored in its own cache 500 '. A copy of the block is sent to the processor module 200 to respond to the cache-cache read request and maintain / change the state of the block in its cache 500 'to the MODIFIED-SHARED state.

The processor module 200 receives a valid copy of the requested block, stores the received block in the cache 500 in the SHARD state, and performs a corresponding read operation.

When the cache 500 in the write hit-processor module 200 holds the block in which the write request is made in the MODIFIED-SHARED state, or the MODIFIED, EXCLUSIVE, SHARED-SOURCE, SHARED state, the cache 500 in the processor module 200 is When the requested block is held in the MODIFIED state, the processor module 200 performs a write operation.

When the cache 500 holds the requested block in the EXCLUSIVE state, the processor module 200 performs a write operation on the block and changes the state of the block to the MODIFIED state.

If the cache 500 holds the requested block in one of MODIFIED-SHARED, SHARED-SOURCE, or SHARED, the processor module 200 sends an invalidation request for the block to the other processor module 200 '. Transmit, causing all other processor modules 200 'to change their state to a NON-COPYBACK-INVALID state and copy the requested blocks they have and update their DESTINATION-ID area to specify processor module 200. do. After all of these copies are invalidated, the processor module 200 performs a write operation on the requested block and changes the state of the block to the MODIFIED state.

Write Fail—Cache 500 in processor module 200 when cache 500 in processor module 200 does not hold a block that has been requested to write or holds in COPYBACK-INVALID, NON-COPYBACK-INVALID states. Does not hold the requested block, the processor module 200 performs a block replacement, and a broadcast read request containing an invalidation request for the block to the memory module 100 and all other processor modules 200 '. Send it. On the other hand, if the cache 500 holds the requested block in the COPYBACK-INVALID state, the processor module 200 sends an invalidation request for the block to the memory module 100 and the other processor module 200 'without replacing the block. Send a nested broadcast read request.

If any of the other processor modules 200 'holds the requested block in any of the following states: MODIFIED, MODIFIED-SHARED, EXCLUSIVE, or SHARED-SOURCE, the processor module 200' will send a MEMORY-INHIBIT signal. Respond to the request by applying a MEMORY-INHIBIT line, providing a copy of the block stored in its own cache 500 ', and changing the state of the block stored in its own cache 500' to the NON-COPYBACK-INVALID state. do. If another processor module 200 'holds the requested block in the SHARED, COPYBACK-INVALID, NON-COPYBACK-INVALID state, the processor module 200' maintains the state of the block stored in its cache 500 '. Keep / change to NON-COPYBACK-INVALID state.

During this transaction, memory module 100 examines the MEMORY-INHIBIT line and provides a copy of the block for the request if the MEMORY-INHIBIT signal is not applied.

When the processor module 200 receives a valid copy of the requested block from any one of the memory module 100 or the other processor module 200 ', the processor module 200 stores the received block in its cache 500 in the MODIFIED state, and Perform a write operation.

However, when the cache 500 in the processor module 200 holds the requested block in the NON-COPYBACK-INVALID state, the processor module 200 (the conventional cache coherence maintaining scheme includes a broadcast containing an invalidation request). Instead of sending a cast read request to the memory module 100 and the other processor module 200 '), the cache-caches read request containing the invalidation request is sent only to the other processor module 200'.

Accordingly, the processor module 200 'that has invalidated the requested block most recently, and thus holds the requested block in its cache 500' in the MODIFIED or MODIFIED-SHARED state, has its own cache 500 '. Sends an updated copy of the stored block to the processor module 200 in response to a cache-caches read request containing the invalidation request, and NON-COPYBACK-INVALID displays the state of the block stored in its cache 500 '. Change to the state. If another processor module 200 'holds the requested block in a state other than that, the processor module 200' itself caches 500 'for a cache-cache read request containing the invalidation request. Change the state of the copy of the block stored in the state to NON-COPYBACK-INVALID.

When the processor module 200 receives a valid copy of the requested block, the processor module 200 stores the state of the received block in its cache 500 as a MODIFIED state and performs a desired write operation.

In operation of the processor module described above, if the processor module 200 is able to identify the processor module that most recently invalidated the requested block (i.e., holds an updated copy of the requested block), the cache- Cache read requests can be replaced with cache-to-cache read requests.

To this end, the caches 500, 500 'of the present invention are one additional area, i.e., for each cache block stored in the caches 500, 500' in their state information cache, according to another embodiment of the present invention. The destination identification area DESTINATION-ID identifying the processor module which invalidated the block most recently may be maintained.

Hereinafter, exemplary operations of processor modules 200, 200 'including caches 500, 500' in accordance with another embodiment of the present invention as described above may be used for read, read, write, and write failures. Each case is explained.

If the cache 500 in the read hit-processor module 200 holds a block that has been requested to be read in any of the following states: MODIFIED-SHARED, MODIFIED, EXCLUSIVE, SHARED-SOURCE, or SHARED, the cache 500 Deliver the block to the processor 400.

Read Fail—Cache 500 in processor module 200 when cache 500 in processor module 200 does not hold a block that has been requested to read or holds in COPYBACK-INVALID, NON-COPYBACK-INVALID states. Does not hold the requested block, processor module 200 performs block replacement and sends a broadcast read request for the block to memory module 100 and other processor module 200 '. On the other hand, if the cache 500 holds the requested block in the COPYBACK-INVALID state, the processor module 200 reads the broadcast for the block to the memory module 100 and the other processor module 200 'without replacing the block. Send the request.

If any one of the other processor modules 200 'holds the requested block in the EXCLUSIVE or SHARED-SOURCE state, the processor module 200' applies the VALID and MEMORY-INHIBIT signals to the corresponding line and reads the read line. Respond to the request by providing a copy of the block stored in its own cache 500 'and change the state of the block stored in its own cache 500' to the SHARED state. If any one of the other processor modules 200 'holds the requested block in the MODIFIED -SHARED or MODIFIED state, the processor module 200' applies the DIRTY and MEMORY-INHIBIT signals to the corresponding line and reads the read line. It responds to the request by providing a copy of the block stored in the stall cache 500 'and maintains / changes the state of the block stored in its cache 500' to the MODIFIED-SHARED state. If another processor module 200 'holds the requested block in the SHARED state, the processor module 200' applies a VALID signal to the VALID line.

The memory module 100 examines the MEMORY-INHIBIT line during this transaction and provides a copy of the block for the read request if the MEMORY-INHIBIT signal is not applied.

When the processor module 200 receives a valid copy of the requested block from any one of the memory module 100 or the other processor module 200 'through the above-described process, the VALID line and the DIRTY line are examined to check the received block. It stores in its own cache 500 as follows, and performs the read operation. When the DIRTY signal is applied, the processor module 200 stores the received block in the cache 500 in the SHARED state; When the VALID signal is applied but the DIRTY signal is not applied, the processor module 200 stores the received block in the cache 500 in the SHARED-SOURCE state; When neither the VALID signal nor the DIRTY signal is applied, the processor module 200 stores the received block in the cache 500 in an EXCLUSIVE state.

However, if the cache 500 in the processor module 200 holds the requested block in the NON-COPYBACK-INVALID state, the processor module 200 requests a cache-cache read request for that block, and the DESTINATION of the requested block. The ID-ID field is sent to another processor module 200 '(the DESTINATION-ID field has most recently invalidated the block, thus putting the block in its cache 500' in the MODIFIED or MODIFIED-SHARED state). Recall that it stores information specifying the processor module 200 'that it holds.

The processor module 200 'sends an updated copy of the requested block he holds to the processor module 200 in response to the cache-cache read request, and MODIFIED the state of the block stored in its cache 500'. -Keep / change to SHARED state.

The processor module 200 receives a valid copy of the requested block, stores the received block in the cache 500 in the SHARD state, and performs a corresponding read operation.

When the cache 500 in the write hit-processor module 200 holds the block in which the write request is made in the MODIFIED-SHARED state, or the MODIFIED, EXCLUSIVE, SHARED-SOURCE, SHARED state, the cache 500 in the processor module 200 is When the requested block is held in the MODIFIED state, the processor module 200 performs a write operation.

When the cache 500 holds the requested block in the EXCLUSIVE state, the processor module 200 performs a write operation on the block and changes the state of the block to the MODIFIED state.

If the cache 500 holds the requested block in one of MODIFIED-SHARED, SHARED-SOURCE, or SHARED, the processor module 200 sends an invalidation request for the block to the other processor module 200 '. Transmit, causing all other processor modules 200 'to change their state to a NON-COPYBACK-INVALID state and copy the requested blocks they have and update their DESTINATION-ID area to specify processor module 200. do. After all these copies have been rendered, the processor module 200 performs a write operation on the requested block and changes the state of the block to the MODIFIED state.

Write Fail—Cache 500 in processor module 200 when cache 500 in processor module 200 does not hold a block that has been requested to write or holds in COPYBACK-INVALID, NON-COPYBACK-INVALID states. Does not hold the requested block, the processor module 200 performs a block replacement, and a broadcast read request containing an invalidation request for the block to the memory module 100 and all other processor modules 200 '. Send it. On the other hand, if the cache 500 holds the requested block in the COPYBACK-INVALID state, the processor module 200 sends an invalidation request for the block to the memory module 100 and the other processor module 200 'without replacing the block. Send a nested broadcast read request.

If any of the other processor modules 200 'holds the requested block in any of the following states: MODIFIED, MODIFIED-SHARED, EXCLUSIVE, or SHARED-SOURCE, the processor module 200' will send a MEMORY-INHIBIT signal. Respond to the request by applying a MEMORY-INHIBIT line, providing a copy of the block stored in its own cache 500 ', and changing the state of the block stored in its own cache 500' to the NON-COPYBACK-INVALID state. The processor module 200 'is specified by changing the DESTINATION-ID region of the block. If another processor module 200 'holds the requested block in the SHARED, NON-COPYBACK-INVALID or COPYBACK-INVALID state, the processor module 200' maintains the state of the block stored in its cache 500 '. The processor module 200 is specified by maintaining / changing the NON-COPYBACK-INVALID state and changing the DESTINATION-ID region of the block stored in its own cache 500 '.

During this transaction, memory module 100 examines the MEMORY-INHIBIT line and provides a copy of the block for the request if the MEMORY-INHIBIT signal is not applied.

When the processor module 200 receives a valid copy of the requested block from any one of the memory module 100 or the other processor module 200 ', the processor module 200 stores the received block in its cache 500 in the MODIFIED state, and Perform a write operation.

However, if the cache 500 in the processor module 200 holds the requested block in the NON-COPYBACK-INVALID state, the processor module 200 requests a cache-cache read request containing an invalidation request for that block. Is transmitted to the other processor module 200 '.

Accordingly, the processor module 200 'specified by the DESTINATION-ID region of the requested block transmits an updated copy of the block stored in its cache 500' to the processor module 200 to contain the invalidation request. In response to the cache-caches read request, changing the state of the block stored in its cache 500 'to the NON-COPYBACK-INVALID state, and the DESTINATION-ID region of the block specifying the processor module 200 do. If another cache 500 'in another processor module 200' holds the requested block elsewhere, the processor module 200 'requests a cache-caches read request containing the invalidation request. Then change the state of the block stored in its cache 500 'to the NON-COPYBACK-INVALID state, and the DESTINATION-ID region of that block operates to specify the processor module 200.

When the processor module 200 receives a valid copy of the requested block, the processor module 200 stores the state of the received block in its cache 500 as a MODIFIED state and performs a desired write operation.

As described above, the novel write-invalidate cache system of the present invention reduces unnecessary memory accesses in the shared memory multiprocessor using a separate transaction bus, thereby reducing the actual memory access time and achieving better multiprocessor performance. .

Claims (30)

A system bus operating under a split transaction protocol, at least one memory module coupled to the system bus, and a plurality of processor modules coupled to the system bus, respectively. A shared memory multiprocessor having a processor, the processor module comprising: a processor; A cache coupled between the processor and the system bus to store blocks; And status information associated with the cache, the status information indicating whether the at least one memory module holds an updated copy of each block when the respective blocks are invalidated for each of the blocks. By including a storage device, each processor module, when receiving an access request for each block from the processor, indicates that the status information does not hold the updated copy of the at least one memory module. A shared memory multiprocessor that accesses the updated copy only by communicating with the plurality of processor modules via the system bus. The method of claim 1, wherein when each processor module receives an access request for each block from the processor, when the status information indicates that the at least one memory module holds the updated copy, And said shared memory multiprocessor accessing said updated copy by communicating with said at least one memory module and said plurality of processor modules via said system bus. 2. The system of claim 1, wherein the status information includes the updated copy of the at least one memory module when one of the plurality of processor modules invalidates each block through the system bus. The at least one memory module retains the updated copy when the one processor module has copied back the updated copy to the at least one memory module via the system bus. The shared memory multiprocessor representing. 4. The updated copy of claim 3, wherein the one processor module is further configured to update the updated copy if a cache miss occurs in the one processor module and the updated copy is replaced by a new block according to block replacement. And extracting the shared memory into the at least one memory module. 5. The shared memory multiprocessor of claim 4 wherein the cache operates under a write-invalidate cache coherence schem. 3. The system of claim 2, wherein the status information is stored in the at least one memory module when the processor module of one of the plurality of processor modules invalidates each block through the system bus. The at least one memory module retains the updated copy when the one processor module has copied back the updated copy to the at least one memory module via the system bus. The shared memory multiprocessor representing. The updated copy of claim 6, wherein the one processor module is further configured when the cache miss occurs in the one processor module and the updated copy is replaced by a new block according to block replacement. And extracting the shared memory into the at least one memory module. 8. The shared memory multiprocessor of claim 7, wherein the cache operates under a write-invalidate cache coherence schem. The system of claim 1, wherein the cache comprises: a data cache for storing the blocks; A processor tag cache for storing tag address portions of the physical addresses of the blocks; And a tag address portion of the physical address of the one block and one of the stored tag address portions specified by the block address portion of the physical address of the one block upon receiving an access request for the one block from the processor. Said shared memory multiprocessor comprising a comparator to compare. 10. The system of claim 9, wherein the cache comprises: a bus monitor tag cache for storing the tag address portions; Upon receiving an access request for one block from another processor module other than each processor module, the stored tag address specified by the tag address portion of the physical address of the one block and the block address portion of the physical address of the one block. And a second comparator to compare one of the portions. The shared memory multiprocessor of claim 1, wherein the processor comprises an internal cache. 2. The shared memory multiprocessor of claim 1 wherein each processor module includes a predetermined number of hierarchical caches. The shared memory multiprocessor of claim 1, wherein the plurality of processor modules are implemented on a predetermined number of circuit boards, the predetermined number being less than or equal to the number of the plurality of processor modules. The shared memory multiprocessor of claim 1, wherein the at least one memory module is distributed among the plurality of processor modules. The shared memory multiprocessor of claim 1, wherein the system bus comprises an address bus, a data bus, and a control bus and provides communication between the at least one memory module and the plurality of processor modules. A system bus operating under a split transaction protocol, at least one memory module coupled to the system bus, and a plurality of processor modules coupled to the system bus, respectively. A shared memory multiprocessor having a processor, the processor module comprising: a processor; A cache coupled between the processor and the system bus to store blocks; And status information associated with the cache and indicating whether the at least one memory module retains an updated copy of each block when the respective blocks are invalidated for each of the blocks. By including a status information storage device having an identification that specifies one processor module that most recently invalidated each block, each processor module requests access to each block from the processor. And upon receipt of the state information indicates that the at least one memory module does not hold the updated copy, the updated by communicating with the one processor module that the identification specifies over the system bus. Shared memory multiprocessor accessing copy multiprocessor). The method of claim 16, wherein when each processor module receives an access request for each block from the processor, the state information indicates that the at least one memory module holds the updated copy. And said shared memory multiprocessor accessing said updated copy by communicating with said at least one memory module and said plurality of processor modules via said system bus. 17. The apparatus of claim 16, wherein the status information indicates that the at least one memory module does not retain the updated copy when the one processor module invalidates each block through the system bus, The shared memory indicating that the at least one memory module retains the updated copy when the one processor module has copied back the updated copy to the at least one memory module via the system bus. Multiprocessor. 19. The system of claim 18, wherein the one processor module is further configured to update the updated copy if a cache miss has occurred in the one processor module and the updated copy is replaced with a new block according to block replacement. And extracting the shared memory into the at least one memory module. 20. The shared memory multiprocessor of claim 19 wherein the cache operates under a write-invalidate cache coherence schem. 18. The apparatus of claim 17, wherein the status information indicates that the at least one memory module does not retain the updated copy when invalidating each block through the system bus of the one processor module, The shared memory indicating that the at least one memory module retains the updated copy when the one processor module has copied back the updated copy to the at least one memory module via the system bus. Multiprocessor. 22. The system of claim 21, wherein the one processor module is further configured to update the updated copy if a cache miss has occurred in the one processor module and the updated copy is replaced with a new block according to block replacement. And extracting the shared memory into the at least one memory module. 23. The shared memory multiprocessor of claim 22 wherein the cache operates under a write-invalidate cache coherency scheme. 17. The system of claim 16, wherein the cache comprises: a data cache for storing the blocks; A processor tag cache for storing tag address portions of the physical addresses of the blocks; And a tag address portion of the physical address of the one block and one of the stored tag address portions specified by the block address portion of the physical address of the one block upon receiving an access request for the one block from the processor. Said shared memory multiprocessor comprising a comparator to compare. 25. The system of claim 24, wherein the cache comprises: a bus monitor tag cache for storing the tag address portions; Upon receiving an access request for one block from another processor module other than each processor module, the stored tag address specified by the tag address portion of the physical address of the one block and the block address portion of the physical address of the one block. And a second comparator to compare one of the portions. 17. The shared memory multiprocessor of claim 16, wherein the processor comprises an internal cache. 17. The shared memory multiprocessor of claim 16, wherein each processor module includes a predetermined number of hierarchical caches. 17. The shared memory multiprocessor of claim 16, wherein the plurality of processor modules are implemented on a predetermined number of circuit boards, the predetermined number being less than or equal to the number of the plurality of processor modules. 17. The shared memory multiprocessor of claim 16 wherein the at least one memory module is distributed among the plurality of processor modules. 17. The shared memory multiprocessor of claim 16, wherein the system bus comprises an address bus, a data bus, and a control bus, and provides communication between the at least one memory module and the plurality of processor modules.