Java Reference
In-Depth Information
1. lw
$10,a
6.
add
$10,$10,$12
2. lw
$11,b
7.
mul
$11,$11,$10
3. mul $11,$10,$11
8.
mul
$12,$10,$12
4. lw
$10,c
9.
add
$12,$11,$12
5. lw
$12,d
10. sw
$12,a
Figure 13.21: MIPS code for a=((a*b)*(c+d))+(d*(c+d))
2
5
1
4
6
3
8
7
9
10
Figure 13.22: Dependency DAG for a=((a*b)*(c+d))+(d*(c+d))
for the expression a=((a*b)*(c+d))+(d*(c+d)). Figure 13.22 illustrates the
corresponding dependency DAG. Double-circled nodes are loads, the critical
nodes in this example because they can stall.
Dependency DAGs have the property that any
topological sort
of the
nodes represents a valid execution order. That is, as long as an instruction is
scheduled before any of its successors in the dependency DAG, it will execute
properly. Any node that is a root of the dependency DAG may be scheduled
immediately. It is then removed from the DAG, and again any resulting root
may be scheduled. Our goal in scheduling instructions will be to choose roots
that avoid stalls. In fact, the first rule in our scheduling algorithm is just that:
When choosing a root to schedule, choose one that
will not
be stalled
by the most recently scheduled node.
Sometimes we cannot find a root that does not stall its predecessor. Not all
instruction sequences are stall-free.
