1
$\begingroup$

enter image description here

Using Tomasulo’s algorithm, for each instruction in the listed 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 last cycle of 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.

Can someone explain why for Instruction 1 the write happens in cycle 5 ? It is given in the question that MUL takes 4 cycles to execute. So write for I1 should have happened in cycle 6 ?

$\endgroup$
  • 2
    $\begingroup$ I don't think this is answerable unless you specify on what sort of processor/assembly language this is. Please edit your question to clarify so that the meaning of all commands and registers is clear. $\endgroup$ – Discrete lizard Apr 22 at 16:33
  • $\begingroup$ updated the question $\endgroup$ – Ishan Kumar Apr 22 at 18:22
  • 1
    $\begingroup$ It looks like you are copying material from some other source. Can you edit your question to credit the source? We require you to always attribute all copied material -- see cs.stackexchange.com/help/referencing. $\endgroup$ – D.W. Apr 24 at 19:27
1
$\begingroup$

The question I have met in class before. I cannot add comment so I write here. Notice the note 'Assume that the result of an instruction can be written in the last cycle of its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that.' which means instead of WR in the 1st cycle after the completion of EXE, it WR in the last cycle of EXE.

E.g. The I1 starts its EXE in 2nd cycle and end in 5th cycle (2, 3, 4, 5). So I1's WR happens in the last cycle of EXE which is 5th cycle.

For the rest of the table you should fill them based on the given notes, kind of the manual of a specific processor. This is not the general case which you will encounter in other scheduler problems. Wish it helps you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.