System, method, and program product for instruction scheduling in the presence of hardware lookahead accomplished by the rescheduling of idle slots
US5887174A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jun 18, 1996 |
| Grant date | Mar 23, 1999 |
| Priority date | — |
| Expiry date | Jun 18, 2016 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/445
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Instructions are scheduled for execution by a processor having a lookahead buffer by identifying an idle slot in a first instruction schedule of a first basic block of instructions, and by rescheduling the idle slot later in the first instruction schedule. The idle slot is rescheduled by determining if the first basic block of instructions may be rescheduled into a second instruction schedule in which the identified idle slot is scheduled later than in the first instruction schedule. The first basic block of instructions is rescheduled by determining a completion deadline of the first instruction schedule, decreasing the completion deadline, and determining the second instruction schedule based on the decreased completion deadline. Deadlines are determined by computing a rank of each node of a DAG corresponding to the first basic block of instructions; constructing an ordered list of the DAG nodes in nondecreasing rank order; and applying a greedy scheduling heuristic to the ordered list. An instruction in a second subsequent basic block of instructions may be rescheduled to execute in the rescheduled idle slot. This process may be repeated for each idle slot.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.