How can the number of clock cycles required to complete an instruction in a pipelined processor less than pipeline latency?

Question

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 ?

Answer 1

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).

Answer 2

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).

Answer 3

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).