Appeal No. 96-1588
Application 08/036,947
Because the two Multiply instructions can be paired with two of
the four Add instructions, the shortest possible schedule length
is four time slots, labeled SLOTS 0-3 in the Resource Utilization
Array of Figure 9a. The scheduler builds a candidate instruction
list using the bottom-up approach, starting with the last
instruction in each instruction set: instr-4 and instr-8
(Fig. 9a). Since the instruction chain ending with instr-4
contains more non-squeezed instructions (four) than does the
instruction chain ending with instr-8 (two), the result is that
instr-4 (Multiply) is assigned to the multiplier resource during
SLOT 0 (Fig. 9a). Next the chains ending in instr-3 and instr-8
are compared (Fig. 9b). Because the instruction chain ending
with instr-3 contains more non-squeezed instructions (three) than
does the instruction chain ending with instr-8 (two), instr-3
(Multiply) is assigned to the next time slot available for the
multiplier, i.e., SLOT 1. Next, the chains ending in instr-2 and
instr-8 are compared (Fig. 9c). Because both chains contain two
non-squeezed instructions, the presence of the squeezed
instructions ("Divide") in the second chain are used for tie-
breaking, with the result that instr-8 (Add) is assigned to the
adder resource during its first available time slot, i.e.,
SLOT 0. Next, the chains ending in instr-2 and instr-7 are
3
Page: Previous 1 2 3 4 5 6 7 8 9 10 Next
Last modified: November 3, 2007