4
$\begingroup$

I'm currently reading through x86 Assembly Language and C Fundamentals and came across this statement in the second chapter of the book:

If the instruction required is not available in the cache, then a cache miss occurs, necessitating a fetch from main memory. This is referred to as a pipeline stall and delays processing the next instruction. Information is passed from one stage to the next by means of a storage buffer.

Having read the Wikipedia article associated to this, and the book covering one paragraph of this subject that I can find, I have a few glaring questions regarding this.

  • Would a pipeline stall occur if there were no further instructions to fetch from main memory, and if so, would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?

  • Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?

  • If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle for both/all of the stages that's trying to use the resource, or is there specificity involved based on stage that would allow for one of the stages to complete its instruction given that the cycle was the cycle in which the pipeline stall occurred?

Note: I'm not formally educated in Computer Science so I apologize if these are CS101 questions.

$\endgroup$
3
$\begingroup$

A CPU pipeline has a number of stages.

The exact stages vary between CPUs and some CPUs have very many stages, but obviously the first stage must be Instruction Fetch (IF) and the second stage must be Instruction decode (ID).
If an instruction is not in the cache it cannot be fetched and delays occur.
Let's call our missing instruction $A$.

The only way for the next instruction $B$ to not be delayed is if $B$ is in the cache and the CPU supports out of order instruction and $B$ does not depend on the outcome of instruction $A$ and the CPU allows fetching from memory and the cache at the same time and the CPU knows where $B$ is located.

Phew that's a lot of if's.
Let's unpack the various issues.

Cache
Because barring jumps instructions are fetched sequentially it's moderately unlikely that $A$ is not cached, whilst $B$ is. But it does happen.

Out of order support
Most CPU's support OoO execution, so there are no problems there.

Independent instruction
Some instructions have no dependencies. e.g. xor rax,rax will zero out rax no matter what.
However we don't know what instruction $A$ does. If it's an unconditional jump it may just jump over $B$.
Still the CPU might elect to execute B speculatively, if the gamble pays off valuable time is gained.

Fetching from memory and cache at the same time
Current x86/x64 CPU's do not support this.
The reason why will become clear in the next paragraph.

Where is $B$ located?
The x86 architecture has a variable length instruction.
A x86/x64 instruction can be anywhere between 1 and 15 instructions long.
Only when the pipeline gets to the Instruction Decode (ID) stage does the CPU know how long the instruction is.
So there is no way for the CPU to know where $B$ starts until $A$ has been decoded.
In normal execution the CPU solves this by either (a) pre-decode instructions and store the instruction lengths in the cache (as meta data), or (b) fetch large chunks of data in one go and parallel decode this or both.
Intel uses strategy b, AMD uses a+b.

However it is impossible to know where $B$ starts without knowing the instruction length of $A$. There are 15 possible lengths and the CPU will not start 15 possible speculative executions, that's would just be a waste of silicon :-).

If the x86 architecture had fixed instruction length then speculative execution would have been an option. The fetch and decode stages pose no problem and perhaps even more stages could be performed.
However CISC and variable instruction length throws a big spanner in the works.

Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?

The details are very complex, but, yes, a stall can and does occur at every stage.
Common stall reasons are:

  • mispredicted jumps. This causes a stall because the pipeline needs to be emptied and reread from some as yet unknown address.
  • instruction $B$ depends on the outcome of instruction $A$. This is called a dependency chain. These chains can be arbitrary long.
  • both instructions $A$ and $B$ require some piece of expensive hardware. The CPU has only one of these available and thus $B$ must wait for $A$ to finish.

If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle

That depends if the resource allows pipelining.
In modern CPU's the answer is yes. Expensive hardware is capable of pipelined operation.
E.g. two multiplication instructions will execute in 4 cycles given that a MUL reg,reg has a 3 cycle latency and a third unrelated instruction can execute in parallel.

would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?

Yes, e.g. if the memory has been swapped out to disk and the disk takes indefinitely long the CPU will just wait.
Well the hardware will generate a page fault exception, but that's beside the point

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