An interior node in Sethi Ullman labelling has children labelled 3 and 1. What label does it receive?
Answer: C
Unequal labels mean the larger subtree can be evaluated first and its result held in one register while the smaller is evaluated, so the maximum is unchanged at three. Reversing the order would have required a fourth register.
Please log in or register to report this question.
Evaluating the child with the larger Sethi Ullman label first is advantageous because
Answer: D
Holding one register while evaluating the smaller subtree costs less than the reverse order. The saving is exactly what makes the labelling worth computing at all. On a machine with few registers the difference can decide whether spilling occurs.
Please log in or register to report this question.
Sethi Ullman numbering assumes
Answer: A
Sharing turns the tree into a graph and the optimality argument no longer holds. The method also assumes a uniform register set with no special purpose registers. Real machines often violate both assumptions, so the result is a useful guide rather than a rule.
Please log in or register to report this question.
An instruction schedule that violates a data dependence produces code that is
Answer: B
Reading a value before it has been written gives the wrong answer, not a stall. Dependences are therefore hard constraints on the schedule, while latencies are merely costs the scheduler tries to hide by filling the gaps with independent work.
Please log in or register to report this question.
A data dependence between two instructions means
Answer: C
True dependences, where one reads what the other wrote, are the fundamental constraint. Anti and output dependences arise from reusing names and can often be removed by renaming. Only the true dependence reflects an actual flow of data.
Please log in or register to report this question.
Match each kind of dependence with its description.
List I
A. true dependence
B. anti dependence
C. output dependence
D. no dependence
List II
1. two writes to the same location
2. a read of a value that was just written
3. the instructions may be freely reordered
4. a write to a location that was just read
Answer: D
Only the true dependence reflects real data flow. The other two arise from reusing a name and can often be removed by giving one of the instructions a fresh destination. Static single assignment form removes them all by construction.
Please log in or register to report this question.
Assertion (A): Anti dependences and output dependences can often be removed by renaming.
Reason (R): They arise from reusing a storage location rather than from any real flow of data between the instructions.
Answer: A
Both are true and the reason gives the mechanism, and this is one of the attractions of static single assignment form. Giving each write its own name leaves only the true dependences, which the schedule genuinely must respect.
Please log in or register to report this question.
List scheduling within a basic block works by
Answer: B
Correct answer: repeatedly issuing a ready instruction chosen by a priority rule
List scheduling maintains the set of instructions whose operands are available and picks one by a heuristic - usually the longest path to the end of the block. It is greedy and not optimal, but optimal scheduling is NP-hard and list scheduling comes close enough at a fraction of the cost.
Please log in or register to report this question.
Instruction scheduling and register allocation interact because
Answer: C
A longer schedule keeps more values live at once and so needs more registers, which may force spilling. Doing allocation first instead constrains the schedule that can be produced. Some compilers interleave the two rather than choosing an order.
Please log in or register to report this question.
Software pipelining is a scheduling technique that
Answer: D
Correct answer: overlaps instructions from successive loop iterations
Software pipelining starts the next iteration before the current one has finished, so the long-latency operations of one iteration overlap the work of another. The result is a steady-state kernel with a prologue and epilogue, and it keeps a deep pipeline full where simple unrolling would not.
Please log in or register to report this question.
