Mechanism to optimize speculative parallel threading

A machine-accessible medium having stored thereon data representing sets of instructions that, when executed by a machine, cause the machine to perform operations for speculative parallel thread compilation and execution of program code comprising:

• selecting a plurality of partition candidate pairs for speculative parallel thread execution, wherein selecting the plurality of partition candidate pairs includes the plurality of partition candidate pairs whose reaching probabilities is high and exceeds a minimum threshold;
• transforming each partition candidate pair of the plurality of partition candidate pairs by altering the program code to improve an expected performance gain of each pair, wherein the program code of the plurality of partition candidate pairs is transformed in both master and speculative regions to reduce re-execution cost, wherein the transformation of each partition candidate pair is determined by estimation of a re-execution ratio, where the re-execution ratio is a probability that a speculatively executed instruction in the speculative region needs to be re-executed, where the re-execution ratio is estimated by dividing an expected number of instructions in the speculative region to be re-executed by an expected total number of instructions executed in the speculative region;
• and
• selecting a set of one or more transformed partition candidate pairs that do not interfere with each other and produce a maximum expected performance gain.

A system for speculative parallel thread compilation and execution of program code, comprising:

• a dynamic random access memory (DRAM) to store the program code;
• and
• a processor coupled with the DRAM memory, the processor to:
• select a plurality of partition candidate pairs for speculative parallel thread execution, wherein selecting the plurality of partition candidate pairs includes the plurality of partition candidate pairs whose reaching probabilities is high and exceeds a minimum threshold;
• transform each partition candidate pair of the plurality of partition candidate pairs by altering the program code to improve an expected performance gain of each pair, wherein the program code of the plurality of partition candidate pairs is transformed in both master and speculative regions to reduce re-execution cost, wherein the transformation of each partition candidate pair is determined by estimation of a re-execution ratio, where the re-execution ratio is a probability that a speculatively executed instruction in the speculative region needs to be re-executed, where the re-execution ratio is estimated by dividing an expected number of instructions in the speculative region to be re-executed by an expected total number of instructions executed in the speculative region;
• and
• select a set of one or more transformed partition candidate pairs that do not interfere with each other and produce a maximum expected performance gain.