System, method, and program product for loop instruction scheduling hardware lookahead
US6044222A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jun 23, 1997 |
| Grant date | Mar 28, 2000 |
| Priority date | — |
| Expiry date | Jun 23, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/4452
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Improved scheduling of instructions within a loop for execution by a computer system having hardware lookahead is provided. A dependence graph is constructed which contains all the nodes of a dependence graph corresponding to the loop, but which only contains loop-independent dependence edges. A start node simulating a previous iteration of the loop may be added to the dependence graph, and an end node simulating a next iteration of the loop may also added to the dependence graph. A loop-independent edge between a source node and the start node is added to the dependence graph, and a loop-independent edge between a sink node and the end node is added to the dependence graph. Loop-carried edges which satisfy a computed lower bound on the time required for a single loop iteration are eliminated from a dependence graph, and loop-carried edges which do not satisfy the computed lower bound are replaced by a pair of loop-independent edges. Instructions may be scheduled for execution based on the dependence graph.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.