Optimize control-flow convergence on simd engine using divergence depth

A system for selecting an active data stream while running a SPMD (Single Program Multiple Data) program of instructions on a SIMD (Single Instruction Multiple Data) machine, an instruction stream having one thread-PC (Program Counter), a value of the thread-PC indicating an instruction memory address which stores an instruction to be fetched next for the instruction stream, the system comprising:

• a plurality of processors;
• a memory device coupled to the plurality of processors,
• wherein the plurality of processors are configured to perform:
• running the instruction stream over a plurality of input data streams each of which corresponds to each of a plurality of lanes, each of the plurality of lanes being associated with a corresponding lane depth counter indicating a number of nested branches for each corresponding lane, a corresponding lane-PC of a lane of the plurality of lanes indicating a memory address which stores the instruction to be fetched next for the lane when the lane is activated, and a lane activation bit indicating whether the lane is active or not;
• incrementing values of the lane depth counters of all active lanes of the plurality of lanes upon the thread-PC value reaching a branch operation in the instruction stream;
• and
• updating the lane-PC value of each of the active lanes according to targets of the branch operation,
• wherein an instruction of said instruction stream comprises a barrier indicating a convergence point for all lanes to join, the plurality of processors being configured to further perform determining a lane reaching a barrier instruction;
• and
• in response to the plurality of processors determining a lane reaching a barrier instruction:
• evaluating whether lane-PCs of all the lanes are set to a same thread-PC;
• and
• if the lane-PCs of all the lanes are not set to the same thread-PC,
• selecting an active lane from the plurality of lanes;
• otherwise, if the lane-PCs of all the lanes are set to the same thread-PC, incrementing the lane-PCs of all the lanes, and then selecting an active lane from the plurality of lanes.

A computer program product for selecting an active data stream while running a SPMD (Single Program Multiple Data) program of instructions on a SIMD (Single Instruction Multiple Data) machine, an instruction stream having one thread-PC (Program Counter), a value of the thread-PC indicating an instruction memory address which stores an instruction to be fetched next for the instruction stream, the computer program product comprising a computer readable storage medium readable by a machine and storing instructions run by the machine to perform a method, said method steps comprising:

• running the instruction stream over a plurality of input data streams each of which corresponds to each of a plurality of lanes, each of the plurality of lanes being associated with a corresponding lane depth counter indicating a number of nested branches for each corresponding lane, a corresponding lane-PC of a lane of the plurality of lanes indicating a memory address which stores the instruction to be fetched next for the lane when the lane is activated, and a lane activation bit indicating whether the lane is active or not;
• incrementing values of the lane depth counters of all active lanes of the plurality of lanes upon the thread-PC value reaching a branch operation in the instruction stream;
• and
• updating the lane-PC value of each of the active lanes according to targets of the branch operation,
• wherein an instruction of said instruction stream comprises a barrier indicating a convergence point for all lanes to join, the SIMD machine being configured to further perform determining a lane reaching a barrier instruction;
• and
• in response to the SIMD machine determining a lane reaching a barrier instruction:
• evaluating whether lane-PCs of all the lanes are set to a same thread-PC;
• and
• if the lane-PCs of all the lanes are not set to the same thread-PC,
• selecting an active lane from the plurality of lanes;
• otherwise, if the lane-PCs of all the lanes are set to the same thread-PC, incrementing the lane-PCs of all the lanes, and then selecting an active lane from the plurality of lanes.