Extension of swing modulo scheduling to evenly distribute uniform strongly connected components
AssigneeInternational Business Machines Corporation
InventorAllan Russell Martin
Life of this patent
Estimating the term…
Abstract
A method, apparatus, and computer instructions for scheduling instructions for execution. Identify a series of instructions in a loop, wherein the series of instructions has a cyclic data dependency. Determine whether the series of instructions is a uniform series of instructions. Schedule execution of the uniform series of instructions within the loop to optimize execution of the loop in response to the identified series of instructions being the uniform series of instructions.
Claims14
A method in a data processing system for scheduling instructions for execution, the method comprising:
- identifying a series of instructions in a loop, wherein the series of instructions has a cyclic data dependency;
- determining whether the series of instructions is a uniform series of instructions;
- scheduling a spacing of the uniform series of instructions within the loop, wherein scheduling a spacing of the uniform series of instructions within the loop includes adding a number of slack cycles between a first instruction and a second instruction following the first instruction in the uniform series, wherein scheduling a spacing of the uniform series of instructions within the loop includes using the following:
- spacing between instruction a(i) and instruction b(i+1)=(((i)*SCC slack/M)−((i+1)*SCC slack)/M), wherein i is an index number, a(i) is a first instruction, b(i+1) is a second instruction following the first instruction, strongly connected component slack is a target initiation interval minus a longest cyclic delay for any series of instructions having the cyclic data dependency in the loop, and M is a number of repetitions of a sequence of instructions in the series of instructions and wherein the spacing is in cycles;
- and
- responsive to the identified series of instructions being the uniform series of instructions, scheduling execution of the uniform series of instructions within the loop to optimize execution of the loop.
A computer program product in a computer readable, recordable-type medium in a data processing system for scheduling instructions for execution, the computer program product comprising:
- first instructions for identifying a series of instructions in a loop, wherein the series of instructions has a cyclic data dependency;
- second instructions for determining whether the series of instructions is a uniform series of instructions;
- third instructions for scheduling a spacing of the uniform series of instructions within the loop, wherein scheduling a spacing of the uniform series of instructions within the loop includes adding a number of slack cycles between a first instruction and a second instruction following the first instruction in the uniform series, wherein the third instructions include:
- sub-instructions for scheduling a spacing of the uniform series of instructions within the loop using the following:
- spacing=(((b)*SCC slack/N)−((a*SCC slack)/N), wherein a is a first instruction, b is a second instruction following the first instruction, strongly connected component (SCC) slack is a target initiation interval minus a longest cyclic delay for any series of instructions having the cyclic data dependency in the loop, and N is a number of instructions and wherein the spacing is in cycles;
- and
- fourth instructions, responsive to the identified series of instructions being the uniform series of instructions, for scheduling execution of the uniform series of instructions within the loop to optimize execution of the loop.
A computer program product in a computer readable, recordable-type medium in a data processing system for scheduling instructions for execution, the computer program product comprising:
- first instructions for identifying a series of instructions in a loop, wherein the series of instructions has a cyclic data dependency;
- second instructions for determining whether the series of instructions is a uniform series of instructions;
- third instructions for scheduling a spacing of the uniform series of instructions within the loop, wherein scheduling a spacing of the uniform series of instructions within the loop includes adding a number of slack cycles between a first instruction and a second instruction following the first instruction in the uniform series, wherein the third instructions include:
- sub-instructions for scheduling a spacing of the uniform series of instructions within the loop using the following:
- spacing=(((b)*SCC slack/M)−((a*SCC slack)/M), wherein a is a first instruction, b is a second instruction following the first instruction, strongly connected component (SCC) slack is a target initiation interval minus a longest cyclic delay for any series of instructions having the cyclic data dependency in the loop, and M is a number of repetitions of a sequence of instructions in the series of instructions and wherein the spacing is in cycles;
- and
- fourth instructions, responsive to the identified series of instructions being the uniform series of instructions, for scheduling execution of the uniform series of instructions within the loop to optimize execution of the loop.
Dependencies are inferred from the claim text.