KR100344065B1 - Shared memory multiprocessor system based on multi-level cache - Google Patents

Abstract

The present invention relates to a multiprocessor device having a shared memory structure using a snooping interconnection network, and to improve performance, a multi-level cache is constructed between the processor and the shared memory. The access-list is configured as a structure for removing the performance degradation caused by the multi-level cache inclusion property, in which the large level of the cache includes the valid contents of the small level. The access list of the present invention indicates a block stored in the lower level cache so that the higher level cache does not need to store the blocks of the lower level cache in duplicate.

Description

SHARED MEMORY MULTIPROCESSOR SYSTEM BASED ON MULTI-LEVEL CACHE}

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiprocessor device having a shared memory structure. In particular, a multiprocessor device having a shared memory structure including a snooping interconnection network can manage several caches on a connection path between processors in stages. Relates to a device.

In general, large shared memory multiprocessor systems with a single address space and a cache that maintain coherence provide a flexible and powerful computing environment. That is, a cache that is consistent with a single address space facilitates data partitioning and dynamic load balancing issues, and provides a better environment for parallel compilers, standard operating systems, and multiprogramming. To make the machine more flexible and effective.

1 illustrates an example of a uniform memory access time (UMA) scheme as an example of such a shared memory multiprocessor system. As shown in the UMA scheme, a single shared memory 30 is provided, and the single shared memory 30 is connected to the plurality of processor nodes 100A to 100C through the global bus 21. Secondary caches 13A to 13C are configured in processor nodes 100A to 100C, and secondary caches 13A to 13C are connected to processor modules 10A to 10F via local buses 20A to 20C. . Processor modules 10A through 10F have primary caches 12A through 12F and processors 11A through 11F as shown.

In the UMA scheme having the above-described configuration, the interconnection network between processors is adopted by employing primary and secondary caches 12A to 12F and 13A to 13F which have a smaller capacity than the shared memory 30 but provide much faster access time. It reduces the number of requests and responses that occur on (local buses 20A to 20C and global bus 21) and provides a small latency for memory access requests from processors 11A to 11F.

However, the use of caches 12A-12F, 13A-13F means that if one processor 11A-11F performs a write operation on its primary caches 12A-12F, the result of that write operation may be in the system. A so-called cache coherence problem arises that must be reflected in the corresponding data blocks of all caches 12A-12F, 13A-13F. In general, the snooping scheme and the directory scheme are widely used to maintain cache coherency in a shared memory multiprocessor.

The snooping method of maintaining consistency is a cache 12A to 12F connected directly on a transfer path (local buses 20A to 20C and global bus 21) when a memory access request is generated from a processor 11A to 11F. In this case, the 13A to 13C checks their block state with respect to the requested address and accordingly performs a necessary process such as a response. Here, the caches 12A to 12F and 13A to 13C are used to store the blocks stored therein. The state information is stored, and the state information of the block can be divided into shared, modified, and invalidated. Shared means that blocks in the caches 12A-12F, 13A-13C are stored in another cache 12A-12F, 13A-13C, and modified means caches 12A-12F, 13A-13C. The blocks within are modified, and invalidated means that the blocks in the caches 12A to 12F and 13A to 13C are invalidated, that is, no significant block contents are stored.

In the above configuration, when a memory access request is generated by a specific processor (for example, 11A), the request is first provided to the primary cache 12A, and the memory block required for the primary cache 12A is valid. If it does not exist (i.e., when the state of the block is invalid or does not exist), a memory access request is provided to the local bus 20A. According to the request provided to the local bus 20A, the contents of the other primary cache 12B in the local bus 20A connected with the secondary cache 13A are retrieved, and the primary cache different from the secondary cache 13A. If the block does not exist in a valid state at 12B, a memory access request is forwarded to the shared memory 30 and other secondary caches 13B and 13C directly connected to the global bus 21 via the global bus 21. do.

In this way, the memory access request generated from the processor 11A is hierarchically passed through the interconnection networks 20A to 20C and 21, and is gradually transferred throughout the system to be located in the delivery paths of the caches 12A to 12F and 13A to 13C. Are searched for a block corresponding to the requested address. As such, in the shared memory multiprocessor architecture, all caches 12A to 12F and 13A to 13C are connected through an interconnection network, and thus, the state of all caches 12A to 12F and 13A to 13C according to a memory access request (storing of the corresponding block) Whether or not) must be retrieved and accompanied by the action accordingly.

The caches 12A to 12F and 13A to 13C store blocks of a certain size stored in the shared memory 30, and memory access addresses generated from the processors 11A to 11F are stored in the caches 12A to 12F and 13A to 13C. It is configured to provide the contents if it matches the block address stored in. Therefore, as the capacity of the caches 12A to 12F and 13A to 13C increases, the processors 11A to 11F may obtain block information without accessing the shared memory 30.

The primary way to increase the performance of a system is to first increase the number of processors it can accommodate. However, the bandwidth provided by a single network is limited, and therefore, in order to configure a plurality of processors in a system, a multi-level interconnect (bus) and a multi-level cache need to be configured as shown in FIG. 1.

The primary caches 12A through 12F store memory blocks without requesting the upper buses 20A through 20C to request memory access requests from processors 11A through 11F that are directly connected to each cache 12A through 12F. By providing a configuration, the memory access request generated from the processors 11A to 11F can be completed quickly, and the local bus (by reducing the number of memory access requests provided to the local buses 20A to 20C). 20A to 20C) can reduce the bottlenecks caused by the demand. Similarly, secondary caches 13A-13C accommodate requests for memory blocks that do not exist in the primary caches 12A- 12F, thereby reducing bottlenecks in the global bus 21 and the rapid provision of memory blocks. Therefore, in the case of a high performance structure, the caches 12A through 12F and 13A through 13C are constituted, and closer to the processors 11A through 11F on the access path from the processors 11A through 11F to the shared memory 30. The caches 12A to 12F are faster, use a smaller capacity, and gradually increase the capacity of the cache 13A to 13C side closer to the shared memory 30 side. For this reason, the caches 12A to 12F placed closer to the processors 11A to 11F are designated as smaller caches (primary caches), and the caches 113A to 13C gradually closer to the shared memory 30 are designated as larger stages. Specify as cache (secondary cache).

However, in order to provide consistency for unit memory access requests, all caches 12A to 12F and 13A to 13C in the system need to be searched, which causes a problem of a long time delay for maintaining consistency. To solve this problem, between the caches 12A through 12F and 13A through 13C of each stage, the contents of the valid state memory blocks stored in the primary caches 12A through 12F of the smaller stages are stored in a larger secondary cache ( 13A to 13C) are basically used to reduce the processing delay time due to snooping by forcing the inclusion property to be maintained and reducing the range of the cache to be searched.

Fault tolerance must include all valid state blocks that exist in the small caches 12A through 12F, where the large caches 13A through 13C are directly connected to themselves via interconnection networks, ie, local buses 20A through 20C. It means limiting to include. In the case of FIG. 1, the cache 13A includes all valid state blocks in the caches 12A and 12B, the cache 13B includes all valid state blocks in the caches 12C and 12D, and the cache 13C. The multi-level cache inclusion property is said to be maintained if is a block containing all valid state blocks in the caches 12E and 12F.

This multi-level cache nesting is intended to simplify the cache protocol, in which blocks that do not exist in the valid state in the cache 13A are guaranteed to not exist in the valid states in the caches 12A and 12B, and are valid in the cache 13B. It is guaranteed that blocks that do not exist in the cache 12C and 12D do not exist in the valid state in the caches 12C and 12D, and blocks that do not exist in the cache 13C do not exist in the valid state in the caches 12E and 12F. Guaranteed. Thus, if a block of any address is not found in the search for the large caches 13A through 13C, then the small, without involving the search for the small caches 12A through 12F directly connected to the caches 13A through 13C. It can be seen that there is no block of that address in the cache 12A-12F of the step. Thus, this inclusion can be used to maintain cache coherency without the need for local buses 20A-20C or global bus 21 to be delivered to all caches 12A-12F, 13A-13C.

For example, when a memory read request is generated from the processor 11A of FIG. 1 and the requested memory block does not exist in the valid state in the primary cache 12A, the cache 12B is provided through the local bus 20A. And a read request to the cache 13A. In response to this read request, the cache 12B and the cache 13A respectively check whether the requested block exists in its own valid state and, if present, the cache 12B or cache responsible for the response, depending on its state. 13A provides a request block of the processor 11A. Here, the cache 12B or the cache 13A responsible for the response provides the request block to the processor 11A, and the response responsibility is determined by ownership of the request block. That is, the cache 13A must store all the contents in the cache 12B in order to maintain its inclusion. However, in the case of a later write method (called a write-back method), the cache 13A is correct in the cache 12B. Occurs when the contents cannot be saved. The later write method means that the write contents are stored in the cache 12B for the write request from the processor (eg, 11B), and the update to the shared memory 30 is performed after the block is evicted from the cache 12B. It's a way of procrastinating. In the later write method, the latest block contents stored in the small cache 12B are not known to the large cache 13A. However, in order to maintain inclusion, the large-sized cache 13A must maintain the block of the corresponding address. Therefore, the large-sized cache block 13A is assigned the corresponding address (the address of the block in which the write occurred). Finally, the contents of the block written from the processor 11B are not contained. Therefore, in this case, the cache 13A will have nesting resistance to the cache 12B, but the correct block is not stored in the cache 13A. In this case, the response responsibility for the block is the cache ( 12B).

In the case where the cache 13A has a response responsibility for the request block, in this case, the block in which the write was generated from the processor 11B in the past so that the cache 12B had the response responsibility is a new block from the processor 11B. By the request, a block stored in the cache 12B is selected as a block to be evicted, and a block replacement occurs from the cache 12B. Block replacement refers to a process of removing a block previously existing in the cache 12B while allocating a new block to the cache (eg, 12B). That is, the cache 12B can store only 10 blocks B1-B10 in total, but when a new block B11 is needed, the least used block (eg B2) of these blocks B1-B10 is eliminated. , A process of newly storing the block B11.

When this block replacement process is performed, the cache 12B is in a state of not storing the block B2, but since the cache 13A is in a state of storing the block B2, the request for the block B2 is not performed. The cache 13A is responsible for the response.

However, if the block of the address requested in the cache 13A does not exist in a valid state, the cache 13A is guaranteed to not exist in the valid state in the cache 12B because of the multi-level cache nesting. 12A) immediately requests the requested block to the global bus 21, and the block requested to the global bus is retrieved from the caches 13B and 13C and the shared memory 30. At this time, if the block does not exist in the cache 13B and 13C in a valid state, the cache 12C and 12D corresponding to the lower portion of the cache 13B, and the cache 12E and the lower portion of the cache 13C, Since the block is guaranteed to not exist in a valid state at 12F), a response is made from the shared memory 30. If the block exists in the cache 13B in a valid state and the modified state (in this case, the latest block content is stored in the cache 12C or 12D, the block content is not correct in the cache 13B, but the corresponding address is stored in the cache 13B). The block is valid and modified, i.e., the state that the block is validly stored in the cache 12C or 12D), and if the block does not exist in the cache 13C in a valid state, the cache 13B makes a request for a block through the local bus 20B to retrieve the caches 12C and 12D so that the cache of the modified state of the caches 12C or 12D responds. At this time, since it is guaranteed that a block does not exist in a valid state in the caches 12E and 12F directly connected to the cache 13C, a search is not necessary.

As such, the multi-level cache inclusion property may be used in a state where several levels of caches 12A to 12F and 13A to 13C are valid on the access path from the processors 11A to 11F to the shared memory 30. If present, it means that the large caches 13A through 13C contain all the blocks of the small caches 12A through 12F in a valid state. By multi-level cache nesting, if a search for a block corresponding to a specific address is required in the global bus 21, and the block corresponding to the address does not exist in the large-level caches 13A to 13C, the cache 13A To 13C), it can be guaranteed that there is no block corresponding to the address required for the small caches 12A to 12F without involving a search for the small caches 12A to 12F having an implicit relationship. have.

The memory access request from the processors 11A through 11F by the multi-level cache nesting does not require searching through all the caches 12A through 12F and 13A through 13C, so that the time delay required for the search is reduced.

On the other hand, in a conventional manner, when the nesting resistance is maintained between the secondary caches 13A, 13B, 13C and the primary caches 12A, 12B, 12C in the processor nodes 100A, 100B, and 100C, the memory from the processor 11A If a request occurs and the request does not hit the primary cache 12A in the processor node, the memory request is forwarded to the secondary cache 13A. The secondary cache 13A provides the block if the block is validly stored in the secondary cache 13A with respect to the generated memory request. If the valid block is not stored, the secondary cache 13A transfers the block to the global bus 21. And the response is provided to the processor module 10A which generated the memory request through the local bus 20A. At this time, since the block must be allocated to the primary cache 12A and the secondary cache 13A in order to maintain the inclusion, the block is duplicated in the primary cache 12A and the secondary cache 13A. At this time, if the eviction of a block present in the secondary cache 13A occurs in order to allocate the block provided via the local bus 21 to the secondary cache 13A (i.e., block replacement should occur). The block to be evicted must first be evicted from all primary caches 12A and 12B of the same processor node. Therefore, the block to be evicted is made irrespective of the object to be evicted in the management policy of the primary cache, so that in the case where a block access received the evict request from the processors 11A and 11B occurs later, the access is the same processor. Failure to access all primary caches 12A, 12B and secondary cache 13A in the node will result in a request for a block over the global bus 21.

However, this conventional multistage cache nesting does not exist in a valid state in the small caches 12A through 12F upon memory accesses from the processors 11A through 11F, so that the memory blocks are moved into the large caches 13A through 13C. When requested, it can lower the hit rate for it. The reason is that the larger caches 13A through 13C must maintain higher nesting tolerances for the smaller caches 12A through 12F, and in the smaller caches 12A through 12F, the address at which the request of the block originated is Since it does not exist in the cache 12A, the space in which the block may exist in the large caches 13A to 13C is left except the space occupied by the block existing in the valid state of the caches 12A to 12F in the small stages. It can be allocated only in space.

In addition, the multi-level cache nesting reduces the probability that memory block accesses from the processors 11A through 11F are present in the small-level caches 12A through 12F. The reason is that when block replacement occurs in the large caches 13A to 13C to maintain the inclusion, the expulsion of the same block for the small caches 12A to 12F must be forced for the replaced block address. Because it can maintain the nature of.

In addition, for the write request generated by the processors 11A to 11F, the written contents can be stored in the cache, and the later write (which can delay the update to the shared memory 30 to a later time when the block is evicted from the cache) In the write-back cache, the latest block contents stored in the small caches 12A to 12F are unknown to the large caches 13A to 13C. However, in order to maintain inclusion, the large caches 13A to 13C must maintain a block of the corresponding address. 11A to 11F) may not contain the recorded contents. In such a case, since the large-level caches 13A to 13C are not up-to-date, the contents of the block are not valid, or the state of the block is kept valid for inclusion. When a request for a block occurs, a search for lower caches 12A to 12F should be made possible. Therefore, the large stage caches 13A to 13C do not have valid contents, but waste of allocating blocks occurs.

Accordingly, an object of the present invention is to provide an apparatus for removing multi-level cache nesting by constructing an access-list and storing information of blocks existing in a small level cache in the access list.

In order to achieve the above object, the present invention provides a shared memory multiprocessor device of a multi-level cache structure in which caches of a higher layer and a lower layer are configured in processor nodes, and an access list is formed in each processor node. Is characterized in that state information indicating blocks stored in the cache of the lower layer is stored.

In the shared memory multiprocessor architecture, a multilevel cache is configured between a processor and a shared memory, a large level cache and an access list are configured, and a small level cache and a higher level are required for a memory access request generated from a processor. For every request and response that passes through the interconnection network, the address and command of the memory block from which the request and response are made are monitored to determine whether the request and response block exists in the small cache, Sets the state of the access list according to whether or not a block exists in the cache.

The access list stores the presence or absence of all block addresses in the smaller caches that are directly associated with the larger caches, so that the access list can be used without retrieving the contents of the caches that are directly connected according to the information in the access list. Be sure to check the possibilities.

Therefore, it is possible to determine whether snooping should be performed on a small cache by an access list without maintaining multilevel cache nesting in a large cache and a small cache directly connected thereto. This eliminates the problems of lowering the hit ratio of the above mentioned large stage cache, lowering the hit ratio of the above mentioned small stage cache, and maintaining the block with incorrect contents of the above mentioned large stage.

Finally, the present invention in a snooping manner eliminates multistage cache nesting, where a large cache must contain all valid state blocks present in the small cache, thereby eliminating block arising from the large cache in order to maintain inclusion. Improve the hit rate of both caches by eliminating the problem of having to evict the same address block for the small cache and reducing the redundancy between the blocks in the large cache and the blocks in the small cache. At the same time, by maintaining the information of blocks existing in the small cache in the access list, it is possible to minimize the unnecessary search for the contents of the small cache.

1 is a block diagram of an even memory access shared memory multiprocessor device of a typical two stage bus structure;

2 is a block diagram of a shared memory multiprocessor device with a multi-level cache structure in accordance with the present invention;

3 is a diagram illustrating a configuration state of a secondary cache and an access list in the configuration of FIG. 2;

4 illustrates another embodiment of an access list;

5 is a schematic structural diagram of a non-uniform memory access shared memory multiprocessor in a general two stage bus structure.

6 illustrates another embodiment of a shared memory multiprocessor device with a multi-level cache structure in accordance with the present invention;

7 and 8 illustrate another embodiment of a shared memory multiprocessor device with a multi-stage cache structure in accordance with the present invention;

9 illustrates another embodiment of an access list;

10 illustrates another embodiment of a shared memory multiprocessor device with a multi-stage cache structure in accordance with the present invention.

<Description of the symbols for the main parts of the drawings>

10A-10F: Processor Module 11A-11F: Processor

12A-12F: Primary Cache 13A-13C: Secondary Cache

20A-20C: Local Bus 21: Global Bus

30: shared memory 40A-40C node controller

50A-50C: Access List

100A-100C: Processor Node

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

2 shows a multiprocessor system based on a snooping bus having a two stage cache in accordance with one embodiment of the present invention.

In FIG. 2, each processor node 100A to 100C is connected to the shared memory 30 via a global bus 21 using snooping. In addition, a plurality of processor modules 10A to 10F including a processor 11A to 11F and primary caches 12A to 12F are configured in the processor nodes 100A to 100C, and these processor modules 10A to 11F are configured. The local buses 20A to 20C are connected to the secondary caches 13A to 13C, the node controllers 40A to 40C, and the access lists 50A to 50C.

Node controllers 40A to 40C, for example, 40A, retrieve whether data blocks corresponding to memory access requests from processor modules 10A and 10B of processor node 100A are stored in the secondary cache 13A in a valid state. For example, if the data block is stored in a valid state, the data block is provided to the processor modules 10A and 10B, but if it is not stored in the secondary cache 13A in a valid state, the other processor is provided through the global bus 21. It transmits a request signal to the nodes 100B and 100C and the shared memory 30. In addition, when a memory block request is input from the other processor nodes 100B and 100C through the global bus 21, the node controller 40A keeps the data block corresponding to the request valid for its secondary cache 13A. At the same time, the status of the block corresponding to the access list 50A is searched and snooped to the response and the primary caches 12A and 12B according to the state of the secondary cache 13A and the access list 50A. Determine whether to request.

The state of the access lists 50A to 50C, for example 50A, means that the block of shared memory 30 addresses is valid in the primary cache (processor cache) 12A, 12B in the processor node 100A in which the access list exists. 'Included', indicating that it may exist, and an 'Excluded' state, ensuring that a block of shared memory 30 addresses does not exist in the processor cache 12A, 12B in a valid state. . FIG. 3 illustrates an example of the access list 50A, which is configured as a memory having a unique space corresponding one-to-one in block size unit with respect to the entire shared memory 30 (all addresses). It is fixedly allocated and is configured such that the corresponding block address may indicate 'not included' and 'included' in the processor caches 12A and 12B by using one bit.

In the case of the secondary cache 13A, the contents and the state of the dynamic address and the block, rather than the static address, must be stored. As shown in FIG. 3, the tag 131A for storing the address and the contents of the block are stored. Space 132A is required, and space 133A is required for storing the state of the block. The state of a block may be divided into a conventional state of being shared, modified, invalidated (or modified and shared as necessary (in the case of the Berkeley method)).

The initial state of the access lists 50A to 50C is 'not included' and, as a valid memory block is allocated to the primary caches 12A to 12F, the state of the address corresponding to the memory block is switched to 'included'. When a new block is to be allocated to the primary caches 12A to 12F in response to a memory block request from the processors 11A to 11F, the new blocks exist in the primary caches 12A to 12F in order to allocate new blocks. Blocks can be evicted. This case is referred to as block replacement as described above, and in the case of block replacement, if a block to be evicted has already had write access from the processors 11A to 11F (ie, in a modified state), it is transferred to the shared memory 30. In the case of a block having a state of responsibility for rewriting, a block to be evicted at the same time as being evicted from the primary caches 12A to 12F must be stored in the secondary caches 13A to 13C or the shared memory 30. This operation is called write-back, and when rewriting occurs, the status bit (for example, address 3 of the block address 3) is rewritten in the access list (50A to 50C) of the corresponding block. ) Must be converted to 'not included'.

When a processor node (eg, one of 100B and 100C) requests a block to the global bus 21, the processor node 100A must snoop and the corresponding block is in the access list 50A state (e.g., If a request is made for block address 2, the status of address 2 in access list 50) is 'included', this request should be requested to primary caches 12A and 12B via local bus 20A.

However, even if the state of address 2 of the access list 50A is 'included', and the block does not exist in the primary caches 12A and 12B, the request corresponding to the repeated block address is stored in the primary cache ( 12A, 12B) switch the access list state of the corresponding block (e.g. address 2 address if requested for block address 2) to 'not included'.

More specifically describing the operation of the secondary caches 13A to 13C and the access lists 50A to 50C, there are two paths through which access occurs to the secondary caches 13A to 13C and the access lists 50A to 50C. . The first is the memory access from the processor modules 10A, 10B in the processor node (eg, 100A) and the second is the access originating from the other processor nodes 100B, 100C via the global bus 21.

The accesses generated by the secondary cache 13A or the access list 50A in the processor node 100A are divided into read, write and rewrite according to the types of memory accesses generated from the processors 11A and 11B in the node.

In the case of a read request, when a block of the address requested from a processor 11A to the primary cache 12A in the processor module 10A fails (that is, the block does not exist or is invalidated in the primary cache 12A). In this case, the state of the corresponding block address of the access list 50A (for example, address 2 if the block address is 2) when the requested block exists in the secondary cache 13A in a valid state. Is switched to 'included' and the response is made by the secondary cache 13A providing the block to the processor 11A and the primary cache 12A.

If no block exists in the secondary cache 13A in a valid state, the node controller 40A issues a read request for the block to the global bus 21. Read requests generated on the global bus are broadcast to the shared memory 30 and other processor nodes 100B and 100C, and are each cached by node controllers 40B and 40C inside the other processor nodes 100B and 100C. If the requested block at 13B, 13C does not exist in a valid state, and the requested block is not included in each of the access lists 50B, 50C, the shared memory 30 provides the block. The response is processed.

If a block is valid and in a modified state in another processor node 100B or 100C, the node's secondary cache 13B or 13C has the block in a valid and modified state, or 1 of that node. Since one of the difference caches (one of 12C, 12D, 12E, 12F) has a valid and modified state block, the valid and modified state cache provides the block and processes the response. When a response is made and the requested block is provided to the secondary cache 13A under the control of the node controller 40A via the global bus 21, the secondary cache 13A allocates the provided block 131A, 132A, 133A) and provide the block back to the primary cache 12A that requested the block. In addition, while providing a block to the primary cache 12A, the block address state of the corresponding access list 50A is switched to 'included'.

When a read request is requested to the global bus 21, other processor nodes 100B and 100C receive the read request from the global bus 21 except for the processor node 100A which generated the read request. The node controllers 40B and 40C retrieve the requested block addresses from the secondary caches 13B and 13C and the access lists 50B and 50C, and the statuses and access lists 50B and 50C of the secondary caches 13B and 13C. Process the request according to the state of). If there are valid blocks in the secondary caches 12B, 12C, and are responsible for the response, regardless of the state of the access lists 50B, 50C, the primary caches 12C, 12D, 12E and 12F are not performed, and the secondary cache (the modified state of 13B or 13C) performs the response of the request under the control of the node controllers 40B and 40C. If a valid block does not exist in the secondary caches 13B and 13C and the state of the access lists 50B and 50C is 'not included', the node controllers 100B and 100C do not participate in the response process of the request. If the status of the list (50B, 50C) is 'included', the request is forwarded to the primary cache (12C, 12D, 12E, 12F) via the local buses 20B, 20C, and the primary cache (12C, 12D, 12E). , 12F). As a result of the search, if the block state of the primary cache (one of 12C, 12D, 12E, 12F) is responsible for the response, the requested block in the primary cache (one of 12C, 12D, 12E, 12F) is retrieved. Reads and sends a response to the global bus 21 under the control of the node controllers 40B and 40C via the local buses 20B and 20C. However, if there are no blocks responsible for response in the primary caches 12C, 12D, 12E, and 12F, the response process is not performed.

Meanwhile, if the requested block does not exist in the primary caches 12C, 12D, 12E, and 12F during this process, the state of the access list 50B or 50C is changed to 'not included' to correspond to the same address block. Do not accept any further requests.

In the case of a write request, it is subdivided again into the case where the block of the address where the write request is issued to the primary cache 12A in the processor module 10A is in a valid state and not.

When a block remains valid in the primary cache 12A, it is subdivided into cases in which it may be shared again by multiple caches and that only valid blocks are stored in the primary cache 12A. If guaranteed, the write request is processed without issuing a request to the secondary cache 13A. However, if there is a possibility of being shared, the write request is completed only by performing a system-wide invalidation on the shared block. Therefore, in this case, an invalidation request is made to the local bus 20A, and the secondary cache 13A invalidates the block of the secondary cache 13A according to the invalidation request, and the state of the access list 50A remains as included. Requesting an invalidation request to the global bus 21 by the node controller 40A. When an invalidation request provided through the global bus 21 is provided, all the processor nodes 100B and 100C except for the shared memory 30 and the processor node 100A which made the invalidation request are each cached by the invalidation request. Access lists (50B, 50C) on all processor nodes (100B, 100C) except for processor nodes (100A) that invalidate blocks on (13B, 13C) and primary caches (12C, 12D, 12E, 12F). ) Switch status to 'not included'.

If a block of addresses for which a write request is made to the primary cache 12A in the processor module 10A in the write request is not in a valid state, a valid block must first be allocated to the primary cache 12A. 20A), a write allocation request is issued, which is again provided to the secondary cache 13A. In this case, an address block corresponding to the secondary cache 13A is divided into a case where there is and a case where there is no. When the address block corresponding to the secondary cache 13A exists, it is subdivided into the case where the block may be shared in several caches again and the case where it is guaranteed to be the only block only in the secondary cache 13A. In the latter case, the secondary cache 13A provides the block to the primary cache 12A via the local bus 20A, invalidates the block of the secondary cache 13A, and includes the state of the access list 50A. The write request is terminated by setting to. In the former case where a block corresponding to the secondary cache 13A exists and may be shared in a block in multiple caches, an invalidation request is requested to the global bus 21 by the node controller 40A. When the invalidation request is provided to the global bus 21, all the processor nodes 100B and 100C except for the shared memory 30 and the processor node 100A that made the invalidation request are assigned to each secondary cache 13B, by the invalidation request. 13C) and the state of access lists 50B, 50C on all processor nodes 100B, 100C, except processor node 100A that invalidated blocks on primary caches 12C, 12D, 12E, and 12F. To 'not included', the secondary cache 13A of the processor node 100A that issued the write request provides the block to the primary cache 12A via the local bus 20A and the secondary cache ( The write request is terminated by invalidating the block of 13A) and setting the state of the access list 50A to included.

There is no block of addresses corresponding to the primary cache 12A in the processor module 10A that issued the request in the write request, and the write allocation request requested through the local bus 20A also exists in the secondary cache 13A. If the corresponding address block does not exist, the node controller 40A requests a write allocation request to the global bus 21. All of the processor nodes 100B and 100C except the shared memory 30 that has received the write allocation request through the global bus 21 and the processor node 100A that issued the request have shared memory 30 or secondary cache 13B. , 13C) or the primary cache 12C, 12D, 12E, 12F, the response is processed by the only device responsible for the response and transmits the corresponding block. At the same time, all processor nodes 100B, 100C, secondary caches 13B, 13C, and primary caches 12C, 12D, 12E, and 12F, except for the processor node 100A that issued the request, invalidate the corresponding block. , Set the access list (50B, 50C) to 'not included'. When the node 100A having issued the write allocation request receives a block through the global bus 21, the node controller 40A allocates the received block to the primary cache 12A through the local bus 21A. The state of the access list 50A is set to 'included'.

Instructions required from the global bus 21 to the processor nodes 100A, 100B, and 100C by the write request are invalidation request and write allocation request as described above. In the case of an invalidation request, the node controllers 40A, 40B, and 40C invalidate the corresponding block addresses in the secondary caches 13A, 13B, and 13C, and retrieve the state of the access lists 50A, 50B, and 50C. If the status of the access list 50A, 50B, 50C is included, the node controllers 40A, 40B, 40C generate an invalidation request via the local buses 20A, 20B, 20C to enable the primary caches 12A-12F. Invalidates the corresponding block in and switches the state of the access list 50A, 50B, 50C to 'not included'.

When the command requested from the global bus 21 to the processor nodes 100A, 100B, and 100C by the write request is a write allocation request, the node controllers 40A, 40B, and 40C store the corresponding block in the secondary cache 13A, 13B, 13C), if the status is responsible for the response, send the block to the global bus 21, and simultaneously retrieve the status of the access list 50A, 50B, 50C, and if it is 'included', An invalidation request is generated via the buses 20A, 20B, and 20C, and the state of the access list 50A, 50B, 50C is switched to not included.

When the command requested from the global bus 21 to the processor nodes 100A, 100B, and 100C by the write request is a write allocation request, the node controllers 40A, 40B, and 40C store the corresponding block in the secondary cache 13A, 13B. 13C), invalidate the block in the secondary cache if its status is not responsible for the response, and simultaneously retrieve the status of the access list 50A, 50B, 50C, and if it is included, the local bus 20A. 20B, 20C) to generate the write allocation request. If the primary cache 12A to 12F blocks are retrieved by the write allocation request requested to the local buses 20A, 20B, and 20C, and the status is responsible for the response, the local buses 20A, 20B, and 20C are Response is made, the primary caches 12A through 12F are invalidated, and the state of the access list 50A, 50B, 50C is 'not included' by the node controllers 40A, 40B, and 40C. Transmit and send the block to the global bus 21 by the node controllers 40A, 40B, and 40C. If the primary cache blocks 12A to 12F retrieved by the write allocation request generated on the local buses 20A, 20B, and 20C are not responsible for response, the primary cache 12A to 12F blocks are invalidated and accessed. Toggle the status of lists 50A, 50B, and 50C to 'not included'.

When the command requested from the global bus 21 to the processor nodes 100A, 100B, and 100C by the write request is a write allocation request, the node controllers 40A, 40B, and 40C store the corresponding block in the secondary cache 13A, 13B. , 13C) and if no block exists, at the same time, the status of the access list 50A, 50B, 50C is retrieved and if it is included, the write allocation request is made via the local bus 20A, 20B, 20C. Generate. When a block is retrieved from the primary caches 12A to 12F by the write allocation request requested to the local bus, and the state is responsible for the response, a response is made through the local buses 20A, 20B, and 20C, The primary caches 12A through 12F are invalidated, and the node controller 40A, 40B, 40C switches the state of the access list to 'not included' and blocks by the node controller to the global bus 21. Send it. If the primary cache block retrieved by the write allocation request generated on the local buses 20A, 20B, and 20C is not responsible for the response, the primary cache block is invalidated and the state of the access list 50A, 50B, or 50C. Switch to 'Not included'.

If the instruction requested from the global bus 21 to the processor nodes 100A, 100B, and 100C by the write request is an invalidation request, the block is invalidated if the block exists in the secondary caches 13A, 13B, and 13C. If the status of (50A, 50B, 50C) is 'included', the local buses 20A, 20B, and 20C are invalidated to invalidate the blocks in the primary caches 12A to 12F and the access list 50A and 50B. , 50C) switches its status to 'not included'.

If a write-back request originates from the primary cache 12A, the resulting rewrite is allocated to the secondary cache 13A and held accountable for rewriting and does not include the state of the access list 50A. Change it to None. That is, if a general block replacement occurs, the block that has not been written the longest in the primary cache 12A is deleted, but if the state of the block to be deleted is modified, this block (modified block) cannot be deleted. After writing to the cache 13A and deleting it in the primary cache 12A, the state of the access list 50A is changed to not included. On the other hand, in the case of the Berkeley method, the cache may be modified and have a shared state. If the block to be rewritten is modified and has a state of shared, this means that another cache is shared with the block. In this case, the corresponding block is deleted from the primary cache 12A, and the state of the access list 50A is kept as 'included'. This is modified in Berkeley and in the shared state the block may be in the shared state in another primary cache 12B in the same processor node 100A, so in this case the access list transitions to 'not included'. This is because there may be blocks corresponding to the primary cache 12B unlike the state meaning of the access list. On the other hand, if the block does not exist in another primary cache 12B in the same processor node 100A in a valid state, the blocks corresponding to all primary caches 12A, 12B in the processor node are not in a valid state. Nevertheless, the status of the access list 50A remains 'included', in which case it does not contradict the meaning of the 'included' status of the access list (the block may exist in a valid state). Meanwhile, in the case of the Berkeley method, when the block is in the modified state, the block is written to the secondary cache 13A as in the general case, and the state of the access list 50A is changed to 'not included'. This is because, in the modified state, it is guaranteed to be the only valid block.

When a rewrite request is made to the global bus 30, the processor nodes 100A and 100B 100C do not participate in snooping and the instruction is completed by transferring the block to the shared memory 30.

Memory access requests that occur on the global bus 21 can be divided into read and write. In the case of writes, the writes must be known to maintain consistency for all caches in the system, whereas in the case of reads, reads are delivered to a valid and modified cache that is responsible for the response. As described above, if the state of the access lists 50A to 50C is maintained in two states, 'included' and 'not included', whether or not a block having a valid state exists in the primary caches 12A to 12F is determined. As can be seen, it does not provide whether or not blocks existing in the primary caches 12A to 12F are valid and in a modified state. Thus, all read requests that occur on the global bus 21 must be retrieved from the primary caches 12A-12F of all processor nodes 100A-100C with the status of access list 50A-50C 'included', among which The valid and modified cache will respond to read requests.

Apart from the state depending on whether or not the state of the access list 50A to 50C is included as described above, as shown in FIG. 4, it can be seen that a valid and modified state exists in the primary caches 12A to 12F. 'Modified' status, in which case a read request to global bus 21 occurs in the primary cache 12A-12F of all processor nodes 100A- 100C whose status of the access list is 'included'. It may not be retrieved and is only retrieved from the primary caches 12A-12F of the processor node whose access list 50A-50C has a status of 'Modified', and this cache will respond to read requests. As described above, when 'modified' is added to the states of the access lists 50A to 50C, as the state increases, the space for storing the state needs to be expanded, but the primary cache 12A to be searched according to the read request is required. To 12F) can be reduced, thereby reducing the load on the local buses 20A to 20C.

The protocols for maintaining cache coherency can be broadly classified into a write-through protocol and a write-back protocol. The direct write protocol is a form in which the shared memory 30 takes responsibility for responding to all memory accesses from the processors 11A to 11F. When a write occurs from the processors 11A to 11F, the shared memory 30 is used. And immediately update the block contents with the contents that have been written to all caches having the same address block. Therefore, the protocol of the direct write method generally exhibits relatively low performance compared to the protocol of the later write method.

Write-once, Synapse, Berkeley, Illinois, read-broadcast protocols, and their modified forms, are commonly used for later write methods. These protocols and their variants differ in the state and behavior of the cache block depending on the state when the write occurs and the read occurs. In this case, the access list proposed by the present invention can be applied when maintaining the multilevel cache nesting. .

In addition, in the case of a non-uniform memory shared memory multiprocessor structure (NUMA) as well as a uniform memory access shared memory multiprocessor structure with a constant memory access time, the same cache hierarchy is formed between the processor and the memory. It is obvious that the same can be applied.

5 is a non-uniform memory access shared memory multiprocessor, in which shared memory is divided into local memories 30A, 30B, and 30C in each of the processor nodes 100A, 100B, and 100C. In this case, when a memory access from any processor 11A occurs, the generated memory access is divided into a local memory 30A area and a remote memory 30B, 30C area according to its address area. When the generated memory access address is the local memory 30A area, such an access has a shorter memory access time than the remote memory 30B and 30C areas, and the remote memory access time is relatively long. In this case the cache of the largest level in the node is kept in the form of a remote cache 13A. In order to at least reduce remote memory access, which results in a significantly longer delay compared to local memory access time, the remote caches 13A-12C are derived not to contain local memory 30A-30C addresses, and thus, with the remote cache 13A. Multilevel cache nesting that occurs between processor caches 12A and 12B in processor module 10A is maintained only for remote memory address regions.

FIG. 6 illustrates a case in which the access lists 50A to 50C of the present invention are applied to the non-uniform memory access shared memory multiprocessor structure of FIG. 5, and the access lists 50A and 50B to each processor node 100A, 100B, and 100C. , 50C) is added, and the state of the access lists 50A, 50B, 50C, for example 50A, is maintained only for remote memory 30B, 30C block addresses excluding local memory 30A. That is, whether the access list 50A is validly stored in the primary cache 12A, 12B only for the state of the blocks stored in the remote memories 30B, 30C among the blocks stored in the primary caches 12A, 12B. It represents. Therefore, when a snooping request has occurred on the global bus 21 and its address area corresponds to the local memory 30A of a specific node 100A, the node controller 40A of the node 100A receives the address of the generated request. If the address area corresponds to the local memory 30A of the node 100A, the processor does not perform a search for the access list 50A, generates a request for the local bus 20A, and generates a processor cache. Perform a search for 12A, 12B and act on the result. That is, for a request from the global bus 21 for the local memory 30A address area of a specific node 100A, the node 100A does not have a remote cache 13A and an access list 50A. It works the same way.

FIG. 7 illustrates a connection structure between nodes 100A to 100F in a non-uniform memory access shared memory multiprocessor structure, and is formed in a ring shape using a point-to-point connection structure instead of a bus. Since the present invention is not limited by the interconnection network structure, a multi-level cache is configured in the access path between the processors 10A and 10B and the shared memory 30A and, as mentioned above, is closer to the processors 11A and 11B. The same may be applied as described above in the case where the contents of the small caches 12A and 12B must maintain the multilevel cache nesting that should be included in the larger caches 13A and 13B.

FIG. 8 is a node-to-node connection structure in a non-uniform memory access shared memory multiprocessor structure, and the case is formed in a double ring form using a dual point-to-point connection structure instead of a bus, and the present invention is not limited by the interconnection network structure. A multilevel cache is configured in the access path between the processors 11A and 11B and the shared memory 30A, and as mentioned above, the contents of the small caches 12A and 12B closer to the processors 11A and 11B are larger. The invention using the access list 50A is equally applicable as described above when it is necessary to maintain the multi-level cache nesting that should be included in the cache 13A of.

FIG. 9 extends the storage structure of an access list to a form in which a variable block address can be allocated, rather than a fixed block address as shown in FIG. 3, and it is necessary to secure space for storing the block address. You can reduce the size of the access list by not maintaining state for the entire shared memory. Status of addresses not stored in the access list is considered 'not included'.

In FIG. 9, the storage structure of the access list is extended to a form in which a variable block address can be allocated, and one access list unit storage space 150A, 151A, 152A, ... is included in a variable size memory block. We added an address space to indicate the state and a space to indicate the block size. In this case, the state of the access list will remain 'included' if the primary cache is storing one or more of the corresponding memory blocks.

In addition, the access list can eliminate the nesting of large stages for small stage caches, so the same applies to smaller stages of cache or to larger stages of cache for large stages of cache. Applicability is obvious. FIG. 10 shows an embodiment in which the cache stage is further extended to the processor modules 10A to 10D inside the processor nodes 100A and 100E, and the fourth cache 15A and the third stage bus 22 are added to the outside of the processor node. Yes. In this case, the multilevel cache implicitity is not maintained between the secondary cache 13A and the tertiary cache 14A, and all memory blocks present in the secondary cache 13A remain 'included' in the access list 50A. do.

As described above, the present invention is not directly related to a specific cache coherency protocol, and can be applied to all snooping-based protocols, and the multi-level cache nesting used to reduce the number of caches to be snooped in all snooping-based protocols. The number of caches to be snooped without being maintained can be reduced by the information in the access list.

In addition, the present invention is directed to reducing the cache hit ratio of the large stage due to block duplication in the large stage and the small stage cache as the large stage cache must include all the blocks in the small stage cache due to multi-level cache nesting. It has a reducing effect.

In addition, the present invention generates a block egress for the same address block present in the small cache when a large block eruption occurs, and reduces the cache hit ratio of the small level by the block elicitation required for the small cache. There is an effect that can eliminate the falling problem.

Claims (17)

A shared memory multiprocessor device with a multi-level cache structure, A processor for requesting data processing for a specific data block stored in the shared memory, and a processor cache which is a primary cache memory which pre-stores some data blocks among the data blocks stored in the shared memory for fast data processing of the processor. A plurality of processor modules configured; A secondary cache connected to the processor module by a local bus and storing some data blocks stored in the shared memory; An access list for storing valid state information of data blocks stored in the processor caches; Cooperatively manage the secondary cache and the access list to update the state information of the access list to correspond to the state of the data block stored in the processor cache, and the secondary for the specific data block requested for data processing from the processor And a node controller for retrieving from the cache memory and the shared memory in another processor module connected to the cache or the global bus and providing the cache to the processor cache. The method of claim 1, The access list has the same number of addresses as the memory block addresses in the shared memory, and the valid state information of the data block is recorded at a corresponding address corresponding to the data block stored in the processor cache. Shared memory multiprocessor device with cache structure. The method of claim 2, The access list is composed of a memory having a unique space corresponding one to one in block size unit with respect to the entire shared memory, and fixedly allocates one bit space per memory block address to correspond to each block address in the shared memory. And a data block included in the processor cache to indicate whether or not a data block is included in the processor cache. The method of claim 1, The node controller records the state information recorded at each address of the access list as 'not included' at the beginning, and then an address on the access list corresponding to the data block is allocated as a valid data block in the processor cache is allocated. And converting the state information of the data into 'included' to indicate that the corresponding data block is stored in the lower processor cache. The method of claim 1, The node controller checks whether a corresponding data block in a secondary cache connected to the processor and an internal local bus exists in a valid state when a read request for a specific data block is received from the processor, thereby checking the requested data in a valid state. And providing the corresponding data block to the processor cache when the block exists, and converting the state information of the corresponding data block address in the access list to 'included'. The method of claim 5, The node controller, when a read request for a specific data block from the processor, does not exist in the secondary cache in a valid state, the request through the global bus connecting a plurality of processor modules and the shared memory. Generate a read request of the data block, and provide the processor cache with a corresponding data block received in response to the read request from another processor module or shared memory connected to the global bus, and the corresponding data block address in the access list. A shared memory multiprocessor device with a multi-level cache structure characterized by converting state information to 'included'. The method of claim 6, When the node controller receives a read request through the global bus, the node controller searches for the requested data block in an access list storing a list of data blocks stored in the secondary cache and the processor cache, and stores the data block. And a multi-stage cache structure, wherein the shared memory multiprocessor device reads from the cache memory and transmits the data to the global bus. The method of claim 1, The node controller checks whether the write requested data block in the processor cache or the secondary cache exists in a valid state upon a write request for a specific data block from the processor, and the requested data block exists in a valid state. In this case, the corresponding data block is provided to the processor cache, the corresponding data block in the secondary cache is invalidated, and an invalidation request for the data block is generated by a global bus connecting a plurality of processor modules and the shared memory. And invalidating the corresponding data block in the cache memory and the shared memory of another processor module, and maintaining the state information of the corresponding data block in the access list as 'included'. The method of claim 8, The node controller, when the write request for a specific data block from the processor, if the write request data block in the processor cache or the secondary cache does not exist in a valid state, the write request data through the global bus Generates a request for a block, provides a corresponding data block received in response to the write request from the other processor module or shared memory to the processor cache, and sets status information of the corresponding block address in the access list as 'included'. Shared memory multiprocessor device with a multi-level cache structure, characterized in that for switching. The method of claim 9, When the node controller receives a write request through the global bus, the node controller retrieves the requested data block from an access list storing a list of data blocks stored in the secondary cache and the processor cache, and stores the corresponding data block. After reading from the cache memory and transmitting it to the global bus, multi-level cache characterized in that invalidates the data block in the cache memory, and converts the status information of the data block address on the access list to 'not included' Shared memory multiprocessor device in architecture. The method of claim 1, When the node controller requests a rewrite of a specific data block from the processor, the node controller stores the rewrite-requested data block in the secondary cache and deletes the data block in the corresponding processor cache, and then status information of the corresponding data block of the access list. Multi-stage cache structure, characterized in that the conversion to 'not included'. The method of claim 11, The access list has the same number of addresses as the memory block addresses in the shared memory and includes information on whether to modify the block along with valid state information of the data block at a corresponding address corresponding to a data block stored in the processor cache. And a shared memory multiprocessor device having a multi-level cache structure. A shared memory multiprocessor device with a multi-level cache structure, A plurality of processors comprising a processor for requesting data processing for a specific data block and a processor cache, which is a primary cache memory that pre-stores some data blocks among data blocks stored in the shared memory for fast data processing of the processor. A module; A local memory arranged to allocate the shared memory for each processor module and to be connected to each processor module by a local bus; A remote cache connected to each processor module by a local bus and storing some data blocks among data blocks stored in the remaining local memory allocated to the other processor module; An access list for storing valid state information of data blocks stored in the processor caches; Cooperatively manage the remote cache and the access list to update the state information of the access list to correspond to the state of the data block stored in the processor cache, and the remote cache for the specific data block requested for data processing from the processor And a node controller which retrieves from the local memory and the cache memory in another processor module connected to the local memory or the global bus and provides the corresponding processor cache to the shared memory multiprocessor device. The method of claim 13, The access list has the same number of addresses as the memory block addresses in the local memory allocated to the remaining processor modules connected to the processor module and the global bus, and stored in the processor cache among the data blocks stored in the remaining local memory. And the valid state information of the data block is recorded at a corresponding address corresponding to the data block. The method according to any one of claims 1 to 14, The shared memory multiprocessor device of claim 1, wherein the shared memory multiprocessor device has a uniform memory access time (UMA) scheme. The method according to any one of claims 1 to 14, The shared memory multiprocessor device is a shared memory multiprocessor device of a multi-level cache structure, characterized in that the non-uniform memory shared memory multi-processor structure (NUMA) method. The method according to claim 15 or 16, Node-control period connection of the processor module is a shared memory multi-processor device having a multi-stage cache structure, characterized in that the ring is made using a point-to-point connection structure.