add pseudocode for swizzle

[libreriscv.git] / simple_v_extension / abridged_spec.mdwn

# Simple-V (Parallelism Extension Proposal) Specification (Abridged)

* Copyright (C) 2017, 2018, 2019 Luke Kenneth Casson Leighton
* Status: DRAFTv0.6
* Last edited: 27 jun 2019
* See: main [[specification]] and [[appendix]]

[[!toc ]]

# Introduction

Simple-V is a uniform parallelism API for RISC-V hardware that allows
the Program Counter to enter "sub-contexts" in which, ultimately, standard
RISC-V scalar opcodes are executed.

Regardless of the actual amount of hardware parallelism (if any is
added at all by the implementor),
in direct contrast to SIMD
hardware parallelism is entirely transparent to software.

The sub-context execution is "nested" in "re-entrant" form, in the
following order:

* Main standard RISC-V Program Counter (PC)
* VBLOCK sub-execution context (PCVBLK increments whilst PC is paused).
* VL element loops (STATE srcoffs and destoffs increment, PC and PCVBLK pause).
  Predication bits may be individually applied per element.
* Optional SUBVL element loops (STATE svdestoffs increments, VL pauses).
  Individual predicate bits from VL loops apply to the *group* of SUBVL
  elements.

An ancillary "SVPrefix" Format (P48/P64) [[sv_prefix_proposal]] may run
its own VL/SUBVL "loops" and specifies its own Register and Predication
format on the 32-bit RV scalar opcode embedded within it.

The [[vblock_format]] specifies how VBLOCK sub-execution contexts
operate.

SV is never actually switched "off".  VL or SUBVL may be equal to 1,
and Register or Predicate over-ride tables may be empty: under such
circumstances the behaviour becomes effectively identical to standard
RV execution, however SV is never truly actually "off".

Note: **there are *no* new opcodes**. The scheme works *entirely*
on hidden context that augments (nests) *scalar* RISC-V instructions.
Thus it may cover existing, future and custom scalar extensions, turning
all existing, all future and all custom scalar operations parallel,
without requiring any special (identical, parallel variant) opcodes to do so.

# CSRs <a name="csrs"></a>

There are five CSRs, available in any privilege level:

* MVL (the Maximum Vector Length)
* VL (which has different characteristics from standard CSRs)
* SUBVL (effectively a kind of SIMD)
* STATE (containing copies of MVL, VL and SUBVL as well as context information)
* PCVBLK (the current operation being executed within a VBLOCK Group)

For Privilege Levels (trap handling) there are the following CSRs,
where x may be u, m, s or h for User, Machine, Supervisor or Hypervisor
Modes respectively:

* (x)ePCVBLK (a copy of the sub-execution Program Counter, that is relative
  to the start of the current VBLOCK Group, set on a trap).
* (x)eSTATE (useful for saving and restoring during context switch,
  and for providing fast transitions)

The u/m/s CSRs are treated and handled exactly like their (x)epc
equivalents.  On entry to or exit from a privilege level, the contents
of its (x)eSTATE are swapped with STATE.

(x)EPCVBLK CSRs must be treated exactly like their corresponding (x)epc
equivalents. See VBLOCK section for details.

## MAXVECTORLENGTH (MVL) <a name="mvl" />

MAXVECTORLENGTH is the same concept as MVL in RVV, except that it
is variable length and may be dynamically set.  MVL is
however limited to the regfile bitwidth XLEN (1-32 for RV32,
1-64 for RV64 and so on).

## Vector Length (VL) <a name="vl" />

VSETVL is slightly different from RVV.  Similar to RVV, VL is set to be within
the range 1 <= VL <= MVL (where MVL in turn is limited to 1 <= MVL <= XLEN)

    VL = rd = MIN(vlen, MVL)

where 1 <= MVL <= XLEN

## SUBVL - Sub Vector Length

This is a "group by quantity" that effectively asks each iteration
of the hardware loop to load SUBVL elements of width elwidth at a
time. Effectively, SUBVL is like a SIMD multiplier: instead of just 1
operation issued, SUBVL operations are issued.

The main effect of SUBVL is that predication bits are applied per
**group**, rather than by individual element.  Legal values are 1 to 4.
Illegal values raise an exception.

## STATE

This is a standard CSR that contains sufficient information for a
full context save/restore.  It contains (and permits setting of):

* MVL
* VL
* destoffs - the destination element offset of the current parallel
  instruction being executed
* srcoffs - for twin-predication, the source element offset as well.
* SUBVL
* dsvoffs - the subvector destination element offset of the current
  parallel instruction being executed

The format of the STATE CSR is as follows:

| (31..28) | (27..26) | (25..24) | (23..18) | (17..12) | (11..6) | (5...0) |
| -------- | -------- | -------- | -------- | -------- | ------- | ------- |
| rsvd     | dsvoffs  | subvl    | destoffs | srcoffs  | vl      | maxvl   |

The relationship between SUBVL and the subvl field is:

| SUBVL | (25..24) |
| ----- | -------- |
| 1     | 0b00     |
| 2     | 0b01     |
| 3     | 0b10     |
| 4     | 0b11     |

Notes:

* The entries are truncated to be within range.  Attempts to set VL to
  greater than MAXVL will truncate VL.
* Both VL and MAXVL are stored offset by one.  0b000000 represents VL=1,
  0b000001 represents VL=2.  This allows the full range 1 to XLEN instead
  of 0 to only 63.

## VL, MVL and SUBVL instruction aliases

This table contains pseudo-assembly instruction aliases. Note the
subtraction of 1 from the CSRRWI pseudo variants, to compensate for the
reduced range of the 5 bit immediate.

| alias           | CSR                  |
| -               | -                    |
| SETVL rd, rs    | CSRRW  VL, rd, rs    |
| SETVLi rd, #n   | CSRRWI VL, rd, #n-1  |
| GETVL rd        | CSRRW  VL, rd, x0    |
| SETMVL rd, rs   | CSRRW  MVL, rd, rs   |
| SETMVLi rd, #n  | CSRRWI MVL,rd, #n-1  |
| GETMVL rd       | CSRRW  MVL, rd, x0   |

Note: CSRRC and other bitsetting may still be used, they are however
not particularly useful (very obscure).

## Register key-value (CAM) table <a name="regcsrtable" />

The purpose of the Register table is to mark which registers change
behaviour if used in a "Standard" (normally scalar) opcode.

[[!inline raw="yes" pages="simple_v_extension/reg_table_format" ]]

Fields:

* i/f is set to "1" to indicate that the redirection/tag entry is to
  be applied to integer registers; 0 indicates that it is relevant to
  floating-point registers.
* isvec indicates that the register (whether a src or dest) is to progress
  incrementally forward on each loop iteration.  this gives the "effect"
  of vectorisation.  isvec is zero indicates "do not progress", giving
  the "effect" of that register being scalar.
* vew overrides the operation's default width.  See table below
* regkey is the register which, if encountered in an op (as src or dest)
  is to be "redirected"
* in the 16-bit format, regidx is the *actual* register to be used
  for the operation (note that it is 7 bits wide)

| vew | bitwidth            |
| --- | ------------------- |
| 00  | default (XLEN/FLEN) |
| 01  | 8 bit               |
| 10  | 16 bit              |
| 11  | 32 bit              |

As the above table is a CAM (key-value store) it may be appropriate
(faster, less gates, implementation-wise) to expand it as follows:

[[!inline raw="yes" pages="simple_v_extension/reg_table" ]]

## Predication Table <a name="predication_csr_table"></a>

The Predication Table is a key-value store indicating whether, if a
given destination register (integer or floating-point) is referred to
in an instruction, it is to be predicated. Like the Register table, it
is an indirect lookup that allows the RV opcodes to not need modification.

* regidx is the register that in combination with the
  i/f flag, if that integer or floating-point register is referred to in a
  (standard RV) instruction results in the lookup table being referenced
  to find the predication mask to use for this operation.
* predidx is the *actual* (full, 7 bit) register to be used for the
  predication mask.
* inv indicates that the predication mask bits are to be inverted
  prior to use *without* actually modifying the contents of the
  register from which those bits originated.
* zeroing is either 1 or 0, and if set to 1, the operation must
  place zeros in any element position where the predication mask is
  set to zero.  If zeroing is set to 0, unpredicated elements *must*
  be left alone (unaltered), even when elwidth != default.
* ffirst is a special mode that stops sequential element processing when
  a data-dependent condition occurs, whether a trap or a conditional test.
  The handling of each (trap or conditional test) is slightly different:
  see Instruction sections for further details

[[!inline raw="yes" pages="simple_v_extension/pred_table_format" ]]

Pseudocode for predication:

[[!inline raw="yes" pages="simple_v_extension/pred_table" ]]
[[!inline raw="yes" pages="simple_v_extension/get_pred_value" ]]

## Swizzle Table <a name="swizzle_table"></a>

The swizzle table is a key-value store that indicates (if a given
register is used, and SUBVL is 2, 3 or 4) that the sub-elements are to
be re-ordered according to the indices in the Swizzle format.
Like the Predication Table, it is an indirect lookup: use of a
source or destination register in any given operation, if that register
occurs in the table, "activates" sub-vector element swizzling for
that register.  Note that the target is taken from the "Register Table"
(regidx).

Source vectors are free to have the swizzle indices point to the same
sub-vector element.  However when using swizzling on destination vectors,
the swizzle **must** be a permutation (no two swizzle indices point to
the same sub-element).  An illegal instruction exception must be raised
if this occurs.

[[!inline raw="yes" pages="simple_v_extension/swizzle_table_format" ]]

Simplified pseudocode example, when SUBVL=4 and swizzle is set on rd:

    # default indices if no swizzling table entry present
    x, y, z, w = 0, 1, 2, 3

    # lookup swizzling in table for rd
    if swizzle_table[rd].active:
        swizzle = swizzle_table[rd].swizzle

        # decode the swizzle table entry for rd
        x = swizzle[0:1] # sub-element 0
        y = swizzle[2:3] # sub-element 1
        z = swizzle[4:5] # sub-element 2
        w = swizzle[6:7] # sub-element 3

    # redirect register numbers through Register Table
    rd  = int_vec[rd ].isvector ? int_vec[rd ].regidx : rd;
    rs1 = int_vec[rs1].isvector ? int_vec[rs1].regidx : rs1;
    rs2 = int_vec[rs2].isvector ? int_vec[rs2].regidx : rs2;

    # loop on VL: SUBVL loop is unrolled (SUBVL=4)
    for (i in 0; i < VL; i++)
        ireg[rd+i*4+x] = OPERATION(ireg[rs1+i*4+0], ireg[rs2+i*4+0])
        ireg[rd+i*4+y] = OPERATION(ireg[rs1+i*4+1], ireg[rs2+i*4+1])
        ireg[rd+i*4+z] = OPERATION(ireg[rs1+i*4+2], ireg[rs2+i*4+2])
        ireg[rd+i*4+w] = OPERATION(ireg[rs1+i*4+3], ireg[rs2+i*4+3])

For more information on swizzling, see the Khronos wiki page
<https://www.khronos.org/opengl/wiki/Data_Type_(GLSL)#Swizzling>

## Fail-on-First Mode <a name="ffirst-mode"></a>

ffirst is a special data-dependent predicate mode.  There are two
variants: one is for faults: typically for LOAD/STORE operations, which
may encounter end of page faults during a series of operations.  The other
variant is comparisons, and anything that returns "zero" or "fail". Note:
no instruction may operate in both fault mode and "condition fail" mode.

Fail on first critically relies on the program order being sequential,
even for elements. Out of order designs must *commit* in-order, and are
required to cancel elements at and beyond the fail point.

See [[appendix]] for more details on fail-on-first modes.

# Simplified Pseudo-code example

A greatly simplified example illustrating (just) the VL hardware for-loop
is as follows:

[[!inline raw="yes" pages="simple_v_extension/simple_add_example" ]]

Note that zeroing, elwidth handling, SUBVL and PCVLIW have all been
left out, for clarity.  For examples on how to handle each, see
[[appendix]].

# Vector Block Format <a name="vliw-format"></a>

The Vector Block format uses the RISC-V 80-192 bit format from Section 1.5
of the RISC-V Spec.  It permits an optional VL/MVL/SUBVL block, up to 4
16-bit (or 8 8-bit) Register Table entries, the same for Predicate Entries,
and the rest of the instruction may be either standard RV opcodes or the
SVPrefix opcodes ([[sv_prefix_proposal]])

[[!inline raw="yes" pages="simple_v_extension/vblock_format_table" ]]

For full details see ancillary resource: [[vblock_format]]

# Exceptions

Exception handling **MUST** be precise, in-order, and exactly
like Standard RISC-V as far as the instruction execution order is
concerned, regardless of whether it is PC, PCVBLK, VL or SUBVL that
is currently being incremented.

This.is extremely important. Exceptions
**MUST** be raised one at a time and in
strict sequential program order.

No instructions are permitted to be out of
sequence, therefore no exceptions are permitted to be, either.

# Hints

With Simple-V being capable of issuing *parallel* instructions where
rd=x0, the space for possible HINTs is expanded considerably.  VL
could be used to indicate different hints.  In addition, if predication
is set, the predication register itself could hypothetically be passed
in as a *parameter* to the HINT operation.

No specific hints are yet defined in Simple-V

# Subsets of RV functionality

It is permitted to only implement SVprefix and not the VBLOCK instruction
format option, and vice-versa.  UNIX Platforms **MUST** raise illegal
instruction on seeing an unsupported VBLOCK or SVprefix opcode, so that
traps may emulate the format.

It is permitted in SVprefix to either not implement VL or not implement
SUBVL (see [[sv_prefix_proposal]] for full details. Again, UNIX Platforms
*MUST* raise illegal instruction on implementations that do not support
VL or SUBVL.

It is permitted to limit the size of either (or both) the register files
down to the original size of the standard RV architecture.  However, below
the mandatory limits set in the RV standard will result in non-compliance
with the SV Specification.