Method and apparatus for synchronizing parallel processors using a fuzzy barrier

Claim 2

A parallel processing system comprising: a. a plurality of parallel processors; and b. means for synchronizing the processors so that at least one of the processors executes at least one non-idling instruction while awaiting synchronization with at least one other processor.

Claim 5

The apparatus of Claim 2 wherein: a. the communicating means comprises: i. input means means for receiving a received indication from other processors that the other processors want to synchronize; and ii. output means means for sending a sent indication to the other processors that the respective processor wants to synchronize; b. the controlling means comprises: i. means for identifying shaded and unshaded regions in a respective one of the instruction streams; and ii. means for controlling execution of the respective one of the instruction streams, in response to the identification of the shaded and unshaded regions and in response to the received indication, so that the respective processor does not execute a respective instruction immediately after a current shaded region until the other processors have completed all respective instructions immediately preceding their respective current shaded regions, the controlling means being coupled to the input and output means.

Claim 6

The apparatus of Claim 2 further comprising means for ignoring a second at least one of the other processors, according to a number of parallel instruction streams.

Claim 7

The apparatus of Claim 4 wherein the ignoring means comprises a mask register.

Claim 8

The apparatus of Claim 2 further comprising means for ignoring at least two of the parallel processors, according to a number of parallel instruction streams, so that the least two processors synchronize independently.

Claim 9

The apparatus of Claim 3 wherein the controlling exeuction means is a state machine.

Claim 10

The apparatus of Claim 7 wherein the state machine comprises: a. a want input, coupled to the input means of the apparatus, for receiving the received indication; b. a second input for receiving a signal identifying the shaded and unshaded regions; c. a first output, coupled to the output means of the apparatus, for supplying the sent indication; d. a stall output, coupled to control execution of the respective processor, for supplying a signal for stopping execution of the respective processor in a stall state and for otherwise enabling the respective processor.

Claim 11

The apparatus of Claim 8 wherein the state machine has four states: a. a first state during which the processor executes instructions in the unshaded region; b. a second state during which the processor executes instructions in the shaded region while waiting for other processors to reach their respective shaded regions; c. a third state during which the processor executes instructions in the shaded region when the other processors have reached their respective shaded regions; and d. a fourth state during which the processor stalls, having reached an end of the shaded region and waits for the other processors to reach their respective shaded regions.

Claim 12

The apparatus of Claim 3 further comprising a mask register for ignoring at least one of the other processors, according to a number of parallel instruction streams; and wherein the execution controlling means is a state machine which comprises: a. a want input, coupled to the input means of the apparatus, for receiving the received indication; b. a second input for receiving a signal identifying the shaded and unshaded regions; c. a first output, coupled to the output means of the apparatus, for supplying the sent indication; d. a stall output, coupled to control execution of the respective processor, for supplying a signal for stopping execution of the respective processor in a stall state and for otherwise enabling the respective processor.

Claim 15

The method of Claim 11 further comprising the steps of: a. generating intermediate code from the portions; and b. converting the intermediate code to assembly language.

Claim 16

The method of Claim 11 further comprising the step of reordering code within the portions so that the unshaded regions are reduced in size.

Claim 17

The method of Claim 11 wherein the second identifying step comprises the steps of: a. first locating a first instruction with a lexically forward or loop carried dependence in the at least one of the portions; b. second locating a last instruction with a lexically forward or loop carried dependence in the at least one of the portions; c. designating as unshaded all instructions between the first and last instructions with dependences; and d. designating as shaded all other instructions in the portions.

Claim 20

The method of Claim 15 comprising the further steps of a. generating intermediate code from the portions; and b. converting the intermediate code to assembly language.