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

SHAPE 1D/2D/3D vector-matrix remapping SPRs

There are four "shape" SPRs, SHAPE0-3, 32-bits in each, which have the same format.

Shape is 32-bits. When SHAPE is set entirely to zeros, remapping is disabled: the register's elements are a linear (1D) vector.

31..30 29..24 23..21 20..18 17..12 11..6 5..0
applydim offset invxyz permute zdimsz ydimsz xdimsz

applydim will set to zero the dimensions less than this. applydim=0 applies all three. applydim=1 applies y and z. applydim=2 applys only z. applydim=3 is reserved.

invxyz will invert the start index of each of x, y or z. If invxyz[0] is zero then x-dimensional counting begins from 0 and increments, otherwise it begins from xdimsz-1 and iterates down to zero. Likewise for y and z.

offset will have the effect equivalent to the sequential element loop to appear to run for offset (additional) iterations prior to actually generating output.

xdimsz, ydimsz and zdimsz are offset by 1, such that a value of 0 indicates that the array dimensionality for that dimension is 1. A value of xdimsz=2 would indicate that in the first dimension there are 3 elements in the array. The format of the array is therefore as follows:

array[xdim+1][ydim+1][zdim+1]

However whilst illustrative of the dimensionality, that does not take the "permute" setting into account. "permute" may be any one of six values (0-5, with values of 6 and 7 being reserved, and not legal). The table below shows how the permutation dimensionality order works:

permute order array format
000 0,1,2 (xdim+1)(ydim+1)(zdim+1)
001 0,2,1 (xdim+1)(zdim+1)(ydim+1)
010 1,0,2 (ydim+1)(xdim+1)(zdim+1)
011 1,2,0 (ydim+1)(zdim+1)(xdim+1)
100 2,0,1 (zdim+1)(xdim+1)(ydim+1)
101 2,1,0 (zdim+1)(ydim+1)(xdim+1)

In other words, the "permute" option changes the order in which nested for-loops over the array would be done.

The algorithm below shows how REMAP works more clearly, and may be executed as a python program:

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

Each element index from the for-loop 0..VL-1 is run through the above algorithm to work out the actual element index, instead. Given that there are four possible SHAPE entries, up to four separate registers in any given operation may be simultaneously remapped:

function op_add(rd, rs1, rs2) # add not VADD!
  ...
  ...
  for (i = 0; i < VL; i++)
    xSTATE.srcoffs = i # save context
    if (predval & 1<<i) # predication uses intregs
       ireg[rd+remap1(id)] <= ireg[rs1+remap2(irs1)] +
                              ireg[rs2+remap3(irs2)];
       if (!int_vec[rd ].isvector) break;
    if (int_vec[rd ].isvector)  { id += 1; }
    if (int_vec[rs1].isvector)  { irs1 += 1; }
    if (int_vec[rs2].isvector)  { irs2 += 1; }

By changing remappings, 2D matrices may be transposed "in-place" for one operation, followed by setting a different permutation order without having to move the values in the registers to or from memory.

Note that:

  • Over-running the register file clearly has to be detected and an illegal instruction exception thrown
  • When non-default elwidths are set, the exact same algorithm still applies (i.e. it offsets polymorphic elements within registers rather than entire registers).
  • If permute option 000 is utilised, the actual order of the reindexing does not change. However, modulo MVL still occurs which will result in repeated operations (use with caution).
  • If two or more dimensions are set to zero, the actual order does not change!
  • The above algorithm is pseudo-code only. Actual implementations will need to take into account the fact that the element for-looping must be re-entrant, due to the possibility of exceptions occurring. See SVSTATE SPR, which records the current element index. Continuing after return from an interrupt may introduce latency due to re-computation of the remapped offsets.
  • Twin-predicated operations require two separate and distinct element offsets. The above pseudo-code algorithm will be applied separately and independently to each, should each of the two operands be remapped. This even includes unit-strided LD/ST and other operations in that category, where in that case it will be the offset that is remapped.
  • Offset is especially useful, on its own, for accessing elements within the middle of a register. Without offsets, it is necessary to either use a predicated MV, skipping the first elements, or performing a LOAD/STORE cycle to memory. With offsets, the data does not have to be moved.
  • Setting the total elements (xdim+1) times (ydim+1) times (zdim+1) to less than MVL is perfectly legal, albeit very obscure. It permits entries to be regularly presented to operands more than once, thus allowing the same underlying registers to act as an accumulator of multiple vector or matrix operations, for example.
  • Note especially that Program Order must still be respected even when overlaps occur that read or write the same register elements including polymorphic ones

Clearly here some considerable care needs to be taken as the remapping could hypothetically create arithmetic operations that target the exact same underlying registers, resulting in data corruption due to pipeline overlaps. Out-of-order / Superscalar micro-architectures with register-renaming will have an easier time dealing with this than DSP-style SIMD micro-architectures.

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.

  • 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 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:

fmac f4, f0, f8, f4
fmac f5, f0, f9, f5
fmac f6, f0, f10, f6
fmac f7, f0, f11, f7
fmac f4, f1, f12, f4
fmac f5, f1, f13, f5
fmac f6, f1, f14, f6
fmac f7, f1, f15, f7
fmac f4, f2, f16, f4
fmac f5, f2, f17, f5
fmac f6, f2, f18, f6
fmac f7, f2, f19, f7
fmac f4, f3, f20, f4
fmac f5, f3, f21, 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.

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:

  for (i = 0; i < VL; i++)
    if (predval & 1<<i) # apply to VL not SUBVL
      for (j = 0; j < SUBVL; j++)
         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.

An example where SUBVL Remap is appropriate is the Rijndael MixColumns stage:

Assuming that the bytes are stored a00 a01 a02 a03 a10 .. a33 a 2D REMAP allows:

  • the column bytes (as a vec4) to be iterated over as an inner loop, progressing vertically (a00 a10 a20 a30)
  • the columns themselves to be iterated as an outer loop
  • a 32 bit GF(256) Matrix Multiply on the vec4 to be performed.

This entirely in-place without special 128-bit opcodes. Below is the pseudocode for Rijndael MixColumns

void gmix_column(unsigned char *r) {
    unsigned char a[4];
    unsigned char b[4];
    unsigned char c;
    unsigned char h;
    // no swizzle here but still SUBVL.Remap
    // can be done as vec4 byte-level
    // elwidth overrides though.
    for (c = 0; c < 4; c++) {
        a[c] = r[c];
        h = (unsigned char)((signed char)r[c] >> 7);
        b[c] = r[c] << 1;
        b[c] ^= 0x1B & h; /* Rijndael's Galois field */
    }
    // SUBVL.Remap still needed here
    // byyelevel elwidth overrides and vec4
    // These may then each be 4x 8bit bit Swizzled
    // r0.vec4 = b.vec4
    // r0.vec4 ^= a.vec4.WXYZ
    // r0.vec4 ^= a.vec4.ZWXY
    // r0.vec4 ^= b.vec4.YZWX ^ a.vec4.YZWX
    r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1];
    r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2];
    r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; 
    r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0];
}

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 other alternative is to simply perform the actual 4x4 GF(256) Matrix Multiply using the MDS Matrix.