Access control method for a shared main memory in a multiprocessor based upon a directory held at a storage location of data in the memory afte

Claims

What is claimed is:

1. A method for controlling main memory accesses in a computer system which includes a plurality of processing units and a main memory shared by said plurality of processing units, wherein each processing unit includes a processor and a cache memory which holds a part of data held in said main memory, the method comprising the steps of:

(a) transferring a data line requested by a read request provided by one of said processing units to a cache memory therewithin from a storage location for said data line within said main memory, when there is no processing unit which has already cached said data line;

(b) storing directory information into said storage location in said main memory in place of said data line, in response to said transferring step (a), said directory information indicating that said one processing unit is a processing unit which has cached said data line;

(c) transferring said data line from said cache memory within said one processing unit as designated by said directory information to another of said plurality of processing units, in response to a new read request provided by said another processing unit for said data line after said data line has been cached by said one processing unit;

(d) renewing the directory information stored in said storage location so that said renewed directory information indicates that said another processing unit is also a processing unit which has cached said data line; and

(e) responsive to replacement of said data line by one of said plurality of processing units which has cached said data line, controlling writing back of said replaced data line, depending upon said directory information, so that said replaced data line is written back into said storage location of said main memory in place of said directory information stored therein, when there is no processing unit in which said data line is still cached, and so that said replaced data line is not written back, when said data line is still cached in one of said plurality of processing units.

2. The method of controlling main memory accesses according to claim 1, wherein said step (e) of controlling the writing back of said replaced data line comprises the steps of:

detecting whether there is at least one processing unit in which said data line is still cached, depending upon said directory information;

writing back said replaced data line into said storage location of said main memory when said detecting indicates that there is no processing unit in which said data line is still cached; and

not writing back said replaced data line when there is at least one processing unit in which said data line is still cached, irrespective of whether or not said replaced data line has been modified after said data line has been transferred to said cache memory of said one processing unit which has replaced said data line.

3. The method for controlling main memory accesses according to claim 1, further comprising the steps of:

storing status information in correspondence to said storage location before execution of said step (a), said status information indicating whether or not a data line at said storage location is already cached in one of said plurality of processing units;

activating said transferring step (a) when said status information indicates that a data line at said storage location is not cached in any of said plurality of processing units;

activating said transferring step (c) when said status information indicates that a data line at said storage location is already cached in at least one of said plurality of processing units; and

altering said status information after execution of said step (e), to indicate that said data line at said storage location is not cached by any of said plurality of processing units.

4. The method for controlling main memory accesses according to claim 1, further comprising the steps of:

storing status information in correspondence to said storage location before execution of said step (a), said status information indicating whether or not a data line at said storage location is read only data;

activating said step (b) when said status information has indicated that a data line at said storage location is not read only data, and prohibitting execution of said step (b) when said status information indicates that a data line at said storage location is read only data;

activating said step (c) when said status information indicates that a data line at said storage location is not read only data; and

transferring said data line at said storage location of said main memory to said cache memory of said another processing unit which has issued said another data read request when said status information indicates that a data line at said storage location is read only data.

5. The method for controlling main memory accesses according to claim 1, further comprising the steps of:

(f) generating a cache invalidation request for said data line at said storage location by one of said plurality of processing units which has cached said data line when said one processing unit has renewed said cached data line;

(g) detecting each of every at least one of a plurality of processing units in which said data line is cached based upon said directory information stored in said storage location of said main memory; and

(h) transferring said cache invalidation request to said each processing unit in which said data line is cached as has been detected in the step (g).

6. A method for controlling main memory accesses in a parallel computer system which includes a plurality of processing units and a network which connects said plurality of processing units for parallel transfer of plural data therebetween, wherein each of said processing units includes a processor, one of a plurality of partial main memories which realize a main memory shared by said plurality of processing units, and a cache memory which holds a part of data held in said main memory, the method comprising the steps of:

(a) transferring a data line held in a storage location within one of said plurality of partial main memories, provided within one of said plurality of processing units, to a cache memory within another of said processing units, in response to a data read request for said data line transferred to said one processing unit by way of said network from said another processing unit when there is no processing unit in which said data line is cached;

(b) storing directory information into said storage location of said one partial main memory in place of the data line in response to the transferring step (a), said directory information indicating that said another processing unit has cached said data line;

(c) said one processing unit responding to a new read request for said data line transferred to said one processing unit from yet another of said plurality of processing units by way of said network after said data line has been cached by said another processing unit, detecting said another processing unit as a processing unit which has cached said data line based upon said directory information, and requesting said another processing unit, by way of said network, to transfer said data line to a cache memory of said yet another of said plurality of processing units;

(d) said another processing unit responding to said requesting and transferring said data line from said cache memory within said another processing unit to said yet another processing unit by way of said network; and

(e) renewing the directory information stored for said data line in said one partial main memory so that said renewed directory information indicates that said further another processing unit also has cached said data line.

7. The method for controlling main memory accesses according to claim 6, further comprising the steps of:

(f) transferring said data line from one of said plurality of processing units which has cached said data line to said one processing unit by way of said network when said one processing unit has replaced said data line from a cache memory therewithin;

(g) said one processing unit judging whether said transferred data line is cached in one of said plurality of said processing units, based upon said directory information stored in said storage location of said one partial main memory for said transferred data line;

(h) writing back said transferred data line into said storage location of said one partial main memory when said judging indicates that there is no processing unit which has cached said data line; and

(i) not writing back said transferred data line into said storage location of said one partial main memory when said judging indicates that there is at least one processing unit which has cached said data line.

8. The method for controlling main memory accesses according to claim 7, wherein said one processing unit which has replaced said data line executes said transferring step (f), irrespective of whether said data line has been modified after said data line has been cached in said one processing unit which has replaced said data line.

9. The method for controlling main memory accesses according to claim 6, further comprising the steps of:

storing status information in correspondence to said storage location before execution of said step (a), said status information indicating whether or not said data line at said storage location is already cached in one of said plurality of processing units;

activating said transferring step (a) when said status information has indicated that said data line at said storage location is not cached in any of said plurality of processing units; and

activating said transferring step (c) when said status information has indicated that said data line at said storage location is already cached in one of said plurality of processing units.

10. The method for controlling main memory accesses according to claim 6, further comprising the steps of:

storing status information in correspondence to said storage location before execution of said step (a), said status information indicating whether or not said data line at said storage location is read only data;

activating said step (b) when said status information has indicated that said data line at said storage location is not read only data, and prohibitting execution of said step (b) when said status information indicates that said data line at said storage location is read only data;

activating said step (c) when said status information indicates that said data line at said storage location is not read only data; and

transferring said data line at said storage location of said main memory to said cache memory of said another processing unit which has issued said another data read request when said status information indicates that said data line at said storage location is read only data.

11. A method for controlling main memory accesses in a computer system which includes a plurality of processing units and a main memory shared by said plurality of processing units, wherein each processing unit includes a processor and a cache memory which holds a part of data held in said main memory, the method comprising the steps of:

(a) transferring a data line requested by a read request provided by one of said processing units to a cache memory therewithin from a storage location for said data line within said main memory when there is no processing unit which has already cached said data line other than said one processing unit;

(b) transferring said data line as requested by said read request provided by said one processing unit to a cache memory therewithin from a cache memory within another of said plurality of processing units which has cached said data line; and

(c) writing back said data line cached in one of said plurality of processing units into said storage location of said main memory in response to replacement of said data line from a cache memory within said one processing unit which has cached said data line when said data line does not remain cached in any processing unit other than said one processing unit which has replaced said data line, and not writing back said replaced data line when said data line remains cached in another of said plurality of processing units.

12. The method for controlling main memory accesses according to claim 11, further comprising a step of:

transferring said replaced data line from said one processing unit which has replaced said data line to said main memory as data to be written back, irrespective of whether said data line has been modified after said data line has been cached in said one processing unit which has replaced said data line;

wherein said writing back step (c) is executed for said data line transferred to said main memory from said one processing unit which has replaced said data line.

13. The method for controlling main memory accesses according to claim 11, further comprising the steps of:

keeping status information in correspondence to said storage location of said main memory after said data line has been transferred by said step (a) to said one processing unit which has requested said data line until said data line is written back into said storage location of said main memory by said step (c) from one of said plurality of said processing units which has replaced said data line, said status information indicating that said data line at said storage location is cached in one of said plurality of processing units;

keeping directory information in correspondence to said storage location of said main memory after said data line has been transferred in said step (a) to said one processing unit which has requested said data line until said data line is written back into said storage location of said main memory in said step (c) from one of said plurality of said processing units which has replaced said data line, said directory information indicating each processing unit which has cached said data line;

activating said transferring step (a) when said status information is not yet kept for said storage location;

detecting said another processing unit which has cached said data line, based upon said directory information stored for said storage location when said status information is already kept for said storage location;

activating said transferring step (b) so that said detected another processing unit is involved in said transferring step (b); and

altering said directory information in response to execution of said step (b) to indicate that said one processing unit which has requested said data line is also one which has cached said data line of said storage location.

14. A method for controlling main memory accesses according to claim 13, wherein said directory information for said storage location is stored in said storage location in place of said data line after execution of said transferring step (a).

15. The method for controlling main memory accesses according to claim 11, further comprising the steps of:

storing status information in correspondence to said storage location before execution of each of said steps (a) and (b), said status information indicating whether or not said data line at said storage location is read only data;

activating said steps (a) and (b) when said status information has indicated that said data line at said storage location is not read only data;

activating said transferring step (a), irrespective of whether or not said data line is cached in one processing unit other than said one processing unit which has provided said read request when said status information indicates that said data line at said storage location is read only data;

storing status information in said one processing unit which has requested said data line in correspondence to said data line transferred to said one processing unit as a result of said activating of step (a), said stored status information indicating said transferred data line is read only data;

activating said step (c) when status information for said replaced data line stored in said one processing unit which has replaced said data line indicates that said data line is not read only data; and

prohibiting writing back of said replaced data line when said status information for said data line indicates said data line is read only data.

16. The method for controlling main memory accesses according to claim 11, further comprising the steps of:

(d) generating a cache invalidation request for said data line by one of said plurality of processing units which has cached said data line when said one processing unit has renewed said cached data line; and

(e) transferring said cache invalidation request to each processing unit which has cached said data line, other than said one processing unit which has generated said cache invalidation request.

17. A method for controlling main memory accesses in a parallel computer system which includes a plurality of processing units and a network which connects said plurality of processing units for parallel transfer of plural data therebetween, wherein each processing unit includes a processor, one of a plurality of partial main memories which realize a main memory shared by said plurality of processing units, and a cache memory which holds a part of data held in said main memory, the method comprising the steps of:

(a) judging, by one of said plurality of processing units, whether a data line held in a storage location within one of said plurality of partial main memories, provided within said one processing unit is already cached in another of said plurality of processing units, in response to a data read request for said data line transferred to said one processing unit from another processing unit by way of said network;

(b) said one processing unit transferring said data line from said storage location of said one partial main memory to said another processing unit which has requested said data line by way of said network when said judging step indicates that no processing unit has cached said data line;

(c) said one processing unit requesting said another of said plurality of processing units by way of said network to transfer said cached data line to said another processing unit which has generated said data read request when said judging step indicates that said another processing unit has cached said data line;

(d) said another processing unit which has cached said data line transferring said data line cached therein by way of said network to said another processing unit which has requested said data line, in response to said requesting;

(e) transferring said data line from one of said plurality of processing units which has cached said data line to said one processing unit by way of said network when said one processing unit has replaced said data line after caching thereof;

(f) said one processing unit judging whether a same data line as said transferred data line remains cached in one of said plurality of processing units other than said one processing unit which has replaced said data line;

(g) writing back said transferred data line into said storage location of said one partial main memory when said judging indicates that there is no processing unit which has cached said data line; and

(h) not writing back said transferred data line into said storage location of said one particular partial main memory when said judging indicates that there is a processing unit which has cached said data line.

18. The method for controlling main memory accesses according to claim 17, wherein said one processing unit which has replaced said data line executes said transferring step (e), irrespective of whether said data line has been modified after said data line has been cached in said one processing unit which has replaced said data line.

19. The method for controlling main memory accesses according to claim 17, further comprising the steps of:

keeping directory information in correspondence to said storage location after said data line has been transferred in said step (b) to said another processing unit which has requested said data line until said data line is written back into said storage location by said step (g), a status information indicating which of said plurality of processing units has cached said data line; and

renewing said directory information after execution of each of said steps (c) and (f);

wherein said judging step (a) includes a step of judging whether directory information is already stored in correspondence to said storage location and judging whether there is another processing unit which has cached said data line of said storage location other than said one processing unit, based upon said directory information stored in correspondence to said storage location when said directory information is already stored in correspondence to said storage information,

wherein said judging step (f) is executed based upon directory information stored in correspondence to said storage location for said transferred data line.

20. The method for controlling main memory accesses according to claim 19,

wherein said directory information is stored in said storage location for said data line in place of said data line after execution of said step (a);

wherein said replaced data line is written back into said storage location at step (g) in place of said directory information held therein.

21. The method for controlling main memory accesses according to claim 17, further comprising the steps of:

storing status information in correspondence to said storage location before execution of said step (a), said status information indicating whether or not said data line at said storage location is read only data;

activating said steps (a) to (d) when said status information has indicated that said data line at said storage location is not read only data;

responsive to said data read request mentioned in step (a), transferring said data line from said storage location of said main memory to said another processing unit which has requested said data line, irrespective of whether said data line has been cached in one of said plurality of processing units.

22. A computer system, including:

a plurality of processing units;

a main memory shared by said plurality of processing units; and

a main memory control circuit which controls accesses to said main memory by said plurality of processing units, wherein each processing unit includes:

a processor, and

a cache memory which holds a part of data held in said main memory;

wherein said main memory control circuit includes:

a main memory access control circuit which responds to data read request and data write requests provided by said plurality of processing units and accesses said main memory; and

a directory information generation circuit which responds to operations of said main memory access control circuit and generates either one of directory information for each storage location of said main memory and renewed directory information generated by said directory generation circuit for said each storage location, said directory information for said each storage location indicating each of said processing units which has cached a data line held in said each storage location;

wherein said main memory access control circuit includes:

an access circuit responsive to a data read request provided by one of said plurality of processing units, for reading a data line requested by said read request from a storage location for said data line within said main memory when there is no processing unit which has already cached said data line, and transferring said read data line to said one processing unit,

a write circuit responsive to said transferring of said data line for writing directory information generated by said directory generation circuit for said data line into said storage location for said data line in place of said data line, and

a data transfer request circuit responsive to another data read request given by another of said plurality of processing units for said data line after said data line has been transferred to said one processing unit, for detecting said one processing unit as a processing unit which has cached said requested data line, based upon said directory information stored in said storage location for said data line, and requesting said one processing unit to transfer said data line which has been transferred thereto from a cache memory of said one processing unit to said another processing unit,

wherein said directory information generation circuit further generates renewed directory information of said directory information generated for said storage location and stored therein by said write circuit, when said data line is requested by another data read request and has been transferred from said one processing unit to said another processing unit by said data transfer request circuit,

said renewed directory information for said storage location indicating said one processing unit and said another processing unit as having cached said data line held in said storage location,

wherein said write circuit further rewrites said directory information written into said storage location by said write circuit by said renewed directory information.

23. The computer system according to claim 22, wherein said main memory access control circuit further includes:

a write back control circuit responsive to replacing of said data line by one of said plurality of processing units, for detecting whether or not said data line is cached in any of said plurality of processing units and writing back said replaced data line into said storage location of said main memory in place of said directory information stored therein when there is no processing unit which has cached said data line and not writing back said replaced data line when there is one processing unit which has cached said data line.

24. A computer system, including:

a plurality of processing units; and

a network for connecting said plurality of processing units for transfer of plural data therebetween;

wherein each processing unit includes:

a processor,

one of a plurality of partial main memories which are distributed in said plurality of processing units and realizes a main memory shared by said plurality of processing units;

a partial main memory access control circuit which controls accesses to said one partial main memory, and

a cache memory which holds a part of data held in said one partial main memory;

wherein said partial main memory control circuit includes:

a partial main memory access control circuit which responds to data read requests and data write requests provided by said plurality of processing units and accesses said main memory, and

a directory information generation circuit which responds to operations of said partial main memory access control circuit and generates either one of directory information for each storage location of said partial main memory and renewed directory information of directory information generated by said directory generation circuit for said each storage location, said directory information for each storage location indicating each of every at least one of a plurality of processing units which has cached a data line held in said each storage location;

wherein said partial main memory access control circuit includes:

an access circuit responsive to a data read request provided by one of said plurality of processing units, for reading a data line requested by said read request from a storage location for said data line within said partial main memory when there is no processing unit which has already cached said data line, and transferring said read data line to said one processing unit,

a write circuit responsive to said transferring of said data line for writing directory information generated by said directory generation circuit for said data line into said storage location for said data line in place of said data line, and

a data transfer request circuit responsive to another data read request given by another of said plurality of processing units for said data line after said data line has been transferred to said one processing unit, for detecting said one processing unit as a processing unit which has cached said requested data line, based upon said directory information stored in said storage location for said data line, and requesting said one processing unit to transfer said data line which has been transferred thereto from a cache memory of said one processing unit to said another processing unit,

wherein said directory information generation circuit further generates renewed directory information of said directory information generated for said storage location and stored therein by said write circuit, when said data line is requested by another data read request and has been transferred from said one processing unit to said another processing unit by said data transfer request circuit,

said renewed directory information for said storage location indicating said one processing unit and said another processing unit as having cached said data line held in said storage location,

wherein said write circuit further rewrites said directory information written into said storage location by said write circuit by said renewed directory information.

25. The computer system according to claim 24, wherein said partial main memory access control circuit further includes:

a write back control circuit responsive to replacing of said data line by one of said plurality of processing units, detecting whether or not said data line is cached in any of said plurality of processing units, and writing back said replaced data line into said storage location of said partial main memory in place of said directory information stored therein when there is no processing unit which has cached said data line and not writing back said replaced data line when there is one processing unit which has cached said data line.

BACKGROUND OF THE INVENTION

The present invention relates to an access request control scheme for a main memory shared by a multiprocessor system incorporating a plurality of processing units by using directory information indicating which processing unit holds specific data in an address of the main memory. More specifically, the present invention relates to a main memory access control scheme suitable for a parallel computer system with a distributed main memory for the processing units connected through a network capable of performing parallel data transfer.

In a parallel computer system, there is a well-known architecture having a main memory shared by a plurality of processing units (referred to as PUs herein), wherein each processing unit being provided for a cache.

In particular, the Japanese Laid-Open Patent Application No. 5-89056 (referred to as "reference #1" herein), "The Stanford dash Multiprocessor," IEEE Computer, March 1992, pp. 63-79 (referred to as "reference #2" herein) and the like have proposed a parallel computer system having physically distributed and logically shared (distributed shared) memory system for this type of parallel processor.

In these parallel computers, a main memory is distributed for each PU, and each PU is coupled with a network, such as multistage interconnection network, for transferring a plurality of data in parallel in order to provide a network throughput suitable to the number of PU's and in order to avoid the limit of the connectable number of PU's.

The main memory controller of the distributed shared memory scheme of the parallel computer of the Prior Art has been connected to, as documented in the reference #2, each data line of the main memory for each respective PU, and the directory structure indicating for which PU a data line is cached (which PU has a copy of that data line in its own cache) is stored in a dedicated memory for this specific purpose and is separate from the main memory.

When a command for maintaining the cache coherency is required to be sent, when shared data has been modified, the command is first sent to the main memory. Then, the main memory controller sends the command to a PU that is indicated by a directory associated with the main memory. At the same time, the contents of the directory are updated. When a PU writes to data, an invalidation command is sent to all of other #PU's indicated by the directory for that data. Then all copies cached in these PU's are erased. When a PU reads cached data, the read command is sent to one of the PU's indicated by the directory so that the cached data is provided from the cache of that PU to the PU requesting the read command.

By managing the caches by means of a directory structure, a command to maintain the cache coherency is sent only to the PU caching the appropriate data line. As the command is not sent to other PU's, the broadcasting to all PU's is not necessary. Thus, the management of the cache coherency of the main memory data distributed to each network-connected PU's may be efficiently performed.

In the reference #2, the directory for each data line is indicated by a so-called bitmap, having one bit indicating whether or not a data line is cached for each PU.

Another scheme has also been proposed, in which the number of PU's actually caching a data line is stored as directory, instead of bitmap. See, for example, "Directory-based Cache Coherence in Large-Scale Multiprocessors," IEEE Computer, 1990 June, pp. 49-58 (referred to as "reference #3" herein). The technique mentioned in this reference is called "limited pointer" scheme (or simply, pointer scheme), in which the PU number stored as directory is limited to a given number, such as eight.

Another scheme has been further proposed, in which the stored PU number, using this pointer scheme, is held in a location in the main memory other than the locations of data lines. See, for example, "The Stanford FLASH Multiprocessor," Proc. of the 21st Annual International Symposium on Computer Architecture, 1994 Apr. 18-21, pp. 302-313 (referred to as "reference #4" herein).

Since the prior art reference #2 requires to hold, for each line of main memory, a directory indicating which PU caches which line in a memory, there is a disadvantage of having a large amount of memory for the directory. In the example of 16 PU's of the Prior Art mentioned above, given that the system has 16 PU's and that a machine is 1 word=8 bytes, 1 line=4 word and a directory of 16 bits is needed for one line of cache (4.times.8.times.8=256 bits), the amount of directory becomes 1/16 of the size of the main memory, and the cost of hardware requirement is high. Thus, the more the PU's the computer system has, the more the directory cost increases. For example, if a machine of 256 PU's holds directories as bitmap pattern mentioned above, a directory of 256 bits is required for one cache line. This amount will correspond to that of main memory.

The pointer scheme mentioned in the reference #3 requires a less amount of dedicated memory for directories than that of the bitmap style directory. However, the amount may not be negligible for a line size since a plurality of pointers must be held.

Another pointer scheme mentioned in the reference #4 uses main memory as the storage of directories to eliminate the requirement of dedicated memory. However, this scheme has a problem in that the memory space for data storage may be decreased, since the amount of main memory used for the storage of directories cannot be neglected.

As set forth above, if the distributed shared memory is implemented by using the directory scheme of the Prior Art, the cost of hardware requirement will significantly increase, because the amount of memory used for the storage of directories becomes large when compared with the amount of main memory for data storage.

SUMMARY OF THE INVENTION

Thus, one object of the present invention is to provide the realization of a distributed shared memory of the directory scheme, without the need to increase the amount of memory for the storage of directory structure.

In order to achieve the object, in one preferable aspect of the present invention, status information indicating whether or not the data line of the main memory of each processing unit is cached in one of the processing units is provided in correspondence with each data line of the main memory. The status information is changed to a cached state if that data line is cached in one of the processing units, and directory information indicating which processing unit has cached the data line is stored into the location in the main memory instead of that data line. If the combination of the processing units caching the data line is changed, then the directory information will be updated to indicate the new combination of the processing units caching the data line.

However, if the data line is not cached in any one of the processing units, the cached data line is written back to the main memory instead of directory information. Thus, when the cached data line is replaced because of a shortage of free space of the cache or is purged from the cache by an explicit command from its processor, the cached data line and its address in the cache are sent to the main memory. The directory corresponding to the data line stored in the main memory is read out, and by examin