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 after reading data to a processor

• US 5,606,686 A
• Filed: 10/24/1994
• Issued: 02/25/1997
• Est. Priority Date: 10/22/1993
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Fujii, Hiroaki, Tarui, Toshiaki, Sukegawa, Naonobu, Kitai, Katsuyoshi
• Primary Examiner(s): Kim, Matthew M.
• Application Number:
  US08/328,759
• Time in Patent Office: 855 Days
• Field of Search: 395/449, 395/470, 395/403, 395/445, 395/446, 395/447, 395/448, 395/457, 395/468, 395/469, 395/471, 395/472, 395/473, 395/483, 395/415, 395/417, 395/200.03 , 395/200.1, 395/200.11, 395/200.13
• US Class Current: 711/121
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 15/17393 having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture

Abstract

A main memory shared by plural processing units in a parallel computer system is composed of plural partial main memories. A directory for each data line of the main memory is generated after the data line has been cached in one of the processing units. The directory is held in one of the partial main memories in place of the data line. The directory indicates a processing unit which has cached the data line. A status bit C provided for the data line is set. If a subsequent read request is given to the data line, the status C bit is checked and the directory is used to identify a processing unit that has cached the data line. The request is transferred to the identified processing unit, and the data line is transferred from that processing unit to the processing unit that has issued the request. If a processing unit that has cached the data line has replaced the data line, it is checked if there is a processing unit that has cached the data line. If there is none, the data line is written back into the one partial main memory. If there is, the data line is not written back. Another status bit RO is also used for each data line. It indicates if the data line is read only. If a data line is read only, generation of the directory and storing it in the partial main memory is prohibited.

Claims

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.