Energy/performance with optimal communication in dynamic parallelization of single-threaded programs

An article of manufacture including program code which, when executed by a machine, causes the machine to perform the operations of:

• creating a plurality of nodes in a flow network corresponding to a plurality of instructions in a replicated dependence chain;
• creating a source node and a sink node in the flow network;
• creating workload edges associated with workload costs from the plurality of nodes to the sink node;
• creating communication edges associated with communication costs from each producer node of the plurality of nodes to each consumer node of the plurality of nodes;
• and

A method comprising:

• determining a workload for each node of a code segment;
• determining a communication cost for each intra-dependence edge between nodes of the code segment;
• creating a flow network for the code segment based on the workload for each node of the code segment and the communication cost for each intra-dependence between nodes of the code segment;
• and
• applying a minimum-cut algorithm to the flow network to determine removable nodes from the code segment.