What I am interested to know is who invented pipelining? I tried googling but without much success. Does anybody know?
I'm guessing https://en.wikipedia.org/wiki/Donald_B._Gillies is a good bet for this claim.
Execution units are often pipelined
11–20 of 102 posts
Re: Execution units are often pipelined
#12Unrelated but for benchmarks like these you can just ask the kernel for how many clock cycles you’ve used using proc_pid_rusage rather than hardcoding it.
Re: Execution units are often pipelined
#13For x86 cores this is visible in Agner Fog's instruction performance tables: https://agner.org/optimize/#manuals The latency shows after how many cycles the result of an instruction can be consumed by another, while the throughput shows how many such instructions can be pipelined per cycle, i.e. in parallel.
I believe the throughput shown in those tables is the total throughput for the whole CPU core, so it isn't immediately obvious which instructions have high throughput due to pipelining within an execution unit and which have high throughput due just to the core having several execution units capable of handling that instruction.
Re: Execution units are often pipelined
#14What I am interested to know is who invented pipelining? I tried googling but without much success. Does anybody know?
EDIT: Adrian_B’s sibling comment has even earlier historical examples that illustrate how architecture ideas are as old as the hills.
There are good historical hardware architecture textbooks: Peter Kogge’s “The Architecture of Pipelined Computers” (‘81) mentions that the UNIVAC 1 pipelined IO (from which dedicated IO units sprung out), the IBM 7094 similarly interleaved multiple-state memory access cycles between multiple memory units to increase throughput, and then the IBM STRETCH had a two-part fetch-execute without attempt to address hazards.
So pipelining came out the ad-hoc application of the patterns of interleaving and hiving off functionality to dedicated units. In general, a lot of hardware architecture ideas cropped up very early in big iron, with microcoding even co-existing with them, without all of the extra full ideas being worked out (e.g. forwarding, hazard resolution of all types, etc.)
There’s a whole fun universe of vintage hardware architecture textbooks that get through the essential concepts through historical big iron, if you’re willing to look beyond Hennessy and Patterson and Shen and Lipasti! I am thinking that the latter might have references to other historical textbooks on pipelining, though. “The Anatomy of a High-Performance Microprocessor”, a pedagogical deep-dive into the design of the AMD K6 uarch (up to detailed algorithms and HDL!), will have good references to historical textbooks too since these authors were trained before the crop of “modern” (microprocessor-era) textbooks.
Re: Execution units are often pipelined
#15What I am interested to know is who invented pipelining? I tried googling but without much success. Does anybody know?
I'm guessing https://en.wikipedia.org/wiki/Donald_B._Gillies is a good bet for this claim.
Nope.
1957 in a transistorized computer is far too late for the origin of pipelining.
Pipelining had already been used in computers with vacuum tubes a few years before and it had also been used already a decade earlier in computers with electromechanical relays, i.e. IBM SSEC, which had a 3-stage pipeline for the execution of its instructions (IBM SSEC had a Harvard architecture, with distinct kinds of memories for program and for data).
Before 1959, pipelining was named "overlapped execution".
The first use of the word "pipeline" was as a metaphor in the description of the IBM Stretch computer, in 1959. The word "pipeline" began to be used as a verb, with forms like "pipelining" and "pipelined" around 1965. The first paper where I have seen such a verbal use was from the US Army.
Outside computing, pipelining as a method of accelerating iterative processes had been used for centuries in the progressive assembly lines, e.g. for cars, and before that for ships or engines.
Pipelined execution and parallel execution are dual methods for accelerating an iterative process that transforms a stream of data. In the former the process is divided into subprocesses through which the stream of data passes in series, while in the latter the stream of data is divided into substreams that go in parallel through multiple instances of the process.
Re: Execution units are often pipelined
#16For x86 cores this is visible in Agner Fog's instruction performance tables: https://agner.org/optimize/#manuals The latency shows after how many cycles the result of an instruction can be consumed by another, while the throughput shows how many such instructions can be pipelined per cycle, i.e. in parallel.
I believe the throughput shown in those tables is the total throughput for the whole CPU core, so it isn't immediately obvious which instructions have high throughput due to pipelining within an execution unit and which have high throughput due just to the core having several execution units capable of handling that instruction.
That's true, but another part of the tables show how many "ports" the operation can be executed on, which is enough information to concluded an operation is pipelined.
For example, for many years Intel chips had a multiplier unit on a single port, with a latency of 3 cycles, but an inverse throughput of 1 cycle, so effectively pipelined across 3 stages.
In any case, I think uops.info [1] has replaced Agner for up-to-date and detailed information on instruction execution.
---
Re: Execution units are often pipelined
#17For x86 cores this is visible in Agner Fog's instruction performance tables: https://agner.org/optimize/#manuals The latency shows after how many cycles the result of an instruction can be consumed by another, while the throughput shows how many such instructions can be pipelined per cycle, i.e. in parallel.
FWIW, there are two ideas of parallelism being conflated here. One is the parallel execution of the different sequential steps of an instruction (e.g. fetch, decode, operate, retire). That's "pipelining", and it's a different idea than decoding multiple instructions in a cycle and sending them to one of many execution units (which is usually just called "dispatch", though "out of order execution" tends to connote the same idea in practice).
The Fog tables try hard show the former, not the latter. You measure dispatch parallelism with benchmarks, not microscopes.
Also IIRC there are still some non-pipelined units in Intel chips, like the division engine, which show latency numbers ~= to their execution time.
Re: Execution units are often pipelined
#18For x86 cores this is visible in Agner Fog's instruction performance tables: https://agner.org/optimize/#manuals The latency shows after how many cycles the result of an instruction can be consumed by another, while the throughput shows how many such instructions can be pipelined per cycle, i.e. in parallel.
FWIW, there are two ideas of parallelism being conflated here. One is the parallel execution of the different sequential steps of an instruction (e.g. fetch, decode, operate, retire). That's "pipelining", and it's a different idea than decoding multiple instructions in a cycle and sending them to one of many execution units (which is usually just called "dispatch", though "out of order execution" tends to connote the…
I don't think anyone is talking about "fetch, decode, operate, retire" pipelining (though that is certainly called pipelinig): only pipelining within the execution of a instruction that takes multiple cycles just to execute (i.e., latency from input-ready to output-ready).
Pipelining in stages like fetch and decode are mostly hidden in these small benchmarks, but are visible when there are branch misprediction, other types of flushes, I$ misses and so on.
Re: Execution units are often pipelined
#19These days CPUs are so complex and have so many interdependencies that the best way to simulate them is simply to run them! In most real code the high throughput of these sorts of operations means that something else is the limiting factor. And if multiplier throughput is limiting performance then you should be using SIMD or a GPU.
> These days CPUs are so complex and have so many interdependencies that the best way to simulate them is simply to run them!
True. You can imagine how difficult it is for the hardware engineer designing and testing these things before production!
Re: Execution units are often pipelined
#20Earlier quoted context omitted.
Probably the first person to ask, 'how can I speed up this processor, maybe there's a way to do more than one processing step at a time for each instruction'
Presumably by analogy to production lines in factories?
Actually, it’s just obvious when you design the most basic ALU and the circuits for doing the carry.