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.
Claims3
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;
- 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:
- and
- scheduling a spacing of the uniform series of instructions evenly within the loop using the following:
- spacing between instruction a(i) and instruction b(i+1)=(((i)* SCC slack/N)−((i+1)*SCC slack)/N);
- 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 (SCC) slack is a target initiation interval minus a longest cyclic delay for aim series of instructions having the cyclic data dependency in the loop, and N is a number of instructions aid wherein the spacing is in cycles.
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;
- 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;
- and
- scheduling a spacing of die uniform series of instructions evenly within the loop 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 (SCC) stack 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.
Dependencies are inferred from the claim text.