(no commit message)

[libreriscv.git] / openpower / sv / remap.mdwn

# REMAP <a name="remap" />

<!-- hide -->
* <https://bugs.libre-soc.org/show_bug.cgi?id=143> matrix multiply
* <https://bugs.libre-soc.org/show_bug.cgi?id=867> add svindex
* <https://bugs.libre-soc.org/show_bug.cgi?id=885> svindex in simulator
* <https://bugs.libre-soc.org/show_bug.cgi?id=911> offset svshape option
* <https://bugs.libre-soc.org/show_bug.cgi?id=864> parallel reduction
* <https://bugs.libre-soc.org/show_bug.cgi?id=930> DCT/FFT "strides"
* <https://bugs.libre-soc.org/show_bug.cgi?id=1155> bigmul (normal and carry-save)
* see [[sv/remap/appendix]] for examples and usage
* see [[sv/propagation]] for a future way to apply REMAP
* [[remap/discussion]]
<!-- show -->

REMAP is an advanced form of Vector "Structure Packing" that provides
hardware-level support for commonly-used *nested* loop patterns that would
otherwise require full inline loop unrolling.  For more general reordering
an Indexed REMAP mode is available (a RISC-paradigm
abstracted analog to `xxperm`).

REMAP allows the usual sequential 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. Up to four separate independent REMAPs may be applied
to the registers of any instruction.

A normal Vector Add (no Element-width Overrides):

```
   for i in range(VL):
     GPR[RT+i] <= GPR[RA+i] + GPR[RB+i];
```

A Hardware-assisted REMAP Vector Add:

```
   for i in range(VL):
     GPR[RT+remap1(i)] <= GPR[RA+remap2(i)] + GPR[RB+remap3(i)];
```

Aside from
Indexed REMAP this is entirely Hardware-accelerated reordering and
consequently not costly in terms of register access for the Indices. It will however
place a burden on Multi-Issue systems but no more than if the equivalent
Scalar instructions were explicitly loop-unrolled without SVP64, and
some advanced implementations may even find the Deterministic nature of
the Scheduling to be easier on resources.

*Hardware note: in its general form, REMAP is quite expensive to set up, and on some
implementations may introduce latency, so should realistically be used
only where it is worthwhile.  Given that even with latency the fact
that up to 127 operations can be Deterministically issued (from a single
instruction) it should be clear that REMAP should not be dismissed
for *possible* latency alone.  Commonly-used patterns such as Matrix
Multiply, DCT and FFT have helper instruction options which make REMAP
easier to use.*

There are five types of REMAP:

* **Matrix**, also known as 2D and 3D reshaping, can perform in-place
  Matrix transpose and rotate. The Shapes are set up for an "Outer Product"
  Matrix Multiply (a future variant may introduce Inner Product).
* **FFT/DCT**, with full triple-loop in-place support: limited to
  Power-2 RADIX
* **Indexing**, for any general-purpose reordering, also includes
  limited 2D reshaping as well as Element "offsetting".
* **Parallel Reduction**, for scheduling a sequence of operations
  in a Deterministic fashion, in a way that may be parallelised,
  to reduce a Vector down to a single value.
* **Parallel Prefix Sum**, implemented as a work-efficient Schedule,
  has several key Computer Science uses. Again Prefix Sum is 100%
  Deterministic.

Best implemented on top of a Multi-Issue Out-of-Order Micro-architecture,
REMAP Schedules are 100% Deterministic **including Indexing** and are
designed to be incorporated in between the Decode and Issue phases,
directly into Register Hazard Management.

As long as the SVSHAPE SPRs
are not written to directly, Hardware may treat REMAP as 100%
Deterministic: all REMAP Management instructions take static
operands (no dynamic register operands)
with the exception of Indexed Mode, and even then
Architectural State is permitted to assume that the Indices
are cacheable from the point at which the `svindex` instruction
is executed.

Further details on the Deterministic Precise-Interruptible algorithms
used in these Schedules is found in the [[sv/remap/appendix]].

*Future specification note: future versions of the REMAP Management instructions
will extend to EXT1xx Prefixed variants. This will overcome some of the limitations
present in the 32-bit variants of the REMAP Management instructions that at
present require direct writing to SVSHAPE0-3 SPRs.  Additional
REMAP Modes may also be introduced at that time.*

## Determining Register Hazards (hphint)

For high-performance (Multi-Issue, Out-of-Order) systems it is critical
to be able to statically determine the extent of Vectors in order to
allocate pre-emptive Hazard protection.  The next task is to eliminate
masked-out elements using predicate bits, freeing up the associated
Hazards.

For non-REMAP situations `VL` is sufficient to ascertain early
Hazard coverage, and with SVSTATE being a high priority cached
quantity at the same level of MSR and PC this is not a problem.

The problems come when REMAP is enabled.  Indexed REMAP must instead
use `MAXVL` as the earliest (simplest)
batch-level Hazard Reservation indicator (after taking element-width
overriding on the Index source into consideration),
but Matrix, FFT and Parallel Reduction must all use completely different
schemes.  The reason is that VL is used to step through the total
number of *operations*, not the number of registers.
The "Saving Grace" is that all of the REMAP Schedules are 100% Deterministic.

Advance-notice Parallel computation and subsequent cacheing
of all of these complex Deterministic REMAP Schedules is
*strongly recommended*, thus allowing clear and precise multi-issue
batched Hazard coverage to be deployed, *even for Indexed Mode*.
This is only possible for Indexed due to the strict guidelines
given to Programmers.

In short, there exists solutions to the problem of Hazard Management,
with varying degrees of refinement possible at correspondingly
increasing levels of complexity in hardware.

A reminder: when Rc=1 each result register (element) has an associated
co-result CR Field (one per result element).  Thus above when determining
the Write-Hazards for result registers the corresponding Write-Hazards for the
corresponding associated co-result CR Field must not be forgotten, *including* when
Predication is used.

**Horizontal-Parallelism Hint**

To help further in reducing Hazards,
`SVSTATE.hphint` is an indicator to hardware of how many elements are 100%
fully independent.  Hardware is permitted to assume that groups of elements
up to `hphint` in size need not have Register (or Memory) Hazards created
between them, including when `hphint > VL`, which greatly aids simplification of
Multi-Issue implementations.

If care is not taken in setting `hphint` correctly it may wreak havoc.
For example Matrix Outer Product relies on the innermost loop computations
being independent.  If `hphint` is set to greater than the Outer Product
depth then data corruption is guaranteed to occur.

Likewise on FFTs it is assumed that each layer of the RADIX2 triple-loop
is independent, but that there is strict *inter-layer* Register Hazards.
Therefore if `hphint` is set to greater than the RADIX2 width of the FFT,
data corruption is guaranteed.

Thus the key message is that setting `hphint` requires in-depth knowledge
of the REMAP Algorithm Schedules, given in the Appendix.

## REMAP area of SVSTATE SPR <a name="svstate_remap_area"> </>

The following bits of the SVSTATE SPR are used for REMAP:

```
    |32:33|34:35|36:37|38:39|40:41| 42:46 | 62     |
    | --  | --  | --  | --  | --  | ----- | ------ |
    |mi0  |mi1  |mi2  |mo0  |mo1  | SVme  | RMpst  |
```

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 (RT/FRT, RS/FRS) respectively.
SVme is 5 bits (one for each of mi0-2/mo0-1) and indicates whether the
SVSHAPE is actively applied or not, and if so, to which registers.

* bit 4 of SVme indicates if mi0 is applied to source RA / FRA / BA / BFA / RT / FRT
* bit 3 of SVme indicates if mi1 is applied to source RB / FRB / BB
* bit 2 of SVme indicates if mi2 is applied to source RC / FRC / BC
* bit 1 of SVme indicates if mo0 is applied to result RT / FRT / BT / BF
* bit 0 of SVme indicates if mo1 is applied to result Effective Address / FRS / RS
  (LD/ST-with-update has an implicit 2nd write register, RA)

The "persistence" bit if set will result in all Active REMAPs being applied
indefinitely.

-----------

\newpage{}

# svremap instruction <a name="svremap"> </a>

SVRM-Form:

|0     |6     |11  |13   |15   |17   |19   |21    | 22:25 |26:31  |
| --   | --   | -- | --  | --  | --  | --  | --   | ----  | ----- |
| PO   | SVme |mi0 | mi1 | mi2 | mo0 | mo1 | pst  | rsvd  | XO    |

* svremap SVme,mi0,mi1,mi2,mo0,mo1,pst

Pseudo-code:

```
    # registers RA RB RC RT EA/FRS SVSHAPE0-3 indices
    SVSTATE[32:33] <- mi0
    SVSTATE[34:35] <- mi1
    SVSTATE[36:37] <- mi2
    SVSTATE[38:39] <- mo0
    SVSTATE[40:41] <- mo1
    # enable bit for RA RB RC RT EA/FRS
    SVSTATE[42:46] <- SVme
    # persistence bit (applies to more than one instruction)
    SVSTATE[62] <- pst
```

Special Registers Altered:

```
    SVSTATE
```

`svremap` establishes the connection between registers and SVSHAPE SPRs.
The bitmask `SVme` determines which registers have a REMAP applied, and mi0-mo1
determine which shape is applied to an activated register.  the `pst` bit if
cleared indicated that the REMAP operation shall only apply to the immediately-following
instruction.  If set then REMAP remains permanently enabled until such time as it is
explicitly disabled, either by `setvl` setting a new MAXVL, or with another
`svremap` instruction. `svindex` and `svshape2` are also capable of setting or
clearing persistence, as well as partially covering a subset of the capability of
`svremap` to set register-to-SVSHAPE relationships.

Programmer's Note: applying non-persistent `svremap` to an instruction that has
no REMAP enabled or is a Scalar operation will obviously have no effect but
the bits 32 to 46 will at least have been set in SVSTATE. This may prove useful
when using `svindex` or `svshape2`.

Hardware Architectural Note: when persistence is not set it is critically important
to treat the `svremap` and the immediately-following SVP64 instruction as an
indivisible fused operation.
*No state* is stored in the SVSTATE SPR in order to allow continuation should an
Interrupt occur between the two instructions. Thus, Interrupts must be prohibited
from occurring or other workaround deployed.  When persistence is set this issue
is moot.

It is critical to note that if persistence is clear then `svremap` is the *only* way
to activate REMAP on any given (following) instruction.  If persistence is set however then
**all** SVP64 instructions go through REMAP as long as `SVme` is non-zero.

-------------

\newpage{}

# SHAPE Remapping SPRs

There are four "shape" SPRs, SHAPE0-3, 32-bits in each,
which have the same format.  It is possible to write directly to these
SPRs but it is recommended to use the Management instructions
`svshape`, `svshape2` or `svindex`.

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

|0:5   |6:11  | 12:17   | 18:20   | 21:23   |24:27 |28:29  |30:31| Mode  |
|----- |----- | ------- | ------- | ------  |------|------ |---- | ----- |
|xdimsz|ydimsz| zdimsz  | permute | invxyz  |offset|skip   |mode |Matrix |
|xdimsz|ydimsz|SVGPR    | 11/     |sk1/invxy|offset|elwidth|0b00 |Indexed|
|xdimsz|mode  | zdimsz  | submode2| invxyz  |offset|submode|0b01 |DCT/FFT|
| rsvd |rsvd  |xdimsz   | rsvd    | invxyz  |offset|submode|0b10 |Red/Sum|
|      |      |         |         |         |      |       |0b11 |rsvd   |

`mode` sets different behaviours (straight matrix multiply, FFT, DCT).

* **mode=0b00** sets straight Matrix Mode
* **mode=0b00** with permute=0b110 or 0b111 sets Indexed Mode
* **mode=0b01** sets "FFT/DCT" mode and activates submodes
* **mode=0b10** sets "Parallel Reduction or Prefix-Sum" Schedules.

*Architectural Resource Allocation note: the four SVSHAPE SPRs are best
allocated sequentially and contiguously in order that `sv.mtspr` may
be used. This is safe to do as long as `SVSTATE.SVme=0`*

## Parallel Reduction / Prefix-Sum Mode

Creates the Schedules for Parallel Tree Reduction and Prefix-Sum

* **submode=0b00** selects the left operand index for Reduction
* **submode=0b01** selects the right operand index for Reduction
* **submode=0b10** selects the left operand index for Prefix-Sum
* **submode=0b11** selects the right operand index for Prefix-Sum

* When bit 0 of `invxyz` is set, the order of the indices
  in the inner for-loop are reversed. This has the side-effect
  of placing the final reduced result in the last-predicated element.
  It also has the indirect side-effect of swapping the source
  registers: Left-operand index numbers will always exceed
  Right-operand indices.
  When clear, the reduced result will be in the first-predicated
  element, and Left-operand indices will always be *less* than
  Right-operand ones.
* When bit 1 of `invxyz` is set, the order of the outer loop
  step is inverted: stepping begins at the nearest power-of two
  to half of the vector length and reduces by half each time.
  When clear the step will begin at 2 and double on each
  inner loop.

**Parallel Prefix Sum**

This is a work-efficient Parallel Schedule that for example produces Trangular
or Factorial number sequences. Half of the Prefix Sum Schedule is near-identical
to Parallel Reduction.  Whilst the Arithmetic mapreduce Mode (`/mr`) may achieve the same
end-result, implementations may only implement Mapreduce in serial form (or give
the appearance to Programmers of the same). The Parallel Prefix Schedule is
*required* to be implemented in such a way that its Deterministic Schedule may be
parallelised. Like the Reduction Schedule it is 100% Deterministic and consequently
may be used with non-commutative operations.
The Schedule Algorithm may be found in the [[sv/remap/appendix]]

**Parallel Reduction**

Vector Reduce Mode issues a deterministic tree-reduction schedule to the underlying micro-architecture.  Like Scalar reduction, the "Scalar Base"
(Power ISA v3.0B) operation is leveraged, unmodified, to give the
*appearance* and *effect* of Reduction. Parallel Reduction is not limited
to Power-of-two but is limited as usual by the total number of
element operations (127) as well as available register file size.

In Horizontal-First Mode, Vector-result reduction **requires**
the destination to be a Vector, which will be used to store
intermediary results, in order to achieve a correct final
result.

Given that the tree-reduction schedule is deterministic,
Interrupts and exceptions
can therefore also be precise.  The final result will be in the first
non-predicate-masked-out destination element, but due again to
the deterministic schedule programmers may find uses for the intermediate
results, even for non-commutative Defined Word-instruction operations.
Additionally, because the intermediate results are always written out
it is possible to service Precise Interrupts without affecting latency
(a common limitation of Vector ISAs implementing explicit
Parallel Reduction instructions, because their Architectural State cannot
hold the partial results).

When Rc=1 a corresponding Vector of co-resultant CRs is also
created.  No special action is taken: the result *and its CR Field*
are stored "as usual" exactly as all other SVP64 Rc=1 operations.

Note that the Schedule only makes sense on top of certain instructions:
X-Form with a Register Profile of `RT,RA,RB` is fine because two sources
and the destination are all the same type.  Like Scalar
Reduction, nothing is prohibited:
the results of execution on an unsuitable instruction may simply
not make sense. With care, even 3-input instructions (madd, fmadd, ternlogi) 
may be used, and whilst it is down to the Programmer to walk through the
process the Programmer can be confident that the Parallel-Reduction is
guaranteed 100% Deterministic.

Critical to note regarding use of Parallel-Reduction REMAP is that,
exactly as with all REMAP Modes, the `svshape` instruction *requests*
a certain Vector Length (number of elements to reduce) and then
sets VL and MAXVL at the number of **operations** needed to be
carried out.  Thus, equally as importantly, like Matrix REMAP
the total number of operations
is restricted to 127.  Any Parallel-Reduction requiring more operations
will need to be done manually in batches (hierarchical
recursive Reduction).

Also important to note is that the Deterministic Schedule is arranged
so that some implementations *may* parallelise it (as long as doing so
respects Program Order and Register Hazards).  Performance (speed)
of any given
implementation is neither strictly defined or guaranteed.  As with
the Vulkan(tm) Specification, strict compliance is paramount whilst
performance is at the discretion of Implementors.

**Parallel-Reduction with Predication**

To avoid breaking the strict RISC-paradigm, keeping the Issue-Schedule
completely separate from the actual element-level (scalar) operations,
Move operations are **not** included in the Schedule.  This means that
the Schedule leaves the final (scalar) result in the first-non-masked 
element of the Vector used.  With the predicate mask being dynamic
(but deterministic) at a superficial glance it seems this result
could be anywhere.

If that result is needed to be moved to a (single) scalar register
then a follow-up `sv.mv/sm=predicate rt, *ra` instruction will be
needed to get it, where the predicate is the exact same predicate used
in the prior Parallel-Reduction instruction.

* If there was only a single
  bit in the predicate then the result will not have moved or been altered
  from the source vector prior to the Reduction
* If there was more than one bit the result will be in the
  first element with a predicate bit set.

In either case the result is in the element with the first bit set in
the predicate mask. Thus, no move/copy *within the Reduction itself* was needed.

Programmer's Note: For *some* hardware implementations
the vector-to-scalar copy may be a slow operation, as may the Predicated
Parallel Reduction itself.
It may be better to perform a pre-copy
of the values, compressing them (VREDUCE-style) into a contiguous block,
which will guarantee that the result goes into the very first element
of the destination vector, in which case clearly no follow-up
predicated vector-to-scalar MV operation is needed. A VREDUCE effect
is achieved by setting just a source predicate mask on Twin-Predicated
operations.

**Usage conditions**

The simplest usage is to perform an overwrite, specifying all three
register operands the same.

```
    svshape parallelreduce, 6
    sv.add *8, *8, *8
```

The Reduction Schedule will issue the Parallel Tree Reduction spanning
registers 8 through 13, by adjusting the offsets to RT, RA and RB as
necessary (see "Parallel Reduction algorithm" in a later section).

A non-overwrite is possible as well but just as with the overwrite
version, only those destination elements necessary for storing
intermediary computations will be written to: the remaining elements
will **not** be overwritten and will **not** be zero'd.

```
    svshape parallelreduce, 6
    sv.add *0, *8, *8
```

However it is critical to note that if the source and destination are
not the same then the trick of using a follow-up vector-scalar MV will
not work.

**Sub-Vector Horizontal Reduction**

To achieve Sub-Vector Horizontal Reduction, Pack/Unpack should be enabled,
which will turn the Schedule around such that issuing of the Scalar
Defined Word-instructions is done with SUBVL looping as the inner loop not the
outer loop. Rc=1 with Sub-Vectors (SUBVL=2,3,4) is `UNDEFINED` behaviour.

*Programmer's Note: Overwrite Parallel Reduction with Sub-Vectors
will clearly result in data corruption.  It may be best to perform
a Pack/Unpack Transposing copy of the data first*

## FFT/DCT mode

submode2=0 is for FFT. For FFT submode the following schedules may be 
selected:

* **submode=0b00** selects the ``j`` offset of the innermost for-loop
  of Tukey-Cooley
* **submode=0b10** selects the ``j+halfsize`` offset of the innermost for-loop
  of Tukey-Cooley
* **submode=0b11** selects the ``k`` of exptable (which coefficient)

When submode2 is 1 or 2, for DCT inner butterfly submode the following
schedules may be selected.  When submode2 is 1, additional bit-reversing
is also performed.

* **submode=0b00** selects the ``j`` offset of the innermost for-loop,
    in-place
* **submode=0b010** selects the ``j+halfsize`` offset of the innermost for-loop,
  in reverse-order, in-place
* **submode=0b10** selects the ``ci`` count of the innermost for-loop,
  useful for calculating the cosine coefficient
* **submode=0b11** selects the ``size`` offset of the outermost for-loop,
  useful for the cosine coefficient ``cos(ci + 0.5) * pi / size``

When submode2 is 3 or 4, for DCT outer butterfly submode the following
schedules may be selected.  When submode is 3, additional bit-reversing
is also performed.

* **submode=0b00** selects the ``j`` offset of the innermost for-loop,
* **submode=0b01** selects the ``j+1`` offset of the innermost for-loop,

`zdimsz` is used as an in-place "Stride", particularly useful for
column-based in-place DCT/FFT.

## Matrix Mode

In Matrix Mode, skip allows dimensions to be skipped from being included
in the resultant output index.  This allows sequences to be repeated:
```0 0 0 1 1 1 2 2 2 ...``` or in the case of skip=0b11 this results in
modulo ```0 1 2 0 1 2 ...```

* **skip=0b00** indicates no dimensions to be skipped
* **skip=0b01** sets "skip 1st dimension"
* **skip=0b10** sets "skip 2nd dimension"
* **skip=0b11** sets "skip 3rd dimension"

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 of offsetting the result by ```offset``` elements:

```
    for i in 0..VL-1:
        GPR(RT + remap(i) + SVSHAPE.offset) = ....
```

This appears redundant because the register RT could simply be changed by a compiler, until element width overrides are introduced.  Also
bear in mind that unlike a static compiler SVSHAPE.offset may
be set dynamically at runtime.

xdimsz, ydimsz and zdimsz are offset by 1, such that a value of 0 indicates
that the array dimensionality for that dimension is 1. any dimension
not intended to be used must have its value set to 0 (dimensionality
of 1).  A value of xdimsz=2 would indicate that in the first dimension
there are 3 elements in the array.  For example, to create a 2D array
X,Y of dimensionality X=3 and Y=2, set xdimsz=2, ydimsz=1 and zdimsz=0

The format of the array is therefore as follows:

```
    array[xdimsz+1][ydimsz+1][zdimsz+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 indicating "Indexed" Mode).  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) |
| 110     | 0,1   | Indexed (xdim+1)(ydim+1) |
| 111     | 1,0   | Indexed (ydim+1)(xdim+1) |

In other words, the "permute" option changes the order in which
nested for-loops over the array would be done.  See executable
python reference code for further details.

*Note: permute=0b110 and permute=0b111 enable Indexed REMAP Mode,
described below*

With all these options it is possible to support in-place transpose,
in-place rotate, Matrix Multiply and Convolutions, without being
limited to Power-of-Two dimension sizes.

**Limitations and caveats**

Limitations of Matrix REMAP are that the Vector Length (VL) is currently
restricted to 127: up to 127 FMAs (or other operation)
may be performed in total.
Also given that it is in-registers only at present some care has to be
taken on regfile resource utilisation. However it is perfectly possible
to utilise Matrix REMAP to perform the three inner-most "kernel" loops of
the usual 6-level "Tiled" large Matrix Multiply, without the usual 
difficulties associated with SIMD.

Also the `svshape` instruction only provides access to *part* of the
Matrix REMAP capability. Rotation and mirroring need to be done by
programming the SVSHAPE SPRs directly, which can take a lot more
instructions. Future versions of SVP64 will 
provide more comprehensive capacity and
mitigate the need to write direct to the SVSHAPE SPRs.

Additionally there is not yet a way to set Matrix sizes from registers
with `svshape`: this was an intentional decision to simplify Hardware, that
may be corrected in a future version of SVP64. The limitation may presently
be overcome by direct programming of the SVSHAPE SPRs.

*Hardware Architectural note: with the Scheduling applying as a Phase between
Decode and Issue in a Deterministic fashion the Register Hazards may be
easily computed and a standard Out-of-Order Micro-Architecture exploited to good
effect.  Even an In-Order system may observe that for large Outer Product
Schedules there will be no stalls, but if the Matrices are particularly
small size an In-Order system would have to stall, just as it would if
the operations were loop-unrolled without Simple-V. Thus: regardless
of the Micro-Architecture the Hardware Engineer should first consider
how best to process the exact same equivalent loop-unrolled instruction
stream. Once solved Matrix REMAP will fit naturally.*

## Indexed Mode

Indexed Mode activates reading of the element indices from the GPR
and includes optional limited 2D reordering.
In its simplest form (without elwidth overrides or other modes):

```
    def index_remap(i):
        return GPR((SVSHAPE.SVGPR<<1)+i) + SVSHAPE.offset

    for i in 0..VL-1:
        element_result = ....
        GPR(RT + indexed_remap(i)) = element_result
```

With element-width overrides included, and using the pseudocode
from the SVP64 [[sv/svp64/appendix#elwidth]] elwidth section
this becomes:

```
    def index_remap(i):
        svreg = SVSHAPE.SVGPR << 1
        srcwid = elwid_to_bitwidth(SVSHAPE.elwid)
        offs = SVSHAPE.offset
        return get_polymorphed_reg(svreg, srcwid, i) + offs

    for i in 0..VL-1:
        element_result = ....
        rt_idx = indexed_remap(i)
        set_polymorphed_reg(RT, destwid, rt_idx, element_result)
```

Matrix-style reordering still applies to the indices, except limited
to up to 2 Dimensions (X,Y). Ordering is therefore limited to (X,Y) or
(Y,X) for in-place Transposition.
Only one dimension may optionally be skipped. Inversion of either
X or Y or both is possible (2D mirroring). Pseudocode for Indexed Mode (including elwidth
overrides) may be written in terms of Matrix Mode, specifically
purposed to ensure that the 3rd dimension (Z) has no effect:

```
    def index_remap(ISHAPE, i):
        MSHAPE.skip   = 0b0 || ISHAPE.sk1
        MSHAPE.invxyz = 0b0 || ISHAPE.invxy
        MSHAPE.xdimsz = ISHAPE.xdimsz
        MSHAPE.ydimsz = ISHAPE.ydimsz
        MSHAPE.zdimsz = 0 # disabled
        if ISHAPE.permute = 0b110 # 0,1
           MSHAPE.permute = 0b000 # 0,1,2
        if ISHAPE.permute = 0b111 # 1,0
           MSHAPE.permute = 0b010 # 1,0,2
        el_idx = remap_matrix(MSHAPE, i)
        svreg = ISHAPE.SVGPR << 1
        srcwid = elwid_to_bitwidth(ISHAPE.elwid)
        offs = ISHAPE.offset
        return get_polymorphed_reg(svreg, srcwid, el_idx) + offs
```

The most important observation above is that the Matrix-style
remapping occurs first and the Index lookup second.  Thus it
becomes possible to perform in-place Transpose of Indices which
may have been costly to set up or costly to duplicate
(waste register file space). In other words: it is fine for two or more
SVSHAPEs to simultaneously use the same
Indices (use the same GPRs), even if one SVSHAPE has different
2D dimensions and ordering from the others.

**Caveats and Limitations**

The purpose of Indexing is to provide a generalised version of
Vector ISA "Permute" instructions, such as VSX `vperm`.  The
Indexing is abstracted out and may be applied to much more
than an element move/copy, and is not limited for example
to the number of bytes that can fit into a VSX register.
Indexing may be applied to LD/ST (even on Indexed LD/ST
instructions such as `sv.lbzx`), arithmetic operations,
extsw: there is no artificial limit.

The only major caveat is that the registers to be used as
Indices must not be modified by any instruction after Indexed Mode
is established, and neither must MAXVL be altered. Additionally,
no register used as an Index may exceed MAXVL-1.

Failure to observe
these conditions results in `UNDEFINED` behaviour.
These conditions allow a Read-After-Write (RAW) Hazard to be created on
the entire range of Indices to be subsequently used, but a corresponding
Write-After-Read Hazard by any instruction that modifies the Indices
**does not have to be created**. Given the large number of registers
involved in Indexing this is a huge resource saving and reduction
in micro-architectural complexity. MAXVL is likewise
included in the RAW Hazards because it is involved in calculating
how many registers are to be considered Indices.

With these Hazard Mitigations in place, high-performance implementations
may read-cache the Indices at the point where a given `svindex` instruction
is called (or SVSHAPE SPRs - and MAXVL - directly altered) by issuing
background GPR register file reads whilst other instructions are being
issued and executed.

Indexed REMAP **does not prevent conflicts** (overlapping
destinations), which on a superficial analysis may be perceived to be a
problem, until it is recalled that, firstly, Simple-V is designed specifically
to require Program Order to be respected, and that Matrix, DCT and FFT
all *already* critically depend on overlapping Reads/Writes: Matrix
uses overlapping registers as accumulators.  Thus the Register Hazard
Management needed by Indexed REMAP *has* to be in place anyway.

*Programmer's Note: `hphint` may be used to help hardware identify
parallelism opportunities but it is critical to remember that the
groupings are by `FLOOR(step/MAXVL)` not `FLOOR(REMAP(step)/MAXVL)`.*

The cost compared to Matrix and other REMAPs (and Pack/Unpack) is
clearly that of the additional reading of the GPRs to be used as Indices,
plus the setup cost associated with creating those same Indices.
If any Deterministic REMAP can cover the required task, clearly it
is adviseable to use it instead.

*Programmer's note: some algorithms may require skipping of Indices exceeding
VL-1, not MAXVL-1. This may be achieved programmatically by performing
an `sv.cmp *BF,*RA,RB` where RA is the same GPRs used in the Indexed REMAP,
and RB contains the value of VL returned from `setvl`. The resultant
CR Fields may then be used as Predicate Masks to exclude those operations
with an Index exceeding VL-1.*

-------------

\newpage{}

# svshape instruction  <a name="svshape"> </a>

SVM-Form

    svshape SVxd,SVyd,SVzd,SVRM,vf

| 0:5|6:10  |11:15  |16:20  | 21:24  | 25 | 26:31 |  name    |
| -- | --   | ---   | ----- | ------ | -- | ------| -------- |
|PO  | SVxd | SVyd  | SVzd  | SVRM   | vf | XO    | svshape  |

See [[sv/remap/appendix]] for `svshape` pseudocode

Special Registers Altered:

```
    SVSTATE, SVSHAPE0-3
```

`svshape` is a convenience instruction that reduces instruction
count for common usage patterns, particularly Matrix, DCT and FFT. It sets up
(overwrites) all required SVSHAPE SPRs and also modifies SVSTATE
including VL and MAXVL. Using `svshape` therefore does not also
require `setvl`.

Fields:

* **SVxd** - SV REMAP "xdim" (X-dimension)
* **SVyd** - SV REMAP "ydim" (Y-dimension, sometimes used for sub-mode selection)
* **SVzd** - SV REMAP "zdim" (Z-dimension)
* **SVRM** - SV REMAP Mode (0b00000 for Matrix, 0b00001 for FFT etc.)
* **vf** - sets "Vertical-First" mode
* **XO** - standard 6-bit XO field

*Note: SVxd, SVyz and SVzd are all stored "off-by-one".  In the assembler
mnemonic the values `1-32` are stored in binary as `0b00000..0b11111`*

There are 12 REMAP Modes (2 Modes are RESERVED for `svshape2`, 2 Modes
are RESERVED)

| SVRM   | Remap Mode description |
| --     | --              |
| 0b0000 | Matrix 1/2/3D    |
| 0b0001 | FFT Butterfly   |
| 0b0010 | reserved |
| 0b0011 | DCT Outer butterfly  |
| 0b0100 | DCT Inner butterfly, on-the-fly (Vertical-First Mode) |
| 0b0101 | DCT COS table index generation |
| 0b0110 | DCT half-swap   |
| 0b0111 | Parallel Reduction and Prefix Sum |
| 0b1000 | reserved for svshape2 |
| 0b1001 | reserved for svshape2 |
| 0b1010 | reserved |
| 0b1011 | iDCT Outer butterfly  |
| 0b1100 | iDCT Inner butterfly, on-the-fly (Vertical-First Mode) |
| 0b1101 | iDCT COS table index generation |
| 0b1110 | iDCT half-swap   |
| 0b1111 | FFT half-swap   |

Examples showing how all of these Modes operate exists in the online
[SVP64 unit tests](https://git.libre-soc.org/?p=openpower-isa.git;a=tree;f=src/openpower/decoder/isa;hb=HEAD).  Explaining
these Modes further in detail is beyond the scope of this document.

In Indexed Mode, there are only 5 bits available to specify the GPR
to use, out of 128 GPRs (7 bit numbering).  Therefore, only the top
5 bits are given in the `SVxd` field: the bottom two implicit bits
will be zero (`SVxd || 0b00`).

`svshape` has *limited applicability* due to being a 32-bit instruction.
The full capability of SVSHAPE SPRs may be accessed by directly writing
to SVSHAPE0-3 with `mtspr`. Circumstances include Matrices with dimensions
larger than 32, and in-place Transpose.  Potentially a future
instruction may extend the capability here.

Programmer's Note: Parallel Reduction Mode is selected by setting `SVRM=7,SVyd=1`.
Prefix Sum Mode is selected by setting `SVRM=7,SVyd=3`:

```
    # Vector length of 8.
    svshape 8, 3, 1, 0x7, 0
    # activate SVSHAPE0 (prefix-sum lhs) for RA
    # activate SVSHAPE1 (prefix-sum rhs) for RT and RB
    svremap 7, 0, 1, 0, 1, 0, 0
    sv.add *10, *10, *10
```

*Architectural Resource Allocation note: the SVRM field is carefully
crafted to allocate two Modes, corresponding to bits 21-23 within the
instruction being set to the value `0b100`, to `svshape2` (not
`svshape`). These two Modes are
considered "RESERVED" within the context of `svshape` but it is
absolutely critical to allocate the exact same pattern in XO for
both instructions in bits 26-31.*

-------------

\newpage{}


# svindex instruction  <a name="svindex"> </a>

SVI-Form

| 0:5|6:10 |11:15  |16:20 | 21:25       | 26:31 |  Form    |
| -- | --  | ---   | ---- | ----------- | ------| -------- |
| PO | SVG | rmm   | SVd  | ew/yx/mm/sk | XO    | SVI-Form |

* svindex SVG,rmm,SVd,ew,SVyx,mm,sk

See [[sv/remap/appendix]] for `svindex` pseudocode

Special Registers Altered:

```
    SVSTATE, SVSHAPE0-3
```

`svindex` is a convenience instruction that reduces instruction count
for Indexed REMAP Mode. It sets up (overwrites) all required SVSHAPE
SPRs and **unlike** `svshape` can modify the REMAP area of the SVSTATE
SPR as well, including setting persistence.  The relevant SPRs *may*
be directly programmed with `mtspr` however it is laborious to do so:
svindex saves instructions covering much of Indexed REMAP capability.

Fields:

* **SVd** - SV REMAP x/y dim
* **rmm** - REMAP mask: sets remap mi0-2/mo0-1 and SVSHAPEs,
  controlled by mm
* **ew** - sets element width override on the Indices
* **SVG** - GPR SVG<<2 to be used for Indexing
* **yx** - 2D reordering to be used if yx=1
* **mm** - mask mode. determines how `rmm` is interpreted.
* **sk** - Dimension skipping enabled

*Note: SVd, like SVxd, SVyz and SVzd of `svshape`, are all stored
"off-by-one".  In the assembler
mnemonic the values `1-32` are stored in binary as `0b00000..0b11111`*.

*Note: when `yx=1,sk=0` the second dimension is calculated as
`CEIL(MAXVL/SVd)`*.

When `mm=0`:

* `rmm`, like REMAP.SVme, has bit 0
  correspond to mi0, bit 1 to mi1, bit 2 to mi2,
  bit 3 to mo0 and bit 4 to mi1
* all SVSHAPEs and the REMAP parts of SVSHAPE are first reset (initialised to zero)
* for each bit set in the 5-bit `rmm`, in order, the first
  as-yet-unset SVSHAPE will be updated
  with the other operands in the instruction, and the REMAP
  SPR set.
* If all 5 bits of `rmm` are set then both mi0 and mo1 use SVSHAPE0.
* SVSTATE persistence bit is cleared
* No other alterations to SVSTATE are carried out

Example 1: if rmm=0b00110 then SVSHAPE0 and SVSHAPE1 are set up,
and the REMAP SPR set so that mi1 uses SVSHAPE0 and mi2
uses mi2.  REMAP.SVme is also set to 0b00110, REMAP.mi1=0
(SVSHAPE0) and REMAP.mi2=1 (SVSHAPE1)

Example 2: if rmm=0b10001 then again SVSHAPE0 and SVSHAPE1
are set up, but the REMAP SPR is set so that mi0 uses SVSHAPE0
and mo1 uses SVSHAPE1. REMAP.SVme=0b10001, REMAP.mi0=0, REMAP.mo1=1

Rough algorithmic form:

```
    marray = [mi0, mi1, mi2, mo0, mo1]
    idx = 0
    for bit = 0 to 4:
        if not rmm[bit]: continue
        setup(SVSHAPE[idx])
        SVSTATE{marray[bit]} = idx
        idx = (idx+1) modulo 4
```

When `mm=1`:

* bits 0-2 (MSB0 numbering) of `rmm` indicate an index selecting mi0-mo1
* bits 3-4 (MSB0 numbering) of `rmm` indicate which SVSHAPE 0-3 shall
  be updated
* only the selected SVSHAPE is overwritten
* only the relevant bits in the REMAP area of SVSTATE are updated
* REMAP persistence bit is set.

Example 1: if `rmm`=0b01110 then bits 0-2 (MSB0) are 0b011 and
bits 3-4 are 0b10. thus, mo0 is selected and SVSHAPE2
to be updated. REMAP.SVme[3] will be set high and REMAP.mo0
set to 2 (SVSHAPE2).

Example 2: if `rmm`=0b10011 then bits 0-2 (MSB0) are 0b100 and
bits 3-4 are 0b11.  thus, mo1 is selected and SVSHAPE3
to be updated. REMAP.SVme[4] will be set high and REMAP.mo1
set to 3 (SVSHAPE3).

Rough algorithmic form:

```
    marray = [mi0, mi1, mi2, mo0, mo1]
    bit = rmm[0:2]
    idx = rmm[3:4]
    setup(SVSHAPE[idx])
    SVSTATE{marray[bit]} = idx
    SVSTATE.pst = 1
```

In essence, `mm=0` is intended for use to set as much of the
REMAP State SPRs as practical with a single instruction,
whilst `mm=1` is intended to be a little more refined.

**Usage guidelines**

* **Disable 2D mapping**: to only perform Indexing without
 reordering use `SVd=1,sk=0,yx=0` (or set SVd to a value larger
 or equal to VL)
* **Modulo 1D mapping**: to perform Indexing cycling through the
 first N Indices use `SVd=N,sk=0,yx=0` where `VL>N`. There is
 no requirement to set VL equal to a multiple of N.
* **Modulo 2D transposed**: `SVd=M,sk=0,yx=1`, sets
 `xdim=M,ydim=CEIL(MAXVL/M)`.

Beyond these mappings it becomes necessary to write directly to
the SVSTATE SPRs manually.

-------------

\newpage{}


# svshape2 (offset-priority) <a name="svshape2"> </a>

SVM2-Form

| 0:5|6:9 |10|11:15  |16:20  | 21:24  | 25 | 26:31 |  Form      |
| -- |----|--| ---   | ----- | ------ | -- | ------| --------   |
| PO |offs|yx| rmm   | SVd   | 100/mm | sk | XO    | SVM2-Form  |

* svshape2 offs,yx,rmm,SVd,sk,mm

See [[sv/remap/appendix]] for `svshape2` pseudocode

Special Registers Altered:

```
    SVSTATE, SVSHAPE0-3
```

`svshape2` is an additional convenience instruction that prioritises
setting `SVSHAPE.offset`. Its primary purpose is for use when
element-width overrides are used. It has identical capabilities to `svindex`
in terms of both options (skip, etc.) and ability to activate REMAP
(rmm, mask mode) but unlike `svindex` it does not set GPR REMAP:
only a 1D or 2D `svshape`, and
unlike `svshape` it can set an arbitrary `SVSHAPE.offset` immediate.

One of the limitations of Simple-V is that Vector elements start on the boundary
of the Scalar regfile, which is fine when element-width overrides are not
needed. If the starting point of a Vector with smaller elwidths must begin
in the middle of a register, normally there would be no way to do so except
through costly LD/ST.  `SVSHAPE.offset` caters for this scenario and `svshape2`
makes it easier to access.

**Operand Fields**:

* **offs** (4 bits) - unsigned offset
* **yx** (1 bit) - swap XY to YX
* **SVd** dimension size
* **rmm** REMAP mask
* **mm** mask mode
* **sk** (1 bit) skips 1st dimension if set

Dimensions are calculated exactly as `svindex`. `rmm` and
`mm` are as per `svindex`.

*Programmer's Note: offsets for `svshape2` may be specified in the range
0-15. Given that the principle of Simple-V is to fit on top of
byte-addressable register files and that GPR and FPR are 64-bit (8 bytes)
it should be clear that the offset may, when `elwidth=8`, begin an
element-level operation starting element zero at any arbitrary byte.
On cursory examination attempting to go beyond the range 0-7 seems
unnecessary given that the **next GPR or FPR** is an
alias for an offset in the range 8-15.  Thus by simply increasing
the starting Vector point of the operation to the next register it
can be seen that the offset of 0-7 would be sufficient.  Unfortunately
however some operations are EXTRA2-encoded it is **not possible**
to increase the GPR/FPR register number by one, because EXTRA2-encoding
of GPR/FPR Vector numbers are restricted to even numbering.
For CR Fields the EXTRA2 encoding is even more sparse.
The additional offset range (8-15) helps overcome these limitations.*

*Hardware Implementor's note: with the offsets only being immediates
and with register numbering being entirely immediate as well it is
possible to correctly compute Register Hazards without requiring
reading the contents of any SPRs.  If however there are
instructions that have directly written to the SVSTATE or SVSHAPE
SPRs and those instructions are still in-flight then this position
is clearly **invalid**. This is why Programmers are strongly
discouraged from directly writing to these SPRs.*

*Architectural Resource Allocation note: this instruction shares
the space of `svshape`. Therefore it is critical that the two
instructions, `svshape` and `svshape2` have the exact same XO
in bits 26 thru 31.  It is also critical that for `svshape2`,
bit 21 of XO is a 1, bit 22 of XO is a 0, and bit 23 of XO is a 0.*

[[!tag standards]]

-------------

\newpage{}