초록 ▼

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

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.

대표청구항 ▼

[ We claim:] [1.] A method of scheduling a plurality of instructions for execution by a processor having one or more functional units and a lookahead buffer, said lookahead buffer capable of storing a fixed number of the instructions to be issued and executed out of order as and when the instruction

[ We claim:] [1.] A method of scheduling a plurality of instructions for execution by a processor having one or more functional units and a lookahead buffer, said lookahead buffer capable of storing a fixed number of the instructions to be issued and executed out of order as and when the instructions become ready for execution, said method comprising the steps of:a) identifying an idle slot in a first instruction schedule, said first instruction schedule comprising a schedule of slots in which each instruction of the first basic block is assigned a start time corresponding to one of the slots said idle slot comprising a slot in the first instruction schedule at which one of the functional units is not starting any one of the instructions of the first basic block; andb) delaying said idle slot to a later slot in said first instruction schedule, such that an instruction in a second subsequent basic block of instructions may be rescheduled to execute in the delayed idle slot.