* <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]]
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 (when elwidth overrides are
-used), independently on each Vector src or dest register.
+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:
+A normal Vector Add (no Element-width Overrides):
```
for i in range(VL):
Multiply, DCT and FFT have helper instruction options which make REMAP
easier to use.*
-*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.*
-
-There are four types of REMAP:
+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.
+ 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
are cacheable from the point at which the `svindex` instruction
is executed.
-Parallel Reduction is unusual in that it requires a full vector array
-of results (not a scalar) and uses the rest of the result Vector for
-the purposes of storing intermediary calculations. As these intermediary
-results are Deterministically computed they may be useful.
-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).
-
-*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.*
-
-## Horizontal-Parallelism Hint
-
-`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`).
-
-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 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
-(costly),
-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 (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 include EXT1xx prefixed
-variants (`psvshape`) which provide more comprehensive capacity and
-mitigate the need to write direct to the SVSHAPE SPRs.
-
-### 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-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.
-
-The original motivation for Indexed REMAP was to mitigate the need to add
-an expensive `mv.x` to the Scalar ISA, which was likely to be rejected as
-a stand-alone instruction
-(`GPR(RT) <- GPR(GPR(RA))`). Usually a Vector ISA would add a non-conflicting
-variant (as in VSX `vperm`) but it is common to need to permute by source,
-with the risk of conflict, that has to be resolved, for example, in AVX-512
-with `conflictd`.
-
-Indexed REMAP on the other hand **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.*
-
-### 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 operations.
-
-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 Words 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*
-
-### 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.
+*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
+## 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
corresponding associated co-result CR Field must not be forgotten, *including* when
Predication is used.
-## REMAP area of SVSTATE SPR
+**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:
SVSTATE
```
-`svremap` determines the relationship between registers and SVSHAPE SPRs.
+`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
when using `svindex` or `svshape2`.
Hardware Architectural Note: when persistence is not set it is critically important
-to treat the `svremap` and the following SVP64 instruction as an indivisible fused operation.
+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
# SHAPE Remapping SPRs
There are four "shape" SPRs, SHAPE0-3, 32-bits in each,
-which have the same format.
+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`.
-Shape is 32-bits. When SHAPE is set entirely to zeros, remapping is
+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| zdimsz | permute | invxyz |offset|skip |0b00 |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` (combined with `permute` when `mode=0b00`) sets different
+general behaviours: straight matrix multiply, FFT, DCT, Reduction or Prefix-Sum.
-* **mode=0b00** sets straight Matrix Mode
-* **mode=0b00** with permute=0b110 or 0b111 sets Indexed Mode
+* **mode=0b00** with `permute != 0b110/0b111` sets straight Matrix Mode
+* **mode=0b00** with `permute = 0b110/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`*
+be used to manipulate (save/restore) them.
+This is safe to do directly as long as `SVSTATE.SVme=0`*
## Parallel Reduction / Prefix-Sum Mode
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
## 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:
+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 ...```
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
+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.
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
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{}
| -- | -- |
| 0b0000 | Matrix 1/2/3D |
| 0b0001 | FFT Butterfly |
-| 0b0010 | reserved |
+| 0b0010 | reserved for Matrix Outer Product |
| 0b0011 | DCT Outer butterfly |
| 0b0100 | DCT Inner butterfly, on-the-fly (Vertical-First Mode) |
| 0b0101 | DCT COS table index generation |
`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.
+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`:
projects / libreriscv.git / blobdiff