Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Execution units are often pipelined

blog.xoria.org

Post reply on HN
Print view View original

91–100 of 102 posts

Re: Execution units are often pipelined

#91

Post by tjoff »

eigenform wrote: post #71
BeeOnRope wrote: post #70

Earlier quoted context omitted.

We are interested in the software visible performance effects of pipelining. For small benchmarks that don't miss in the predictors or icache, this mostly means execution pipelining. That's the type of pipelining the article is discussing and the type of pipelining considered in instruction performance breakdowns considered by Agner, uops.info, simulated by LLVM-MCA, etc. I.e., a lot of what you need to model for tig…

Adding to this: the distinction is that an entire "instruction pipeline" can be [and often is ] decomposed into many different pipelined circuits. This article is specifically describing the fact that some execution units are pipelined. Those are different notions of pipelining with different motivations: one is motivated by "instruction-level parallelism," and the other is motivated by "achieving higher clock rates.…

> one is motivated by "instruction-level parallelism," and the other is motivated by "achieving higher clock rates."

Which are exactly the same thing? For exactly the same reasons?

Sure, you can focus your investigation on one or the other but that doesn't change what they are or somehow change the motivations for why it is being done.

And you can have a shorter clock period than your non-pipelined multiplier just fine. Just that other uses of that multiplier would stall in the meantime.

Re: Execution units are often pipelined

#93

Post by tliltocatl »

atq2119 wrote: post #84
ajross wrote: post #52

Earlier quoted context omitted.

In-order parallel designs are "VLIW". The jargon indeed gets thick. :) But as to OO: the whole idea of issuing sequential instructions in parallel means that the hardware needs to track dependencies between them so they can't race ahead of their inputs. And if you're going to do that anyway, allowing them to retire out of order is a big performance/transistor-count win as it allows the pipeline lengths to be differen…

VLIW means Very Large Instruction Word . It is a property of the instruction set, not of the processor that implements it. You could have a VLIW ISA that is implemented by a processor that "unrolls" each instruction word and mostly executes the constituent instructions serially.

Also you can have out-of-order VLIW. Later Itaniums were like that, because turns VLIW doesn't help much with random memory access latency.

Re: Execution units are often pipelined

#94

Post by Joker_vD »

mpweiher wrote: post #58
Joker_vD wrote: post #54

Earlier quoted context omitted.

> the best way to simulate them is simply to run them! And it's quite sad because when you are faced with choosing between two ways to express something in the code, you can't predict how fast one or another option will run. You need to actually run both, preferrably in an environment close to the prod, and under similar load, to get accurate idea which one is more performant. And the worst thing is, you most likely…

> you can't predict how fast one or another option will run "The best way to predict the future is to invent it" -- Alan Kay > You need to actually run both Always! If you're not measuring, you're not doing performance optimization. And if you think CPUs are bad: try benchmarking I/O. Operating System (n) -- Mechanism designed specifically to prevent any meaningful performance measurement (every performance engineer…

My point is, it's impossible to test everything in a reasonable timeframe. It would be much, much more convenient to know (call it "having an accurate theory") beforehand which approach will be faster.

Imagine having to design electronics the way we design performant programs. Will this opamp survive the load? Who knows, let's build and try these five alternatives of the circuit and see which one of them will not blow. Oh, this one survived but it distorts the input signal horribly ("yeah, this one is fast, but it has multithreading correctness issues and reintroduction of locks makes it again about as slow"), what a shame. Back to the drawing board.

Re: Execution units are often pipelined

#95

Post by adrian_b »

GregarianChild wrote: post #90
adrian_b wrote: post #88

Earlier quoted context omitted.

Parallel execution can exist at many different levels, e.g. at processor level you can have multiple processors executing in parallel some threads. At instruction level, the execution of instructions is an iterative process, so like for any other iterative process parallelism or pipelining or both parallelism and pipelining may be used. Most modern CPUs use both parallelism and pipelining in the execution of instruct…

> both parallelism and pipelining You are right, but this can be make more precise: pipelining is a specific form of parallelism. After all the different stages of the pipeline are executing in parallel.

You use "parallelism" with a different meaning than me.

I use "parallel" with its original meaning "one besides the other", i.e. for spatial parallelism.

You use "parallel" with the meaning "simultaneous in time", because only with this meaning you can call pipelining as a form of parallelism.

You are not the only one who uses "parallel" for "simultaneous in time", but in my opinion this is a usage that must be discouraged, because it is not useful.

If you use "parallel" with your meaning, you must find new words to distinguish parallelism in space from parallelism in time. There are no such words in widespread use, so the best that you can do is to say "parallel in space" and "parallel in time", which is too cumbersome.

It is much more convenient to use "parallel" only with its original meaning, for parallelism in space, which in the case of parallel execution requires multiple equivalent execution units (unlike pipelined execution, which in most cases uses multiple non-equivalent execution units).

When "parallel" is restricted to parallelism in space, pipelining is not a form of parallelism. Both for pipelining and for parallelism there are multiple execution units that work simultaneously in time, but the stream of data passes in parallel through the parallel execution units and in series through the pipelined execution units.

With this meaning of "parallel", one can speak about "parallel execution" and "pipelined execution" without any ambiguity. It is extremely frequent to have the need to discuss about both "parallel execution" and "pipelined execution" in the same context or even in the same sentence, because these 2 techniques are normally combined in various ways.

When "parallel" is used for simultaneity in time it becomes hard to distinguish parallel in space execution from pipelined execution.

Re: Execution units are often pipelined

#96

Post by adrian_b »

formerly_proven wrote: post #27
adrian_b wrote: post #15

Earlier quoted context omitted.

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…

Zuse Z3 had a three stage instruction pipeline.

If this is true, then it resembles in this feature the IBM SSEC, another electromechanical computer with a three stage instruction pipeline, which however was built only later, after WWII, between 1944 and 1947.

The main inspiration for IBM SSEC has been Harvard Mark I, an earlier electromechanical computer built by IBM based on a design done mostly by Howard Aiken, but it would not have been impossible for some information about the Zuse computers to have reached IBM after WWII, contributing to the design of the SSEC.

Re: Execution units are often pipelined

#97

Post by mshockwave »

gpderetta wrote: post #89
mshockwave wrote: post #73

divisions, regardless of integer or floating point, are usually NOT pipelined though

I haven't seen any cpu with a fully pipelined division, but division units are at least partially pipelined in recent-ish cpus. They usually can start a new division well before the previous one has stopped executing. ALUs in Recent Apple cpus can actually start a new division every other cycle (in addition to having an abnormally low latency), which is very impressive.

> ALUs in Recent Apple cpus can actually start a new division every other cycle (in addition to having an abnormally low latency)

That's indeed impressive.

I'll argue that we're definitely capable of making fully pipelined divisions, it's just that it's usually not worth the PPA.

Re: Execution units are often pipelined

#98

Post by mafribe »

adrian_b wrote: post #95
GregarianChild wrote: post #90

Earlier quoted context omitted.

> both parallelism and pipelining You are right, but this can be make more precise: pipelining is a specific form of parallelism. After all the different stages of the pipeline are executing in parallel.

You use "parallelism" with a different meaning than me. I use "parallel" with its original meaning "one besides the other", i.e. for spatial parallelism. You use "parallel" with the meaning "simultaneous in time", because only with this meaning you can call pipelining as a form of parallelism. You are not the only one who uses "parallel" for "simultaneous in time", but in my opinion this is a usage that must be disco…

The pipeline stages (say: fetch, decode, execute, memory access, register write back), are organised "parallel in space" as transistors on chip. The point of having a pipeline is so the stages can execute "parallel in time".

More generally, parallel in space is interesting because it is a necessary precondition for parallel in time.

Re: Execution units are often pipelined

#99

Post by adrian_b »

mafribe wrote: post #98
adrian_b wrote: post #95

Earlier quoted context omitted.

You use "parallelism" with a different meaning than me. I use "parallel" with its original meaning "one besides the other", i.e. for spatial parallelism. You use "parallel" with the meaning "simultaneous in time", because only with this meaning you can call pipelining as a form of parallelism. You are not the only one who uses "parallel" for "simultaneous in time", but in my opinion this is a usage that must be disco…

The pipeline stages (say: fetch, decode, execute, memory access, register write back), are organised "parallel in space" as transistors on chip. The point of having a pipeline is so the stages can execute "parallel in time" . More generally, parallel in space is interesting because it is a necessary precondition for parallel in time .

In its original meaning, which is still the meaning used in mathematics and physics, "parallel" provides more information than just saying that the parallel things are located in different places in space. Such an information can be provided by other words.

One should not say that the pipeline stages are parallel, when the intended meaning is that they are separate or distinct, which is the correct precondition for their ability to work simultaneous in time.

"Parallel" says about two things that they are located side-by-side, with their front-to-back axes aligned, which is true for parallel execution units where the executions of multiple operations are initiated simultaneously in all subunits, but it is false for pipelined execution units, where the executions of multiple operations are initiated sequentially, both in the first stage and in all following stages, but the initiation of an execution is done before the completion of the previous execution, leading to executions that are overlapped in time.

The difference between parallel execution and pipelined execution is the same as between parallel connections and series connections in any kind of networks, e.g. electrical circuits or networks describing fluid flow.

Therefore it is better if the terms used in computing remain consistent with the terms used in mathematics, physics and engineering, which have already been used for centuries before the creation of the computing terminology.

Re: Execution units are often pipelined

#100

Post by BeeOnRope »

eigenform wrote: post #67
ajross wrote: post #17

Earlier quoted context omitted.

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…

> Also IIRC there are still some non-pipelined units in Intel chips, like the division engine, which show latency numbers ~= to their execution time I don't think that's accurate. That latency exists because the execution unit is pipelined. If it were not pipelined, there would be no latency. The latency corresponds to the fact that "doing division" is distributed across multiple clock cycles.

Division is complicated by the fact that it is a complex micro-coded operation with many component micro-operations. Many or all of those micro-operations may in fact be pipelined (e.g., 3/1 lat/itput) , but the overall effect of executing a large number of them looks not very pipelined at all (e.g., 20 of them on a single EU would have 22/20 lat/itput, basically not pipelined when examined at that level).
Post reply on HN