see [[sv/propagation]] because it is currently the only way to apply
REMAP.
-REMAP allows the usual vector loop `0..VL-1` to be "reshaped" (re-mapped) from a linear
-form to a 2D or 3D transposed form, or "offset" to permit arbitrary
-access to elements, independently on each Vector src or dest register.
-
-Their primary use is for Matrix Multiplication, reordering of sequential data in-place. Four SPRs are provided so that a single FMAC may be used in a single loop to perform 4x4 times 4x4 Matrix multiplication, generating 64 FMACs. Additional uses include regular "Structure Packing" such as RGB pixel data extraction and reforming.
-
-REMAP, like all of SV, is abstracted out, meaning that unlike traditional Vector ISAs which would typically only have a limited set of instructions that can be structure-packed (LD/ST typically), REMAP may be applied to literally any instruction: CRs, Arithmetic, Logical, LD/ST, anything.
-
-Note that REMAP does not apply to sub-vector elements: that is what swizzle is for. Swizzle *can* however be applied to the same instruction as REMAP.
-
-REMAP is quite expensive to set up, and on some implementations introduce latency, so should realistically be used only where it is worthwhile
+REMAP allows the usual vector loop `0..VL-1` to be "reshaped" (re-mapped)
+from a linear form to a 2D or 3D transposed form, or "offset" to permit
+arbitrary access to elements, independently on each Vector src or dest
+register.
+
+Their primary use is for Matrix Multiplication, reordering of sequential
+data in-place. Four SPRs are provided so that a single FMAC may be
+used in a single loop to perform 4x4 times 4x4 Matrix multiplication,
+generating 64 FMACs. Additional uses include regular "Structure Packing"
+such as RGB pixel data extraction and reforming.
+
+REMAP, like all of SV, is abstracted out, meaning that unlike traditional
+Vector ISAs which would typically only have a limited set of instructions
+that can be structure-packed (LD/ST typically), REMAP may be applied to
+literally any instruction: CRs, Arithmetic, Logical, LD/ST, anything.
+
+Note that REMAP does not apply to sub-vector elements: that is what
+swizzle is for. Swizzle *can* however be applied to the same instruction
+as REMAP.
+
+REMAP is quite expensive to set up, and on some implementations introduce
+latency, so should realistically be used only where it is worthwhile
+
+# Principle
+
+* normal vector element read/write as operands would be sequential
+ (0 1 2 3 ....)
+* this is not appropriate for (e.g.) Matrix multiply which requires
+ accessing elements in alternative sequences (0 3 6 1 4 7 ...)
+* normal Vector ISAs use either Indexed-MV or Indexed-LD/ST to "cope"
+ with this. both are expensive (copy large vectors, spill through memory)
+* REMAP **redefines** the order of access according to set "Schedules"
+
+Only the most commonly-used algorithms in computer science have REMAP
+support, due to the high cost in both the ISA and in hardware.
+
+# REMAP SPR
+
+| 0 | 2 | 4 | 6 | 8 | 10.14 | 15..23 |
+| -- | -- | -- | -- | -- | ----- | ------ |
+|mi0 |mi1 |mi2 |mo0 |mo1 | SVme | rsv |
+
+mi0-2 and mo0-1 each select SVSHAPE0-3 to apply to a given register.
+mi0-2 apply to RA, RB, RC respectively, as input registers, and
+likewise mo0-1 apply to output registers (FRT, FRS respectively).
+SVme is 5 bits, and indicates indicate whether the
+SVSHAPE is actively applied or not.
+
+* bit 0 of SVme indicates if mi0 is applied to RA / FRA
+* bit 1 of SVme indicates if mi1 is applied to RB / FRB
+* bit 2 of SVme indicates if mi2 is applied to RC / FRC
+* bit 3 of SVme indicates if mo0 is applied to RT / FRT
+* bit 4 of SVme indicates if mo1 is applied to Effective Address / FRS
+ (LD/ST-with-update has an implicit 2nd write register, RA)
+
+There is also a corresponding SVRM-Form for the svremap
+instruction which matches the above SPR:
+
+ |0 |6 |11 |13 |15 |17 |19 |21 | 22 |26 |31 |
+ | PO | SVme |mi0 | mi1 | mi2 | mo0 | mo1 | pst | rsvd | XO | / |
# SHAPE 1D/2D/3D vector-matrix remapping SPRs
The algorithm below shows how REMAP works more clearly, and may be
executed as a python program:
-[[!inline quick="yes" raw="yes" pages="/openpower/sv/remap.py" ]]
-
- xdim = 3 # changeme
- ydim = 4
- zdim = 1
-
- lims = [xdim, ydim, zdim]
- idxs = [0,0,0] # starting indices
- order = [0,1,2] # experiment with different permutations, here
- offset = 2 # experiment with different offset, here
- VL = xdim * ydim * zdim # multiply (or add) to this to get "cycling"
- applydim = 0
- invxyz = [0,0,0]
-
- # run for offset iterations before actually starting
- for idx in range(offset):
- for i in range(3):
- idxs[order[i]] = idxs[order[i]] + 1
- if (idxs[order[i]] != lims[order[i]]):
- break
- idxs[order[i]] = 0
-
- break_count = 0
-
- for idx in range(VL):
- ix = [0] * 3
- for i in range(3):
- if i >= applydim:
- ix[i] = idxs[i]
- if invxyz[i]:
- ix[i] = lims[i] - 1 - ix[i]
- new_idx = ix[0] + ix[1] * xdim + ix[2] * xdim * ydim
- print new_idx,
- break_count += 1
- if break_count == lims[order[0]]:
- print
- break_count = 0
- for i in range(3):
- idxs[order[i]] = idxs[order[i]] + 1
- if (idxs[order[i]] != lims[order[i]]):
- break
- idxs[order[i]] = 0
+```
+[[!inline quick="yes" raw="yes" pages="openpower/sv/remap.py" ]]
+```
+
+An easier-to-read version (using python iterators) shows the loop nesting:
+```
+[[!inline quick="yes" raw="yes" pages="openpower/sv/remapyield.py" ]]
+```
Each element index from the for-loop `0..VL-1`
is run through the above algorithm to work out the **actual** element
register-renaming will have an easier time dealing with this than
DSP-style SIMD micro-architectures.
+## svstate instruction
+
+Please note: this is **not** intended for production. It sets up
+(overwrites) all required SVSHAPE SPRs and indicates that the
+*next instruction* shall have those REMAP shapes applied to it,
+assuming that instruction is of the form FRT,FRA,FRC,FRB.
+
+Form: SVM-Form SV "Matrix" Form (see [[isatables/fields.text]])
+
+| 0.5|6.10 |11.15 |16..20 | 21..25 | 25 | 26..30 |31| name |
+| -- | -- | --- | ----- | ------ | -- | ------ |--| -------- |
+|OPCD| SVxd | SVyd | SVzd | SVRM | vf | XO |/ | svstate |
+
+
+Fields:
+
+* **SVxd** - SV REMAP "xdim"
+* **SVyd** - SV REMAP "ydim"
+* **SVMM** - SV REMAP Mode (0b00000 for Matrix, 0b00001 for FFT)
+* **vf** - sets "Vertical-First" mode
+* **XO** - standard 5-bit XO field
+
# 4x4 Matrix to vec4 Multiply Example
-The following settings will allow a 4x4 matrix (starting at f8), expressed as a sequence of 16 numbers first by row then by column, to be multiplied by a vector of length 4 (starting at f0), using a single FMAC instruction.
+The following settings will allow a 4x4 matrix (starting at f8), expressed
+as a sequence of 16 numbers first by row then by column, to be multiplied
+by a vector of length 4 (starting at f0), using a single FMAC instruction.
* SHAPE0: xdim=4, ydim=4, permute=yx, applied to f0
* SHAPE1: xdim=4, ydim=1, permute=xy, applied to f4
* VL=16, f4=vec, f0=vec, f8=vec
* FMAC f4, f0, f8, f4
-The permutation on SHAPE0 will use f0 as a vec4 source. On the first four iterations through the hardware loop, the REMAPed index will not increment. On the second four, the index will increase by one. Likewise on each subsequent group of four.
+The permutation on SHAPE0 will use f0 as a vec4 source. On the first
+four iterations through the hardware loop, the REMAPed index will not
+increment. On the second four, the index will increase by one. Likewise
+on each subsequent group of four.
-The permutation on SHAPE1 will increment f4 continuously cycling through f4-f7 every four iterations of the hardware loop.
+The permutation on SHAPE1 will increment f4 continuously cycling through
+f4-f7 every four iterations of the hardware loop.
-At the same time, VL will, because there is no SHAPE on f8, increment straight sequentially through the 16 values f8-f23 in the Matrix. The equivalent sequence thus is issued:
+At the same time, VL will, because there is no SHAPE on f8, increment
+straight sequentially through the 16 values f8-f23 in the Matrix. The
+equivalent sequence thus is issued:
fmac f4, f0, f8, f4
fmac f5, f0, f9, f5
fmac f6, f3, f22, f6
fmac f7, f3, f23, f7
-The only other instruction required is to ensure that f4-f7 are initialised (usually to zero).
-
-It should be clear that a 4x4 by 4x4 Matrix Multiply, being effectively the same technique applied to four independent vectors, can be done by setting VL=64, using an extra dimension on the SHAPE0 and SHAPE1 SPRs, and applying a rotating 1D SHAPE SPR of xdim=16 to f8 in order to get it to apply four times to compute the four columns worth of vectors.
+The only other instruction required is to ensure that f4-f7 are
+initialised (usually to zero).
+
+It should be clear that a 4x4 by 4x4 Matrix Multiply, being effectively
+the same technique applied to four independent vectors, can be done by
+setting VL=64, using an extra dimension on the SHAPE0 and SHAPE1 SPRs,
+and applying a rotating 1D SHAPE SPR of xdim=16 to f8 in order to get
+it to apply four times to compute the four columns worth of vectors.
+
+# Warshall transitive closure algorithm
+
+TODO move to [[sv/remap/discussion]] page, copied from here
+http://lists.libre-soc.org/pipermail/libre-soc-dev/2021-July/003286.html
+
+with thanks to Hendrik.
+
+> Just a note: interpreting + as 'or', and * as 'and',
+> operating on Boolean matrices,
+> and having result, X, and Y be the exact same matrix,
+> updated while being used,
+> gives the traditional Warshall transitive-closure
+> algorithm, if the loops are nested exactly in thie order.
+
+this can be done with the ternary instruction which has
+an in-place triple boolean input:
+
+ RT = RT | (RA & RB)
+
+and also has a CR Field variant of the same
+
+notes from conversations:
+
+> > for y in y_r:
+> > for x in x_r:
+> > for z in z_r:
+> > result[y][x] +=
+> > a[y][z] *
+> > b[z][x]
+
+> This nesting of loops works for matrix multiply, but not for transitive
+> closure.
+
+> > it can be done:
+> >
+> > for z in z_r:
+> > for y in y_r:
+> > for x in x_r:
+> > result[y][x] +=
+> > a[y][z] *
+> > b[z][x]
+>
+> And this ordering of loops *does* work for transitive closure, when a,
+> b, and result are the very same matrix, updated while being used.
+>
+> By the way, I believe there is a graph algorithm that does the
+> transitive closure thing, but instead of using boolean, "and", and "or",
+> they use real numbers, addition, and minimum. I think that one computes
+> shortest paths between vertices.
+>
+> By the time the z'th iteration of the z loop begins, the algorithm has
+> already peocessed paths that go through vertices numbered < z, and it
+> adds paths that go through vertices numbered z.
+>
+> For this to work, the outer loop has to be the one on teh subscript that
+> bridges a and b (which in this case are teh same matrix, of course).
# SUBVL Remap
-Remapping even of SUBVL (vec2/3/4) elements is permitted, as if the sub-vectir elements were simply part of the main VL loop. This is the *complete opposite* of predication which **only** applies to the whole vec2/3/4. In pseudocode this would be:
+Remapping even of SUBVL (vec2/3/4) elements is permitted, as if the
+sub-vectir elements were simply part of the main VL loop. This is the
+*complete opposite* of predication which **only** applies to the whole
+vec2/3/4. In pseudocode this would be:
for (i = 0; i < VL; i++)
if (predval & 1<<i) # apply to VL not SUBVL
id = i*SUBVL + j # not, "id=i".
ireg[RT+remap1(id)] ...
-The reason for allowing SUBVL Remaps is that some regular patterns using Swizzle which would otherwise require multiple explicit instructions with 12 bit swizzles encoded in them may be efficently encoded with Remap instead. Not however that Swizzle is *still permitted to be applied*.
+The reason for allowing SUBVL Remaps is that some regular patterns using
+Swizzle which would otherwise require multiple explicit instructions
+with 12 bit swizzles encoded in them may be efficently encoded with Remap
+instead. Not however that Swizzle is *still permitted to be applied*.
-An example where SUBVL Remap is appropriate is the Rijndael MixColumns stage:
+An example where SUBVL Remap is appropriate is the Rijndael MixColumns
+stage:
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/7/76/AES-MixColumns.svg/600px-AES-MixColumns.svg.png" width="400px" />
}
```
-With the assumption made by the above code that the column bytes have already been turned around (vertical rather than horizontal) SUBVL.REMAP may transparently fill that role, in-place, without a complex byte-level mv operation.
+With the assumption made by the above code that the column bytes have
+already been turned around (vertical rather than horizontal) SUBVL.REMAP
+may transparently fill that role, in-place, without a complex byte-level
+mv operation.
-The application of the swizzles allows the remapped vec4 a, b and r variables to perform four straight linear 32 bit XOR operations where a scalar processor would be required to perform 16 byte-level individual operations. Given wide enough SIMD backends in hardware these 3 bit XORs may be done as single-cycle operations across the entire 128 bit Rijndael Matrix.
+The application of the swizzles allows the remapped vec4 a, b and r
+variables to perform four straight linear 32 bit XOR operations where a
+scalar processor would be required to perform 16 byte-level individual
+operations. Given wide enough SIMD backends in hardware these 3 bit
+XORs may be done as single-cycle operations across the entire 128 bit
+Rijndael Matrix.
-The other alternative is to simply perform the actual 4x4 GF(256) Matrix Multiply using the MDS Matrix.
+The other alternative is to simply perform the actual 4x4 GF(256) Matrix
+Multiply using the MDS Matrix.
# TODO
projects / libreriscv.git / blobdiff