5
\$\begingroup\$

I am not new to computer architecture but I have only academic experience with micro-architecture implementation.

I have heard and read this many times but never really bothered to understand the statement: Some instructions complete in 1 or 2 clock cycles while more complex instructions say integer or floating point complete in 2, 4, 6 clock cycles etc or load/store in 80-100 clock cycles because of slow memory.

Now I am sure most processors be it embedded or desktop have few stages of pipelines say from 5 stages upto 30 stages. So the latency for each instruction should be equal to pipeline depth or number of pipeline stages. Also, throughput of a single pipeline scalar processor can be maximum 1 IPC (Instructions per cycle). But how can some instructions finish in 1,2 or 4 clock cycles for a processor with 10 stage or 12 stage pipeline ? Can someone explain me that ?

PS: Only thing I can understand is that maybe some stages are marked as a Multi-Cycle stage as is usually done during STA and timing closure. And that they are trying to say that execution of instruction takes 1cc, 2cc, 4cc etc. in that particular Multi-cycle stage ?

\$\endgroup\$
  • 1
    \$\begingroup\$ A specific instruction 'uses' only the pipeline stage it needs, the others are 'skipped'. It would make no sense to do (= wait for) operand-fetch-from-memory and ALU stages in a register-to-register move instruction! \$\endgroup\$ – Wouter van Ooijen Sep 26 '13 at 15:49
  • \$\begingroup\$ Where did you read your quoted statement? It sounds to me like something that might be said about an earlier generation of processors (say 6800 / 8086 era) before pipeline architectures became common. For a pipelined architecture you'd more likely say something like "the processor has a throughput of 1 (or 2) cycles per instruction". \$\endgroup\$ – The Photon Sep 26 '13 at 16:44
  • \$\begingroup\$ @WoutervanOoijen: Yes absolutely correct. So some instructions might have higher latency and some have lower. \$\endgroup\$ – nurabha Sep 26 '13 at 17:55
3
\$\begingroup\$

Generally, instruction execution time is measured not from when it enters the pipeline to when it leaves, but rather from the time it passes some arbitrary point in the pipeline to the time the next instruction passes that point. If no instruction takes more than e.g. 20 cycles to make its way through the pipeline, measuring the time for a sequence of instructions to pass through some arbitrary state will yield a result that's within 20 cycles of the actual time required to execute the whole sequence from start to finish. Since programmers are generally far less interested in the time to execute a single instruction, than in the time required to execute sequences containing many instructions (often thousands, if not more), they generally will only care about pipelining in cases where it can add a non-constant cost to the overall execution time (e.g. if repeated execution of an instruction sequence will add a pipeline stall each time).

\$\endgroup\$
  • \$\begingroup\$ "Measuring the time for a sequence of instructions to pass through some arbitrary state will yield a result that's within 20 cycles of the actual time required to execute the whole sequence from start to finish." Wouldn't the time to execute an arbitrary sequence be within "20 plus the number of insns in the sequence" cycles, assuming one insn enters the pipeline per cycle? \$\endgroup\$ – cr1901 Mar 30 '17 at 15:54
  • 1
    \$\begingroup\$ If every instruction passes through the same sequence of 20 states, then the measured time would be exactly 20 cycles shorter than the actual time. If the measured time is 1000, the actual time would be 1020. The reason I said "within" is to allow for the possibility that a pipeline would have 8 stages, but could stall for a total of 12 cycles while processing them. No instruction would take more than 20 cycles to get through the pipeline, but the total time could be anywhere from (measurement+8) to (measurement+20. In all cases, though, it would be "within 20". \$\endgroup\$ – supercat Mar 30 '17 at 16:16
2
\$\begingroup\$

Length of pipeline is just the delay between the input and the output.

Cycles for completion is the amount of time it needs per operation.

This is not the same, one is "delay" the other is "speed". So it is perfectly possible to have pipeline and multiple cycles per instruction at any ratio.

Suppose you have a 5 stage pipeline and need 3 cycles per instruction. This means that the next two cycles after you apply an input the unit is not ready to accept new input. In addition to that, there is an delay of 5 cycles because of the pipeline. Hence it takes 8 cycles from applying the input until the result is available. But regarding throughput only 3 cycles per operation are needed. I.e. although the first result is not fully completed, in the 3rd cycle new input can be accepted and the computation is started (and the results is obtained 8 cycles later).

With a pipeline you are doing things in parallel (at the cost of delay), which you otherwise had to to serially (more cycles per operation).

\$\endgroup\$
  • \$\begingroup\$ I understand most of your points. But I cannot understand your comment: "need 3 cycles per instruction" - do you mean average IPC ? And also the comment: "3 cycles per operation" - you mean execution of actual operation in a given stage requires 3 cycles ? \$\endgroup\$ – nurabha Sep 26 '13 at 18:00
  • \$\begingroup\$ I mean by 3 cycles/instruction an IPC of 1/3. Or in the time corresponding to 3000 cycles 1000 instructions can be completed. So I think the aswer to your question is yes. \$\endgroup\$ – Andreas H. Sep 26 '13 at 18:05
2
\$\begingroup\$

Having an instruction which can proceed through all the pipeline stages (Fetch -> Decode -> ...) in one or two clock cycles seems impossible to me. The "execution time" as you cited it is, probably, some kind of slang.

The best guess I can make without being able to see the whole context of the statement which puzzles you, is that these numbers represent the "stalling" of the pipeline when the instruction of some kind is executed. The other way to say it is that this number represents the theoretical throughput of the pipeline if just the instructions of this kind would be executed.

For example:

  • If the only instructions which is supplied to the pipeline could be Move Between Registers, the throughput of the pipeline would be equal to 1 - on each clock cycle one instruction gets completed.
  • If the only instruction which is supplied to the pipeline could be Load From Memory, the throughput of the pipeline would be equal to \$\frac{1}{100}\$ (assuming this instruction stalls the pipeline for 100 clock cycles).

In modern multi-pipeline CPUs there is no much use to the raw "instruction execution time" alone. The employment of multi-level caching, out-of-order execution, predictive branching and many more, complicates the analysis and mitigate the penalty of stalling a single pipeline. Sometimes this penalty can be reduced to zero.

Yes, the source of this stalling of the pipeline is the fact that some instructions can have "multi-cycle" stages. However, the use of "multi-cycle" in this context is not always the same as the use of "multi-cycle" in context of STA tools. The pipeline multi-cycle stage can be a combinatorial stage which takes few clock cycles (in which case it should also be defined as multi-cycle for STA tools), or it can be a sequential stage which requires more than a single clock cycle to complete (in which case it still needs to meet timing as a single cycle stage).

\$\endgroup\$
  • \$\begingroup\$ Consider a 10-stage pipeline with a 32-bit floating point add instruction FPADD Dest, Src1, Src2.FPADD instrctn goes through various stages (Fetch, Decode, ..) & takes 1cc in each of these stages before reaching Exec stage. The actual addition happens in Exec stage where it takes 4 Clock cycles to perform this operation. This could happen in 2 ways: 1:FP Adder unit is itself pipelined with 4 pipeline registers 2:If its purely combinational path, then it is marked as multi-cycle path of 4 cycles. Overall FP ADD still requires at least 10+4=14 cycles (LATENCY) to come out of pipeline. \$\endgroup\$ – nurabha Sep 26 '13 at 17:47
  • \$\begingroup\$ If we execute 101 independent FPADD instructions, it would take 14+100*1= 114 clock cycles. This give IPC (throughput or completion rate) = 101/114 = 0.88. So if someone makes the statement that "Each FP ADD operation takes 4 cc" only makes sense for the actual FP operation happening in Exec stage. Neither latency nor instruction throughput has anything to do with it. Isn't it ? \$\endgroup\$ – nurabha Sep 26 '13 at 17:52
  • \$\begingroup\$ @nurabha, if each exec stage stalls the pipeline for 3 additional clock cycles, how comes the throughput will be at 1? I believe that the execution of 101 such instructions will take \$ \sim 14+100*4=414\$ clock cycles. \$\endgroup\$ – Vasiliy Sep 26 '13 at 17:57
  • \$\begingroup\$ Please correct me if I am wrong. I think 3 cycle stalls will be caused by exec stage only when FP adder is non-pipelined unit i.e. it is a combinational unit with 4cc delay (multi-cycle). However if the FP adder is itself pipelined with 4 pipeline registers, then stalls would not happen in exec stage as 4 operand pairs can be in flight together in exec stage ? So your answer is correct for 1st case and my answer is correct for 2nd case ? \$\endgroup\$ – nurabha Sep 26 '13 at 18:13
  • \$\begingroup\$ @Vasily: With your 414 clock cycles. CPI ~ 4.15. Only now the statement "Each FP Add operation takes 4 cc" make sense. \$\endgroup\$ – nurabha Sep 26 '13 at 18:30

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.