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

21–30 of 102 posts

Re: Execution units are often pipelined

#21

Post by adrian_b »

paulsutter wrote: post #8
codedokode wrote: post #7

What I am interested to know is who invented pipelining? I tried googling but without much success. Does anybody know?

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'

Actually there are 2 ways to do more than one processing step at a time: parallel execution and pipelined (a.k.a. overlapped) execution.

Both ways had been used for many centuries for the manufacturing of complex things, as ways to organize the work of multiple workers.

Re: Execution units are often pipelined

#23

Post by BeeOnRope »

delusional wrote: post #3

Is this still the case if I have different ALU operations. Say I have a single ALU on a single x86 core. Would the ALU be able to interleave say ADD and MULs? or would I incur the latency measure for each operation switch? I know that some ALU's have multiple ADD complexes, and I assume that would influence the answer, hence why I specified x86.

Yes, it applies to different operations. E.g. you could interleave two or three different operations with 3 cycle latency and 1 cycle inv throughput on the same port and get 1 cycle inv throughput in aggregate for all of them. There is no restriction that they must be same operation.

In some cases mixing operations with _different_ latencies on the same execution port will leave you with less throughput than you expect due to "writeback conflicts", i.e., two instructions finishing on the same cycle (e.g., a 2 cycle operation starting on cycle 0 and a 1 cycle operation on cycle 1, will both finish on cycle 2 and in some CPUs this will delay the results of one of the operations by 1 cycle due to a conflict).

Re: Execution units are often pipelined

#24

Post by NotCamelCase »

zelos wrote: post #10
paulsutter wrote: post #8

Earlier 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?

Is it really that much different than e.g. a cook preparing carrots while onions are being cooked? Nobody needed to invent this as far as my knowledge of history goes; so, maybe there really is nothing new under the sun :)

Joking aside, of course, the ingenuity lies in finding a fitting solution to problem at hand, as well as knowing how to apply it.

Re: Execution units are often pipelined

#25

Post by taneq »

adrian_b wrote: post #21
paulsutter wrote: post #8

Earlier 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'

Actually there are 2 ways to do more than one processing step at a time: parallel execution and pipelined (a.k.a. overlapped) execution. Both ways had been used for many centuries for the manufacturing of complex things, as ways to organize the work of multiple workers.

Slightly offtopic but did we go to uni together and team up on a couple of demo compos and VJ some events? If so hey it's been ages and whats up? :D If not, cool name and stuff. :)

Re: Execution units are often pipelined

#26

Post by cogman10 »

adrian_b wrote: post #15
PittleyDunkin wrote: post #11

Earlier quoted context omitted.

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…

The earliest "pipeline" example I can find is the portsmouth block mills [1] implemented by Marc Brunel[2]/Henry Maudslay[3] around 1802

[1] https://en.wikipedia.org/wiki/Portsmouth_Block_Mills

[2] https://en.wikipedia.org/wiki/Marc_Isambard_Brunel

[3] https://en.wikipedia.org/wiki/Henry_Maudslay

Re: Execution units are often pipelined

#27

Post by formerly_proven »

adrian_b wrote: post #15
PittleyDunkin wrote: post #11

Earlier quoted context omitted.

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…

Zuse Z3 had a three stage instruction pipeline.

Re: Execution units are often pipelined

#28

Post by ryukoposting »

If the two ALUs could feed results into each other, that would make things really interesting, especially when you consider the way it would affect reordering.

Imagine if the OP's benchmark had two of those multiplication chains on independent registers:

  mul x1, x0, x0 // a
  mul x2, x1, x1 // b
  mul x3, x2, x2 // c
  mul x4, x3, x3 // d

  mul x6, x5, x5 // e
  mul x7, x6, x6 // f
  mul x8, x7, x7 // g
  mul x9, x8, x8 // h
If you had two independent ALUs, my intuition is that you'd want to dispatch the instructions as AEBFCGDH, interleaving the two chains.

But, if the two ALUs could feed each other, perhaps you'd actually want to leave it in ABCDEFGH order? Hmm.

Re: Execution units are often pipelined

#30

Post by monocasa »

ryukoposting wrote: post #28

If the two ALUs could feed results into each other, that would make things really interesting, especially when you consider the way it would affect reordering. Imagine if the OP's benchmark had two of those multiplication chains on independent registers: mul x1, x0, x0 // a mul x2, x1, x1 // b mul x3, x2, x2 // c mul x4, x3, x3 // d mul x6, x5, x5 // e mul x7, x6, x6 // f mul x8, x7, x7 // g mul x9, x8, x8 // h If yo…

They are able to do this via what's called a bypass network.
Post reply on HN