date: 2014-03-07 20:38:35

Problem Set Solutions/Interrupts Exceptions/Problem 2

Using Tomasulo’s algorithm, for each instruction in the following sequence determine when (in which cycle, counting from the start) it issues, begins execution, and writes its result to the CDB. Assume that the result of an instruction can be written in the cycle after it finishes its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that. The execution time of all instructions is two cycles, except for multiplication (which takes 4 cycles) and division (which takes 8 cycles). The processor has one multiply/divide unit and one add/subtract unit. The multiply/divide unit has two reservation stations and the add/subtract unit has four reservation stations. None of the execution units is pipelined – each can only be executing one instruction at a time. If a conflict for the use of an execution unit occurs when selecting which instruction should start to execute, the older instruction (the one that appears earlier in program order) has priority. If a conflict for use of the CBD occurs, the result of the add/subtract unit has priority over the result of the multiply/divide unit. Assume that at start all instructions are already in the instruction queue, but none has yet been issued to any reservation stations. The processor can issue only one instruction per cycle, and there is only one CDB for writing results.


A way of handling exceptions in the processor described above would be to simply delete all instructions from reservation stations and the instruction queue, set all RAT entries to point to the register file, and jump to the exception handler as soon as possible (i.e. in the cycle after the one in which divide-by-zero is detected). What would be printed in the exception handler if exceptions are handled this way?


The exception occurs in cycle 20, so the cycle in which we start executing the exception handler is cycle 21. At that time, the processor has completed instructions I1-I4, but it has also completed instructions I6 and I10. As a result, register F4 in the register file would have the result of I10, which is -1 (5-6). The exception handler would print 2,0, -2, -1, which is incorrect.