Appeal No. 96-1588
Application 08/036,947
overall execution time of those instructions (col. 1, lines 25-
33). Referring to Figure 1b, Rasbold's sequencing method begins
with all of the instructions being classified in the basic block
(10)m, from which they will be moved to the Leader Set (12) and
then to the Ready Set (16), unless they are Instructions With
Interlocks (18). Figure 2 shows an example of a series of source
equations 20 and corresponding intermediate language statements
21 that approximate assembly language instructions (col. 9, lines
11-16). Membership in the Leader Set is determined by
constructing a direct acyclic graph (DAG) 22, which depicts the
dependency of the instructions in the basic block (col. 9, lines
16-29). Each instruction is assigned a "cost" representing the
time consequence of not issuing the instruction; an instruction
from which many others depend has a higher cost than an
instruction from which few others depend (col. 9, lines 30-36).
With the aid of the DAG, each instruction in the basic block that
has not yet been scheduled is placed in the Leader Set if it is
not dependent on any unissued instructions (col. 9, lines 53-56;
col. 11, lines 13-19). This function is represented as step 40
in the flow chart of Figure 4. In step 60, the desired issue
time (DIT) is calculated for each instruction in the Leader Set,
after which the instructions with a DIT less than the current
6
Page: Previous 1 2 3 4 5 6 7 8 9 10 Next
Last modified: November 3, 2007