Control-quasi-independent-points guided speculative multithreading

Abstract

A method for generating instructions to facilitate control-quasi-independent-point multithreading is provided. A spawn point and control-quasi-independent-point are determined. An instruction stream is generated to partition a program so that portions of the program are parallelized by speculative threads. A method of performing control-quasi-independent-point guided speculative multithreading includes spawning a speculative thread when the spawn point is encountered. An embodiment of the method further includes performing speculative precomputation to determine a live-in value for the speculative thread.

What is claimed is:  
     
         1 . A method of compiling a software program, comprising: 
 selecting a spawning pair that includes a spawn point and a control-quasi-independent point (CQIP);    providing for calculation of a live-in value for a speculative thread; and    generating an enhanced binary file that includes instructions, the instructions including a trigger instruction to cause spawning of the speculative thread at the CQIP.    
     
     
         2 . The method of  claim 1 , further comprising: 
 performing profile analysis.    
     
     
         3 . The method of  claim 1 , further comprising: 
 computing a plurality of reaching probabilities.    
     
     
         4 . The method of  claim 1 , further comprising: 
 identifying a plurality of candidate basic blocks.    
     
     
         5 . The method of  claim 4 , wherein: 
 selecting a spawning pair further comprises selecting the spawning pair from the plurality of candidate basic blocks.    
     
     
         6 . The method of  claim 1 , wherein: 
 generating the enhanced binary file further comprises embedding a trigger at a spawn point associated with the spawning pair.    
     
     
         7 . The method of  claim 1 , wherein selecting the spawning pair further comprises: 
 selecting a spawning pair having at least a minimum average number of instructions between the spawn point and the CQIP of the spawning pair.    
     
     
         8 . The method of  claim 3 , wherein selecting the spawning pair further comprises: 
 selecting a spawning pair having at least a minimum reaching probability.    
     
     
         9 . The method of  claim 1 , wherein providing for calculation of the live-in value further comprises: 
 providing an instruction to invoke hardware prediction of the live-in value.    
     
     
         10 . The method of  claim 1 , wherein providing for calculation of the live-in value further comprises: 
 generating one or more instructions to perform speculative precomputation of the live-in values.    
     
     
         11 . The method of  claim 1 , wherein: 
 selecting a spawning pair further comprises selecting a first spawning pair and a second spawning pair; and    generating an enhanced binary file that includes instructions further comprises generating an enhanced binary file that includes a trigger instruction for each spawning pair.    
     
     
         12 . An article comprising: 
 a machine-readable storage medium having a plurality of machine accessible instructions;    wherein, when the instructions are executed by a processor, the instructions provide for 
 selecting a spawning pair that includes a spawn point and a control-quasi-independent point (CQIP);  
 providing for calculation of a live-in value for a speculative thread; and  
 generating an enhanced binary file that includes instructions, the instructions including a trigger instruction to cause spawning of a speculative thread at the control-quasi-independent.  
   
     
     
         13 . The article of  claim 12 , wherein the instructions further comprise: 
 instructions that provide for performing profile analysis.    
     
     
         14 . The article of  claim 12 , wherein the instructions further comprise: 
 instructions that provide for computing a plurality of reaching probabilities.    
     
     
         15 . The article of  claim 12 , wherein the instruction further comprise: 
 instructions that provide for identifying a plurality of candidate basic blocks.    
     
     
         16 . The article of  claim 15 , wherein: 
 the instructions that provide for selecting a spawning pair further comprise instructions that provide for selecting the spawning pair from the plurality of candidate basic blocks.    
     
     
         17 . The article of  claim 12 , wherein: 
 the instructions that provide for generating the enhanced binary file further comprise instructions that provide for embedding a trigger at a spawn point associated with the spawning pair.    
     
     
         18 . The article of  claim 12 , wherein the instructions that provide for selecting the spawning pair further comprise: 
 instructions that provide for selecting a spawning pair having at least a minimum average number of instructions between the spawn point and the CQIP of the spawning pair.    
     
     
         19 . The article of  claim 14 , wherein the instructions that provide for selecting the spawning pair further comprise: 
 instructions that provide for selecting a spawning pair having at least a minimum reaching probability.    
     
     
         20 . The article of  claim 12 , wherein the instructions that provide for providing for calculation of the live-in value further comprise: 
 instructions that provide for providing an instruction to invoke hardware prediction of the live-in value.    
     
     
         21 . The article of  claim 12 , wherein instructions that provide for providing for calculation of the live-in value further comprise: 
 instructions that provide for generating one or more instructions to perform speculative precomputation of the live-in values.    
     
     
         22 . A method, comprising: 
 executing one or more instructions in a first instruction stream in a non-speculative thread;    spawning a speculative thread at a spawn point in the first instruction stream, wherein the computed probability of reaching a control quasi-independent point during execution of the first instruction stream, after execution of the spawn point, is higher than a predetermined threshold; and    simultaneously: 
 executing in the speculative thread a speculative thread instruction stream that includes a subset of the instructions in the first instruction stream, the speculative thread instruction stream including the control-quasi-independent point; and  
 executing one or more instructions in the first instruction stream following the spawn point.  
   
     
     
         23 . The method of  claim 22 , wherein: 
 executing one or more instructions in the first instruction stream following the spawn point further comprises executing instructions until the CQIP is reached.    
     
     
         24 . The method of  claim 23 , further comprising: 
 determining, responsive to reaching the CQIP, whether speculative execution performed in the speculative thread is correct.    
     
     
         25 . The method of  claim 24 , further comprising: 
 responsive to determining the speculative execution performed in the speculative thread is correct, relinquishing the non-speculative thread.    
     
     
         26 . The method of  claim 24 , further comprising: 
 responsive to determining that the speculative execution performed in the speculative thread is not correct, squashing the speculative thread.    
     
     
         27 . The method of  claim 26 , further comprising: 
 responsive to determining that the speculative execution performed in the speculative thread is not correct, squashing all active successor threads, if any, of the speculative thread.    
     
     
         28 . The method of  claim 22 , wherein: 
 the speculative thread instruction stream includes a precomputation slice for the speculative computation of a live-in value.    
     
     
         29 . The method of  claim 22 , wherein: 
 spawning the speculative thread triggers hardware prediction of a live-in value.    
     
     
         30 . The method of  claim 28 , wherein: 
 the speculative thread instruction stream includes, after the precomputation slice, a branch instruction to the CQIP.    
     
     
         31 . The method of  claim 22 , further comprising: 
 spawning a second speculative thread at a spawn point in the speculative thread instruction stream.    
     
     
         32 . An article comprising: 
 a machine-readable storage medium having a plurality of machine accessible instructions;    wherein, when the instructions are executed by a processor, the instructions provide for 
 executing one or more instructions in a first instruction stream in a non-speculative thread;  
 spawning a speculative thread at a spawn point in the first instruction stream, wherein the computed probability of reaching a control quasi-independent point during execution of the first instruction stream, after execution of the spawn point, is higher than a predetermined threshold; and  
 simultaneously: 
 executing in the speculative thread a speculative thread instruction stream that includes a subset of the instructions in the first instruction stream, the speculative thread instruction stream including the control-quasi-independent point; and  
 executing one or more instructions in the first instruction stream following the spawn point.  
 
   
     
     
         33 . The article of  claim 32 , wherein: 
 the instructions that provide for executing one or more instructions in the first instruction stream following the spawn point further comprise instructions that provide for executing instructions until the CQIP is reached.    
     
     
         34 . The article of  claim 33 , wherein the instructions further comprise: 
 instructions that provide for determining, responsive to reaching the CQIP, whether speculative execution performed in the speculative thread is correct.    
     
     
         35 . The article of  claim 34 , wherein the instructions further comprise: 
 instructions that provide for, responsive to determining that the speculative execution performed in the speculative thread is correct, relinquishing the non-speculative thread.    
     
     
         36 . The article of  claim 34 , further comprising: 
 instructions that provide for, responsive to determining that the speculative execution performed in the speculative thread is not correct, squashing the speculative thread.    
     
     
         37 . The article of  claim 36 , wherein the instructions further comprise: 
 instructions that provide for, responsive to determining that the speculative execution performed in the speculative thread is not correct, squashing all active successor threads, if any, of the speculative thread.    
     
     
         38 . The article of  claim 32 , wherein: 
 the speculative thread instruction stream includes a precomputation slice for the speculative computation of a live-in value.    
     
     
         39 . The article of  claim 32 , wherein: 
 the instruction that provides for spawning the speculative thread triggers hardware prediction of a live-in value.    
     
     
         40 . The article of  claim 38 , wherein: 
 the speculative thread instruction stream includes, after the precomputation slice, a branch instruction to the CQIP.    
     
     
         41 . A compiler comprising: 
 a spawning pair selector module to select a spawning pair that includes a control-quasi-independent point (“CQIP”) and a spawn point; and    a code generator to generate an enhanced binary file that includes a trigger instruction at the spawn point.    
     
     
         42 . The compiler of  claim 41 , wherein: 
 the trigger instruction is to spawn a speculative thread to begin execution at the CQIP.    
     
     
         43 . The compiler of  claim 41 , further comprising: 
 a slicer to generate a slice for precomputation of a live-in value;    wherein the code generator is further to include the precomputation slice in the enhanced binary file.    
     
     
         44 . The compiler of  claim 41 , wherein: 
 the spawning pair selector module is further to select the spawning pair such that a computed probability of reaching the control-quasi-independent point after execution of the spawn point is higher than a predetermined threshold.    
     
     
         45 . The compiler of  claim 44 , further comprising: 
 a matrix builder to compute the reaching probability for the spawning pair.    
     
     
         46 . The compiler of  claim 41 , further comprising: 
 a profile analyzer to build a control flow graph.    
     
     
         47 . The compiler of  claim 41 , wherein: 
 the trigger instruction is to trigger hardware value prediction for a live-in value.    
     
     
         48 . The compiler of  claim 41 , further comprising: 
 a matrix builder to compute the reaching probability for the spawning pair.