US 5,434,995 A · Barrier synchronization for distributed memory massively parallel processing systems

Abstract

A barrier mechanism provides a low-latency method of synchronizing all or some of the processing elements (PEs) in a massively parallel processing system. The barrier mechanism is supported by several physical barrier synchronization circuits, each receiving an input from every PE in the processing system. Each PE has two associated barrier synchronization registers, in which each bit is used as an input to one of several logical barrier synchronization circuits. The hardware supports both a conventional barrier function and an alternative eureka function. Each bit in each of the barrier synchronization registers can be programmed to perform as either barrier or eureka function, and all bits of the registers and each barrier synchronization circuit functions independently. Partitioning among PEs is accomplished by a barrier mask and interrupt register which enables certain of the bits in the barrier synchronization registers to a defined group of PEs. Further partitioning is accomplished by providing bypass points in the physical barrier synchronization circuits to subdivide the physical barrier synchronization circuits into several types of PE barrier partitions of varying size and shape. The barrier mask and interrupt register and the bypass points are used in concert to accomplish flexible and scalable partitions corresponding to user-desired sizes and shapes with a latency several orders of magnitude faster than existing software implementations.

Claims10

Dependent claims

A system for processor barrier synchronization of a plurality of processing elements (PEs) in a distributed processing computer, comprising:

a barrier detection program means operative in each PE to determine when each individual PE has reached a processor barrier;
a plurality of boolean DONE outputs from each PE, each output controlled by the barrier detection program means, indicating when a processor barrier was reached by that PE;
a plurality of processor barrier synchronization circuits for detecting which PEs have reached a processor barrier, comprising:
a plurality of boolean logical AND gates connected to corresponding DONE outputs of the plurality of PEs to indicate when all of the PEs reach a processor barrier;
an ALLDONE signal output from the plurality of AND gates for providing an output indicating that all of the PEs have reached a particular processor barrier;
and
a plurality of logical fanout devices, with inputs connected to the ALLDONE signal line and outputs connected to the multiplicity of PEs to indicate to every PE in the system that the particular processor barrier was reached;
and
a plurality of barrier synchronization registers (BSRs) for storing the status of each barrier synchronization process.

6 more elements

A computer system comprising:

a plurality of processing elements (PEs) including a first processing element (PE), wherein said first PE comprises:
a barrier synchronization register one (BSR1), said BSR1 including a first BSR bit and a second BSR bit, wherein said first BSR bit and said second BSR bit are set when said first PE reaches a first barrier point and a second barrier point, respectively;
a first BSR output;
and
a coupler which couples a value representative of said first BSR bit to said first BSR output;
and
a barrier synchronization mechanism (BSM) having a first physical barrier synchronization circuit (PBSC), wherein said PBSC comprises a plurality of bypass points including a first bypass point and a second bypass point, wherein each of said bypass points comprise:
a fanin gate having a plurality of fanin inputs and a fanin output, wherein said fanin output generates an indication of whether said fanin inputs are all set;
a fanout circuit having a fanout input and a fanout output;
and
a bypass switch for switchably coupling said fanin output to said fanout input;
wherein one of the fanin inputs of said first bypass point is coupled to said first BSR output, wherein one of the fanin inputs of said second bypass point is coupled to the fanin output of said first bypass point, wherein the fanout input of said second bypass point is coupled to the fanin output of said second bypass point, wherein the fanout input of said first bypass point is coupled to the fanout output of said second bypass point, and wherein the fanout output of said first bypass point is coupled to said first PE.

9 more elements

Dependencies are inferred from the claim text.

Barrier synchronization for distributed memory massively parallel processing systems

Life of this patent

Barrier synchronization for distributed memory massively parallel processing systems

Life of this patent

Abstract

Claims10