https://bugs.libre-soc.org/show_bug.cgi?id=985

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

[[!tag standards]]

# REMAP <a name="remap" />

* <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
* see [[sv/remap/appendix]] for examples and usage
* see [[sv/propagation]] for a future way to apply REMAP

REMAP is an advanced form of Vector "Structure Packing" that
provides hardware-level support for commonly-used *nested* loop patterns.
For more general reordering an Indexed REMAP mode is available.

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 (when elwidth overrides are used),
independently on each Vector src or dest
register.

The initial primary motivation of REMAP was for Matrix Multiplication, reordering of sequential
data in-place: in-place DCT and FFT were easily justified given the
high usage in Computer Science.
Four SPRs are provided which may be applied to any GPR, FPR or CR Field
so that for example a single FMAC may be
used in a single loop to perform 5x3 times 3x4 Matrix multiplication,
generating 60 FMACs *without needing explicit assembler unrolling*.
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 *directly* apply to sub-vector elements: that 
is what swizzle is for.  Swizzle *can* however be applied to the same
instruction as REMAP.  As explained in [[sv/mv.swizzle]], [[sv/mv.vec]] and the [[svp64/appendix]], Pack and Unpack EXTRA Mode bits
can extend down into Sub-vector elements to perform vec2/vec3/vec4
sequential reordering, but even here, REMAP is not extended down to
the actual sub-vector elements themselves.

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.
Commonly-used patterns such as Matrix Multiply, DCT and FFT have
helper instruction options which make REMAP easier to use.

There are three types of REMAP:

* **Matrix**, also known as 2D and 3D reshaping, can perform in-place
  Matrix transpose and rotate.
* **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.

# Basic principle

* normal vector element read/write of 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)
  and very few Packed SIMD ISAs cope with non-Power-2.
* REMAP **redefines** the order of access according to set "Schedules".
* The Schedules are not necessarily restricted to power-of-two boundaries
  making it unnecessary to have for example specialised 3x4 transpose
  instructions.

Only the most commonly-used algorithms in computer science have REMAP
support, due to the high cost in both the ISA and in hardware.  For
arbitrary remapping the `Indexed` REMAP may be used.

# Executive Summary Usage

* `svshape` to set the type of reordering to be applied to an
  otherwise usual `0..VL-1` hardware for-loop
* `svremap` to set which registers a given reordering is to apply to
  (RA, RT etc)
* `sv.{instruction}` where any Vectorised register marked by `svremap`
  will have its ordering REMAPPED according to the schedule set
  by `svshape`.

The following illustrative example multiplies a 3x4 and a 5x3
matrix to create
a 5x4 result:

    svshape 5, 4, 3, 0, 0
    svremap 15, 1, 2, 3, 0, 0, 0, 0
    sv.fmadds 0.v, 8.v, 16.v, 0.v

* svshape sets up the four SVSHAPE SPRS for a Matrix Schedule
* svremap activates four out of five registers RA RB RC RT RS (15)
* svremap requests:
  - RA to use SVSHAPE1
  - RB to use SVSHAPE2
  - RC to use SVSHAPE3
  - RT to use SVSHAPE0
  - RS Remapping to not be activated
* sv.fmadds has RT=0.v, RA=8.v, RB=16.v, RC=0.v
* With REMAP being active each register's element index is
  *independently* transformed using the specified SHAPEs.

Thus the Vector Loop is arranged such that the use of
the multiply-and-accumulate instruction executes precisely the required
Schedule to perform an in-place in-registers Matrix Multiply with no
need to perform additional Transpose or register copy instructions.
The example above may be executed as a unit test and demo,
[here](https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=src/openpower/decoder/isa/test_caller_svp64_matrix.py;h=c15479db9a36055166b6b023c7495f9ca3637333;hb=a17a252e474d5d5bf34026c25a19682e3f2015c3#l94)
     
# REMAP types

This section summarises the motivation for each REMAP Schedule
and briefly goes over their characteristics and limitations.
Further details on the Deterministic Precise-Interruptible algorithms
used in these Schedules is found in the [[sv/remap/appendix]].

## Matrix (1D/2D/3D shaping)

Matrix Multiplication is a huge part of High-Performance Compute,
and 3D.
In many PackedSIMD as well as Scalable Vector ISAs, non-power-of-two
Matrix sizes are a serious challenge. PackedSIMD ISAs, in order to
cope with for example 3x4 Matrices, recommend rolling data-repetition and loop-unrolling.
Aside from the cost of the load on the L1 I-Cache, the trick only
works if one of the dimensions X or Y are power-two. Prime Numbers
(5x7, 3x5) become deeply problematic to unroll.

Even traditional Scalable Vector ISAs have issues with Matrices, often
having to perform data Transpose by pushing out through Memory and back,
or computing Transposition Indices (costly) then copying to another
Vector (costly).

Matrix REMAP was thus designed to solve these issues by providing Hardware
Assisted
"Schedules" that can view what would otherwise be limited to a strictly
linear Vector as instead being 2D (even 3D) *in-place* reordered.
With both Transposition and non-power-two being supported the issues
faced by other ISAs are mitigated.

Limitations of Matrix REMAP are that the Vector Length (VL) is currently
restricted to 127: up to 127 FMAs may be performed in total (potentially
127 vec2/3/4 FMAs may be used but this requires additional research).
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 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.

## FFT/DCT Triple Loop

DCT and FFT are some of the most astonishingly used algorithms in
Computer Science.  Radar, Audio, Video, R.F. Baseband and dozens more.  At least
two DSPs, TMS320 and Hexagon, have VLIW instructions specially tailored
to FFT.

An in-depth analysis showed that it is possible to do in-place in-register
DCT and FFT as long as twin-result "butterfly" instructions are provided.
These can be found in the [[openpower/isa/svfparith]] page if performing
IEEE754 FP transforms. *(For fixed-point transforms, equivalent 3-in 2-out
integer operations would be required)*. These "butterfly" instructions
avoid the need for a temporary register because the two array positions
being overwritten will be "in-flight" in any In-Order or Out-of-Order
micro-architecture.

DCT and FFT Schedules are currently limited to RADIX2 sizes and do not
accept predicate masks.  Given that it is common to perform recursive
convolutions
combining smaller Power-2 DCT/FFT to create larger DCT/FFTs in practice the RADIX2
limit is not a problem.  A Bluestein convolution to compute arbitrary
length is demonstrated
by [Project Nayuki](https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.py)

## Indexed

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.

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 from the point where a given `svindex` instruction
is called (or SVSHAPE SPRs - and MAXVL- directly altered).

# REMAP area of SVSTATE

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.

* 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 / RS
  (LD/ST-with-update has an implicit 2nd write register, RA)

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

There is also a corresponding SVRM-Form for the svremap
instruction which matches the above SPR:

    svremap SVme,mi0,mi1,mi2,mo0,mo2,pst

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

# SHAPE Remapping SPRs

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

[[!inline pages="openpower/sv/shape_table_format" raw="yes" ]]

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

`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`.

Form: SVM-Form SV "Matrix" Form (see [[isatables/fields.text]])

    svshape SVxd,SVyd,SVzd,SVRM,vf

| 0.5|6.10  |11.15  |16..20 | 21..25 | 25 | 26..31|  name    |
| -- | --   | ---   | ----- | ------ | -- | ------| -------- |
|OPCD| SVxd | SVyd  | SVzd  | SVRM   | vf | XO    | svstate  |

Fields:

* **SVxd** - SV REMAP "xdim"
* **SVyd** - SV REMAP "ydim"
* **SVzd** - SV REMAP "zdim"
* **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`*

| SVRM   | Remap Mode description |
| --     | --              |
| 0b0000 | Matrix 1/2/3D    |
| 0b0001 | FFT Butterfly   |
| 0b0010 | DCT Inner butterfly, pre-calculated coefficients |
| 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 | reserved  |
| 0b1000 | reserved |
| 0b1001 | reserved  |
| 0b1010 | iDCT Inner butterfly, pre-calculated coefficients |
| 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)
and the full pseudocode setting up all SPRs
is in the [[openpower/isa/simplev]] page.

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 v3.1 Prefixed
instruction, `psvshape`, may extend the capability here.

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

`svindex` is a convenience instruction that reduces instruction
count for Indexed REMAP Mode. It sets up
(overwrites) all required SVSHAPE SPRs and can modify the REMAP
SPR as well.  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.

Form: SVI-Form SV "Indexed" Form (see [[isatables/fields.text]])

    svindex SVG,rmm,SVd,ew,yx,mr,sk

| 0.5|6.10 |11.15  |16.20 | 21..25      | 26..31|  name    | Form |
| -- | --  | ---   | ---- | ----------- | ------| -------- | ---- |
|OPCD| SVG | rmm   | SVd  | ew/yx/mm/sk | XO    | svindex | SVI-Form |

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 RS
* **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
* **XO** - standard 6-bit XO field

*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.


# TODO

* investigate https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6879380/#!po=19.6429
in https://bugs.libre-soc.org/show_bug.cgi?id=653
* UTF-8 <https://bugs.libre-soc.org/show_bug.cgi?id=794>
* Triangular REMAP
* Cross-Product REMAP (actually, skew Matrix: https://en.m.wikipedia.org/wiki/Skew-symmetric_matrix)
* Convolution REMAP