GB2223868A - Multiprocessor system with multi-level caching - Google Patents

Description

1 1 U is 2223868 1 "A MULTIPROCESSOR SYSTEM' The present invention relates

to a multiprocessor system having a hierarchial storage structure and, more particularly, to a multiprocessor system which has a storage structure containing a main storage and a buffer storage with two or more levels and to carry out a storage control of each level and execute the processing by plural processors, in which an exclusive control of data is effectively carried out between plural buffer storages when data of the same address is entered into the plural buffer storages of each level.

Conventional data processing systems have used multiprocessor system having a structure in order to enhance a technology of a hierarchial storage processing velocity and capacity.

FIG. 6 illustrates one example of such a conventional multiprocessor system as having a hierarchial storage structure.

As shown in FIG. 6, this multiprocessor system is such that its storage structure is a three-level hierarchial structure consisting of a main storage (MS) 61, a working buffer storage (WS: Working Buffer Storage) 66 in a storage controller (SC) 62, buffer storages (BS) 64a and 64b in respective central processing units (CPU) 63a and 63b. The WS 66 of the SC 62 is connected to an input-output processor (including channel processing function;CH) for carrying out an input-output control. A 2 storage control is carried - out, between. the- MS. 61, WS - 66:, and BS 64a and the data processing-is executed by having-.

the CRU 6 3 read data and a;program from - the. MS 6 1.

-1n such a multiprocessor system, a transfer, from the WS 66 to the BS 64a and the BS.64b is made in a block unit, and a transfer from the MS 61 to the WS 66 is made - consisting of one block or plural in a so-called line unit (n) blocks. A one line unit (A) is shown therein to consist of four block units (aO, al, a2 and a3). For instance, if the CPU 63a reads data in block aO yet when this block aO does not exist in the BS 64a of the CPU 63a, access is made to the WS 66 of the SC 62 to allow the block aO to be entered into the BS 64a. In this case, if no line A containing the block aO exists on the WS 66, the SC 62 makes access to the MS 61 to read the line A from the MS 61 and enter it into the WS 66 as well as to transfer it to the BS 64a.

Likewise, for instance, if the CPU 63b transfer data in block aO yet when this block aO does not exist in the BS 64b, the block aO is entered from the WS 66. In this case, as shown in FIG. 6, if the block aO is registered in the BS 64a, the block aO exists the BS 64a. and the BS 64b.

for writing data in each of the simultaneously in both A store method buffer storages in a system having such a hierarchial storage structure in many cases uses a store-through method (a method in which a main storage is written simultaneously with a buffer storage) for the BS 64a and the BS 64b for ease of a control-amd. a store-in method (a 30 method in which the writing is executed only in the 3 working buffer system and rewrited to the main storage for replacement) for the WS 66 for a reduction of throughputs. In the system shown in FIG. 6, the BS 64a and the BS 64b adopt the store-through method and the WS 5 66 adopts the store-in method.

In this case, there is the occasion that data of the same block is registered simultaneously in the BS 64a and the BS 64b, as have been described hereinabove. For instance, if the CPU 63a rewrites data in the block aO of the BS 64a in such a state that the block aO exists simultaneously in both the BS 64a and the BS 64b, the block aO in the BS 64a is updated while the block aO in the BS 64b is not updated although the content of the data should be identical to each other, whereby a mismatch is caused in the data between the buffer storages.

Furthermore, when data of the block aO in the WS 66 of the SC 62 is rewritten or altered by the input-output processing by means of the CH 65, the block aO in both the BS 64a and the BS 64b is not updated so that a mismatch of data is caused between the block aO in the WS 66 and the block aO in the BS 64a and the BS 64b.

In order to remove the mismatch of data between the buffer storages, it is thus required to execute the processing of invalidating the block of the buffer storage whose data is not updated.

FIG. 7 illustrates one example of block invalidating processing of the buffer storage in themultiprocessor system. As shown in FIG. 7, reference numerals 67a and 67b denote BS directories (buffer address arrays: BAA) in c 4 which- is. st'ored -data- of a.: main storage... address-1 stored, in the buffer storage, which--- are -provided to correspond - to-the BS 64a and the BS 64b, respectively- The BS directory. (BAA) 67a is a directory of data stored in the 29- 64a and 5 the BAA 67b is a directory of data stored in the BS 64b. The BAA 67a, and the BAA. 67b consist of plural entries each of which is disposed at least so as to correspond on a 1-to1 basis to each of blocks of the BS 64a and the BS 64b. As shown in FIG. 8, each of the entries consists of an address (ADR) portion 68, indicating an address data in which a block of the buffer storage corresponds to an address of a main storage address, and a valid bit (V bit) portion 69, indicating the validity of an entry.

Referring back to FIG. 7, interfaces 71, 72 and 73 connecting the respective CPU 63a, CPU 63b, and CH 65 are used to control the invalidation processing. Each of the interfaces 71, 72 and 73 is a signal path for transmitting to each of the CPUs a signal, indicating the storing in each of the respective CPUs 63a, 63b and 63c, and its 20 store address.

When the block aO exists in the BS 64a and the BS 64b, a main storage address ADR aO on the MS 61 f or the block aO is registered in the address portion 68 of the corresponding entry of the BAA 67a and the BAA 67b and ' the corresponding the V bit of the valid bit portion 69 of entry is a "V', indicating that the data of the block is valid. When the CPU 63a rewrites data in the block aO of the BS 64a in this instance, communication stating that the block aO is written is given to the CPU 63b through the interface 71. This allows the CPU 63a to make a 1,1, search in the BAA 67b and the entry is invalidated (the processing for setting the V bit to a "Oll) when it was found that the store address ADR aO of the CPU 63a sent through the interface 71 has been registered in the BAA 67b. If it was found that the address ADR aO has not been registered in the BAA 67b, no invalidation processing is executed. The processing of storing in the CPU 63b is executed in the same manner as have been described hereinabove. Furthermore, when the CH 65 is stored in the WS 66 (FIG. 6), a store address is sent through the interface 73 to both the CPU 63a and the CPU 63b. The invalidation processing for the CPUs 63a and 63b is executed in the same manner as have been described hereinabove.

FIG. 9 illustrates another example of the block invalidation processing of the buffer storage in the multiprocessor system. In this example, furthermore, a copy of a buffer address array (BAA), which is a directory of a buffer storage, is provided on the storage controller (SC) as a front address array (FAA) in order to -orage. In carry out an identity control of the buffer st other words, as shown in FIG. 9, the SC 62 is further provided with a FAA 77a, which is a copy of the BAA 67a, and with a FAA 77b, which is a copy, of the BAA 67b. The structures of the FAA 77a and the FAA 77b are the same as those of the BAA 67a and the BAA 67b, respectively. When a block of the data is registered in the buffer storage and the address data is registered in the BAA, the same address data is registered in the corresponding FAA.

For instance, when the block aO exists simultaneously - c 6..

on the BS 64a and the HS. 64b, the -blo-ck address! ADR a1D is registered in the FAA 67a and the... FAA;67b.- as, well - as in the BAA 77a and the BAA 77b. lr order- to: al,low the CPU 63a to rewrite data in the block aO of the'BS 64a at --this time, a store request is issued from -the CPU 63a through the interface 74 to the SC 62 because data is registered in the BS in the store-through system. The SC 62 rewrites a request data in the block aO on the WS 66 and searches for the FAA 77a to investigate whether the block exists on the BS 64b. In this case, as the address ADR aO of the block aO is also registered in the FAA 77b, the SC 62 invalidates the entry of the FAA 77b. At the same time, invalidation of the entry of the BAA 67b is requested to the CPU 63b through the interface 75, whereby the CPU 63b invalidates the entry of the BAA 67b.

When the CPU 63b stores, in the same manner as hereinabove, the SC 62 searches for the FAA 77a and invalidates the entry if the block address would be registered and requires the CPU 63a to invalidate the entry of the BAA 67a through the interface 74. When the CH 65 stores, the FAA 77b address would The SC directory of the FAA 77a the SC 62 searches for both the FAA 77a and and invalidates the entries if the block have been registered.

62 is provided with a, WAA 76, which isa the WS 66, in addition to the directories of and the FAA 77b. As shown in FIG. 10, each entry of the WAA 76 consists of a valid bit (V bit) portion 78, indicating a valid entry, an address (ADR) portion 79, indicating a main storage address of a line of the WS 66 corresponding to the entry, and a rewriting/ - ill- 7 non-rewriting bit (C bit) portion 80, indicating that the line has been entered into the WS 66 and then the line has been rewritten. As the working buffer storage is registered in the store-in method, the SC 62 determines the need for writing back to the MS 61 the line to be fetched from the WS 66 by the number of bits of the C bit portion 80 when the line is replaced in the WS 66.

It is to be noted, however, that demands have been made to provide a data processing system with extendability in order to structure a system which can afford to process an increased amount of data increasing recently in recent years or which can lend itself to various use forms.

FIG. 11 is a block diagram illustrating one example of a multiprocessor system in which the multiprocessor system of FIG. 6 is further extended. This extended multiprocessor system is composed of a system consisting of four central processing units (CPU#O 63a, CPU1#1l 63b, CPU#2 63c, and CPU#3 63d) and two input -output processors (65a and 65b), a system structure being an addition of two central processing units and one input-output processor to the system structure of the multiprocessor system shown in FIG. 6. This data processing system connects the numbers of the central processing 'units (CPU) and the input- output processor (CH), which are twice as large as the multiprocessor system shown in FIG. 6.

In order to extend a multiprocessor system with the system structure as shown in FIG. 11, the following problems should be resolved. In other words, the storage 30 controller (SC 62) in the multiprocessor system of FIG.

- C.

a- 11 requires. -.the-. process ing t to - - - be, executed by. accepting a request - f rom, the. f our -,- CRUs and - the,-: two CHs '. so. that the system should have - throughputs capable of - processing.

requests from the total number of six machines. At this end, the storage controller of this extended multiprocessor system requires a high-speed internal control logic and its control logical unit becomes complicated, threby increasing a number of logical elements of a hardware and requiring a high-speed memory element. Furthermore, in order to maintain a hit rate of a request from each of request sources, i.e., CPUs 63a, 63b, 63c, 3d and CHs 65a, 65b, as high as the system as shown in FIG. 6, a working buffer storage (WS) capacity is required to be more than two times as large as the working buffer storage capacity of the system as shown in FIG. 6. It is further required to use a large number of cables connecting the CPUs 63a, 63b, 63c, 63d and the CHs 65a, 65b to the SC 62 as well as to provide the SC 62 with connection orifices corresponding to the number of the connecting cables.

As have been described hereinabove, in order to extend a system structure of tne multiprocessor system as shown in FIG. 11, its control logic is not complicated yet it undergoes various restrictions from hardware performance.

As an alternative example, a multiprocessor system can be constructed having a structure in which a storage controller is separatly installed. This example will be described with reference to FIG. 12 which illustrates a block diagram of one example of a multiprocessor system structure in which two storage controllers are installed.

9 The multiprocessor system of FIG. 12 constructs its data processing system consisting of two storage controllers (62a, 62b), four central processing units (CPUs 63a, 63b, 63c, 63d), and two input-output processors (65a, 65b). In such a system structure, as shown in the drawing, the numbers of the CPUs and the CHs to be connected to each of the storage controllers (SC 62a, 62b) are the same as in the system structure illustrated in FIG. 6. Thus, throughputs required for the SC 62a and the 62b in the system shown in FIG. 12 are almost the- same as for the SC 62 of FIG. 6 so that the system structure is not restricted by hardware performance as the system structure as shown in FIG. 11.

In the system structure as shown in FIG. 12, however, a data identity control of the BS in each of the CPUS is required to be executed for the BSs 64c and 64d as well as for the BSs 64a and 64b. It is further required to execute the data identity control for the WS 66a and the WS 66b in the respective SCs 62a and 62b.

For instance, if data of the block aO registered in neither the WS nor the BS, the CPU issues a read request for data in the block aO to the is 63a SC 62a. Then the line A containing the block aO is registered in the WS 66a as well as the block -aO is 25 registered in the BS 64a. In this state, when the CPU 63c issues a read request for data in the block aO to the SC 62b, too, the line A is registered in the WS 66b and the block aO is also registered in the BS 64c. If a data read request for data in the block aO is issued by the CPU 63b and the CPU 63d to the SC 62a and the SC 62b in this state,- the block aO: is, - also..- registered - in the ES 6-4b and the BS 64d,., respectively.. As- - a-,. resulti - the line A is registered in both the WS 66a and the WS 66b and all the BSs 64a, 64b, 64c and 64d are in: a state in which the 5 block aO is registered simultaneously.

In this state, the rewriting of data in the blockaO by the CPU 63a executes the processing of rewriting the data of the block aO in the BS 64a and in the line in the WS 66a. However, neither the data of the BSs 64b, 64c and 64d nor the data of the line A in the WS 66b is written. For is necessary to invalidate the block aO 64c and 64d by the BS data identity invalidate the line A of the WS 66b the block aO in the block aO in this reason, it in the BSs 64b, control and to by the WS data identity control.

In order to execute the invalidation processing, the WA-A entry is constructed to extend its registration content to contain an EX bit portion 99 in addition to a V bit portion 96, an ADR portion 97 and a C bit portion 98, as shown in FIG. 13. The EX bit portion 99 should have the following meaning in order to implement an exclusive control of the invalidation process. In other words, a line of EX bits consisting of a 1 is located on the WS in the self SC only, not on the WS in the other SC and in the BS in the CPU connected to the self SC, not in the BS in the CPU connected to the other SC.

This arrangement enables the absence of the line containing the block in the WS of the SC other than the self SC to be immediately found merely by making the SC connected to the CPU to retrieve its own WAA for the WS 1 U when the CPU rewrites data of the block in the working buffer storage and the other SC are not started when the line does not exist.

Operation in such a multiprocessor system will be 5 specifically described with reference to FIG. 14.

As shown in FIG. 14, two SCs 62a and 62b connected to the MS 61 while the CPUs 63a and 63b and CH 65a are connected to the SC 62a and the CPUs 63c are the and 63d and the CH 65b are connected to the SC 62b. The CPU 63a contains the BS 64a and its directory BAA 67a and the CPU 63b contains the BS 64b and its directory BAA 67b. The SC 62a contains the WS 66a and its directory WAA 76a as well as directories FAAs 77a and 77b, which are copies of the respective BAAs 67a and 67b. The SC 62b, CPU 63c, and CPU 63d are constructed each to have a structure comprising a working buffer storage, a buffer storage, their directories and copies of their directories. -A registration content of each entry of the BAAs 67a, 67b, 67c and. 67d comprises a valid bit portion and an address portion in the same manner as the entry shown in FIG. 8. A registration content of each entry of the WAAs 76a and 76b comprises the valid bit (V bit) portion 96, the address (ADR) portion 97, the rewriting/non- rewriting bit (C bit) portion 98, and an EX bit portion 99, as shown in FIG. 13.

The SC 62a starts its retrival of the WAA 76 when it has received a write request for data in the block aO of the line A through the interface 74 from the CPU 63a.

When the line A is registered in the WAA 76a, on 30 the one hand, the rewrite request is processed on the WS 1 1 12 6,6a and data of the block 40 of the line A --on- the- WS 66a is rewritten. In order to -- execut-ez the - data. - identi:ty control for the BS 64b, the SC 62& searches far the FAA 77a and invalidates the entry of the FAA 77b when the block is registered followed by an issuance of a request for invalidating the block of the BAA 67b to the CPU 63b through the interface 75. If the line is not registered in the FAA 77b, no processing is executed.

The data identity control for the WS 66b, BS 64c, and the BS 64d may vary with a number of EX bits of the entry in which the line A of the FAA 76a is registered.

When the EX bit consists of a "1", the line A exists in neither the WS 66b nor the BSs 64c and 64d so that the SC 62a does not initiate the interface 91. When the EX bit consists of a "0", there is the possibility that the line A exists in the WS 66b or the block (aO, aO, a2, a3) on the line A in the BSs 64c and 64d so that the SC 62a initiates the interface 91 and requests the data identity control to the SC 62b. This request allows the SC 62a to initiate the interface 91 and further requests the SC 62b to issue a request for the data identity control. The request has the SC 62b retrieve the WAA 76b and invalidate the entry if the line A is registered. For the FAAs 77c and 77d, all the blocks (aO, al, a2 and a3 in this example) in the line A are retrieved and the corresponding entry is invalidated if the registered block exists, issuing a request of invalidating the block by the interfaces 94 and 95 to the CPUs 63c and 63d, respectively. This invalidates the data of the line A on the WS 66b, BS 64c, and BS 64d and they disappear,so L1 13 that the SC 62a resets the EX bit of the entry in which the line A is registered in the WAA 76a to a ttly'.

When the line A is not registered in the WAA 76a, on the other hand, the SC 62a sends a request for the data identity control to the SC 62b through the interface 91 and interrupts the processing of the write request to the WS 66a. The SC 62b then retrieves the WAA 76b and communicates the retrieval result, i.e., the result that the line A is not registered in the WAA 76b, or the C bit value of the entry, when the line A was registered, to the SC 62a through the itnerface 91 and invalidates the line on the WAA 76d. The SC 62b further retrieves the FAAs 77-- ' and 77d and issues a reauest for the invalidation of the BSs 64d and 64d to the CPU 63c and the CPU 63d, respectively, when the line A is registered.

As the SC 62a receives the retrieval result of the WAA 76b of the SC 62b through the interface 91, i.'L- reads the line A from the MS 61, writes it into the WS 66a, processes a write request from the CPU 63a, and register the entry of the line A in the WAA 76a. At this time, the line A is sent from the WS 66b and the BSs 64c and 64d in the manner as have been described hereinabove, and the EX bit is registered as a I'll' in the WAA 76a.

In either case, the C bit of the entry in which the line A of the WAA 76a is registered is set to a "V'. It is further to be noted that there is the occasion the EX bit is set for the read request. In other words, if there is the possibility that data in the 'Line A is rewritten after the data has been read, the EX bit is set in advance when the line was read.

14 Operation of the SC w7ill- be-. described when-. the read request for the EX bit.- of the--line A"is's.ued-,-. from the CPU or the CH.

As shown in FIG. 14, when the CPU 63a issues a read request for data of the line A to set the EX bit, the request is processed by the BS 64a if the data exists on the BS 64a, so that the EX bit of the WAA 76a is not set. If the data does not exist on the BS 64a, the read request of the EX bit is issued to the SC 62a. If the line A is registered in the WAA 76a, the processing is executed within the SC 62a. by reading the WS 66a so that the EX bit is not set in this case, too. If the line A does not exist on the WS 66a, however, an inquiry is made to the SC 62b through the interface 91 into whether the line A exists in a rewritten state on the WS 66b. In this instance, the SC 62b retrieves the WAA 76b as well as the FAAs 77c and 77d, and a communication is made by the interface 92 that the EX bit can be set when the line A does not exist at all. In this case, the SC 62a reads data of the line A from the MS 61, stores in the WS 66a, and sets the EX bit to a "1" w.Len the entry of the line A is registered in the WAA 76a.

A technology of a non-exclusive control between buf fer storages in relation to an extended multiprocessor system is disclosed in Japanese Patent Publication (LaidOpen) No. 60-138, 653/1985.

It is further to be noted, however, that when an exclusive control of a hierarchial buffer storage is carried out in a multiprocessbr system, the store processing is executed by retrieving the line in the WAA -i of the other SC and invalidating the entry if the line would exist, when the EX bit of the self SC consists of a 1101', as well as by retrieving all the blocks in the line as to whether or not the blocks would exist in the BS connected to the other SC and invalidating these blocks if they exist. This method is efficient in executing the store processing, continuously in a range of a one line. When the store processing is required to be executed only for a one block portion in a one line, the rest of the blocks sent to the BS are not originally required to be invalidated, however, they are nevertheless invalidated unconditionally, so that the problem may arise because NIER (Not In Buffer Storage Ratio - a probability of absence of a block to be made access to BS) becomes high.

is It is an object of the present invention to provide a multiprocessor system in which an exclusive control between buffer storages can be carried out without raising a NIBR.

It is another object of the present invention to provide a multiprocessor system with at least a two-SC structure having a WS of a line size that is plural times as large as a block of a BS, which enables the processing of invalidating data of the BS on the other SC side in a block unit, not in a line unit, upon a data identity control between WSs.

In order to achieve the above objects, the present invention consists of a multiprocessor system comprising 30 a main storage (MS), a plurality of working buffer 16..

5,tor,ag"-- (TWISI) for storing. - a copy- MS, a -data, on the plurality of buffer storage&-- (BS.). for -storing a -copy of data on each of the WS, at least ona BS. be.ing d.isposed, so as to correspond to each of the and a. buffer address array (BAA) for registering a main storage address of data stored in the WS and the BS cor responding to each of the WS and the BS, having a hierarchial storage structure wherein a data register unit of the WS is plural times as large as a data registration unit of the BS, and having a structure in which the BS is exclusively used for each of the CPUs, wherein control means is disposed in which plural particular bits, indicating whether or not data of the main storage address stored in the WS corresponding to its self CPU is stored in the WS corresponding to the other CPU and in the BS connected thereto, are disposed so as to correspond to a WAA corresponding to the WS and in which, when data of the WS is rewritten, the WAA of the WS is retrieved and whether or not data of WS corresponding to the other CPU and data of BS connected to the WS are required to be invalidated by the plural particular bits of an entry of the WAA.

The multiprocessor system according to the present invention is characterized by the control means in which the particular bits ind icating whether or not data of the main storage address stored in the WS corresponding to the self CPU is stored in the WS corresponding to the other CPU and in the BS connected thereto, are separated into a first particular bit for managing a data identity between the WSs and a second particular bit for managing a data identity between the WS and the BS connected to i 17 the other W5 and disposed as part of an entry of the WAA of the WS or as memory array information corresponding to the entry and in which, when data of the WS is rewritten by a value of the particular bits, an identity control between the WSs and an identity control between the WS and the other BS can be carried out independently from each other.

It is to be noted herein that, in the multiprocessor system, a plurality of particular bits are provided, which indicate whether or not data of the main storage address stored in the WS corresponding to the self CPU is stored in the WS corresponding to the other CPU and in the BS connected thereto, and they are provided so as correspond to the WAA of the WS. When data of the WS rewritten, the WAA of the WS is retrieved and whether not there is required the processing of invalidating data of the WS corresponding to the other CPU and of BS connected thereto.

to is or the the The plural particular bits are divided into a EX bit for managing the dataidentity between the WSs and a EX bit for managing the data identity between the WS and the BS connected to the other WS and are provided as part of the entry of the WAA or as memory array information corresponding to the WAA entry. They carry out independently the identity control between the WSs and the identity control between the WS and the other BS with reference to each of the particular bits.

In other words, when the EX bit for the WS of the particular bits for implementing the identity control between the WSs is stored, for example, as EXL bit and 18 when the; part:icular- bits -corresponding to- the.---BS block. are stored, for, example,; as- EXCY- bits to EX3 - bits, inclusive, the processing is: controlled.. to store the -data only in the self WS because the same 'data doe's not exist in the other WS if the EXL bit of the WAA entry is assigned to "V'. When the EXi bit (i = 0 - 3) corresponding to the block of the store address is assigned to "V', the block does not exist in the other BS so that no block cancel request is not issued to the other BS. When the EXi block is assigned to "0", the store operation of the WS is carried out and a block cancel request is issued to the other BS. When the corresponding entry does not exist in the self WAA or when the EXL bit is assigned to PV even if the entry would exist, the other WAA is retrieved and invalidated if the entry exists on the WAA, thereby assigning the EXL bit to "1" and registering the updated data in the self WAA and WS. At this -'L-ime, the block of the other BS corresponding to block 0 to block 3 are not invalidated as a whole and only the block corresponding to the store address to the self WS isinvalidated, thereby assigning the EXi bit (i = a block number of store addresses) to "1" and registering it in the self WAA.

Accordingly, when the data identity control is carried out between the WSs, the BS data invalidation processing on the other SC side can be executed in a block unit, not in a line. In other words, in execution of the invalidation processing of data an the WS and the BS, which accompanies the store operation, the invalidation of the block of the BS connected to the 19 other SC is made only against the block containing the store address while leaving data of the block in the line which is left unchanged. Thus, unless a store request would be issued for all blocks in the line, a hit ratio of the BS can be prevented from reducing.

v The present inventinn will now be described in greater detail by way of examDles with reference to the accompanying drawings, wherein:- FIG. 1 is a block diagram illusrating an overall structure of an essential portion of the multiprocessor system according to one example of the present invention.

is FIG. 2 illustrates one example of an entry structure of a directory of the working buffer storage according to one example of the present invention.

FIG. 3 is a block diagram illustrating one example of a hit judgment circuit for comparing a request address with an entry of the WAA.

FIG. 4 is a circuit diagram illustrating an essential portion of a control circuit for carrying out the hit control and the exclusive control of the working buffer storage in the storage controller.

FIG. 5 is a circuit diagram illustrating other example of a hit judgment circuit for comparing the request address with the WAA entry.

FIG. 6 is a block diagram illustrating one example of a multiprocessor system in a hierarchial storage 30 structure.

FIG. 7 illustrates, one,,- example. - af the block invalidation processing - - of the.' bUf fer''- stcyrage in the is multipxc)cessor system.- FIG. 8 illustrates one example of an entry 5 structure of a directory of the buffer storage FIG. 9 illustrates another example of the block invalidation processing of the buffer storage in the multiprocessor system.

FIG. 10 illustrates one example of an entry 10 structure of a directory of the working buffer storage.

FIG. 11 is a block diagram illustrating on example of a multiprocessor system of FIG. 6, in which the system is further extended.

FIG. 12 is a block diagram illustrating the structure of a multiprocessor system in which two storage controllers are installed.

FIG. 13 illustrates another example of an entry structure of a directory of the working buffer storage.

FIG. 14 illustrates an example of the block invalidation processing of the buffer storage in the multiprocessor system of FIG. 12.

FIG. 1 is a block diagram illusrating an overall structure of an essential portion of the multiprocessor system according to one example of the present invention and FIG. 2 illustrates one example of an entry structure of a directory of the working buffer storage according to one example of the present invention.

As shown in FIG. 1, two SCs 62a and 62b are k I- - 21 connected to the MS 61 while CPUs 63a, 63b and the CH 65a are connected to the SC 62a as well as CPUs 63c, 63d and the CH 65b are connected to the SC 62b. The CPU 63a contains a buffer storage (BS) 64a and a buffer address array (BAA) 67a, which is a directory of the BS 64b, and the CPU 63b likewise contains a buffer storage (BS) 64b and a BAA 67b, which is a directory of the BS 64b. The SC 62a contains a working buffer storage (WS) 66a, its directory WAA 76a of the WS 66a as well as front address arrays (FAAs) 77a and 77b, i.e., a copy of each of the respective BAAs 67a and 67b. The SC 62b, CPU 63c and CPU 63d are likewise constructed to have a structure containing a working buffer storage, their directories, and copies of the directories. The registration content of each entry of the BAAs 67a, 67b, 67c and 67d comprises a valid bit portion and an address portion (as shown in FIG. 8). The registration content of each entry of the WAAs 76a and 76b comprises a valid bit portion, an address portion,rewriting/non-rewriting bit portion, and a particular bit portion for registering plural particular bits for executing the exclusive control between the buffer storages.

As have been described hereinabove, the system structure of the multiprocessor system of FIG. 1 is the same as that as have been described in FIG. 12, and the content of each entry of the WAAs 76a and 76b is used which has been described in FIG. 2. It is characterized in that the particular bits for carrying out the exclusive control between the buffer storages are plural.

As shown in FIG. 2, the plural particular bit portions a buffer storage, 22 - for- registeringz--- the, entry, 20 --'consist.- of, EXL bit 21, EXO bit 22- corresponding to ea-ch,,b-1.oc3c., EXI'. bit 23, EX2 bit 24, and EX3 bit 25. The EXL bit 2-1 is - a, bit -.indicating that a line data of the WS is ' in. an-.. exclusive state between the WSs. When the EXL bit 21 is'.assigned to a..-"1", it is guaranteed that the identical line data does not exist in the WS of the other SC. The EXO bit 22, EX1 bit 23, EX2 bit 24 and EX3 bit 25 are control bits corresponding to the numbers of the BS blocks consisting of line data of the entry 20 of the WSs. When each of EXO bit 22, EX1 bit 233, EX2 bit 24 and EX3 bit 25 is assigned to a 1,111, it is guaranteed that, for each block, no identical data exists in all the BS connected to the WS of the other SC.

is Hit Judgment operation of the WS will be described with reference to FIG. 3 and mutual inquiry operation of the WS and BS for executing the exclusive control will be described with reference to FIG. 4.

FIG. 3 is a block diagram illustrating one example of a hit judgment circuit for comparing a request address with a WAA entry. As shown in FIG. 3, reference numeral stands for a WAA entry, 30 for a request address, 30a for an entry address data of the request address, 30b for a 2-bit data indicating a block number in the WS line, 31 for a 2-bit decorder, 32 for an entry address comparing circuit, 33 - 37 for AND gates, 38 for an OR gate, 39 and 40 for AND gates, 41 for an inverter, 42 and 43 f or AND gates, and 44 for a OR gate. The entry address is compared by the entry address comparing circuit 32 and generated, together with the comparison results, by judging bits by the WS resul ts gate 42, shown in 23 a status by a logic with output of the EXO to EX3 a decode output of the block number in each of lines. Signals A, B, C, and D of the output from the respective OR gate 44, inverter 41, AND and AND gate 43 indicate each status as will be TABLE 1 below.

Signal A:

Signal D:

T A B L E 1 No exclusive control is required for the other WS and BS in a Hit status. This applies to cases wherein a line exists for a request other than the store request and a desired line exists in the WS at EXL = 1 for the store request.

Signal B: Not Hit status.

Signal C: Although a line to which access was made exists, exclusive control is required for the other SC because EXL bit is assigned to "0" when the store request issues.

Although a line to which access was made exists in the WS, a block cancel is required for the BS connected to the other WS because the EXi bit of the access block is assigned to a IT".

FIG. 4 illustrates a circuit diagram indicating an essential portion of the control circuit for executing the hit control and the exclusive control of the working buffer storage in the storage controller.

Operation of the hit control and exclusive control 30 by the SC by integrating outputs of signals A, B, C, and 1 1 i 24.

D from the hit judgment, circuit- CFIG... 3) for each-- row. will be described in more detai:,l," with -reference- to FIG-4,. As shown in FIG. 4, reference numerals- 45a,.;-: 45b, 45c. and 45d denote hit judgment circuits of row numbers 0, 11, 2, and 3, respectively. Outputs of signals A, B, C, and D of each hit judgment circuits for the row numbers correspond to AO - A3, BO - B3, CO - C3, and DO - D3, respectively. In the drawing, reference numerals 46a 46d, 47, 48, 50, 54 and 55 denote OR gates, reference 10 numerals 49 and 51 - 53 denote AND gates, 56 denotes a 4-bit encorder, 57 denotes a selector, and 59 denotes a signal from a replacement logic (WRA) for determining a replacement row for determination of a row replacing the line when the desired line does not exist in the WS, which is a 2-bit row data. Reference numeral 58 denotes a row number register (2 bits) of the WS.

Logical outputs I, II, III, IV, V, and VI of output gates will be described by TABLE 2 below, which are outputted by gating the logic from each of logicical 20 gates of the control circuits.

11:

T A B L E 2 I: Hit processing request. No exclusive control for the other WS is required.

When EXi bit of a block containing a store address is assigned to "l", a block cancel request is issued to the other SC from logical output VI and the self EXi bit is assigned to a "1".

Hit processing request with exclusive control 1, IV:

V:

for other WS.

Since EXL bit is assigned to a "0" although a desired line data exists in the self WS, it is inquired that the identical line exists in the WAA of the other WS and, if it exists, the entry is invalidated.

Not-Hit processing request for read only fetch request.

When the latest data is found to exist in the other WAA upon retrieval, the data is transferred from the other WS and EXL and EXO to EX3 bits of the self WAA are assigned all to a 11011.

Not-Hit processing request for fetch request with EX demand.

When the latest data is found to exist in the other WAA upon retrieval (if data is changed in the other WS), the data is transferred from the other WS to the self WS and the entry of the other WAA is invalidated.

Not-Hit request for store request.

When it is found upon retrieval of the other WAA that the corresponding line exists, the entry is invalidated and EXL bit is assigned to a 11111.

The latest data is transferred from the other WS or MS to the self WS. To the other BS is issued an invalidation request only for a block containing the store request (IV), and the EXi bit is assigned to a 11111 (i being a 26, :5 VI:

block.-. number for whkch the invalidation request has beerr issued)..

Block cancel request for the. other BS -during store processing.

A block cancel request is.. issued for a block containing a store address and the EXi bit is assigned to a "ll' (i being a block number containing the store address).

In the block cancel request for the BS, the block cancelling of the BSs 64c and 64d in the system on the side of the SC 62b from the SC 62a is executed by retrieving whether or not the corresponding entry exists in the BAAs 67c and 67d, using the FAAs 77c and 77d, and by issuing an invalidation request f or the entry to the BAAs 67c and 67d only when it is found that the entry exists upon retrieval.

The fetch request with the EX demand means - a request which will store a block or line fetched with a high probability..

-ing another FIG. 5 is a circuit diagram illustrat example of the hit judgment circuit for comparing the request address with the WAA entry. This hit judgment circuit has substantially the same structure as that shown in FIG. 3, with the exception that particular bits to be registered in the WAA entry are those corresponding to an entry in which a EXL bit of EX bits for the WS is not provided. In other words, a logical sum signal of signals from the particular bits, EXO bit to EX3 bit, corresponding to the block, in place of signals from the 30 EXL bit of EX bits for the WS. Accordingly, the OR gate 27 is particularly provided and a signal gated from this gate is used. In using such a hit judgement circuit, what is different from the case wherein the EXL bit is provided is that the EXi bit should be assigned to a 'U" in the processing of the fetch request with the EX request even if the EXi bit of the block i corresponding to the access address is not stored.

As have been described hereinabove, the essential portion of the multiprocessor system according to the examples of the present invention may be summarized as follows.

1. The identity control between the WSs for the store request is carried out in a line unit, however, data of the BS in the other system is left non-invalidated as long as the block is not updated, in order to manage the data of the BS in a block unit. This prevents a NIBR of the other BS from being elevated.

2. In the identity control between the WSs for the fetch request with the EX request, the entry of the other WS is invalidated, however, the other BS is not invalidated until a store request is issued. Thus a NIBR of the other BS can be made smaller.

As the above examples are directed to a 3-level hierarchial storage structure, it is to be understood that the present invention can be applied to a system in which its storage structure is in a hierarchy with four levels or more. It is noted that the numbers of CPUs, CHs, and WSs can be extended with ease.

As have been described hereinabove, the present 30 invention has been described by way of examples, but it k' Z8.'. - - understood --, that, kt -is. not;:,, restricted to - these is to be. examples and it encompasses various, changesand variations. without departing the spirit and -. scope of the present invention.

In accordance with the present tinvention,- when data on the WS and the BS is invalidated in accompany with store operation, the multiprocessor system comprising the main storage (MS), a plurality of working buffer storages (WSs), and a buffer storage (BS) allows the WS to invalidate the data of the other WS and at the same time to invalidate the block containing the store address on the BS connected to the other SC yet leaving the data of the rest block in the unchaged line as it is not invalidated. Accordingly, a reduction in hit ratio of the BS can be prevented unless a store request is issued for all the blocks in the line.

1 29 CT,AlMS: - 1. A multiprocessor system comprising a main storage, a plurality of working buffer storages for storing a copy of data on the main storage, a plurality of buffer storages each for storing a copy of data on each of the working, buffer storages, and a directory for registering a main storage address of the data stored in the working buffer storage and the buffer storage corresponding to each of the working buffer storages and the buffer storages, respectively; having a hierarchial storage structure in which a data registration unit of the working buffer storage is plural times as large as a data registration unit of the buffer storage; and having a structure in which each of the buffer storages is used exclusively in a processor unit; wherein:

a plurality of particular bits are provided so as to correspond to the directory of the working buffer storage, which indicate whether or not data of the main storage address stored in the working buffer storage corresponding to a self processor is stored in the working buffer storage corresponding to an other processor or in the buffer storage connected thereto; and invalidation processing is executed when the data of the working buffer storage is rewritten, by retrieving the directory of the working buffer storage and by judging whether or not the data of the working buffer storage corresponding to the other processor and the data of the buffer storage connected thereto is required to be 30 invalidated, by a value of the plurality of the 4 partIcular bits of an, entry of the, d.irectcrry-.

2. A multiprocessor--- system, as- claimed in - claim 1, wherein the plurality of the particular bits: provided in correspondence to the directory of the working buffer storage consists of a sum of n+l bits in which the working buffer storage corresponding to the other processor consists of a one bit and a block unit of the buffer storage corresponding to the self processor or each of units being plural times as large as the block unit consists of n bits.

3. A multiprocessor system as claimed in claim 1, wherein:

the plurality of the particular bits provided in correspondence to the directory of the working buffer storage is provided so as to allow the block unit of the buffer storage corresponding to the self processor or each of units being plural times as large as the block unit consists of n bits; and a signal of the particular bits for the working buffer storage corresponding to the other processor is a logical sum signal of the particular bits consisting of n bits provided for the buffer storage.

4. A multiprocessor system as claimed in claim 1, 4 wherein, when data of the working buffer storage is rewritten, data of the working buffer storage corresponding to the other processor is invalidated by a logical sum value of the particular bits consisting of one bit for the working buffer storage and n bits for the buffer storage.

5. A multiprocessor system as claimed in claim 1, v V, 31 wherein, when data of the working buffer storage is rewritten, data of the working buffer storage corresponding to the other processor is invalidated by a value of the particular bits corresponding to a buffer storage block of a directory of the working buffer storage.

6. A multiprocessor system comprising a. main storage, a plurality of working buffer storages for storing a copy of data on the main storage, a plurality of buffer storages each for storing a copy of data on each of the working buffer storages, and a directory for registering a main storage address of the data stored in the working buffer storage and the buffer storage corresponding to each of the working buffer storages and the buffer storages, respectively; having a hierarchial storage structure in which a data registration unit of the working buffer storage is plural times as large as a data registration unit of the buffer storage; and having a structure in which each of the buffer storages is used exclusively in a processor unit; wherein:

particular bits, indicating whether or not data of the main storage address stored in the working buffer storage corresponding to a self processor is stored in the working buffer storage corresponding to an other processor and in the buffer storage connected thereto, are divided into a first particular bit for managing a data identity between the working buffer storages and a second particular bit for managing a data identity between the working buffer storage and the buffer storage connected to an other working buffer storage, and the 32 particular-- bits are provided as - part- of an entry of-- thedirectory. of the working buffer. - storage'. o'r.- as a memory array information;. and - the identity control between the working buffer storages by a value of the particular bit upon the rewriting of data of the working buf fer storage and the identity control between the working buf fer storage and the other buf f er storage are executed respectively by the first particular bit and the second particular bit 10 independently from each other.

7. A multiprocessor system constructed substantially as herein described with reference to and as illustrated in the accompanying drawings.

Published 1990 atThe Patent Office, State House, 66171 High Holborn, London WCIR 4TP. Further copies maybe obtamedfrom The Patent Office. Sales Branch, St Mary Cray, Orpington. Kent BR5 3RD. Printed by Multiplex techniques ltd, St Mary Cray. Kent, Con. 1187