Problem Set Solutions/Instruction Scheduling/Problems 1-3


I1 issues in 1, executes in 2,3,4,5 and writes result in 5. Meanwhile, we issue I2 in 2 and I3 in 3, but they can’t execute (need result of I1). We issue I4 in 4, but it depends on I3. In cycle 5, I5 cannot issue because it needs a free MUL/DIV RS, which only becomes available in 6 (after I1 writes result).

In cycle 6, after I1 wrote its result, I2 and I3 can begin to execute (note that they use different execution units). Also in 6, I5 can issue (I1’s RS in now free). In cycle 7, we issue I6, and I3 completes execution. In cycle 8, we can issue I7, and I4 can now execute (it was waiting for I3 to complete). In cycle 9 we complete I4, but we can’t issue I8 because it needs a free MUL/DIV RS and both are in use (by I2 and I5).

Nothing new happens until cycle 13, when I2 writes its result. This frees an RS, so I8 can issue in cycle 14. Also in cycle 14, I5 and I6 can begin to execute (again, different units are used so these two can be executed in parallel). In cycle 15 we can issue I9, and I6 is completed. In cycle 16 we issue I10. In cycle 17 we can execute I10 (note that the ADD/SUB unit was idle since 15, when I6 was completed). In cycle 18, I10 completes and writes its result. After this, nothing happens for a while (until I5 completes in 21).

In cycle 21, I5 completes, allowing I7 and I8 to execute in cycle 22. I7 completes in 23, so I9 executes in 24. In cycle 25, both I8 and I9 finish execution and want to write their results. Because there is only one CDB, and because the ADD/SUB instruction has priority (see problem statement), I9 writes its result in cycle 25 and I8 writes its result in cycle 26.