Technique for parallel synchronization

• US 4,989,131 A
• Filed: 07/26/1988
• Issued: 01/29/1991
• Est. Priority Date: 07/26/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Stone, Harold S.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US07/224,846
• Time in Patent Office: 917 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 712/203
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A parallel synchronization technique utilizing a combining network in which two processors synchronize by having one processor suspend operation while the other processor becomes the agent for the one processor, while continuing to operate on its own behalf. This reduces the access requests and subsequent contention caused by multiple concurrent requests to a common variable.

Claims

1. A computing system comprising:

a plurality of data processors, each of which includes means for issuing a synch instruction for purposes of synchronizing certain ones of said processors that are issuing a same synch instruction for indicating that a common variable is to be processed;

a plurality of synchronizers, each of which has two inputs for receiving first and second synch instructions, respectively, from a first processor and from a second processor, respectively, of said plurality of data processors, each of said synchronizers including means for comparing the synch instructions received at the two inputs to determine equality of same, each of said synchronizers further including means, responsive to said comparing means determining that the first and the second synch instructions are equal, for signalling said first processor to continue processing said common variable for itself and for said second processor, and further including means, responsive to said comparing means determining that the first and the second synch instructions are equal, for signalling said second processor to suspend processing said common variable; and

means for said first processor to inform said second processor of the results of the processing of said common variable for said second processor.

2. In a data processing system, the combination comprising:

n, where n is an integer, data processors, each of which includes means for issuing a synch instruction for synchronizing certain ones of said n data processors that are issuing the same synch instruction, said synch instruction including a synch address indicative of the destination of said synch instruction, and an operand address indicative of the address of a common variable;

n synchronizers, each of which has two inputs identified by first and second synch addresses, respectively, for receiving said synch instruction from a first processor and from a second processor, respectively, of said n data processors, each of said n synchronizers including means for comparing the respective operand address of the synch instructions received at the two inputs to determine if the operand addresses are identical, each of said n synchronizers further including means, responsive to said comparing means determining that the operand addresses are identical, for synchronizing said first and second processors, said synchronizing means comprising means for providing a first signal to instruct said first processor to continue processing operations relative to said common variable and to act as agent for said second processor in processing operations relative to said common variable, and means for providing a second signal to instruct said second processor to suspend processing operations relative to said common variable;

means for said first processor to inform said second processor of the result of the processing of said common variable for said second processor, and

an interconnection network which provides a plurality of data communication paths between said n data processors and said n synchronizers for selectively communicating said synch instructions from said n data processors to said n synchronizers, and for selectively communicating said first and second signals from said synchronizer to said first and second processors, respectively.

3. In a data processing system, the combination comprising:

n, where n is an integer, data processors, each of which includes means for issuing a synch instruction for synchronizing certain ones of said n data processors that are issuing the same synch instruction, said synch instruction including a synch address indicative of the destination of said synch instruction, and an operand address indicative of the address of a common variable;

synchronizing means for receiving said synch instruction from each said n data processors, said synchronizing means including means for comparing the respective operand address of the synch instructions from each of said n data processors to determine if the operand addresses are identical, said synchronizing means including means, responsive to said comparing means determining that at least two of the operand addresses are identical, for synchronizing the ones of said n data processors that have identical synch addresses, including means for providing a first signal to instruct a first one of the synchronized processors that have identical synch addresses to continue processing operations relative to said common variable for itself and to act as agent for the other ones of the synchronized processors that have identical synch addresses in processing operations relative to said common variable, and including means for providing a second signal to instruct the other ones of the synchronized processors that have identical synch addresses to suspend processing operations relative to said common variable;

means for said first one of the synchronized processors to individually inform each of the other ones of the synchronized processors of the results of processing said common variable for it; and

an interconnection network which provides a plurality of data communication paths between said n data processors and said synchronizing means for selectively communicating said synch instructions from said n data processors to said synchronizing means, and for selectively communicating said first and second signals from said synchronizing means to said first one of the synchronized processors and the other ones of said synchronized processors, respectively.

4. A computing system comprising:

a plurality of data processors, each of which includes means for issuing a synch instruction for purposes of synchronizing certain ones of said processors that are issuing the same synch instruction for processing a common variable;

a crossbar switch having a plurality of switch points, with each such switch point including means for storing a synch instruction from a first processor of said plurality of data processors;

a plurality of arbiters, with one such arbiter at each switch point of said crossbar switch for arbitrating between the synch instruction from said first processor stored at the switch point and synch instructions from at least second and third processors of said plurality of data processors;

means for comparing the synch instruction of said first processor stored at said switch point with the synch instructions of said second and third processors, under the control of said arbiter, including means for providing a first arbitration request to said arbiter if the synch instructions from the first and second processors are the same, and for providing a second arbitration request to said arbiter if the synch instructions from said first processor and said third processor are the same, with said arbiter including means for assigning one of said first, second and third processors as the agent for one of the other two processors for processing said common variable for itself and for said one of the other two processors, including means for signalling said one of the other two processors to suspend processing said common variable; and

means for the assigned one of said first, second and third processors to inform said one of the other two processors of the result of processing said common variable for said one of the other two processors.

5. A computing system comprising:

a plurality of processors each of which issues requests including synch instructions for synchronizing certain ones of the processors that are issuing the same synch instruction for processing a common variable;

at least one crossbar switch having a plurality of switch points, with each such switch point including means for storing a synch instruction from a processor;

a plurality of arbiters, with one such arbiter being associated with each switch point for arbitrating between synch instructions from selected ones of said plurality of processors;

means for a given arbiter selecting a request from a first processor and determining if the request is a synch instruction;

means for storing the synch instruction from said first processor at the switch point associated with said given arbiter;

means for comparing the synch instruction of a second processor with the synch instruction of said first processor stored at the switch point associated with said given arbiter, and if the synch instructions are identical including means for signalling said given arbiter that the comparison is identical;

means for instructing the first processor to act as agent for the second processor in processing the common variable identified in the synch instruction;

means for instructing the second processor to suspend processing said common variable and become a client of said first processor during the time said first processor is acting as its agent; and

means for said first processor to inform said second processor of the results of the processing of said common variable for said second processor.

6. The combination claimed in claim 5, wherein said at least one crossbar switch comprises a multilevel switch comprised of n, where n is an integer, levels of crossbar switches.

7. The combination claimed in claim 6, wherein said plurality of arbiters are situated at the nth level of said multilevel switch.

8. The combination claimed in claim 6, wherein said plurality of arbiters are situated at a level other than the nth level of said multilevel switch.

9. A computing system comprising:

a plurality of processors each of which issue a synch request and a synch instruction for synchronizing certain ones off the processors that are issuing the same synch instruction for processing a common variable;

at least one crossbar switch having a plurality of switch points, with each such switch point including means for storing a synch instruction from a processor;

a plurality of arbiters, with one such arbiter being associated with each switch point for arbitrating between synch requests from at least two of said plurality of processors;

means for storing the synch instruction from a first processor at the switch point associated with a given arbiter;

a comparator for comparing the synch instruction from said first processor stored at the switch point associated with said given arbiter, with the synch instruction issued from a second processor, and providing an identity signal if the respective synch instructions are the same;

means responsive to the identity signal from said comparator and a synch request from said second processor to provide an arbitration request signal to said arbiter;

means included in said given arbiter and responsive to said arbitration request signal for designating one of said first and second processors as an agent and the other of said first and second processors as a client, with the agent processor processing the common variable identified in the synch instruction for itself and the client, with the client suspending processing said common variable; and

means for said agent processor to inform the client processor of the result of processing said common variable for said agent processor.

10. The combination claimed in claim 9, wherein said at least one crossbar switch comprises a multilevel switch comprised of n, where n is an integer, levels of crossbar switches.

11. The combination claimed in claim 10, wherein said plurality of arbiters are situated at the nth level of said multilevel switch.

12. The combination claimed in claim 10, wherein said plurality of arbiters are situation at a level other than the nth level of said multilevel switch.

13. A method of synchronizing processes in a computing system, said method comprising the steps of:

issuing a synch instruction by each of a plurality of processors for purposes of synchronizing processors that issue a same synch instruction for indicating that a common variable is to be processed;

receiving said synch instructions by a plurality of synchronizers, each synchronizer having two inputs for receiving first and second synch instructions, respectively, from a first processor and from a second processor, respectively, of said plurality of processors;

comparing the synch instructions received at the two inputs to determine if they are the same, and if determined to be the same further executing the steps of;

signalling said first processor to continue processing said common variable, and to act as agent for said second processor in processing said common variable;

signalling said second processor to suspend processing said common variable during the time said first processor acts as its agent; and

informing said second processor by said first processor of the result of the processing of said common variable for said second processor.

14. A method of synchronizing processors in a data processing system, said method comprising the steps of:

issuing synch instructions, including a synch address indicative of the destination of said synch instruction, and an operand address indication of the address of a common variable, by each of n, where n is an integer, data processors for synchronizing processors that have the same operand address;

receiving said synch instructions with a synchronizer;

comparing the respective operand addresses of the received synch instructions with said synchronizer to determine if the operand addresses are identical, and if at least two of the operand addresses are determined to be identical;

synchronizing the ones of said n data processors that have identical operand addresses in their respective synch instructions;

providing a first signal to instruct a first one of the synchronized data processors to continue processing operations relative to said common variable and to act as agent for the other ones of the synchronized data processors in processing operations relative to said common variable;

providing a second signal to instruct the other ones of the synchronized data processors to suspend processing operations relative to said common variable as long as said first one of the synchronized data processors is acting as agent; and

informing said other ones of the synchronized data processors by said first one of the synchronized data processors of the result of the processing of the common variable for said other ones of the synchronized data processors.

15. A method of synchronizing processors in a computing system which includes a plurality of processors each of which issues requests including synch instructions for synchronizing certain ones of the processors for processing a common variable;

at least one crossbar switch having a plurality of switch points, with each such switch point being capable of storing a synch instruction from a processor, and a plurality of arbiters, with one such arbiter being associated with each switch point for arbitrating between synch instructions, said method comprising the steps of;

selecting an active request from a first processor by a first arbiter and determining if it is a synch instruction, and if so;

storing the synch instruction from said first processor at the switch point associated with said first arbiter;

comparing the synch instruction of a second processor with the synch instruction stored at the switch point associated with said first arbiter, and if the same;

instructing the first processor to act as agent for the second processor in processing the common variable identified in the synch instruction;

instructing the second processor to suspend processing said common variable as long as said first processor is acting as its agent; and

informing said second processor by said first processor of the result of processing said common variable for said second processor.

16. A method of synchronizing processors in a computing system which includes a plurality of processors each of which issues a synch request and a synch instruction for synchronizing certain ones of the processors for processing a common variable;

at least one crossbar switch in a multilevel switch having a plurality of switch points, with each such switch point being capable of storing a sync instruction from a processor; and

a plurality of arbiters, with one such arbiter being associated with each switch point for arbitrating between synch instructions, said method comprising the steps of;

selecting an active request from a first processor by a first arbiter and determining if it is a synch instruction, and if so;

storing the synch instruction from said first processor at the switch point associated with said first arbiter;

comparing the synch instruction of a second processor with the synch instruction stored at the switch point associated with said first arbiter, and if the same;

responding to a synch request by said second processor by said first arbiter to designate one of said first and second processors as an agent and the other as a client, with the agent processor processing the common variable identified in the synch instruction for itself and the client;

instructing said client processor to suspend processing said common variable; and

informing said client processor by said agent processor of the result of processing said common variable for said agent processor.