4
$\begingroup$

I know what vectorizing is, and I know what pipelining is. I assume "vector pipelining" might mean vectorizing in such a way that vector instructions can be pipelined. Is this a new or coming feature in modern architectures with a more specific meaning?

Update on March 5

I consider this one pretty well-answered. I indeed was unclear about whether I was looking for "a new thing" or the vector pipelining of yore (Sorry Brian!). I encountered this phrase in the context of future hardware technology and wanted to know if I was missing something. Thanks to everyone for their insight/contributions. I'll be more careful with my questions in the future.

$\endgroup$
  • $\begingroup$ Could you share the reference where you saw this used in a new context? $\endgroup$ – Brian Borchers Mar 5 '15 at 16:38
  • $\begingroup$ I don't think the phrase was being correctly used, given the response here. $\endgroup$ – Aron Ahmadia Mar 6 '15 at 4:48
6
$\begingroup$

The term "vector pipeline" was used in the 1970's to describe vector processing at a time when a single vector instruction might (for example) compute the sum of two vectors of floating point numbers using a single pipelined floating point arithmetic unit. Pairs of floating point numbers would be brought from memory into the pipelined arithmetic unit to be added together, and once the pipeline filled, you'd get one sum out per cycle and these sums would be streamed back into memory. See this 1977 article by Ramamoorthy and Li:

http://web.ece.ucdavis.edu/~vojin/CLASSES/EEC272/S2005/Papers/Ramamoorthy_mar77.pdf

Early supercomputers like the STAR, ASC, and CRAY-1 implemented vector processing in this way. The basic approach can be modified by adding "vector registers" to store fixed length sections (say 64 elements long) of a vector. Multiple pipelined ALU's can also be used to simultaneously perform the same or different operations on their own vectors. The Cray-1 could "chain" together vector operations so that the output from one vector operation was fed into another operation.

This is somewhat different from the SSE and AVX instructions on modern x86 processors from Intel and AMD. These processors include "Single Instruction Multiple Data" instructions. The processors have multiple parallel floating point arithmetic units that can (for example) take four pairs of floating point numbers from two vector registers, add them together in a single cycle and then store the result in another vector register.

Although the modern implementation of this is vastly different from the way things were done in the 1970's and 80's, from a programming point of view the idea of expressing your algorithm in terms of operations like vector addition is similar.

$\endgroup$
  • 3
    $\begingroup$ It's scary to realize that stuff that was new and exciting when I was an undergraduate student is now ancient history to the current generation... $\endgroup$ – Brian Borchers Mar 5 '15 at 4:12
3
$\begingroup$

I'm barely old enough to understand this, but my understanding is that vector pipelining in the old days allowed for one vector instruction in the pipeline to use the result from the vector instruction ahead of it. I believe that now on the most common vector architectures this is not possible. Vector instructions are pipelined, but only insofar as they are independent.

$\endgroup$
  • $\begingroup$ You may be thinking of the "vector chaining" that could be done on Cray supercomputers. On a machine with multiple pipelined floating point arithmetic units, the output from one pipeline could be input to another pipelined floating point unit. $\endgroup$ – Brian Borchers Mar 5 '15 at 3:49
  • $\begingroup$ @BrianBorchers, yes, precisely. $\endgroup$ – Bill Barth Mar 5 '15 at 4:25
3
$\begingroup$

Instruction Level Parallelism (ILP) is complementary to vectorization, but both require sufficient cache and register space. Our paper (it's fun to learn that your own paper answers your question, eh?) analyzes this in detail for stencil operations on Blue Gene/P, combining vectorization and unroll/jam to expose sufficient parallelism while using registers effectively.

Modern hardware has a floating point instruction latency of a few cycles (more for GPUs). For peak flops, you need to be able to issue FP instructions every cycle. This can be done using ILP or using multiple hardware threads. Hardware threads typically give you access to more registers, but have to share caches and cross-thread communication is relatively more expensive than data dependencies within a single thread. Consequently, it is application- and hardware-dependent whether hardware threads are better or worse than ILP.

$\endgroup$
  • 1
    $\begingroup$ Fair enough to quote my own paper back at me :) I ran into this term in somebody's literature, and I wanted to double-check that it wasn't some completely new thing that I'd never heard of yet. $\endgroup$ – Aron Ahmadia Mar 4 '15 at 21:24
  • 1
    $\begingroup$ Vector pipelining is more than ILP because ILP is easy when you have multiple execution components which may then be used to issue multiple instructions per clock -- super-scalar, which is how POWER was originally designed. Vector pipelining is closer to pipelining SIMD. This was done on the Cray-1, which was able to "chain" vector instructions, with their execution then pipelined. $\endgroup$ – Julie in Austin Mar 5 '15 at 1:21
  • $\begingroup$ Thanks. Are you aware of any modern architectures that work this way? (Aron said offline he saw "vector pipelining" in some nominally modern context, so I didn't think it had anything to do with the old Crays.) $\endgroup$ – Jed Brown Mar 5 '15 at 3:49
  • $\begingroup$ @JedBrown, I'm not aware of any. $\endgroup$ – Bill Barth Mar 5 '15 at 4:47
1
$\begingroup$

This obscure 1990 technical review from the U of Sydney refers to "vector pipelining" as a means of implementing SIMD under the hood — if you suppose that the processor doesn't have enough logic to execute a vector instruction in "full width" at one go, but that the instruction can be broken down into sub-operations (at a level below instruction set level), then there's a performance gain to be had by pipelining those sub-operations, so that processing n times as much data takes less than n times as long.

To illustrate a little bit, suppose that the 8x8=8 bit operation "swizzle" takes 4 clocks, and can be conveniently broken down into four 1-clock stages. Our chip also has eight independent swizzle units.

We can swizzle one pair of values in 4 clocks.

With SIMD, we can swizzle up to 8 pairs of values (64x64=64 bits) by engaging all of the swizzle units at once.

Without pipelining, a 16-wide (128x128=128) swizzle instruction would take 8 clocks, and a 32-wide (256x256=256) swizzle instruction would take 16 clocks.

With vector vector pipelining, the chip can introduce the first 8 operands to the first stage of the swizzle pipeline on clock 1 (to emerge on clock 4), the second set on clock 2 (to emerge on clock 5), etc. Assuming nil overhead of breaking up and reassembling the operands, and assuming I've understood this all right, then you can have a 16-wide swizzle in 5 clocks, and a 32-wide swizzle in 7.

Whether modern architectures have (or need) anything like this, I'm afraid I don't know.

$\endgroup$
  • $\begingroup$ Thanks for digging this up hobbs. I'm not quite sure what you're asking, but pipelining vector operations is indeed a thing, and you don't have to look any further than the various vendor math libraries for examples. $\endgroup$ – Aron Ahmadia Mar 5 '15 at 16:09

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.