Determination of branch convergence in a sequence of program instruction

Abstract

A method of compiling a sequence of program instructions, a method of parallel execution of a sequence of program instructions and apparatuses and software supporting such methods are disclosed. The sequence of program instructions is analyzed in terms of basic blocks forming a control flow graph and execution paths through that control flow graph are identified. When more than one execution path leads to a given basic block, or when a loop path is found leading from a given basic block back to the same basic block, a potential convergence point may be identified. A convergence marker is added to the computer program associated with the basic blocks identified in this way and then when the program is executed, the convergence markers found are used to trigger a determination of a subset of the multiple execution threads which are executed following that convergence marker.

We claim: 
     
       1. A method of parallel execution of a computer program using multiple execution threads, wherein the computer program comprises a sequence of program instructions, the method comprising:
 identifying basic blocks of program instructions, wherein each basic block has only one entry point and only one exit point; 
 determining at least one execution path which leads to each basic block; 
 when more than one execution path leads to a selected basic block, adding a convergence marker to the computer program associated with the selected basic block; 
 when a loop path exists from a further selected basic block to the further selected basic block, adding the convergence marker to the computer program associated with each exit basic block for the loop path; and 
 executing the multiple execution threads, wherein executing the multiple execution threads comprises: 
 when a first subset of the multiple execution threads takes a first execution path from a divergent basic block and a second subset of the multiple execution threads takes a second execution path from the divergent basic block, causing the second subset to wait; and 
 when the convergence marker is encountered selecting at least one thread of the multiple execution threads for execution in accordance with predetermined parallel execution rules. 
 
     
     
       2. The method as claimed in  claim 1 , wherein selecting the at least one thread of the multiple execution threads for execution in accordance with the predetermined parallel execution rules comprises selecting a group of threads for which a next instruction to be executed is earliest in program counter order. 
     
     
       3. Apparatus for parallel execution of a computer program, wherein the apparatus has a configuration to carry out the method of  claim 1 . 
     
     
       4. The apparatus as defined in  claim 3 , wherein the apparatus is a graphics processing unit. 
     
     
       5. A computer readable storage medium storing in a non-transient fashion a computer program which when executed on a computer causes the computer to carry out the method of  claim 1 .