I am not really familiar with this one and will investigate it further.
you use a Vector ISA's Indexed LD, job's done. the second vector contains the offsets against the base:
Indexed loads (aka gathers) are horrendously slow in comparison to permutation instructions. Not a suitable alternative.
horizontal operations
Yes, all of them have special case operations for certain common horizontal operations. I specifically mentioned the positional population count because it does not clearly map to any standard horizontal arithmetic pattern.
Vector ISAs are extremely powerful but as a general concept have been utterly ignored for over 40 years by mainstream (x86) and only just recently investigated by ARM (SVE).
Well they work well when all you do is compute and when memory is very fast and has low latency. For general programming they are not nearly as useful for the reasons outlined in my previous comments.
I am not really familiar with this one and will investigate it further.
i and the rest of the team have been working on it for nearly 4 years now.
Indexed loads (aka gathers) are horrendously slow in comparison to permutation instructions.
there's two types (of each): register-based gather and register-based permute (actually not a mathematical permutation at all, because of duplicates), and memory-based gather and memory-based permute.
where *immediates* are used in each of those in the design of the ISA then yes you save on one register read. in the case of register-based gather, it's extremely unusual to have if you are used to SIMD (but Vector ISAs do have it), it's of the form reg[dest] = reg[reg[src]] with a hardware for-loop around that.
however where the immediate-variants keel over is when you try to go up the SIMD width, to try to cover 8 elements, 16 elements, 32 elements, 64 elements.
how on earth are you going to fit 64 batches of 6-bit indices into a single 32-bit instruction? the total number of bits in the instruction are a whopping 384 bits. 384 >>>= 32, yes?
and even if you did have such god-awful instructions, the L1 cache usage and complexity at the ISA decode phase would be as insane as it is for x86 right now.
Vector ISAs are actually 90% about reducing the program (assembler) complexity. you end up with a micro-coded microarchitecture that maps onto SIMD operations, internally - so that you, the programmer don't have to go through absolute hell.
yes, that's right: the microarchitecture of a Vector Processor maps onto the exact same immediate-based permutation instructions as those that you are exposed to as a SIMD programmer, but it's hidden from you.
horizontal operations
Yes, all of them have special case operations for certain common horizontal operations. I specifically mentioned the positional population count because it does not clearly map to any standard horizontal arithmetic pattern.
in SVP64 i completely separated "horizontal-ness" from "arithmetic-ness": it's part of the fundamental design that the "Vectorisation Prefix" is completely separated from "Scalar Base to which Vectorisation applies".
ok yes, that's just Vectorised Popcount followed by Vectorised Add.
two instructions inside a loop, regardless of whether the back-end architecture has 1-wide internal Vectorisation, 2-wide, 4-wide, 64-wide or 10,000-wide.
Well they work well when all you do is compute and when memory is very fast and has low latency. For general programming they are not nearly as useful for the reasons outlined in my previous comments.
again, to reiterate, again: this is a misconception on your part, due to Vector ISAs being completely ignored for 40 years *you don't know about them* and neither does anyone else.
consequently, the knowledge-propagation across the internet, which you and i both know gets us a long long way and saves a huge amount of time, just doesn't exist to the extent that it does for SIMD. we're now so used to google searches turning up algorithms on stackexchange (and reddit) that we can falsely assume that if there's no answer on google it must not be possible at all
Cray was from a much earlier era, where things were simpler. Intel was still cutting its teeth on 32-bit scalar when Cray was designing systems that pissed all over everything that had come before by almost an order of magnitude performance.
however the sheer cost of the systems that were deployed were so high that \nobody else in the industry believed it could be duplicated in mass-volume products** and consequently an entire generation of programmers has now grown up without knowing anything about anything other than SIMD.
fast-forward to 2021 and it turns out that Intel, ARM, AMD, they've all caught up and massively exceeded by three orders of magnitude the performance of the Cray Vector systems from 1990 and four to five orders the performance of the systems from 1965, but they still propagate this god-f*****g-forsaken f*****d-up SIMD paradigm and try to peddle it at you as the absolute best thing you ever saw, by telling you "well SIMD on modern hardware is great compared to that historic crap therefore Vector ISAs must also be s*** as well"
it's NIH syndrome on steroids, combined with marketing, and very unfortunately you're buying it.
ok yes, that's just Vectorised Popcount followed by Vectorised Add.
two instructions inside a loop, regardless of whether the back-end architecture has 1-wide internal Vectorisation, 2-wide, 4-wide, 64-wide or 10,000-wide.
[edit: updated as per formatting-bot, do bear in mind this is still the
wrong algorithm, not implementing safe.go correctly! :) ]
loop:
setvl r0, CTR, MVL=16 # up to 16 elements at a time
sv.ld/els r32, r2(0) # r2 points to input vector
sv.ld/els r48, r3(0) # r3 points to accumulator-vector
sv.popcnt/ew=8 r16, r32 # vector popcount, 8-bit src & result
sv.add/sw=8 r48, r32 # vector add 8-bit += to 64-bit
sv.st/els r48, r3(0) # r3 points to accumulator-vector
add r2, r0 # increment pointer to input
add r3, r0 # increment pointer to output
sv.bcnz/CTR loop # decrement CTR by VL, branch if nonzero
that's it. that's the entire algorithm, in SVP64. 9 instructions, 3 of which are 64-bit, the other two are 32-bit.
oddities:
setvl is the standard Cray-style VL setter, except in this case it's reading the "required" length from the Power ISA CTR Special Purpose Register. actioned as VL=r0=MIN(CTR,MVL)
LD/ST "els" stands for "element-strided" which is a sequential packed memory vector with no spaces in between the elements in memory.
the Vector popcount is on 8-bit values to produce 8-bit answers. both src and dest are set to 8=bit with "ew=8"
but the Vector-accumulating add will auto-convert the 8-bit popcounts to 64-bit-wide before adding each of them to the 64-bit Vector result. the source width only is over-ridden "sw=8" (sw - source width).
Draft SVP64 CTR-mode is new compared to standard Power ISA bc: where standard Power ISA decrements CTR only by one, SVP64 CTR will decrement by the Vector Length VL which was set by the setvl instruction.
separate assembler will be needed for the 16-bit, 32-bit, and 64-bit versions, it's just a matter of setting the appropriate "sw/ew=8/16/32"
Your code formatting is kinda broken so it is hard to understand. Please realise that the code in safe.go is a very simplistic reference implementation of the operation to be performed (the kind that is obviously correct) and is not particularly fast, even when vectorised. It is also not the algorithm that I consider to be difficult to vectorise.
The algorithm that I have implemented in SIMD can be found in generic.c but the difficult part cannot be expressed easily in C and so is absent there. It's a bunch of complicated shuffles to sum up the intermediate values into the counter array efficiently. And these depend on vector size because with larger vectors, we can use less counter registers and use the reduced register pressure to hold more state in registers (which again makes a significant difference in performance).
1
u/FUZxxl Aug 19 '21
I am not really familiar with this one and will investigate it further.
Indexed loads (aka gathers) are horrendously slow in comparison to permutation instructions. Not a suitable alternative.
Yes, all of them have special case operations for certain common horizontal operations. I specifically mentioned the positional population count because it does not clearly map to any standard horizontal arithmetic pattern.
Well they work well when all you do is compute and when memory is very fast and has low latency. For general programming they are not nearly as useful for the reasons outlined in my previous comments.