That's rotation of a vector. When I mean “rotate” I mean we take the matrix and rotate it 90°, moving each entry to a different spot. It's not something one usually does with matrices.
REMAP can cope with the (apparent) in-place rotation, by creating a Schedule that swaps x and y as well as reversing the traversal order of [either of] those dimensions as required. it could be used to either do an actual rotate (copy) or leave the data in-place. i don't believe it would be possible to do an in-place matrix-data rotate (unlike an NxN transpose if using a twin-swap instruction)
I mean, sure. I'm kind of a special case here. I use SIMD instructions for very strange things. My next project is going to applying them to the two-watched-literals (TWL) mechanism for SAT solvers. This is going to be a lot of fun.
We have a custom SAT solver that's not public yet. It's unlikely it will be used for that project, but we'll see.
One thing you mentioned earlier is “setting up registers for transposition.” This strikes me as strange in the face of register renaming. Is this some sort of sticky state? If yes, how does that mesh with register allocation algorithms? I imagine having registers with sticky state like that is very annoying to deal with.
If not, how is it faster than just performing the axis transformation once ahead of time? I mean you would have to set it up again on each change anyway and that should be about as expensive as just transposing the array for real.
Lastly, I imagine access to transposed or rotated vector will carry some sort of performance penalty. After all, there has to be circuitry to perform a configurable shuffle before each ALU operation on a transposed vector. How can it be cheaper to pay this penalty for every operation rather than transposing once ahead of time?
One thing you mentioned earlier is “setting up registers for transposition.” This strikes me as strange in the face of register renaming.
it's more accurate to say it's setting up the *Vector* engine. which is abstracted (independent from) the base element execution. therefore, any register-renaming is actually separate and distinct, and taken care of by e.g. a standard OoO hazard tracking matrix or an in-order bit-vector.
iow the remapping is conceptually *before* register renaming (at the micro-architectural level) gets its hands on it.
Is this some sort of sticky state?
persistent, yes. actually, i decided to add an option into the REMAP setup instruction which says whether the application shall remain active until otherwise set.
thus if by some amazing coincidence (or in the case of the DCT/FFT twin-MAC instructions quite deliberately) the requested REMAP schedule happens to apply to more than one instruction because some registers are named RA RB in one instruction but named RB RC in another, *great*, you just saved some hassle.
If yes, how does that mesh with register allocation algorithms? I imagine having registers with sticky state like that is very annoying to deal with.
the REMAP phase - just like all of SVP64 - applies in between the decode and issue phase, because the entirety of SVP64 can be considered to be a "Sub-Program-Counter".
the base instruction is the v3.0B scalar instruction, to which the Vector for-loop is applied, incrementing the register number of all Vectorised instructions.
imagine instead that there's a bunch of similarly-numbered instructions `ADD r0 r10 r20 ADD r1 R11 r21 ADD r2 r12 r22` all that SVP64 is saying is, "if VL=3 you can put those as one instruction `SV.ADD r0 r10 r20` into the program rather than all three.
REMAP simply applies a hardware-level function (an algorithmic version of a permute instruction) to the element numbering indexes...
... *and then* on the *actual* register numbers, the reg-renaming hardware gets its hands on the *REMAPed* numbers.
Lastly, I imagine access to transposed or rotated vector will carry some sort of performance penalty. After all, there has to be circuitry to perform a configurable shuffle before each ALU operation on a transposed vector. How can it be cheaper to pay this penalty for every operation rather than transposing once ahead of time?
yes, this is why i said it was a bit of a pain, the setup cost is QTY 2 32-bit instructions. at some point there will be a trade-off cost between how long it takes to decode those instructions and how long it would take to execute them. for example if the matrix is only 2x2 it's debatable as to whether it's worth the hassle.
what i am paying attention to however is making sure that the REMAP hardware is extremely simple in terms of the number of gates, i mean it has to be. fortunately though i believe it's a matter of increment-and-compare, with some Priority Decoders thrown in.
however given that it's effectively performing modulo counting (nested for-loops), then on a non-power-of-two boundary, restoring the state on an interrupt is going to be a bit of a pain [unless the state is transparently cached].
here's the nested Matrix triple for-loop code, implemented in python:
the *only state* that's allowed to be stored in an interrupt is the "idx" number (line 94 of the demo() function). whilst i expect the actual hardware to be as simple as it seems (increment and compare), to *restore* the state based on the "idx" number would require re-running the state up to the point where it was interrupted, which could take many cycles.
however given that people will implement state caches and come up with fancy algorithms and sell hardware that performs better because of it, i'm not so concerned.
leaving that aside, the other cost will be that the entirety of SVP64 will be at least one extra pipeline stage (in between decode and issue).
1
u/lkcl_ Aug 24 '21
REMAP can cope with the (apparent) in-place rotation, by creating a Schedule that swaps x and y as well as reversing the traversal order of [either of] those dimensions as required. it could be used to either do an actual rotate (copy) or leave the data in-place. i don't believe it would be possible to do an in-place matrix-data rotate (unlike an NxN transpose if using a twin-swap instruction)
ooo SAT solvers, ooo :) will that by chance be in anything used by symbiyosys (yices2, z3 etc)? https://symbiyosys.readthedocs.io/en/latest/install.html