1 # REMAP <a name="remap" />
4 * <https://bugs.libre-soc.org/show_bug.cgi?id=143> matrix multiply
5 * <https://bugs.libre-soc.org/show_bug.cgi?id=867> add svindex
6 * <https://bugs.libre-soc.org/show_bug.cgi?id=885> svindex in simulator
7 * <https://bugs.libre-soc.org/show_bug.cgi?id=911> offset svshape option
8 * <https://bugs.libre-soc.org/show_bug.cgi?id=864> parallel reduction
9 * <https://bugs.libre-soc.org/show_bug.cgi?id=930> DCT/FFT "strides"
10 * see [[sv/remap/appendix]] for examples and usage
11 * see [[sv/propagation]] for a future way to apply REMAP
12 * [[remap/discussion]]
15 REMAP is an advanced form of Vector "Structure Packing" that provides
16 hardware-level support for commonly-used *nested* loop patterns that would
17 otherwise require full inline loop unrolling. For more general reordering
18 an Indexed REMAP mode is available (a RISC-paradigm
19 abstracted analog to `xxperm`).
21 REMAP allows the usual sequential vector loop `0..VL-1` to be "reshaped"
22 (re-mapped) from a linear form to a 2D or 3D transposed form, or "offset"
23 to permit arbitrary access to elements (when elwidth overrides are
24 used), independently on each Vector src or dest register.
30 GPR[RT+i] <= GPR[RA+i] + GPR[RB+i];
33 A Hardware-assisted REMAP Vector Add:
37 GPR[RT+remap1(i)] <= GPR[RA+remap2(i)] + GPR[RB+remap3(i)];
41 Indexed REMAP this is entirely Hardware-accelerated reordering and
42 consequently not costly in terms of register access for the Indices. It will however
43 place a burden on Multi-Issue systems but no more than if the equivalent
44 Scalar instructions were explicitly loop-unrolled without SVP64, and
45 some advanced implementations may even find the Deterministic nature of
46 the Scheduling to be easier on resources.
48 *Hardware note: in its general form, REMAP is quite expensive to set up, and on some
49 implementations may introduce latency, so should realistically be used
50 only where it is worthwhile. Given that even with latency the fact
51 that up to 127 operations can be Deterministically issued (from a single
52 instruction) it should be clear that REMAP should not be dismissed
53 for *possible* latency alone. Commonly-used patterns such as Matrix
54 Multiply, DCT and FFT have helper instruction options which make REMAP
57 *Future specification note: future versions of the REMAP Management instructions
58 will extend to EXT1xx Prefixed variants. This will overcome some of the limitations
59 present in the 32-bit variants of the REMAP Management instructions that at
60 present require direct writing to SVSHAPE0-3 SPRs. Additional
61 REMAP Modes may also be introduced at that time.*
63 There are five types of REMAP:
65 * **Matrix**, also known as 2D and 3D reshaping, can perform in-place
66 Matrix transpose and rotate. The Shapes are set up for an "Outer Product"
68 * **FFT/DCT**, with full triple-loop in-place support: limited to
70 * **Indexing**, for any general-purpose reordering, also includes
71 limited 2D reshaping as well as Element "offsetting".
72 * **Parallel Reduction**, for scheduling a sequence of operations
73 in a Deterministic fashion, in a way that may be parallelised,
74 to reduce a Vector down to a single value.
75 * **Parallel Prefix Sum**, implemented as a work-efficient Schedule,
76 has several key Computer Science uses. Again Prefix Sum is 100%
79 Best implemented on top of a Multi-Issue Out-of-Order Micro-architecture,
80 REMAP Schedules are 100% Deterministic **including Indexing** and are
81 designed to be incorporated in between the Decode and Issue phases,
82 directly into Register Hazard Management.
84 As long as the SVSHAPE SPRs
85 are not written to directly, Hardware may treat REMAP as 100%
86 Deterministic: all REMAP Management instructions take static
87 operands (no dynamic register operands)
88 with the exception of Indexed Mode, and even then
89 Architectural State is permitted to assume that the Indices
90 are cacheable from the point at which the `svindex` instruction
93 ## Horizontal-Parallelism Hint
95 `SVSTATE.hphint` is an indicator to hardware of how many elements are 100%
96 fully independent. Hardware is permitted to assume that groups of elements
97 up to `hphint` in size need not have Register (or Memory) Hazards created
98 between them (including when `hphint > VL`).
100 If care is not taken in setting `hphint` correctly it may wreak havoc.
101 For example Matrix Outer Product relies on the innermost loop computations
102 being independent. If `hphint` is set to greater than the Outer Product
103 depth then data corruption is guaranteed to occur.
105 Likewise on FFTs it is assumed that each layer of the RADIX2 triple-loop
106 is independent, but that there is strict *inter-layer* Register Hazards.
107 Therefore if `hphint` is set to greater than the RADIX2 width of the FFT,
108 data corruption is guaranteed.
110 Thus the key message is that setting `hphint` requires in-depth knowledge
111 of the REMAP Algorithm Schedules, given in the Appendix.
115 This section summarises the motivation for each REMAP Schedule
116 and briefly goes over their characteristics and limitations.
117 Further details on the Deterministic Precise-Interruptible algorithms
118 used in these Schedules is found in the [[sv/remap/appendix]].
120 ## Determining Register Hazards
122 For high-performance (Multi-Issue, Out-of-Order) systems it is critical
123 to be able to statically determine the extent of Vectors in order to
124 allocate pre-emptive Hazard protection. The next task is to eliminate
125 masked-out elements using predicate bits, freeing up the associated
128 For non-REMAP situations `VL` is sufficient to ascertain early
129 Hazard coverage, and with SVSTATE being a high priority cached
130 quantity at the same level of MSR and PC this is not a problem.
132 The problems come when REMAP is enabled. Indexed REMAP must instead
133 use `MAXVL` as the earliest (simplest)
134 batch-level Hazard Reservation indicator (after taking element-width
135 overriding on the Index source into consideration),
136 but Matrix, FFT and Parallel Reduction must all use completely different
137 schemes. The reason is that VL is used to step through the total
138 number of *operations*, not the number of registers.
139 The "Saving Grace" is that all of the REMAP Schedules are 100% Deterministic.
141 Advance-notice Parallel computation and subsequent cacheing
142 of all of these complex Deterministic REMAP Schedules is
143 *strongly recommended*, thus allowing clear and precise multi-issue
144 batched Hazard coverage to be deployed, *even for Indexed Mode*.
145 This is only possible for Indexed due to the strict guidelines
146 given to Programmers.
148 In short, there exists solutions to the problem of Hazard Management,
149 with varying degrees of refinement possible at correspondingly
150 increasing levels of complexity in hardware.
152 A reminder: when Rc=1 each result register (element) has an associated
153 co-result CR Field (one per result element). Thus above when determining
154 the Write-Hazards for result registers the corresponding Write-Hazards for the
155 corresponding associated co-result CR Field must not be forgotten, *including* when
158 ## REMAP area of SVSTATE SPR
160 The following bits of the SVSTATE SPR are used for REMAP:
163 |32:33|34:35|36:37|38:39|40:41| 42:46 | 62 |
164 | -- | -- | -- | -- | -- | ----- | ------ |
165 |mi0 |mi1 |mi2 |mo0 |mo1 | SVme | RMpst |
168 mi0-2 and mo0-1 each select SVSHAPE0-3 to apply to a given register.
169 mi0-2 apply to RA, RB, RC respectively, as input registers, and
170 likewise mo0-1 apply to output registers (RT/FRT, RS/FRS) respectively.
171 SVme is 5 bits (one for each of mi0-2/mo0-1) and indicates whether the
172 SVSHAPE is actively applied or not, and if so, to which registers.
174 * bit 4 of SVme indicates if mi0 is applied to source RA / FRA / BA / BFA / RT / FRT
175 * bit 3 of SVme indicates if mi1 is applied to source RB / FRB / BB
176 * bit 2 of SVme indicates if mi2 is applied to source RC / FRC / BC
177 * bit 1 of SVme indicates if mo0 is applied to result RT / FRT / BT / BF
178 * bit 0 of SVme indicates if mo1 is applied to result Effective Address / FRS / RS
179 (LD/ST-with-update has an implicit 2nd write register, RA)
181 The "persistence" bit if set will result in all Active REMAPs being applied
188 # svremap instruction <a name="svremap"> </a>
192 |0 |6 |11 |13 |15 |17 |19 |21 | 22:25 |26:31 |
193 | -- | -- | -- | -- | -- | -- | -- | -- | ---- | ----- |
194 | PO | SVme |mi0 | mi1 | mi2 | mo0 | mo1 | pst | rsvd | XO |
196 * svremap SVme,mi0,mi1,mi2,mo0,mo1,pst
201 # registers RA RB RC RT EA/FRS SVSHAPE0-3 indices
202 SVSTATE[32:33] <- mi0
203 SVSTATE[34:35] <- mi1
204 SVSTATE[36:37] <- mi2
205 SVSTATE[38:39] <- mo0
206 SVSTATE[40:41] <- mo1
207 # enable bit for RA RB RC RT EA/FRS
208 SVSTATE[42:46] <- SVme
209 # persistence bit (applies to more than one instruction)
213 Special Registers Altered:
219 `svremap` determines the relationship between registers and SVSHAPE SPRs.
220 The bitmask `SVme` determines which registers have a REMAP applied, and mi0-mo1
221 determine which shape is applied to an activated register. the `pst` bit if
222 cleared indicated that the REMAP operation shall only apply to the immediately-following
223 instruction. If set then REMAP remains permanently enabled until such time as it is
224 explicitly disabled, either by `setvl` setting a new MAXVL, or with another
225 `svremap` instruction. `svindex` and `svshape2` are also capable of setting or
226 clearing persistence, as well as partially covering a subset of the capability of
227 `svremap` to set register-to-SVSHAPE relationships.
229 Programmer's Note: applying non-persistent `svremap` to an instruction that has
230 no REMAP enabled or is a Scalar operation will obviously have no effect but
231 the bits 32 to 46 will at least have been set in SVSTATE. This may prove useful
232 when using `svindex` or `svshape2`.
234 Hardware Architectural Note: when persistence is not set it is critically important
235 to treat the `svremap` and the following SVP64 instruction as an indivisible fused operation.
236 *No state* is stored in the SVSTATE SPR in order to allow continuation should an
237 Interrupt occur between the two instructions. Thus, Interrupts must be prohibited
238 from occurring or other workaround deployed. When persistence is set this issue
241 It is critical to note that if persistence is clear then `svremap` is the *only* way
242 to activate REMAP on any given (following) instruction. If persistence is set however then
243 **all** SVP64 instructions go through REMAP as long as `SVme` is non-zero.
249 # SHAPE Remapping SPRs
251 There are four "shape" SPRs, SHAPE0-3, 32-bits in each,
252 which have the same format.
254 Shape is 32-bits. When SHAPE is set entirely to zeros, remapping is
255 disabled: the register's elements are a linear (1D) vector.
257 |0:5 |6:11 | 12:17 | 18:20 | 21:23 |24:27 |28:29 |30:31| Mode |
258 |----- |----- | ------- | ------- | ------ |------|------ |---- | ----- |
259 |xdimsz|ydimsz| zdimsz | permute | invxyz |offset|skip |mode |Matrix |
260 |xdimsz|ydimsz|SVGPR | 11/ |sk1/invxy|offset|elwidth|0b00 |Indexed|
261 |xdimsz|mode | zdimsz | submode2| invxyz |offset|submode|0b01 |DCT/FFT|
262 | rsvd |rsvd |xdimsz | rsvd | invxyz |offset|submode|0b10 |Red/Sum|
263 | | | | | | | |0b11 |rsvd |
265 `mode` sets different behaviours (straight matrix multiply, FFT, DCT).
267 * **mode=0b00** sets straight Matrix Mode
268 * **mode=0b00** with permute=0b110 or 0b111 sets Indexed Mode
269 * **mode=0b01** sets "FFT/DCT" mode and activates submodes
270 * **mode=0b10** sets "Parallel Reduction or Prefix-Sum" Schedules.
272 *Architectural Resource Allocation note: the four SVSHAPE SPRs are best
273 allocated sequentially and contiguously in order that `sv.mtspr` may
274 be used. This is safe to do as long as `SVSTATE.SVme=0`*
276 ## Parallel Reduction / Prefix-Sum Mode
278 Creates the Schedules for Parallel Tree Reduction and Prefix-Sum
280 * **submode=0b00** selects the left operand index for Reduction
281 * **submode=0b01** selects the right operand index for Reduction
282 * **submode=0b10** selects the left operand index for Prefix-Sum
283 * **submode=0b11** selects the right operand index for Prefix-Sum
285 * When bit 0 of `invxyz` is set, the order of the indices
286 in the inner for-loop are reversed. This has the side-effect
287 of placing the final reduced result in the last-predicated element.
288 It also has the indirect side-effect of swapping the source
289 registers: Left-operand index numbers will always exceed
290 Right-operand indices.
291 When clear, the reduced result will be in the first-predicated
292 element, and Left-operand indices will always be *less* than
294 * When bit 1 of `invxyz` is set, the order of the outer loop
295 step is inverted: stepping begins at the nearest power-of two
296 to half of the vector length and reduces by half each time.
297 When clear the step will begin at 2 and double on each
300 **Parallel Prefix Sum**
302 This is a work-efficient Parallel Schedule that for example produces Trangular
303 or Factorial number sequences. Half of the Prefix Sum Schedule is near-identical
304 to Parallel Reduction. Whilst the Arithmetic mapreduce Mode (`/mr`) may achieve the same
305 end-result, implementations may only implement Mapreduce in serial form (or give
306 the appearance to Programmers of the same). The Parallel Prefix Schedule is
307 *required* to be implemented in such a way that its Deterministic Schedule may be
308 parallelised. Like the Reduction Schedule it is 100% Deterministic and consequently
309 may be used with non-commutative operations.
310 The Schedule Algorithm may be found in the [[sv/remap/appendix]]
312 **Parallel Reduction**
314 Vector Reduce Mode issues a deterministic tree-reduction schedule to the underlying micro-architecture. Like Scalar reduction, the "Scalar Base"
315 (Power ISA v3.0B) operation is leveraged, unmodified, to give the
316 *appearance* and *effect* of Reduction. Parallel Reduction is not limited
317 to Power-of-two but is limited as usual by the total number of
318 element operations (127) as well as available register file size.
320 In Horizontal-First Mode, Vector-result reduction **requires**
321 the destination to be a Vector, which will be used to store
322 intermediary results, in order to achieve a correct final
325 Given that the tree-reduction schedule is deterministic,
326 Interrupts and exceptions
327 can therefore also be precise. The final result will be in the first
328 non-predicate-masked-out destination element, but due again to
329 the deterministic schedule programmers may find uses for the intermediate
330 results, even for non-commutative Defined Word operations.
331 Additionally, because the intermediate results are always written out
332 it is possible to service Precise Interrupts without affecting latency
333 (a common limitation of Vector ISAs implementing explicit
334 Parallel Reduction instructions, because their Architectural State cannot
335 hold the partial results).
337 When Rc=1 a corresponding Vector of co-resultant CRs is also
338 created. No special action is taken: the result *and its CR Field*
339 are stored "as usual" exactly as all other SVP64 Rc=1 operations.
341 Note that the Schedule only makes sense on top of certain instructions:
342 X-Form with a Register Profile of `RT,RA,RB` is fine because two sources
343 and the destination are all the same type. Like Scalar
344 Reduction, nothing is prohibited:
345 the results of execution on an unsuitable instruction may simply
346 not make sense. With care, even 3-input instructions (madd, fmadd, ternlogi)
347 may be used, and whilst it is down to the Programmer to walk through the
348 process the Programmer can be confident that the Parallel-Reduction is
349 guaranteed 100% Deterministic.
351 Critical to note regarding use of Parallel-Reduction REMAP is that,
352 exactly as with all REMAP Modes, the `svshape` instruction *requests*
353 a certain Vector Length (number of elements to reduce) and then
354 sets VL and MAXVL at the number of **operations** needed to be
355 carried out. Thus, equally as importantly, like Matrix REMAP
356 the total number of operations
357 is restricted to 127. Any Parallel-Reduction requiring more operations
358 will need to be done manually in batches (hierarchical
359 recursive Reduction).
361 Also important to note is that the Deterministic Schedule is arranged
362 so that some implementations *may* parallelise it (as long as doing so
363 respects Program Order and Register Hazards). Performance (speed)
365 implementation is neither strictly defined or guaranteed. As with
366 the Vulkan(tm) Specification, strict compliance is paramount whilst
367 performance is at the discretion of Implementors.
369 **Parallel-Reduction with Predication**
371 To avoid breaking the strict RISC-paradigm, keeping the Issue-Schedule
372 completely separate from the actual element-level (scalar) operations,
373 Move operations are **not** included in the Schedule. This means that
374 the Schedule leaves the final (scalar) result in the first-non-masked
375 element of the Vector used. With the predicate mask being dynamic
376 (but deterministic) at a superficial glance it seems this result
379 If that result is needed to be moved to a (single) scalar register
380 then a follow-up `sv.mv/sm=predicate rt, *ra` instruction will be
381 needed to get it, where the predicate is the exact same predicate used
382 in the prior Parallel-Reduction instruction.
384 * If there was only a single
385 bit in the predicate then the result will not have moved or been altered
386 from the source vector prior to the Reduction
387 * If there was more than one bit the result will be in the
388 first element with a predicate bit set.
390 In either case the result is in the element with the first bit set in
391 the predicate mask. Thus, no move/copy *within the Reduction itself* was needed.
393 Programmer's Note: For *some* hardware implementations
394 the vector-to-scalar copy may be a slow operation, as may the Predicated
395 Parallel Reduction itself.
396 It may be better to perform a pre-copy
397 of the values, compressing them (VREDUCE-style) into a contiguous block,
398 which will guarantee that the result goes into the very first element
399 of the destination vector, in which case clearly no follow-up
400 predicated vector-to-scalar MV operation is needed. A VREDUCE effect
401 is achieved by setting just a source predicate mask on Twin-Predicated
406 The simplest usage is to perform an overwrite, specifying all three
407 register operands the same.
410 svshape parallelreduce, 6
414 The Reduction Schedule will issue the Parallel Tree Reduction spanning
415 registers 8 through 13, by adjusting the offsets to RT, RA and RB as
416 necessary (see "Parallel Reduction algorithm" in a later section).
418 A non-overwrite is possible as well but just as with the overwrite
419 version, only those destination elements necessary for storing
420 intermediary computations will be written to: the remaining elements
421 will **not** be overwritten and will **not** be zero'd.
424 svshape parallelreduce, 6
428 However it is critical to note that if the source and destination are
429 not the same then the trick of using a follow-up vector-scalar MV will
432 **Sub-Vector Horizontal Reduction**
434 To achieve Sub-Vector Horizontal Reduction, Pack/Unpack should be enabled,
435 which will turn the Schedule around such that issuing of the Scalar
436 Defined Words is done with SUBVL looping as the inner loop not the
437 outer loop. Rc=1 with Sub-Vectors (SUBVL=2,3,4) is `UNDEFINED` behaviour.
439 *Programmer's Note: Overwrite Parallel Reduction with Sub-Vectors
440 will clearly result in data corruption. It may be best to perform
441 a Pack/Unpack Transposing copy of the data first*
445 submode2=0 is for FFT. For FFT submode the following schedules may be
448 * **submode=0b00** selects the ``j`` offset of the innermost for-loop
450 * **submode=0b10** selects the ``j+halfsize`` offset of the innermost for-loop
452 * **submode=0b11** selects the ``k`` of exptable (which coefficient)
454 When submode2 is 1 or 2, for DCT inner butterfly submode the following
455 schedules may be selected. When submode2 is 1, additional bit-reversing
458 * **submode=0b00** selects the ``j`` offset of the innermost for-loop,
460 * **submode=0b010** selects the ``j+halfsize`` offset of the innermost for-loop,
461 in reverse-order, in-place
462 * **submode=0b10** selects the ``ci`` count of the innermost for-loop,
463 useful for calculating the cosine coefficient
464 * **submode=0b11** selects the ``size`` offset of the outermost for-loop,
465 useful for the cosine coefficient ``cos(ci + 0.5) * pi / size``
467 When submode2 is 3 or 4, for DCT outer butterfly submode the following
468 schedules may be selected. When submode is 3, additional bit-reversing
471 * **submode=0b00** selects the ``j`` offset of the innermost for-loop,
472 * **submode=0b01** selects the ``j+1`` offset of the innermost for-loop,
474 `zdimsz` is used as an in-place "Stride", particularly useful for
475 column-based in-place DCT/FFT.
479 In Matrix Mode, skip allows dimensions to be skipped from being included
480 in the resultant output index. This allows sequences to be repeated:
481 ```0 0 0 1 1 1 2 2 2 ...``` or in the case of skip=0b11 this results in
482 modulo ```0 1 2 0 1 2 ...```
484 * **skip=0b00** indicates no dimensions to be skipped
485 * **skip=0b01** sets "skip 1st dimension"
486 * **skip=0b10** sets "skip 2nd dimension"
487 * **skip=0b11** sets "skip 3rd dimension"
489 invxyz will invert the start index of each of x, y or z. If invxyz[0] is
490 zero then x-dimensional counting begins from 0 and increments, otherwise
491 it begins from xdimsz-1 and iterates down to zero. Likewise for y and z.
493 offset will have the effect of offsetting the result by ```offset``` elements:
497 GPR(RT + remap(i) + SVSHAPE.offset) = ....
500 This appears redundant because the register RT could simply be changed by a compiler, until element width overrides are introduced. Also
501 bear in mind that unlike a static compiler SVSHAPE.offset may
502 be set dynamically at runtime.
504 xdimsz, ydimsz and zdimsz are offset by 1, such that a value of 0 indicates
505 that the array dimensionality for that dimension is 1. any dimension
506 not intended to be used must have its value set to 0 (dimensionality
507 of 1). A value of xdimsz=2 would indicate that in the first dimension
508 there are 3 elements in the array. For example, to create a 2D array
509 X,Y of dimensionality X=3 and Y=2, set xdimsz=2, ydimsz=1 and zdimsz=0
511 The format of the array is therefore as follows:
514 array[xdimsz+1][ydimsz+1][zdimsz+1]
517 However whilst illustrative of the dimensionality, that does not take the
518 "permute" setting into account. "permute" may be any one of six values
519 (0-5, with values of 6 and 7 indicating "Indexed" Mode). The table
520 below shows how the permutation dimensionality order works:
522 | permute | order | array format |
523 | ------- | ----- | ------------------------ |
524 | 000 | 0,1,2 | (xdim+1)(ydim+1)(zdim+1) |
525 | 001 | 0,2,1 | (xdim+1)(zdim+1)(ydim+1) |
526 | 010 | 1,0,2 | (ydim+1)(xdim+1)(zdim+1) |
527 | 011 | 1,2,0 | (ydim+1)(zdim+1)(xdim+1) |
528 | 100 | 2,0,1 | (zdim+1)(xdim+1)(ydim+1) |
529 | 101 | 2,1,0 | (zdim+1)(ydim+1)(xdim+1) |
530 | 110 | 0,1 | Indexed (xdim+1)(ydim+1) |
531 | 111 | 1,0 | Indexed (ydim+1)(xdim+1) |
533 In other words, the "permute" option changes the order in which
534 nested for-loops over the array would be done. See executable
535 python reference code for further details.
537 *Note: permute=0b110 and permute=0b111 enable Indexed REMAP Mode,
540 With all these options it is possible to support in-place transpose,
541 in-place rotate, Matrix Multiply and Convolutions, without being
542 limited to Power-of-Two dimension sizes.
544 **Limitations and caveats**
546 Limitations of Matrix REMAP are that the Vector Length (VL) is currently
547 restricted to 127: up to 127 FMAs (or other operation)
548 may be performed in total.
549 Also given that it is in-registers only at present some care has to be
550 taken on regfile resource utilisation. However it is perfectly possible
551 to utilise Matrix REMAP to perform the three inner-most "kernel" loops of
552 the usual 6-level "Tiled" large Matrix Multiply, without the usual
553 difficulties associated with SIMD.
555 Also the `svshape` instruction only provides access to *part* of the
556 Matrix REMAP capability. Rotation and mirroring need to be done by
557 programming the SVSHAPE SPRs directly, which can take a lot more
558 instructions. Future versions of SVP64 will include EXT1xx prefixed
559 variants (`psvshape`) which provide more comprehensive capacity and
560 mitigate the need to write direct to the SVSHAPE SPRs.
562 Additionally there is not yet a way to set Matrix sizes from registers
563 with `svshape`: this was an intentional decision to simplify Hardware, that
564 may be corrected in a future version of SVP64. The limitation may presently
565 be overcome by direct programming of the SVSHAPE SPRs.
567 *Hardware Architectural note: with the Scheduling applying as a Phase between
568 Decode and Issue in a Deterministic fashion the Register Hazards may be
569 easily computed and a standard Out-of-Order Micro-Architecture exploited to good
570 effect. Even an In-Order system may observe that for large Outer Product
571 Schedules there will be no stalls, but if the Matrices are particularly
572 small size an In-Order system would have to stall, just as it would if
573 the operations were loop-unrolled without Simple-V. Thus: regardless
574 of the Micro-Architecture the Hardware Engineer should first consider
575 how best to process the exact same equivalent loop-unrolled instruction
576 stream. Once solved Matrix REMAP will fit naturally.*
580 Indexed Mode activates reading of the element indices from the GPR
581 and includes optional limited 2D reordering.
582 In its simplest form (without elwidth overrides or other modes):
586 return GPR((SVSHAPE.SVGPR<<1)+i) + SVSHAPE.offset
589 element_result = ....
590 GPR(RT + indexed_remap(i)) = element_result
593 With element-width overrides included, and using the pseudocode
594 from the SVP64 [[sv/svp64/appendix#elwidth]] elwidth section
599 svreg = SVSHAPE.SVGPR << 1
600 srcwid = elwid_to_bitwidth(SVSHAPE.elwid)
601 offs = SVSHAPE.offset
602 return get_polymorphed_reg(svreg, srcwid, i) + offs
605 element_result = ....
606 rt_idx = indexed_remap(i)
607 set_polymorphed_reg(RT, destwid, rt_idx, element_result)
610 Matrix-style reordering still applies to the indices, except limited
611 to up to 2 Dimensions (X,Y). Ordering is therefore limited to (X,Y) or
612 (Y,X) for in-place Transposition.
613 Only one dimension may optionally be skipped. Inversion of either
614 X or Y or both is possible (2D mirroring). Pseudocode for Indexed Mode (including elwidth
615 overrides) may be written in terms of Matrix Mode, specifically
616 purposed to ensure that the 3rd dimension (Z) has no effect:
619 def index_remap(ISHAPE, i):
620 MSHAPE.skip = 0b0 || ISHAPE.sk1
621 MSHAPE.invxyz = 0b0 || ISHAPE.invxy
622 MSHAPE.xdimsz = ISHAPE.xdimsz
623 MSHAPE.ydimsz = ISHAPE.ydimsz
624 MSHAPE.zdimsz = 0 # disabled
625 if ISHAPE.permute = 0b110 # 0,1
626 MSHAPE.permute = 0b000 # 0,1,2
627 if ISHAPE.permute = 0b111 # 1,0
628 MSHAPE.permute = 0b010 # 1,0,2
629 el_idx = remap_matrix(MSHAPE, i)
630 svreg = ISHAPE.SVGPR << 1
631 srcwid = elwid_to_bitwidth(ISHAPE.elwid)
633 return get_polymorphed_reg(svreg, srcwid, el_idx) + offs
636 The most important observation above is that the Matrix-style
637 remapping occurs first and the Index lookup second. Thus it
638 becomes possible to perform in-place Transpose of Indices which
639 may have been costly to set up or costly to duplicate
640 (waste register file space). In other words: it is fine for two or more
641 SVSHAPEs to simultaneously use the same
642 Indices (use the same GPRs), even if one SVSHAPE has different
643 2D dimensions and ordering from the others.
645 **Caveats and Limitations**
647 The purpose of Indexing is to provide a generalised version of
648 Vector ISA "Permute" instructions, such as VSX `vperm`. The
649 Indexing is abstracted out and may be applied to much more
650 than an element move/copy, and is not limited for example
651 to the number of bytes that can fit into a VSX register.
652 Indexing may be applied to LD/ST (even on Indexed LD/ST
653 instructions such as `sv.lbzx`), arithmetic operations,
654 extsw: there is no artificial limit.
656 The only major caveat is that the registers to be used as
657 Indices must not be modified by any instruction after Indexed Mode
658 is established, and neither must MAXVL be altered. Additionally,
659 no register used as an Index may exceed MAXVL-1.
662 these conditions results in `UNDEFINED` behaviour.
663 These conditions allow a Read-After-Write (RAW) Hazard to be created on
664 the entire range of Indices to be subsequently used, but a corresponding
665 Write-After-Read Hazard by any instruction that modifies the Indices
666 **does not have to be created**. Given the large number of registers
667 involved in Indexing this is a huge resource saving and reduction
668 in micro-architectural complexity. MAXVL is likewise
669 included in the RAW Hazards because it is involved in calculating
670 how many registers are to be considered Indices.
672 With these Hazard Mitigations in place, high-performance implementations
673 may read-cache the Indices at the point where a given `svindex` instruction
674 is called (or SVSHAPE SPRs - and MAXVL - directly altered) by issuing
675 background GPR register file reads whilst other instructions are being
678 Indexed REMAP **does not prevent conflicts** (overlapping
679 destinations), which on a superficial analysis may be perceived to be a
680 problem, until it is recalled that, firstly, Simple-V is designed specifically
681 to require Program Order to be respected, and that Matrix, DCT and FFT
682 all *already* critically depend on overlapping Reads/Writes: Matrix
683 uses overlapping registers as accumulators. Thus the Register Hazard
684 Management needed by Indexed REMAP *has* to be in place anyway.
686 *Programmer's Note: `hphint` may be used to help hardware identify
687 parallelism opportunities but it is critical to remember that the
688 groupings are by `FLOOR(step/MAXVL)` not `FLOOR(REMAP(step)/MAXVL)`.*
690 The cost compared to Matrix and other REMAPs (and Pack/Unpack) is
691 clearly that of the additional reading of the GPRs to be used as Indices,
692 plus the setup cost associated with creating those same Indices.
693 If any Deterministic REMAP can cover the required task, clearly it
694 is adviseable to use it instead.
696 *Programmer's note: some algorithms may require skipping of Indices exceeding
697 VL-1, not MAXVL-1. This may be achieved programmatically by performing
698 an `sv.cmp *BF,*RA,RB` where RA is the same GPRs used in the Indexed REMAP,
699 and RB contains the value of VL returned from `setvl`. The resultant
700 CR Fields may then be used as Predicate Masks to exclude those operations
701 with an Index exceeding VL-1.*
707 # svshape instruction <a name="svshape"> </a>
711 svshape SVxd,SVyd,SVzd,SVRM,vf
713 | 0:5|6:10 |11:15 |16:20 | 21:24 | 25 | 26:31 | name |
714 | -- | -- | --- | ----- | ------ | -- | ------| -------- |
715 |PO | SVxd | SVyd | SVzd | SVRM | vf | XO | svshape |
717 See [[sv/remap/appendix]] for `svshape` pseudocode
719 Special Registers Altered:
725 `svshape` is a convenience instruction that reduces instruction
726 count for common usage patterns, particularly Matrix, DCT and FFT. It sets up
727 (overwrites) all required SVSHAPE SPRs and also modifies SVSTATE
728 including VL and MAXVL. Using `svshape` therefore does not also
733 * **SVxd** - SV REMAP "xdim" (X-dimension)
734 * **SVyd** - SV REMAP "ydim" (Y-dimension, sometimes used for sub-mode selection)
735 * **SVzd** - SV REMAP "zdim" (Z-dimension)
736 * **SVRM** - SV REMAP Mode (0b00000 for Matrix, 0b00001 for FFT etc.)
737 * **vf** - sets "Vertical-First" mode
738 * **XO** - standard 6-bit XO field
740 *Note: SVxd, SVyz and SVzd are all stored "off-by-one". In the assembler
741 mnemonic the values `1-32` are stored in binary as `0b00000..0b11111`*
743 There are 12 REMAP Modes (2 Modes are RESERVED for `svshape2`, 2 Modes
746 | SVRM | Remap Mode description |
748 | 0b0000 | Matrix 1/2/3D |
749 | 0b0001 | FFT Butterfly |
750 | 0b0010 | reserved |
751 | 0b0011 | DCT Outer butterfly |
752 | 0b0100 | DCT Inner butterfly, on-the-fly (Vertical-First Mode) |
753 | 0b0101 | DCT COS table index generation |
754 | 0b0110 | DCT half-swap |
755 | 0b0111 | Parallel Reduction and Prefix Sum |
756 | 0b1000 | reserved for svshape2 |
757 | 0b1001 | reserved for svshape2 |
758 | 0b1010 | reserved |
759 | 0b1011 | iDCT Outer butterfly |
760 | 0b1100 | iDCT Inner butterfly, on-the-fly (Vertical-First Mode) |
761 | 0b1101 | iDCT COS table index generation |
762 | 0b1110 | iDCT half-swap |
763 | 0b1111 | FFT half-swap |
765 Examples showing how all of these Modes operate exists in the online
766 [SVP64 unit tests](https://git.libre-soc.org/?p=openpower-isa.git;a=tree;f=src/openpower/decoder/isa;hb=HEAD). Explaining
767 these Modes further in detail is beyond the scope of this document.
769 In Indexed Mode, there are only 5 bits available to specify the GPR
770 to use, out of 128 GPRs (7 bit numbering). Therefore, only the top
771 5 bits are given in the `SVxd` field: the bottom two implicit bits
772 will be zero (`SVxd || 0b00`).
774 `svshape` has *limited applicability* due to being a 32-bit instruction.
775 The full capability of SVSHAPE SPRs may be accessed by directly writing
776 to SVSHAPE0-3 with `mtspr`. Circumstances include Matrices with dimensions
777 larger than 32, and in-place Transpose. Potentially a future v3.1 Prefixed
778 instruction, `psvshape`, may extend the capability here.
780 Programmer's Note: Parallel Reduction Mode is selected by setting `SVRM=7,SVyd=1`.
781 Prefix Sum Mode is selected by setting `SVRM=7,SVyd=3`:
784 # Vector length of 8.
785 svshape 8, 3, 1, 0x7, 0
786 # activate SVSHAPE0 (prefix-sum lhs) for RA
787 # activate SVSHAPE1 (prefix-sum rhs) for RT and RB
788 svremap 7, 0, 1, 0, 1, 0, 0
792 *Architectural Resource Allocation note: the SVRM field is carefully
793 crafted to allocate two Modes, corresponding to bits 21-23 within the
794 instruction being set to the value `0b100`, to `svshape2` (not
795 `svshape`). These two Modes are
796 considered "RESERVED" within the context of `svshape` but it is
797 absolutely critical to allocate the exact same pattern in XO for
798 both instructions in bits 26-31.*
805 # svindex instruction <a name="svindex"> </a>
809 | 0:5|6:10 |11:15 |16:20 | 21:25 | 26:31 | Form |
810 | -- | -- | --- | ---- | ----------- | ------| -------- |
811 | PO | SVG | rmm | SVd | ew/yx/mm/sk | XO | SVI-Form |
813 * svindex SVG,rmm,SVd,ew,SVyx,mm,sk
815 See [[sv/remap/appendix]] for `svindex` pseudocode
817 Special Registers Altered:
823 `svindex` is a convenience instruction that reduces instruction count
824 for Indexed REMAP Mode. It sets up (overwrites) all required SVSHAPE
825 SPRs and **unlike** `svshape` can modify the REMAP area of the SVSTATE
826 SPR as well, including setting persistence. The relevant SPRs *may*
827 be directly programmed with `mtspr` however it is laborious to do so:
828 svindex saves instructions covering much of Indexed REMAP capability.
832 * **SVd** - SV REMAP x/y dim
833 * **rmm** - REMAP mask: sets remap mi0-2/mo0-1 and SVSHAPEs,
835 * **ew** - sets element width override on the Indices
836 * **SVG** - GPR SVG<<2 to be used for Indexing
837 * **yx** - 2D reordering to be used if yx=1
838 * **mm** - mask mode. determines how `rmm` is interpreted.
839 * **sk** - Dimension skipping enabled
841 *Note: SVd, like SVxd, SVyz and SVzd of `svshape`, are all stored
842 "off-by-one". In the assembler
843 mnemonic the values `1-32` are stored in binary as `0b00000..0b11111`*.
845 *Note: when `yx=1,sk=0` the second dimension is calculated as
850 * `rmm`, like REMAP.SVme, has bit 0
851 correspond to mi0, bit 1 to mi1, bit 2 to mi2,
852 bit 3 to mo0 and bit 4 to mi1
853 * all SVSHAPEs and the REMAP parts of SVSHAPE are first reset (initialised to zero)
854 * for each bit set in the 5-bit `rmm`, in order, the first
855 as-yet-unset SVSHAPE will be updated
856 with the other operands in the instruction, and the REMAP
858 * If all 5 bits of `rmm` are set then both mi0 and mo1 use SVSHAPE0.
859 * SVSTATE persistence bit is cleared
860 * No other alterations to SVSTATE are carried out
862 Example 1: if rmm=0b00110 then SVSHAPE0 and SVSHAPE1 are set up,
863 and the REMAP SPR set so that mi1 uses SVSHAPE0 and mi2
864 uses mi2. REMAP.SVme is also set to 0b00110, REMAP.mi1=0
865 (SVSHAPE0) and REMAP.mi2=1 (SVSHAPE1)
867 Example 2: if rmm=0b10001 then again SVSHAPE0 and SVSHAPE1
868 are set up, but the REMAP SPR is set so that mi0 uses SVSHAPE0
869 and mo1 uses SVSHAPE1. REMAP.SVme=0b10001, REMAP.mi0=0, REMAP.mo1=1
871 Rough algorithmic form:
874 marray = [mi0, mi1, mi2, mo0, mo1]
877 if not rmm[bit]: continue
879 SVSTATE{marray[bit]} = idx
880 idx = (idx+1) modulo 4
885 * bits 0-2 (MSB0 numbering) of `rmm` indicate an index selecting mi0-mo1
886 * bits 3-4 (MSB0 numbering) of `rmm` indicate which SVSHAPE 0-3 shall
888 * only the selected SVSHAPE is overwritten
889 * only the relevant bits in the REMAP area of SVSTATE are updated
890 * REMAP persistence bit is set.
892 Example 1: if `rmm`=0b01110 then bits 0-2 (MSB0) are 0b011 and
893 bits 3-4 are 0b10. thus, mo0 is selected and SVSHAPE2
894 to be updated. REMAP.SVme[3] will be set high and REMAP.mo0
897 Example 2: if `rmm`=0b10011 then bits 0-2 (MSB0) are 0b100 and
898 bits 3-4 are 0b11. thus, mo1 is selected and SVSHAPE3
899 to be updated. REMAP.SVme[4] will be set high and REMAP.mo1
902 Rough algorithmic form:
905 marray = [mi0, mi1, mi2, mo0, mo1]
909 SVSTATE{marray[bit]} = idx
913 In essence, `mm=0` is intended for use to set as much of the
914 REMAP State SPRs as practical with a single instruction,
915 whilst `mm=1` is intended to be a little more refined.
919 * **Disable 2D mapping**: to only perform Indexing without
920 reordering use `SVd=1,sk=0,yx=0` (or set SVd to a value larger
922 * **Modulo 1D mapping**: to perform Indexing cycling through the
923 first N Indices use `SVd=N,sk=0,yx=0` where `VL>N`. There is
924 no requirement to set VL equal to a multiple of N.
925 * **Modulo 2D transposed**: `SVd=M,sk=0,yx=1`, sets
926 `xdim=M,ydim=CEIL(MAXVL/M)`.
928 Beyond these mappings it becomes necessary to write directly to
929 the SVSTATE SPRs manually.
936 # svshape2 (offset-priority) <a name="svshape2"> </a>
940 | 0:5|6:9 |10|11:15 |16:20 | 21:24 | 25 | 26:31 | Form |
941 | -- |----|--| --- | ----- | ------ | -- | ------| -------- |
942 | PO |offs|yx| rmm | SVd | 100/mm | sk | XO | SVM2-Form |
944 * svshape2 offs,yx,rmm,SVd,sk,mm
946 See [[sv/remap/appendix]] for `svshape2` pseudocode
948 Special Registers Altered:
954 `svshape2` is an additional convenience instruction that prioritises
955 setting `SVSHAPE.offset`. Its primary purpose is for use when
956 element-width overrides are used. It has identical capabilities to `svindex`
957 in terms of both options (skip, etc.) and ability to activate REMAP
958 (rmm, mask mode) but unlike `svindex` it does not set GPR REMAP:
959 only a 1D or 2D `svshape`, and
960 unlike `svshape` it can set an arbitrary `SVSHAPE.offset` immediate.
962 One of the limitations of Simple-V is that Vector elements start on the boundary
963 of the Scalar regfile, which is fine when element-width overrides are not
964 needed. If the starting point of a Vector with smaller elwidths must begin
965 in the middle of a register, normally there would be no way to do so except
966 through costly LD/ST. `SVSHAPE.offset` caters for this scenario and `svshape2`
967 makes it easier to access.
971 * **offs** (4 bits) - unsigned offset
972 * **yx** (1 bit) - swap XY to YX
973 * **SVd** dimension size
976 * **sk** (1 bit) skips 1st dimension if set
978 Dimensions are calculated exactly as `svindex`. `rmm` and
979 `mm` are as per `svindex`.
981 *Programmer's Note: offsets for `svshape2` may be specified in the range
982 0-15. Given that the principle of Simple-V is to fit on top of
983 byte-addressable register files and that GPR and FPR are 64-bit (8 bytes)
984 it should be clear that the offset may, when `elwidth=8`, begin an
985 element-level operation starting element zero at any arbitrary byte.
986 On cursory examination attempting to go beyond the range 0-7 seems
987 unnecessary given that the **next GPR or FPR** is an
988 alias for an offset in the range 8-15. Thus by simply increasing
989 the starting Vector point of the operation to the next register it
990 can be seen that the offset of 0-7 would be sufficient. Unfortunately
991 however some operations are EXTRA2-encoded it is **not possible**
992 to increase the GPR/FPR register number by one, because EXTRA2-encoding
993 of GPR/FPR Vector numbers are restricted to even numbering.
994 For CR Fields the EXTRA2 encoding is even more sparse.
995 The additional offset range (8-15) helps overcome these limitations.*
997 *Hardware Implementor's note: with the offsets only being immediates
998 and with register numbering being entirely immediate as well it is
999 possible to correctly compute Register Hazards without requiring
1000 reading the contents of any SPRs. If however there are
1001 instructions that have directly written to the SVSTATE or SVSHAPE
1002 SPRs and those instructions are still in-flight then this position
1003 is clearly **invalid**. This is why Programmers are strongly
1004 discouraged from directly writing to these SPRs.*
1006 *Architectural Resource Allocation note: this instruction shares
1007 the space of `svshape`. Therefore it is critical that the two
1008 instructions, `svshape` and `svshape2` have the exact same XO
1009 in bits 26 thru 31. It is also critical that for `svshape2`,
1010 bit 21 of XO is a 1, bit 22 of XO is a 0, and bit 23 of XO is a 0.*