1
\$\begingroup\$

I saw this HW solution in CMU Comp Arch course website. I am reading ComputerArchitecture on my own. I just have a doubt.

Here is the HW question:

Given the following code (MIPS):

MUL R3, R1, R2
ADD R5, R4, R3
ADD R6, R4, R1
MUL R7, R8, R9
ADD R4, R3, R7
MUL R10, R5, R6
Fetch (one clock cycle)
Decode (one clock cycle)
Execute (MUL takes 6, ADD takes 4 clock cycles). The multiplier and the adder are not pipelined.
Write-back (one clock cycle)

Calculate the number of cycles it takes to execute the given code on a pipelined machine with scoreboarding and five adders and five multipliers without data forwarding.

Here is the actual solution: enter image description here

My doubt:

  • Why the second instruction ADD R5, R4, R3 is in decode state two times? (in 3rd cycle and again in 10th cycle)

  • Why the third instruction ADD R6, R4, R1 did not do its DECODE state 4th cycle?

\$\endgroup\$
  • \$\begingroup\$ Follow the data. \$\endgroup\$ – Chris Stratton Jun 18 '17 at 16:52
  • \$\begingroup\$ @ChrisStratton I agree with data dependency. The second instruction needs R3 but first instruction has not produced R3. But how does that answer why DECODE must happen two times? \$\endgroup\$ – user3219492 Jun 18 '17 at 16:52
  • \$\begingroup\$ That depends on the rules of the unspecified assembly language quoted. If the first register given is the destination then the first instruction does set R3. ARM would be an example written in that order with registers named as shown. \$\endgroup\$ – Chris Stratton Jun 18 '17 at 16:55
  • \$\begingroup\$ @ChrisStratton After First instruction produce R3, the DECODE must happen at 10th cycle alone. And it must be NOP in2nd cycle, right? \$\endgroup\$ – user3219492 Jun 18 '17 at 16:57
  • 1
    \$\begingroup\$ Probably some rule about being in a blocked state trickling down. Looking at it another way, because the 2nd instruction hasn't exited DECODE yet. \$\endgroup\$ – Chris Stratton Jun 18 '17 at 17:02
1
\$\begingroup\$

Why the second instruction ADD R5, R4, R3 is in decode state two times? (in 3rd cycle and again in 10th cycle)

The decode stage includes the reading of the operands from the register file. In the second cycle, the decoder discovers that one of the operands for the second instruction is not yet available — the decode of the first instruction had marked R3 as "busy". Therefore, the decode of the second instruction needs to be repeated after the write from the first instruction makes R3 "not busy". The write occurs in cycle 9, which means that the read can happen in cycle 10.

Why the third instruction ADD R6, R4, R1 did not do its DECODE state 4th cycle?

Because the decode of the second instruction had not been completed. Instructions must be decoded in sequence, because that's how the data dependencies are established.

\$\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.