Patent US6016399A successfully refreshed from Google Patents.
US6016399A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Software pipelining a hyperblock loop
Assignee: Intel Corp
•
Filing: 1998-12-16
•
Granted: 2000-01-18
•
Expires: 2018-12-16
Abstract
Abstract An iterative software pipelining method promotes instructions of a program loop to previous loop iterations and then reschedules the instructions until either 1) the resultant schedule is optimal (i.e., the initiation interval is equal to the minimal initiation interval) or 2) the resultant schedule is not an improvement over the previous schedule generated. The method is applicable to a sequence of instructions within a program loop having a single control flow entry and one or more control flow exit points. First, a minimum initiation interval of the program loop is computed. Second, instruction level parallelism transformations are applied on the program loop. Third, a single iteration schedule is determined for the program loop. Fourth, selected instructions are percolated to a prior iteration of the program loop to generate a new instruction order for the program loop. Each of steps two through four is performed as long as a previous length of the program loop exceeds a single iteration schedule length and the single iteration schedule length exceeds the minimum initiation interval.
Inventors
- 👤 Pohua Chang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 16:28
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F8/4452
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
128 words
A machine-readable medium having stored thereon sequences of instructions that when executed by a processor cause the processor to: a) compute a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) apply instruction level parallelism transformations on the program loop; c) apply single iteration scheduling on the program loop; d) percolate selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop; e) repeat b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.
Claim 2
Dependent Claim
128 words
A machine-readable medium having stored thereon sequences of instructions that when executed by a processor cause the processor to: a) compute a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) apply instruction level parallelism transformations on the program loop; c) apply single iteration scheduling on the program loop; d) percolate selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop; e) repeat b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.
Claim 3
Dependent Claim
209 words
A machine-readable medium having stored thereon sequences of instructions that when executed by a processor cause the processor to: a) compute a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) save the program loop as a recorded program loop; c) apply instruction level parallelism transformations on the program loop to produce a revised program loop; d) apply single iteration scheduling on the revised program loop; e) determine a single iteration schedule length, SL, of the revised program loop; f) restore the recorded program loop as the revised program loop, if a previous length is not greater than SL; g) perform the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval: i) equate the previous length to SL; and ii) percolate selected instructions of the revised program loop to a prior iteration of the revised program loop; h) repeat b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval; i) generate a loop prologue for the revised program loop; and j) generate a loop epilogue for the revised program loop.
Claim 4
Dependent Claim
209 words
A machine-readable medium having stored thereon sequences of instructions that when executed by a processor cause the processor to: a) compute a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) save the program loop as a recorded program loop; c) apply instruction level parallelism transformations on the program loop to produce a revised program loop; d) apply single iteration scheduling on the revised program loop; e) determine a single iteration schedule length, SL, of the revised program loop; f) restore the recorded program loop as the revised program loop, if a previous length is not greater than SL; g) perform the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval: i) equate the previous length to SL; and ii) percolate selected instructions of the revised program loop to a prior iteration of the revised program loop; h) repeat b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval; i) generate a loop prologue for the revised program loop; and j) generate a loop epilogue for the revised program loop.
Claim 5
Dependent Claim
147 words
A machine-readable medium having stored thereon sequences of instructions that when executed cause the processor to: a) compute a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit; b) apply instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop; c) apply single iteration scheduling on the current loop; d) percolate selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and e) repeat b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.
Claim 6
Dependent Claim
147 words
A machine-readable medium having stored thereon sequences of instructions that when executed cause the processor to: a) compute a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit; b) apply instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop; c) apply single iteration scheduling on the current loop; d) percolate selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and e) repeat b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.
Claim 7
Dependent Claim
43 words
The machine-readable medium of claim 3 further comprising sequences of instructions that when executed cause the processor to: f) select the previous loop as the current loop, if the current loop single iteration schedule length exceeds the previous loop single iteration schedule length.
Claim 8
Dependent Claim
31 words
The machine-readable medium of claim 3 further comprising sequences of instructions that when executed cause the processor to: g) generate a current loop prologue; and h) generate a current loop epilogue.
Claim 9
Dependent Claim
15 words
The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include constant combining.
Claim 10
Dependent Claim
15 words
The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include operation combining.
Claim 11
Dependent Claim
17 words
The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include software based register renaming.
Claim 12
Dependent Claim
16 words
The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include an LHS/RHS transformation.
Claim 13
Independent Claim
122 words
An apparatus comprising: a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) means for applying instruction level parallelism transformations on the program loop; c) means for applying single iteration scheduling on the program loop; d) means for percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop; e) means for repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.
Claim 14
Independent Claim
122 words
An apparatus comprising: a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) means for applying instruction level parallelism transformations on the program loop; c) means for applying single iteration scheduling on the program loop; d) means for percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop; e) means for repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.
Claim 15
Independent Claim
209 words
An apparatus comprising: a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) means for saving the program loop as a recorded program loop; c) means for applying instruction level parallelism transformations on the program loop to produce a revised program loop; d) means for applying single iteration scheduling on the revised program loop; e) means for determining a single iteration schedule length, SL, of the revised program loop; f) means for restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL; g) means for performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval: i) equating the previous length to SL; and ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop; h) means for repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval; i) generate a loop prologue for the revised program loop; and j) generate a loop epilogue for the revised program loop.
Claim 16
Independent Claim
209 words
An apparatus comprising: a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) means for saving the program loop as a recorded program loop; c) means for applying instruction level parallelism transformations on the program loop to produce a revised program loop; d) means for applying single iteration scheduling on the revised program loop; e) means for determining a single iteration schedule length, SL, of the revised program loop; f) means for restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL; g) means for performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval: i) equating the previous length to SL; and ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop; h) means for repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval; i) generate a loop prologue for the revised program loop; and j) generate a loop epilogue for the revised program loop.
Claim 17
Independent Claim
144 words
An apparatus comprising: a) means for computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit; b) means for applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop; c) means for applying single iteration scheduling on the current loop; d) means for percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and e) means for repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.
Claim 18
Independent Claim
144 words
An apparatus comprising: a) means for computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit; b) means for applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop; c) means for applying single iteration scheduling on the current loop; d) means for percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and e) means for repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.
Claim 19
Dependent Claim
34 words
The apparatus of claim 12 further comprising: f) means for selecting the previous loop as the current loop, if the current loop single iteration schedule length exceeds the previous loop single iteration schedule length.
Claim 20
Dependent Claim
24 words
The apparatus of claim 12 further comprising: g) means for generating a current loop prologue; and h) means for generating a current loop epilogue.
Claim 21
Dependent Claim
14 words
The apparatus of claim 12 wherein the instruction level parallelism transformations include constant combining.
Claim 22
Dependent Claim
14 words
The apparatus of claim 12 wherein the instruction level parallelism transformations include operation combining.
Claim 23
Dependent Claim
16 words
The apparatus of claim 12 wherein the instruction level parallelism transformations include software based register renaming.
Claim 24
Dependent Claim
15 words
The apparatus of claim 12 wherein the instruction level parallelism transformations include an LHS/RHS transformation.
Claim 25
Independent Claim
137 words
A system comprising: a memory to store a sequence of instructions; a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) applying instruction level parallelism transformations on the program loop; c) applying single iteration scheduling on the program loop; d) percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop; e) repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.
Claim 26
Independent Claim
137 words
A system comprising: a memory to store a sequence of instructions; a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) applying instruction level parallelism transformations on the program loop; c) applying single iteration scheduling on the program loop; d) percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop; e) repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.
Claim 27
Independent Claim
218 words
A system comprising: a memory to store a sequence of instructions; a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) saving the program loop as a recorded program loop; c) applying instruction level parallelism transformations on the program loop to produce a revised program loop; d) applying single iteration scheduling on the revised program loop; e) determining a single iteration schedule length, SL, of the revised program loop; f) restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL; g) performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval: i) equating the previous length to SL; and ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop; h) repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval; i) generating a loop prologue for the revised program loop; and j) generating a loop epilogue for the revised program loop.
Claim 28
Independent Claim
218 words
A system comprising: a memory to store a sequence of instructions; a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit; b) saving the program loop as a recorded program loop; c) applying instruction level parallelism transformations on the program loop to produce a revised program loop; d) applying single iteration scheduling on the revised program loop; e) determining a single iteration schedule length, SL, of the revised program loop; f) restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL; g) performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval: i) equating the previous length to SL; and ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop; h) repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval; i) generating a loop prologue for the revised program loop; and j) generating a loop epilogue for the revised program loop.
Claim 29
Independent Claim
159 words
A system comprising: a memory to store a sequence of instructions; a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by a) computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit; b) applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop; c) applying single iteration scheduling on the current loop; d) percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and e) repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.
Claim 30
Independent Claim
159 words
A system comprising: a memory to store a sequence of instructions; a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by a) computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit; b) applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop; c) applying single iteration scheduling on the current loop; d) percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and e) repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.
Claim 31
Dependent Claim
39 words
The system of claim 21 wherein the processor further schedules the sequence of instructions by selecting the previous loop as the current loop, if the current loop single iteration schedule length exceeds the previous loop single iteration schedule length.
Claim 32
Dependent Claim
28 words
The system of claim 21 wherein the processor further schedules the sequence of instructions by: g) generating a current loop prologue; and h) generating a current loop epilogue.
Claim 33
Dependent Claim
14 words
The system of claim 21 wherein the instruction level parallelism transformations include constant combining.
Claim 34
Dependent Claim
14 words
The system of claim 21 wherein the instruction level parallelism transformations include operation combining.
Claim 35
Dependent Claim
16 words
The system of claim 21 wherein the instruction level parallelism transformations include software based register renaming.
Claim 36
Dependent Claim
15 words
The system of claim 21 wherein the instruction level parallelism transformations include an LHS/RHS transformation.
References Cited (Backward Citations)
US5317743A
Cited
US5265253A
Cited
US5375238A
Cited
US5303357A
Cited
US5386562A
Cited
US5367651A
Cited
US5920724A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-17 | 2003-07-19 | 2004-01-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-17 | 2007-07-19 | 2008-01-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-17 | 2011-07-19 | 2012-01-18 | $7700.00 | Window Closed / Lapsed |