# SoA Vectors on SPU

I've read a lot about the benefits of organizing data into 'Structs of Arrays' (SoA) instead of the typical 'Array of Structs' (AoS) to get better throughput when using SIMD instructions. While the 'why' makes total sense to me, I'm not sure how much to do this when working with things like vectors.

Vectors themselves can be tought of as a struct of a (fixed size) array of data, so you could convert an array of these into a struct of X, Y and Z arrays. Through this, you can work on 4 vectors at once as opposed to one at a time.

Now, for the specific reason I'm posting this on GameDev:

Does this make sense for working with vectors on the SPU? More specifically, does it make sense to DMA multiple arrays just for a single vector? Or would it be better to stick with DMAing the array of Vectors and unrolling them into the different components to work with?

I could see the benefit of cutting out the unrolling (if you did it 'AoS'), but it seems like you could quickly run out of DMA channels if you took this route and were working with multiple sets of vectors at once.

(Note: no professional experience with Cell yet, but have been toying around in OtherOS for a while)

-

One approach is to use an AoSoA (read: Array of Struct of Array) approach which is a hybrid of AoS and SoA. The idea is to store N structs worth of data in a contiguous chunk in SoA form, then the next N structs worth in SoA form.

Your AoS form for 16 vectors (labelled 0,1,2...F), swizzled at granularity of 4 structs is:

```000111222333444555666777888999AAABBBCCCDDDEEEFFF
XYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZ
```

for SoA, this is:

```0123456789ABCDEF
XXXXXXXXXXXXXXXX

0123456789ABCDEF
YYYYYYYYYYYYYYYY

0123456789ABCDEF
ZZZZZZZZZZZZZZZZ
```

for AoSoA, this becomes:

```01230123012345674567456789AB89AB89ABCDEFCDEFCDEF
XXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZ
```

The AoSoA approach has the following benefits of AoS:

• Only a single DMA transfer is required to transfer a chunk of structs to SPU local memory.
• structs still have a chance of all data fitting in a cacheline.
• Block prefetching is still very easy.

The AoSoA approach also has these benefits of SoA form:

• You can load data from SPU local memory directly into 128-bit vector registers without having to swizzle your data.
• You can still operate on 4 structs at once.
• You can fully utilize the SIMD'ness of your vector processor if there is no basic branching (ie. no unused lanes in your vector arithmetic)

The AoSoA approach still has some of these drawbacks of SoA form:

• object management has to be done at swizzling granularity.
• random access writes of a full struct now needs to touch scattered memory.
• (these can turn out to be non-issues depending on how you organize/manage your structs and their lifetime)

BTW, these AoSoA concepts apply very well to SSE/AVX/LRBni, as well as GPUs which can be likened to very wide SIMD processors eg. 32/48/64 wide depending on the vendor/architecture.

-
I don't see how this offers any advantage over not packing them per component unless you're packing non-vector data that you actually use as floats - although I see your AoS excludes W, which would not seem very memory access friendly, I guess in that case there is a win. Also note that SPUs have no cache lines except for communicating with main memory. – Kaj Aug 4 '10 at 21:48
1. As with all things, your mileage may vary depending on your exact data/algorithm/processor. In register constrained cases, avoiding the need for 4 temp registers before you can shuffle all your X fields into the same register can be useful. But again, YMMV. 2. My answer was more general because the concepts transfer well within the field of data parallel programming; cache lines considerations are more pertinent to GPU/SSE but I felt I should mention them all the same :) – jpaver Aug 5 '10 at 0:10
Fair enough, I stand enlightened and shall learn to critique more subtly! Thanks for sharing your insight :o) – Kaj Aug 5 '10 at 4:04

SPUs are actually an interesting special case when it comes to vectorizing code. Instructions are divided into "arithmetic" and "load/store" families, and the two families run on separate pipelines. The SPU can issue one of each type per cycle.

Math code is obviously heavily bound by math instructions - so usually mathy loops on SPU will have lots and lots of open cycles on the load/store pipe. Since shuffles happen on the load/store pipe, you often have enough free load/store instructions to swizzle xyzxyzxyzxyz form into xxxxyyyyzzzz form without any overhead at all.

This technique is in use at Naughty Dog at least - see their SPU assembly presentations (part 1 and part 2) for details.

Unfortunately the compiler is often not smart enough to do this automatically - if you decide to go this route you'll need to either write assembly yourself or unroll your loops using intrinsics and check the assembler to make sure it's what you want. So if you are looking to write general cross-platform code that happens to run well on SPU, you may want to go with SoA or AoSoA (as jpaver suggests.)

-
Ah, we agree after all :o) Swizzle on the SPU if you need it, time enough to do it there. – Kaj Aug 4 '10 at 23:36

As with any optimisations, profile! Readability comes first, and should only be sacrificed when profiling identifies a particular bottleneck and you have exhausted all your options for tuning the high level algorithm (the fastest way to do the work is to not have to do the work!) You should always reprofile following any low level optimisation to confirm that you really have made things faster rather than the opposite, especially with pipelines as quirky as the Cell's.

What techniques you use then will depend on the particulars of the bottleneck. In general, when working with vector types, a vector component you ignore in a result represents work wasted. Switching SoA / AoS does not make sense unless it allows you to do more useful work by filling such unused components (e.g. one dot product on PS3's PPU vs four dot products in parallel in the same amount of time). To address your question, spending time shuffling components around just to perform one operation on a single vector sounds like a pessimisation to me!

The flip side on SPUs is that the bulk of the cost of small DMA transfers is in setup; anything less than 128 bytes will take the same number of cycles to transfer, and anything less than about a kilobyte only a few cycles more. So don't worry about DMAing more data than you strictly need; reducing the number of sequential DMA transfers triggered, and performing work while DMA transfers are happening - and therefore unfolding loop prologues and epilogues to form software pipelines - is key to good SPU performance, and it is easiest to deal with corner cases by fetching extra data / discarding partially computed results than jumping through hoops to try to arrange for the exact amount of data that is necessary to be read and processed.

-
If you DO end up unpacking them, as per the AOSAO approach, at least pull in multiple vectors at once indeed. Also you'd want to pull in a batch, and while processing those pull in the next batch. While sending out the first batch, you process the second and pull in the third. That way you hide as much latency as you can. – Kaj Aug 4 '10 at 22:04

No, that would not make much sense in general as most vector opcodes operate on a vector as a whole and not on seperate components. So you can already multiply a vector in 1 instruction, whereas with splitting up the seperate components you'd spend 4 instructions on it. So since you basically do a lot of operations in general on part of a struct you're better of packing them in an array, but you hardly ever do things only on one component of a vector, or wildly different on each component so breaking them out wouldn't work.
Of course, if you do find a situation where you have to do something to only the (say) x components of vectors it might work, however the penalty of swizzling everything back when you need the actual vector wouldn't be cheap so you could wonder if you shouldn't use vectors to begin with but just an array of floats that happen to allow for vector opcodes to do their specific calculations.

-
You're missing the point of SoA for vector math. You rarely ever have only one object you're working on - in practice you're iterating an array and doing the same thing to many objects. Consider doing 4 dot products. If you're storing vectors as AoS in xyz0 form, taking the dot of two vectors requires multiply-shuffle-add-shuffle-add - 5 instructions. Doing 4 dot products requires 20 instructions. On the other hand, if you have 8 vectors stored SoA fashion (xxxx, yyyy, zzzz, xxxx, yyyy, zzzz) you can do 4 dot products with only 3 instructions (mul, madd, madd) - that's over 6 times faster. – Charlie Aug 4 '10 at 23:08
Fair point. However, two observations. I would always keep the W present so I wouldn't need 20 instructions, secondly, most of the remaining overhead can be hidden in the latency of other instructions - your tight loop would suffer from severe pipeline stalls, no? making the 6 times is a theoretical optimization. So, while yes, you want to batch your operations - hardly ever will you just need to do a rapid batch of dot products without anything else to do on said data. The cost of deswizzling/scatter on the PPU side would be too much of a sacrifice for me. – Kaj Aug 4 '10 at 23:24
Groan, I stand corrected - on SPU I would need 20 if done naively (but I would shuffle in place). It's one of the things where I ended up doing a lot of swizzles to get it optimal. 360 has a nice dot intrinsic (but lacks the awesome bit manipulation). – Kaj Aug 5 '10 at 0:33
Yeah, now that I think of it, if you're trying to do "4 dot products" you can do rather better than 20 instructions because you can combine some of the later adds. But having your vectors in registers as xxxx, yyyy, zzzz - whether you swizzled or stored as SoA - gets rid of those shuffles completely. Anyway, you're right that SoA makes branchy logic code slower - but I would argue that the solution in many cases like that is to bucket your data and refactor the branchy logic into nice flat loops. – Charlie Aug 5 '10 at 0:53
Agreed. I am fairly sure if I go over my old SPU code (can't, previous company) there's instances where I did move it into xxxxyyyyzzzz format for optimization without realizing it specifically. I never offered it from the PPU in that format though. Mind you, OP what contemplating dma-ing x,y,z in seperately. That definitely wouldn't work for me. I'd also (as I did) would rather swizzle locally as not everything works nicer in xxxxyyyyzzzz format. Gotta pick your battles I guess. Optimizing for SPU is a blast and you feel awfully clever once you got that tight solution :o) – Kaj Aug 5 '10 at 3:59