Technique for parallel synchronization

Claim 2

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.

Claim 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; 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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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

Claim 18

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.