simple_v_extension/remap.mdwn

   1 [[!tag standards]]
   2
   3 # NOTE
   4
   5 This section is under revision (and is optional)
   6
   7 # REMAP CSR <a name="remap" />
   8
   9 (Note: both the REMAP and SHAPE sections are best read after the
  10  rest of the document has been read)
  11
  12 There is one 32-bit CSR which may be used to indicate which registers,
  13 if used in any operation, must be "reshaped" (re-mapped) from a linear
  14 form to a 2D or 3D transposed form, or "offset" to permit arbitrary
  15 access to elements within a register.
  16
  17 Their primary use is for Matrix Multiplication, reordering of sequential data in-place.  Three CSRs are provided so that a single FMAC may be used in a single loop to perform 4x4 times 4x4 Matrix multiplication, generating 64 FMACs
  18
  19 The 32-bit REMAP CSR may reshape up to 3 registers:
  20
  21 | 29..28 | 27..26 | 25..24 | 23 | 22..16  | 15 | 14..8   | 7  | 6..0    |
  22 | ------ | ------ | ------ | -- | ------- | -- | ------- | -- | ------- |
  23 | shape2 | shape1 | shape0 | 0  | regidx2 | 0  | regidx1 | 0  | regidx0 |
  24
  25 regidx0-2 refer not to the Register CSR CAM entry but to the underlying
  26 *real* register (see regidx, the value) and consequently is 7-bits wide.
  27 When set to zero (referring to x0), clearly reshaping x0 is pointless,
  28 so is used to indicate "disabled".
  29 shape0-2 refers to one of three SHAPE CSRs.  A value of 0x3 is reserved.
  30 Bits 7, 15, 23, 30 and 31 are also reserved, and must be set to zero.
  31
  32 It is anticipated that these specialist CSRs not be very often used.
  33 Unlike the CSR Register and Predication tables, the REMAP CSRs use
  34 the full 7-bit regidx so that they can be set once and left alone,
  35 whilst the CSR Register entries pointing to them are disabled, instead.
  36
  37 # SHAPE 1D/2D/3D vector-matrix remapping CSRs
  38
  39 (Note: both the REMAP and SHAPE sections are best read after the
  40  rest of the document has been read)
  41
  42 There are three "shape" CSRs, SHAPE0, SHAPE1, SHAPE2, 32-bits in each,
  43 which have the same format.  When each SHAPE CSR is set entirely to zeros,
  44 remapping is disabled: the register's elements are a linear (1D) vector.
  45
  46 | 26..24  | 23      | 22..16  | 15      | 14..8   | 7       | 6..0    |
  47 | ------- | --      | ------- | --      | ------- | --      | ------- |
  48 | permute | offs[2] | zdimsz  | offs[1] | ydimsz  | offs[0] | xdimsz  |
  49
  50 offs is a 3-bit field, spread out across bits 7, 15 and 23, which
  51 is added to the element index during the loop calculation.
  52
  53 xdimsz, ydimsz and zdimsz are offset by 1, such that a value of 0 indicates
  54 that the array dimensionality for that dimension is 1.  A value of xdimsz=2
  55 would indicate that in the first dimension there are 3 elements in the
  56 array.  The format of the array is therefore as follows:
  57
  58     array[xdim+1][ydim+1][zdim+1]
  59
  60 However whilst illustrative of the dimensionality, that does not take the
  61 "permute" setting into account.  "permute" may be any one of six values
  62 (0-5, with values of 6 and 7 being reserved, and not legal).  The table
  63 below shows how the permutation dimensionality order works:
  64
  65 | permute | order | array format             |
  66 | ------- | ----- | ------------------------ |
  67 | 000     | 0,1,2 | (xdim+1)(ydim+1)(zdim+1) |
  68 | 001     | 0,2,1 | (xdim+1)(zdim+1)(ydim+1) |
  69 | 010     | 1,0,2 | (ydim+1)(xdim+1)(zdim+1) |
  70 | 011     | 1,2,0 | (ydim+1)(zdim+1)(xdim+1) |
  71 | 100     | 2,0,1 | (zdim+1)(xdim+1)(ydim+1) |
  72 | 101     | 2,1,0 | (zdim+1)(ydim+1)(xdim+1) |
  73
  74 In other words, the "permute" option changes the order in which
  75 nested for-loops over the array would be done.  The algorithm below
  76 shows this more clearly, and may be executed as a python program:
  77
  78     # mapidx = REMAP.shape2
  79     xdim = 3 # SHAPE[mapidx].xdim_sz+1
  80     ydim = 4 # SHAPE[mapidx].ydim_sz+1
  81     zdim = 5 # SHAPE[mapidx].zdim_sz+1
  82
  83     lims = [xdim, ydim, zdim]
  84     idxs = [0,0,0] # starting indices
  85     order = [1,0,2] # experiment with different permutations, here
  86     offs = 0        # experiment with different offsets, here
  87
  88     for idx in range(xdim * ydim * zdim):
  89         new_idx = offs + idxs[0] + idxs[1] * xdim + idxs[2] * xdim * ydim
  90         print new_idx,
  91         for i in range(3):
  92             idxs[order[i]] = idxs[order[i]] + 1
  93             if (idxs[order[i]] != lims[order[i]]):
  94                 break
  95             print
  96             idxs[order[i]] = 0
  97
  98 Here, it is assumed that this algorithm be run within all pseudo-code
  99 throughout this document where a (parallelism) for-loop would normally
 100 run from 0 to VL-1 to refer to contiguous register
 101 elements; instead, where REMAP indicates to do so, the element index
 102 is run through the above algorithm to work out the **actual** element
 103 index, instead.  Given that there are three possible SHAPE entries, up to
 104 three separate registers in any given operation may be simultaneously
 105 remapped:
 106
 107     function op_add(rd, rs1, rs2) # add not VADD!
 108       ...
 109       ...
 110       for (i = 0; i < VL; i++)
 111         xSTATE.srcoffs = i # save context
 112         if (predval & 1<<i) # predication uses intregs
 113            ireg[rd+remap(id)] <= ireg[rs1+remap(irs1)] +
 114                                  ireg[rs2+remap(irs2)];
 115            if (!int_vec[rd ].isvector) break;
 116         if (int_vec[rd ].isvector)  { id += 1; }
 117         if (int_vec[rs1].isvector)  { irs1 += 1; }
 118         if (int_vec[rs2].isvector)  { irs2 += 1; }
 119
 120 By changing remappings, 2D matrices may be transposed "in-place" for one
 121 operation, followed by setting a different permutation order without
 122 having to move the values in the registers to or from memory.  Also,
 123 the reason for having REMAP separate from the three SHAPE CSRs is so
 124 that in a chain of matrix multiplications and additions, for example,
 125 the SHAPE CSRs need only be set up once; only the REMAP CSR need be
 126 changed to target different registers.
 127
 128 Note that:
 129
 130 * Over-running the register file clearly has to be detected and
 131   an illegal instruction exception thrown
 132 * When non-default elwidths are set, the exact same algorithm still
 133   applies (i.e. it offsets elements *within* registers rather than
 134   entire registers).
 135 * If permute option 000 is utilised, the actual order of the
 136   reindexing does not change!
 137 * If two or more dimensions are set to zero, the actual order does not change!
 138 * The above algorithm is pseudo-code **only**.  Actual implementations
 139   will need to take into account the fact that the element for-looping
 140   must be **re-entrant**, due to the possibility of exceptions occurring.
 141   See MSTATE CSR, which records the current element index.
 142 * Twin-predicated operations require **two** separate and distinct
 143   element offsets.  The above pseudo-code algorithm will be applied
 144   separately and independently to each, should each of the two
 145   operands be remapped.  *This even includes C.LDSP* and other operations
 146   in that category, where in that case it will be the **offset** that is
 147   remapped (see Compressed Stack LOAD/STORE section).
 148 * Offset is especially useful, on its own, for accessing elements
 149   within the middle of a register.  Without offsets, it is necessary
 150   to either use a predicated MV, skipping the first elements, or
 151   performing a LOAD/STORE cycle to memory.
 152   With offsets, the data does not have to be moved.
 153 * Setting the total elements (xdim+1) times (ydim+1) times (zdim+1) to
 154   less than MVL is **perfectly legal**, albeit very obscure.  It permits
 155   entries to be regularly presented to operands **more than once**, thus
 156   allowing the same underlying registers to act as an accumulator of
 157   multiple vector or matrix operations, for example.
 158
 159 Clearly here some considerable care needs to be taken as the remapping
 160 could hypothetically create arithmetic operations that target the
 161 exact same underlying registers, resulting in data corruption due to
 162 pipeline overlaps.  Out-of-order / Superscalar micro-architectures with
 163 register-renaming will have an easier time dealing with this than
 164 DSP-style SIMD micro-architectures.
 165