[CST-2] Op. Comp. 99/9/7

[M.Y.W.Y. Becker]

--On 21 May 2001 14:23 +0100 Phebe Mann <pm258@hermes.cam.ac.uk> wrote:

>
> Can someone provide a comprehesive solution to the "algorithm of
> instruction scheduling" part of the question please ? (10 marks)

You just need to summarise the stuff in the notes:

* architecture: 5-stage RISC pipeline (IF,RF,EX,MEM,WB) with delayed 
branches and loads
* reorder instruction within a BB
* aim: minimise interlocks
* scheduling is NP-complete, but can use heuristics:

(1) Construct a dag: nodes=all instructions of BB; edges: n->n' if n is 
before n' and n,n' cannot be permuted, i.e. either JUMP or one writes to a 
register read/written by the other

(2) Initialise candidateList := min. elements of dag (i.e. top elements)

(3) Pick an instruction from candidateList using heuristics (in that 
order):
  * choose instruction not causing delay
    with previously emitted instruction
  * choose instruction most likely to cause
    interlock with instruction after it
  * choose instruction farthest away (over
    longest path) from a leaf node

(4) emit chosen instruction (insert NOPs if interlock & if architecture 
requires that) and remove from dag

(5) insert the new minimal elements into candidateList

(6) go back to (3) until candidateList is empty



Mo