Grand Unified Theory of SIMD

Glen Low writes " All of a sudden, there's going to be an Altivec unit in every pot: the Mac Mini, the Cell processor, the Xbox2. Yet programming for the PowerPC Altivec and Intel MMX/SSE SIMD (single instruction multiple data) units remains the black art of assembly language magicians. The macstl project tries to unify the architectures in a simple C++ template library. It just reached its 0.2 milestone and claims a 3.6x to 16.2x speed-up over hand-coded scalar loops. And of course it's all OSI-approved RPL goodness. "

Comments

Altivec

[BWJones]

For those who want a little background on Altivec, of course Wiki has a description here. Apple, who now ships Altivec in every system they make has a pretty good page here and Motorola nee Freescale has one here.

The benefits of Altivec can be truly astounding for those processes that can be "vectorized". After all putting these kinds of calculations in hardware has got it all over software computation. It kind of reminds me of when I got one of those Photoshop accelerator hardware cards (Radius Photoengine with 4 DSPs on a daughter card linked to the Thunder series video card) for my IIci. Photoshop filter functions ran faster on that IIci than they did on much later PowerPC systems simply because you now had four hardware DSPs running your image math.

Re:Altivec

[shawnce]

Just pick a few items out ...

Apple provides source code for some of their vector libraries

Re:Altivec

[mod_critical]

Altivec == Velocity Engine

And is part of every G4

More AltiVec Goodness

[LordRPI]

Apple has had AltiVec optimized libraries for DSP and such since the early releases of OS X.

Umm

[TheKidWho]

Doesn't XCode have a feature that lets you "vectorize" certain parts of your code already?

Re:Umm

[Richard_at_work]

The next version of Xcode will support autovectorisation, but I dont think it does it atm.

A little background

[xXunderdogXx]

From the Wikipedia article on SIMD:

An example of an application that can take advantage of SIMD is one where the same value is being added to a large number of data points, a common operation in many multimedia applications. One example would be changing the brightness of an image. Each pixel of an image consists of three 8-bit values for the brightness of the red, green and blue portions of the color. To change the brightness, the R G and B values are read from memory, a value is added (or subtracted) from it, and the resulting value is written back out to memory.

With a SIMD processor there are two improvements to this process. For one the data is understood to be in blocks, and a number of values can be loaded all at once. Instead of a series of instructions saying "get this pixel, now get this pixel", a SIMD processor will have a single instruction that effectively says "get all of these pixels" ("all" is a number that varies from design to design). For a variety of reasons, this can take much less time than it would to load each one by one as in a traditional CPU design.

But of course I'm sure everyone here knew that..

Re:A little background

[DLWormwood]

How is this different for MMX?

Based on personal recollections reenforced by a quick Wiki'ing, MMX's problem wasn't the concept itself, but Intel's braindead constraints placed on x86 support for vectors. MMX recycled the same registers as used for floating point math, causing expensive context switches between each mode and only allowing integer math to be vectorized. Intel eventually developed SSE to work around some of the bottlenecks, but the eventual dominance of GPUs on the PC platform reduced the development priority for vector math in the CPU.

Re:A little background

[Dominic_Mazzoni]

Quick summary:

MMX (x86): 8-byte registers, only integer operations
SSE (x86): 16-byte registers, single-precision float ops
AltiVec (PPC): 16-byte registers, integer and single-precision float ops
SSE2 (x86): 16-byte registers, double-precision float ops

In order to implement many complex algorithms on x86, you need to use a motley combination of MMX and SSE. There are many flaws in both; lots of very useful instructions are missing, and MMX can't be used in conjunction with non-SIMD floating-point operations without a huge expensive context switch. One of the biggest flaws in MMX/SSE that I found was the lack of instructions to shuffle data around within a (8-byte or 16-byte) register. The only advantage on a modern x86 CPU is SSE2, which is the only SIMD unit with double-precision floats. But you can only work with two doubles at a time, so the speedup is not that great.

AltiVec, on the other hand, included both floats and integers right from the start, with no penalty for switching between them, and it includes a very detailed and useful set of instructions, including an awesome shuffle instruction. My personal experience, coding for both, is that AltiVec is about twice as useful as MMX/SSE/SSE2 combined.

Also, note that in Mac OS X, many of the standard libraries and system calls are already AltiVec-optimized for you, and Apple also provides a great Vector library with lots of common DSP operations.

Re:A little background

[TheRaven64]

As well as the vDSP libraries, Apple also provide a set of wrapper functions around the vector instructions. These expose the instructions directly, but let the compiler handle register allocation, making using AltiVec directly very easy.

Long thread about using Altivec

[ThousandStars]

The Mac forum at Ars Technica has a long, continuing post about Altivec optimizations and how they should be used. The thread started more than two years ago and still gets relevent points and questions added to it. It's an amazing resource if you're interested in starting.

License issues

[IO ERROR]

Be careful; the "open source" license (PDF) is not GPL-compatible. I don't even think it's BSD-compatible on first reading.

The Reciprocal Public License requires you to release all of your source code if you link to this library, even if your project is personal or used in-house only.

Re:License issues

[IO ERROR]

Simple to understand; if you use it for free, you're expected to release your source code (i.e. the 'reciprocal' part of RPL). If you pay to use it, you don't have to release your source code.

True enough, but using the proprietary license makes it impossible to use this in existing projects without changing the license. Suddenly your open source project is either no longer open source, or doesn't look so attractive.

One of the nicest features of the GPL (and, to be fair, of the BSD license) is that you do not have to release source code if you don't distribute your software. This RPL requires you to release your source code even if you don't distribute your software. And the proprietary license simply isn't appropriate for any type of open source project.

The guy wants to get paid, and that's fine, I want to get paid, too. But he's got no business telling me I have to distribute my source code for an internal project that will never be distributed. He could easily have used a method similar to Trolltech's dual-licensing, but he chose instead to do something a whole lot more obnoxious.

Re:License issues

[IO ERROR]

It sounds like the GPL virus to me.

Look, a troll! The GPL doesn't require you to release your code, unless you distribute it. This RPL thing requires you to release your code, even if you don't distribute it. I've discussed the linking issue elsewhere.

oops

[Anonymous Coward]

Typo...
Propellerheads.SE

Re:16X increase?

[LordRPI]

The principle behind SIMD, or, rather, Single Instruction Multiple Data, is that you can process wide arrays of values in a single instruction. With the PowerPC version of SIMD, also known as AltiVec, you can issue an instruction and have it work with a 128-bit wide register. These registers may contain up to 4 32-bit numbers, 8 16-bit numbers or 16 8-bit numbers. For example, I can load two AltiVec registers with 16 unsigned chars, add them together using Vec_Add() and have it return its results to an AltiVec register. So this in essense is adding 16 values at once and in theory it's good enough for markeing to claim a 16X speedup, but this is rarely the case.

About the RPL

[pavon]

The RPL ( Reciprocal Public License) is an odd choice for this project. It is an even stronger viral copy-left than the GPL, to the point where the FSF takes issue with it. If create a derivative work you are required required to 1) Notify the original author, and 2) Publish your changes even if you only use the program in house. Furthermore, their definition of derivative work is much, much broader than the "linking" definition that the GPL uses.

The fact that it puts these additional requirements / restrictions on the user makes it incompatible with the GPL. In fact, considering the requirements placed on you by the license, I would expect that you will have difficulty incorporating this RPL library into any existing FLOSS project without running into license conflicts. The only thing I can see this being useful for is a new project that you don't mind releasing under the RPL, or with existing BSD style licensed code which you dual license as BSD/RPL (since BSD can be included in anything).

So this library does not appear to very useable for the FLOSS world, although if you want to license it for proprietary software you may.

Re:About the RPL

[geoffspear]

Clearly, we need to get everyone in the world to download the source, make one superficial change, and email the entire thing back to the original developer.

And what happens if the original developer dies? Is everyone prohibited from using his code until the copright runs out in 95 years, as they can't notify him of changes?

Slides about SIMD

[quigonn]

A bit OT, but nevertheless quite interesting to read and it contains information about SIMD instruction sets other than just MMX/SSE: http://www.fefe.de/ccccamp2003-simd.pdf

It's in the compiler

[Mad Hughagi]

Vectorization (SIMD) is built into the Intel compiler. There is no need to hack in assembly as the compiler will do it for you. This is the case with most vendor supplied compilers, as they want to fully exploit their hardware functionality.

The problem is bringing this functionality to OS compilers, which as far as I know, there is not even an OpenMP (threading) implementation, let alone internal vectorization.

already exists

[jeif1k]

SIMD support already exists, in the form of C, C++, and Fortran libraries (usually, as a small part of larger numerical libraries), as well as in language constructs in languages like Fortran.

Read the Altivec mailing list

[kuwan]

A better resource for Altivec and SIMD in general is the SIMDtech.org website and Altivec mailing list. There are tutorials and technical manuals available and the email list is indispensable. While the mailing list is mostly geared towards Altivec optimizations and discussions all SIMD discussion is welcome, including MMX/SSE. There are Apple engineers that read and contribute to the list as well as Motorola/Freescale engineers. It's probably the single best resource available to Altivec programmers and you get to talk directly to the Wizards that created it.

I'm a relative newcomer to the list and it's been an invaluable resource as I've optimized with Altivec.

--
Join the Pyramid - Free Mini Mac

Re:Other way around

[Anonymous Coward]

Or born, like the french word it is: née.

No need for anyone to whip out the online dictionary and tell me "formerly known as" is an acceptable alternative.

Re:OS X Tiger will do it for you

[be-fan]

Actually, Apple's Tiger will get an auto-vectorizing compiler courtesy of the public GCC 4.0 release. The auto-vectorizer wasn't developed in Apple's version of GCC. IBM's GCC team at the Haifa Research Lab developed the vectorizer in the public LNO (loop nest optimization) branch of GCC 4.0. I'm not trying to minimize Apple's contribution here, one of their developers did work on the team, but let's give credit where credit is due.

Yes.

[Trillan]

Yes it does.

Re:Yes.

[homb]

No the current version of XCode uses GCC 3.3 and does NOT support autovectorization.
The page you link to is a page that shows how to code vector-based programs. What the parent is asking is if the standard "Hello World" program can be auto-vectorized with one command-line argument, and that won't work currently.
The next version of XCode (2.0) with GCC 3.4 will support partial auto-vectorization, as another comment said as well.

Maybe it's just Ignorant criticism...

[kuwan]

If you'd actually read what this is all about then you'd have find out that this is a cross-platform library for SIMD programming. You program in standard C++ using std::valarray and you get code optimized for Altivec and MMX/SSE/SSE2/SSE3 without having to do anything else. You don't need to worry about coding to two different libraries on two different platforms nor do you have to worry about learning the platform-specific C intrinsics, alignment issues, head/tail cases, etc.

SIMD programming becomes as easy as this:

float af1 [] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
stdext::valarray <float> v1 (af1, 10); // construct from first 10 elements of af1
stdext::valarray <float> v2 (10, 3.0f); // construct with 10 repeats of 3.0f
stdext::valarray <float> v3 (10); // construct with 10 repeats of 0.0f

v3 = sin (v1) * cos (v2) + sin (v2) * cos (v1);

He claims that the above code is 17.4x faster than Codewarrior MSL C++, 11.6x faster than gcc libstdc++ and 9.5x faster than Visual C++.

Macstl also provides a cross-platform syntax for using vector registers that is similar to using the native C intrinsics on each platform. So while not all of the native operations are available, his cross-platform "vec" API allows you to write cross-platform code without having to learn both the Altivec and MMX/SSE intrinsics (which is a good solution for someone who knows one platform but not the other).

--
Join the Pyramid - Free Mini Mac

Re:16X increase?

[Anonymous Coward]

The concept, and radical performance boost, is in line (pardon the pun) with Expression Templates for C++.

A good example is what happens when you let the compiler decide how to do aritmetic with vectors and matrixes.

Matrix a,b,c,x;
x = a + b + c;

The naked compiler, in combination with your custom Matrix class, will probably unwind the operator overloads to do something like this:

// assuming a reasonable STL w/function inlining
Matrix __t1;
for(int i=0; i<a.width; i++){
for(int j=0; j<a.width; j++){
__ti[i][j] = a[i][j] + b[i][j];
}
}
Matrix __t2;
for(int i=0; i<b.width; i++){
for(int j=0; j<c.width; j++){
__t2[i][j] = __t1[i][j] + c[i][j];
}
}
x = __t2;

All those temporary copies and inlined loops really kill performance.

Now, with an expression library, it handles each arithmetic expression discretely by type. By treating the expressions, as well as the types involved, you can do more sophisticated things. In this case, the Expression Template Library solves the problem thusly:

// using ETL
for(i=0; i<a.length; i++){
x[i] = a[i] + b[i] + c[i];
}

Here the library has carnal knowledge of the data structures involved as well as order of operations to come to such a succint solution.

In the case of MACSTL, its still using these principals of "vectorizing" the expressions as well as unrolling and other traditional optimization techniques. Its also going the extra mile and using processor specific code and/or C code that targets *extremely* well to PPC. For example, the above example would opitmize well using Altivec, due to the platform's built-in vector type; you wouldn't even need a loop for adding several 'vec' instances.

I wish I knew enough about MACSTL and altivec to give a hard example of a 16X speedup. I hope this gets you closer to seeing at least *where* the reducable overhead is coming from. :)

Check out Blitz++'s papers listing for more info:
http://www.oonumerics.org/blitz/papers/