0
$\begingroup$

I've been told that if you understand a pipeline then you should be able to make it with any depth, but I can only do 4 stages and maybe 5 if the memory is not too slow. How can I learn how to make infinite pipelines?

$\endgroup$
1
$\begingroup$

The thing about the MIPS/DLX-ish pipeline that you're probably talking about is that all of the pipeline control is central. There is a pipeline/hazard circuit which knows what's going on everywhere, and it does all the hard work.

This is probably why you asked the question: you can already see that there is no way this will scale!

There are three main techniques to construct a deep pipeline:

  • Nest pipelines and use hierarchical control.
  • Eliminate central control by making control as local as possible.
  • Reduce the need for control by designing the pipeline so that some situations that would require control never happen, or turn into an easier-to-handle control situation.

We'll take a look at these in turn, but bear in mind that all of these techniques can be mixed and matched as appropriate.

Hierarchical control

This is the simplest modification to what you've already seen. The idea here is that each logical unit in a CPU (e.g. instruction fetch unit, integer unit, load/store unit) may be a small pipeline by itself. Then you can decide what control needs to happen within that unit and what control needs to happen between units.

If you think about an instruction fetch unit, for example, there are various reasons why it might stall: it might be experiencing a cache miss, it might be recovering from a mispredicted branch, or whatever. In many situations, the control for the core as a whole may not care why the IFU is stalling, it only matters that it is stalling, because that means it isn't supplying instructions to the next stage. So the IFU may implement its own control, and communicate with higher-level control using coarser signals.

An extreme example of this is to use a coprocessor design. Coprocessors don't have to be on separate chips; the MIPS architecture uses a coprocessor for the MMU, for example. It isn't really a separate processor, but it is wired up to the core's control system as if it were.

This was an especially popular technique back in the day when CPUs came on more than one physical die such as POWER1.

Local control

Based on the previous idea, another way of coordinating different units is to just let them communicate with their surrounding units. There will probably still need to be some central control, but this could be reserved for large-scale events such as recovering from a fault or bad speculation.

So, for example, a unit which can't take any more work at the moment (whether it's because it's doing a multi-cycle operation, stalled on a cache miss, or stalled because the unit it needs to send a result to is itself busy) might simply provide a signal which says "I cannot take any more work right now". Any unit which wants to feed it work looks for that signal.

Another example of something that could reasonably be called "local control" is to use busses with arbitration. You can move data through the CPU using busses, and if two units want to write to the same bus at the same time, they decide between them that one will back off. You might use this in a Tomasulo pipeline.

An extreme example of local control is the counterflow pipeline. This is an example of a pipeline which can be arbitrarily deep using only local control, to the point where the pipeline could in principle be made completely asynchronous.

Redesign

If it is possible to eliminate the need for control by redesigning the pipeline, this is always worth considering. The classic example is register renaming, which effectively eliminates WAR hazards for registers. If a hazard is impossible, there doesn't need to be any control for it!

There are endless variations on this theme. For example, register renaming when there aren't "enough" physical registers available turns the WAR hazard into a stall in the rename stage. A stall early in the pipeline may be easier to control than a hazard late in a deep pipeline, because there are fewer cases to consider.

Another variation is to use speculation with a general recovery mechanism. If you think of a SPARC/MIPS-like pipeline, there is a delay slot after every branch, which is only possible because the pipeline is short. In a deeper pipeline, the most common solution is to speculate the branch and then use a general pipeline recovery mechanism if we got it wrong.

It's a similar story with instructions that could fault. Any memory access could cause a page fault. Any division could be a division by zero. We effectively "speculate" that this didn't happen, and fall back on the general recovery mechanism if it actually did. That way we don't need special control for a page fault.

A good place to start on this is Mike Johnson's book Superscalar Microprocessor Design (1991). It's old but it's full of good stuff that explains how these sorts of things actually work in practice.

$\endgroup$
  • $\begingroup$ Ooh, how did you learn all these cool things? I also want to be a pipeline expert. $\endgroup$ – Benny Sweetz Feb 2 '18 at 9:12
  • $\begingroup$ I read a lot! That book reference at the end is particularly good. $\endgroup$ – Pseudonym Feb 2 '18 at 13:14

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.