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 branch operations 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;
• updating the lane-PC value of each of the active lanes according to targets of the branch operation;
• and
• selecting at least one active lane from of the plurality of lanes based on the lane depth counter value of the active lane, and assigning a corresponding lane-PC value of the selected at least one active lane to the thread-PC, and activating only lanes of the plurality of lanes whose lane-PC values are equal toes the thread-PC value.

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 non-transitory 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 branch operations 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;
• updating the lane-PC value of each of the active lanes according to targets of the branch operation;
• and
• selecting at least one active lane from the plurality of lanes based on the lane depth counter value of the active lane, and assigning a corresponding lane-PC value of the selected at least one active lane to the thread-PC, and activating only lanes of the plurality of lanes whose lane-PC values are equal to the thread-PC value.