3 # REMAP <a name="remap" />
5 * <https://bugs.libre-soc.org/show_bug.cgi?id=143> matrix multiply
6 * <https://bugs.libre-soc.org/show_bug.cgi?id=867> add svindex
7 * <https://bugs.libre-soc.org/show_bug.cgi?id=885> svindex in simulator
8 * <https://bugs.libre-soc.org/show_bug.cgi?id=911> offset svshape option
9 * <https://bugs.libre-soc.org/show_bug.cgi?id=864> parallel reduction
10 * <https://bugs.libre-soc.org/show_bug.cgi?id=930> DCT/FFT "strides"
11 * see [[sv/remap/appendix]] for examples and usage
12 * see [[sv/propagation]] for a future way to apply REMAP
13 * [[remap/discussion]]
15 REMAP is an advanced form of Vector "Structure Packing" that
16 provides hardware-level support for commonly-used *nested* loop patterns.
17 For more general reordering an Indexed REMAP mode is available.
19 REMAP allows the usual vector loop `0..VL-1` to be "reshaped" (re-mapped)
20 from a linear form to a 2D or 3D transposed form, or "offset" to permit
21 arbitrary access to elements (when elwidth overrides are used),
22 independently on each Vector src or dest
25 The initial primary motivation of REMAP was for Matrix Multiplication, reordering of sequential
26 data in-place: in-place DCT and FFT were easily justified given the
27 high usage in Computer Science.
28 Four SPRs are provided which may be applied to any GPR, FPR or CR Field
29 so that for example a single FMAC may be
30 used in a single loop to perform 5x3 times 3x4 Matrix multiplication,
31 generating 60 FMACs *without needing explicit assembler unrolling*.
32 Additional uses include regular "Structure Packing"
33 such as RGB pixel data extraction and reforming.
35 REMAP, like all of SV, is abstracted out, meaning that unlike traditional
36 Vector ISAs which would typically only have a limited set of instructions
37 that can be structure-packed (LD/ST and Move operations
38 being the most common), REMAP may be applied to
39 literally any instruction: CRs, Arithmetic, Logical, LD/ST, anything.
41 When SUBVL is greater than 1 a given group of Subvector
42 elements are kept together: effectively the group becomes the
43 element, and the group is REMAPed together.
44 Swizzle *can* however be applied to the same
45 instruction as REMAP, providing re-sequencing of
46 Subvector elements which REMAP cannot. Also as explained in [[sv/mv.swizzle]], [[sv/mv.vec]] and the [[svp64/appendix]], Pack and Unpack Mode bits
47 can extend down into Sub-vector elements to influence vec2/vec3/vec4
48 sequential reordering, but even here, REMAP is not extended down to
49 the actual sub-vector elements themselves.
51 In its general form, REMAP is quite expensive to set up, and on some
52 implementations may introduce
53 latency, so should realistically be used only where it is worthwhile.
54 Given that most other ISAs require full loop-unrolling for Matrix,
55 DCT and FFT, savings are still anticipated.
56 Commonly-used patterns such as Matrix Multiply, DCT and FFT have
57 helper instruction options which make REMAP easier to use.
59 There are four types of REMAP:
61 * **Matrix**, also known as 2D and 3D reshaping, can perform in-place
62 Matrix transpose and rotate. The Shapes are set up for an "Outer Product"
64 * **FFT/DCT**, with full triple-loop in-place support: limited to
66 * **Indexing**, for any general-purpose reordering, also includes
68 * **Parallel Reduction**, for scheduling a sequence of operations
69 in a Deterministic fashion, in a way that may be parallelised,
70 to reduce a Vector down to a single value.
72 Best implemented on top of a Multi-Issue Out-of-Order Micro-architecture,
73 REMAP Schedules are 100% Deterministic **including Indexing** and are
74 designed to be incorporated in between the Decode and Issue phases,
75 directly into Register Hazard Management.
77 Parallel Reduction is unusual in that it requires a full vector array
78 of results (not a scalar) and uses the rest of the result Vector for
79 the purposes of storing intermediary calculations. As these intermediary
80 results are Deterministically computed they may be useful.
81 Additionally, because the intermediate results are always written out
82 it is possible to service Precise Interrupts without affecting latency
83 (a common limitation of Vector ISAs).
87 * normal vector element read/write of operands would be sequential
89 * this is not appropriate for (e.g.) Matrix multiply which requires
90 accessing elements in alternative sequences (0 3 6 1 4 7 ...)
91 * normal Vector ISAs use either Indexed-MV or Indexed-LD/ST to "cope"
92 with this. both are expensive (copy large vectors, spill through memory)
93 and very few Packed SIMD ISAs cope with non-Power-2.
94 * REMAP **redefines** the order of access according to set
95 (Deterministic) "Schedules".
96 * The Schedules are not at all restricted to power-of-two boundaries
97 making it unnecessary to have for example specialised 3x4 transpose
98 instructions of other Vector ISAs.
100 Only the most commonly-used algorithms in computer science have REMAP
101 support, due to the high cost in both the ISA and in hardware. For
102 arbitrary remapping the `Indexed` REMAP may be used.
106 * `svshape` to set the type of reordering to be applied to an
107 otherwise usual `0..VL-1` hardware for-loop
108 * `svremap` to set which registers a given reordering is to apply to
110 * `sv.{instruction}` where any Vectorised register marked by `svremap`
111 will have its ordering REMAPPED according to the schedule set
114 The following illustrative example multiplies a 3x4 and a 5x3
118 svshape 5, 4, 3, 0, 0
119 svremap 15, 1, 2, 3, 0, 0, 0, 0
120 sv.fmadds *0, *8, *16, *0
122 * svshape sets up the four SVSHAPE SPRS for a Matrix Schedule
123 * svremap activates four out of five registers RA RB RC RT RS (15)
129 - RS Remapping to not be activated
130 * sv.fmadds has RT=0.v, RA=8.v, RB=16.v, RC=0.v
131 * With REMAP being active each register's element index is
132 *independently* transformed using the specified SHAPEs.
134 Thus the Vector Loop is arranged such that the use of
135 the multiply-and-accumulate instruction executes precisely the required
136 Schedule to perform an in-place in-registers Matrix Multiply with no
137 need to perform additional Transpose or register copy instructions.
138 The example above may be executed as a unit test and demo,
139 [here](https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=src/openpower/decoder/isa/test_caller_svp64_matrix.py;h=c15479db9a36055166b6b023c7495f9ca3637333;hb=a17a252e474d5d5bf34026c25a19682e3f2015c3#l94)
143 This section summarises the motivation for each REMAP Schedule
144 and briefly goes over their characteristics and limitations.
145 Further details on the Deterministic Precise-Interruptible algorithms
146 used in these Schedules is found in the [[sv/remap/appendix]].
148 ## Matrix (1D/2D/3D shaping)
150 Matrix Multiplication is a huge part of High-Performance Compute,
152 In many PackedSIMD as well as Scalable Vector ISAs, non-power-of-two
153 Matrix sizes are a serious challenge. PackedSIMD ISAs, in order to
154 cope with for example 3x4 Matrices, recommend rolling data-repetition and loop-unrolling.
155 Aside from the cost of the load on the L1 I-Cache, the trick only
156 works if one of the dimensions X or Y are power-two. Prime Numbers
157 (5x7, 3x5) become deeply problematic to unroll.
159 Even traditional Scalable Vector ISAs have issues with Matrices, often
160 having to perform data Transpose by pushing out through Memory and back,
161 or computing Transposition Indices (costly) then copying to another
164 Matrix REMAP was thus designed to solve these issues by providing Hardware
166 "Schedules" that can view what would otherwise be limited to a strictly
167 linear Vector as instead being 2D (even 3D) *in-place* reordered.
168 With both Transposition and non-power-two being supported the issues
169 faced by other ISAs are mitigated.
171 Limitations of Matrix REMAP are that the Vector Length (VL) is currently
172 restricted to 127: up to 127 FMAs (or other operation)
173 may be performed in total.
174 Also given that it is in-registers only at present some care has to be
175 taken on regfile resource utilisation. However it is perfectly possible
176 to utilise Matrix REMAP to perform the three inner-most "kernel" loops of
177 the usual 6-level large Matrix Multiply, without the usual difficulties
178 associated with SIMD.
180 Also the `svshape` instruction only provides access to part of the
181 Matrix REMAP capability. Rotation and mirroring need to be done by
182 programming the SVSHAPE SPRs directly, which can take a lot more
185 ## FFT/DCT Triple Loop
187 DCT and FFT are some of the most astonishingly used algorithms in
188 Computer Science. Radar, Audio, Video, R.F. Baseband and dozens more. At least
189 two DSPs, TMS320 and Hexagon, have VLIW instructions specially tailored
192 An in-depth analysis showed that it is possible to do in-place in-register
193 DCT and FFT as long as twin-result "butterfly" instructions are provided.
194 These can be found in the [[openpower/isa/svfparith]] page if performing
195 IEEE754 FP transforms. *(For fixed-point transforms, equivalent 3-in 2-out
196 integer operations would be required)*. These "butterfly" instructions
197 avoid the need for a temporary register because the two array positions
198 being overwritten will be "in-flight" in any In-Order or Out-of-Order
201 DCT and FFT Schedules are currently limited to RADIX2 sizes and do not
202 accept predicate masks. Given that it is common to perform recursive
203 convolutions combining smaller Power-2 DCT/FFT to create larger DCT/FFTs
204 in practice the RADIX2 limit is not a problem. A Bluestein convolution
205 to compute arbitrary length is demonstrated by
206 [Project Nayuki](https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.py)
210 The purpose of Indexing is to provide a generalised version of
211 Vector ISA "Permute" instructions, such as VSX `vperm`. The
212 Indexing is abstracted out and may be applied to much more
213 than an element move/copy, and is not limited for example
214 to the number of bytes that can fit into a VSX register.
215 Indexing may be applied to LD/ST (even on Indexed LD/ST
216 instructions such as `sv.lbzx`), arithmetic operations,
217 extsw: there is no artificial limit.
219 The only major caveat is that the registers to be used as
220 Indices must not be modified by any instruction after Indexed Mode
221 is established, and neither must MAXVL be altered. Additionally,
222 no register used as an Index may exceed MAXVL-1.
225 these conditions results in `UNDEFINED` behaviour.
226 These conditions allow a Read-After-Write (RAW) Hazard to be created on
227 the entire range of Indices to be subsequently used, but a corresponding
228 Write-After-Read Hazard by any instruction that modifies the Indices
229 **does not have to be created**. Given the large number of registers
230 involved in Indexing this is a huge resource saving and reduction
231 in micro-architectural complexity. MAXVL is likewise
232 included in the RAW Hazards because it is involved in calculating
233 how many registers are to be considered Indices.
235 With these Hazard Mitigations in place, high-performance implementations
236 may read-cache the Indices from the point where a given `svindex` instruction
237 is called (or SVSHAPE SPRs - and MAXVL- directly altered).
239 The original motivation for Indexed REMAP was to mitigate the need to add
240 an expensive `mv.x` to the Scalar ISA, which was likely to be rejected as
241 a stand-alone instruction. Usually a Vector ISA would add a non-conflicting
242 variant (as in VSX `vperm`) but it is common to need to permute by source,
243 with the risk of conflict, that has to be resolved, for example, in AVX-512
246 Indexed REMAP on the other hand **does not prevent conflicts** (overlapping
247 destinations), which on a superficial analysis may be perceived to be a
248 problem, until it is recalled that, firstly, Simple-V is designed specifically
249 to require Program Order to be respected, and that Matrix, DCT and FFT
250 all *already* critically depend on overlapping Reads/Writes: Matrix
251 uses overlapping registers as accumulators. Thus the Register Hazard
252 Management needed by Indexed REMAP *has* to be in place anyway.
254 The cost compared to Matrix and other REMAPs (and Pack/Unpack) is
255 clearly that of the additional reading of the GPRs to be used as Indices,
256 plus the setup cost associated with creating those same Indices.
257 If any Deterministic REMAP can cover the required task, clearly it
258 is adviseable to use it instead.
260 *Programmer's note: some algorithms may require skipping of Indices exceeding
261 VL-1, not MAXVL-1. This may be achieved programmatically by performing
262 an `sv.cmp *BF,*RA,RB` where RA is the same GPRs used in the Indexed REMAP,
263 and RB contains the value of VL returned from `setvl`. The resultant
264 CR Fields may then be used as Predicate Masks to exclude those operations
265 with an Index exceeding VL-1.*
267 ## Parallel Reduction
269 Vector Reduce Mode issues a deterministic tree-reduction schedule to the underlying micro-architecture. Like Scalar reduction, the "Scalar Base"
270 (Power ISA v3.0B) operation is leveraged, unmodified, to give the
271 *appearance* and *effect* of Reduction.
273 In Horizontal-First Mode, Vector-result reduction **requires**
274 the destination to be a Vector, which will be used to store
275 intermediary results.
277 Given that the tree-reduction schedule is deterministic,
278 Interrupts and exceptions
279 can therefore also be precise. The final result will be in the first
280 non-predicate-masked-out destination element, but due again to
281 the deterministic schedule programmers may find uses for the intermediate
284 When Rc=1 a corresponding Vector of co-resultant CRs is also
285 created. No special action is taken: the result and its CR Field
286 are stored "as usual" exactly as all other SVP64 Rc=1 operations.
288 Note that the Schedule only makes sense on top of certain instructions:
289 X-Form with a Register Profile of `RT,RA,RB` is fine because two sources
290 and the destination are all the same type. Like Scalar
291 Reduction, nothing is prohibited:
292 the results of execution on an unsuitable instruction may simply
293 not make sense. With care, even 3-input instructions (madd, fmadd, ternlogi)
296 Critical to note regarding use of Parallel-Reduction REMAP is that,
297 exactly as with all REMAP Modes, the `svshape` instruction *requests*
298 a certain Vector Length (number of elements to reduce) and then
299 sets VL and MAXVL at the number of **operations** needed to be
300 carried out. Thus, equally as importantly, like Matrix REMAP
301 the total number of operations
302 is restricted to 127. Any Parallel-Reduction requiring more operations
303 will need to be done manually in batches (hierarchical
304 recursive Reduction).
306 Also important to note is that the Deterministic Schedule is arranged
307 so that some implementations *may* parallelise it (as long as doing so
308 respects Program Order and Register Hazards). Performance (speed)
310 implementation is neither strictly defined or guaranteed. As with
311 the Vulkan(tm) Specification, strict compliance is paramount whilst
312 performance is at the discretion of Implementors.
314 **Parallel-Reduction with Predication**
316 To avoid breaking the strict RISC-paradigm, keeping the Issue-Schedule
317 completely separate from the actual element-level (scalar) operations,
318 Move operations are **not** included in the Schedule. This means that
319 the Schedule leaves the final (scalar) result in the first-non-masked
320 element of the Vector used. With the predicate mask being dynamic
321 (but deterministic) this result could be anywhere.
323 If that result is needed to be moved to a (single) scalar register
324 then a follow-up `sv.mv/sm=predicate rt, *ra` instruction will be
325 needed to get it, where the predicate is the exact same predicate used
326 in the prior Parallel-Reduction instruction.
328 * If there was only a single
329 bit in the predicate then the result will not have moved or been altered
330 from the source vector prior to the Reduction
331 * If there was more than one bit the result will be in the
332 first element with a predicate bit set.
334 In either case the result is in the element with the first bit set in
337 For *some* implementations
338 the vector-to-scalar copy may be a slow operation, as may the Predicated
339 Parallel Reduction itself.
340 It may be better to perform a pre-copy
341 of the values, compressing them (VREDUCE-style) into a contiguous block,
342 which will guarantee that the result goes into the very first element
343 of the destination vector, in which case clearly no follow-up
344 vector-to-scalar MV operation is needed.
348 The simplest usage is to perform an overwrite, specifying all three
349 register operands the same.
351 svshape parallelreduce, 6
354 The Reduction Schedule will issue the Parallel Tree Reduction spanning
355 registers 8 through 13, by adjusting the offsets to RT, RA and RB as
356 necessary (see "Parallel Reduction algorithm" in a later section).
358 A non-overwrite is possible as well but just as with the overwrite
359 version, only those destination elements necessary for storing
360 intermediary computations will be written to: the remaining elements
361 will **not** be overwritten and will **not** be zero'd.
363 svshape parallelreduce, 6
366 However it is critical to note that if the source and destination are
367 not the same then the trick of using a follow-up vector-scalar MV will
370 ## Sub-Vector Horizontal Reduction
372 Note that when SVM is clear and SUBVL!=1 a Parallel Reduction is performed
373 on all first Subvector elements, followed by another separate independent
374 Parallel Reduction on all the second Subvector elements and so on.
376 for selectsubelement in (x,y,z,w):
377 parallelreduce(0..VL-1, selectsubelement)
379 By contrast, when SVM is set and SUBVL!=1, a Horizontal
380 Subvector mode is enabled, applying the Parallel Reduction
381 Algorithm to the Subvector Elements. The Parallel Reduction
382 is independently applied VL times, to each group of Subvector
383 elements. Bear in mind that predication is never applied down
384 into individual Subvector elements, but will be applied
385 to select whether the *entire* Parallel Reduction on each
386 group is performed or not.
388 Â for (i = 0; i < VL; i++)
389 if (predval & 1<<i) # predication
391 parallelreduction([el.x, el.y, el.z, el.w])
393 Note that as this is a Parallel Reduction, for best results
394 it should be an overwrite operation, where the result for
395 the Horizontal Reduction of each Subvector will be in the
396 first Subvector element.
397 Also note that use of Rc=1 is `UNDEFINED` behaviour.
399 In essence what is happening here is that Structure Packing is being
400 combined with Parallel Reduction. If the Subvector elements may be
401 laid out as a 2D matrix, with the Subvector elements on rows,
402 and Parallel Reduction is applied per row, then if `SVM` is **clear**
403 the Matrix is transposed (like Pack/Unpack)
404 before still applying the Parallel Reduction to the **row**.
406 # Determining Register Hazards
408 For high-performance (Multi-Issue, Out-of-Order) systems it is critical
409 to be able to statically determine the extent of Vectors in order to
410 allocate pre-emptive Hazard protection. The next task is to eliminate
411 masked-out elements using predicate bits, freeing up the associated
414 For non-REMAP situations `VL` is sufficient to ascertain early
415 Hazard coverage, and with SVSTATE being a high priority cached
416 quantity at the same level of MSR and PC this is not a problem.
418 The problems come when REMAP is enabled. Indexed REMAP must instead
419 use `MAXVL` as the earliest (simplest)
420 batch-level Hazard Reservation indicator,
421 but Matrix, FFT and Parallel Reduction must all use completely different
422 schemes. The reason is that VL is used to step through the total
423 number of *operations*, not the number of registers. The "Saving Grace"
424 is that all of the REMAP Schedules are Deterministic.
426 Advance-notice Parallel computation and subsequent cacheing
427 of all of these complex Deterministic REMAP Schedules is
428 *strongly recommended*, thus allowing clear and precise multi-issue
429 batched Hazard coverage to be deployed, *even for Indexed Mode*.
430 This is only possible for Indexed due to the strict guidelines
431 given to Programmers.
433 In short, there exists solutions to the problem of Hazard Management,
434 with varying degrees of refinement possible at correspondingly
435 increasing levels of complexity in hardware.
437 # REMAP area of SVSTATE
439 The following bits of the SVSTATE SPR are used for REMAP:
441 |32.33|34.35|36.37|38.39|40.41| 42.46 | 62 |
442 | -- | -- | -- | -- | -- | ----- | ------ |
443 |mi0 |mi1 |mi2 |mo0 |mo1 | SVme | RMpst |
445 mi0-2 and mo0-1 each select SVSHAPE0-3 to apply to a given register.
446 mi0-2 apply to RA, RB, RC respectively, as input registers, and
447 likewise mo0-1 apply to output registers (RT/FRT, RS/FRS) respectively.
448 SVme is 5 bits (one for each of mi0-2/mo0-1) and indicates whether the
449 SVSHAPE is actively applied or not.
451 * bit 0 of SVme indicates if mi0 is applied to RA / FRA
452 * bit 1 of SVme indicates if mi1 is applied to RB / FRB
453 * bit 2 of SVme indicates if mi2 is applied to RC / FRC
454 * bit 3 of SVme indicates if mo0 is applied to RT / FRT
455 * bit 4 of SVme indicates if mo1 is applied to Effective Address / FRS / RS
456 (LD/ST-with-update has an implicit 2nd write register, RA)
458 # svremap instruction <a name="svremap"> </a>
460 There is also a corresponding SVRM-Form for the svremap
461 instruction which matches the above SPR:
463 svremap SVme,mi0,mi1,mi2,mo0,mo2,pst
465 |0 |6 |11 |13 |15 |17 |19 |21 | 22.25 |26..31 |
466 | -- | -- | -- | -- | -- | -- | -- | -- | ---- | ----- |
467 | PO | SVme |mi0 | mi1 | mi2 | mo0 | mo1 | pst | rsvd | XO |
469 # SHAPE Remapping SPRs
471 There are four "shape" SPRs, SHAPE0-3, 32-bits in each,
472 which have the same format.
474 Shape is 32-bits. When SHAPE is set entirely to zeros, remapping is
475 disabled: the register's elements are a linear (1D) vector.
477 |31.30|29..28 |27..24| 23..21 | 20..18 | 17..12 |11..6 |5..0 | Mode |
478 |---- |------ |------| ------ | ------- | ------- |----- |----- | ----- |
479 |0b00 |skip |offset| invxyz | permute | zdimsz |ydimsz|xdimsz|Matrix |
480 |0b00 |elwidth|offset|sk1/invxy|0b110/0b111|SVGPR|ydimsz|xdimsz|Indexed|
481 |0b01 |submode|offset| invxyz | submode2| zdimsz |mode |xdimsz|DCT/FFT|
482 |0b10 |submode|offset| invxyz | rsvd | rsvd |rsvd |xdimsz|Preduce|
483 |0b11 | | | | | | | |rsvd |
485 mode sets different behaviours (straight matrix multiply, FFT, DCT).
487 * **mode=0b00** sets straight Matrix Mode
488 * **mode=0b00** with permute=0b110 or 0b111 sets Indexed Mode
489 * **mode=0b01** sets "FFT/DCT" mode and activates submodes
490 * **mode=0b10** sets "Parallel Reduction" Schedules.
492 ## Parallel Reduction Mode
494 Creates the Schedules for Parallel Tree Reduction.
496 * **submode=0b00** selects the left operand index
497 * **submode=0b01** selects the right operand index
499 * When bit 0 of `invxyz` is set, the order of the indices
500 in the inner for-loop are reversed. This has the side-effect
501 of placing the final reduced result in the last-predicated element.
502 It also has the indirect side-effect of swapping the source
503 registers: Left-operand index numbers will always exceed
504 Right-operand indices.
505 When clear, the reduced result will be in the first-predicated
506 element, and Left-operand indices will always be *less* than
508 * When bit 1 of `invxyz` is set, the order of the outer loop
509 step is inverted: stepping begins at the nearest power-of two
510 to half of the vector length and reduces by half each time.
511 When clear the step will begin at 2 and double on each
516 submode2=0 is for FFT. For FFT submode the following schedules may be
519 * **submode=0b00** selects the ``j`` offset of the innermost for-loop
521 * **submode=0b10** selects the ``j+halfsize`` offset of the innermost for-loop
523 * **submode=0b11** selects the ``k`` of exptable (which coefficient)
525 When submode2 is 1 or 2, for DCT inner butterfly submode the following
526 schedules may be selected. When submode2 is 1, additional bit-reversing
529 * **submode=0b00** selects the ``j`` offset of the innermost for-loop,
531 * **submode=0b010** selects the ``j+halfsize`` offset of the innermost for-loop,
532 in reverse-order, in-place
533 * **submode=0b10** selects the ``ci`` count of the innermost for-loop,
534 useful for calculating the cosine coefficient
535 * **submode=0b11** selects the ``size`` offset of the outermost for-loop,
536 useful for the cosine coefficient ``cos(ci + 0.5) * pi / size``
538 When submode2 is 3 or 4, for DCT outer butterfly submode the following
539 schedules may be selected. When submode is 3, additional bit-reversing
542 * **submode=0b00** selects the ``j`` offset of the innermost for-loop,
543 * **submode=0b01** selects the ``j+1`` offset of the innermost for-loop,
545 `zdimsz` is used as an in-place "Stride", particularly useful for
546 column-based in-place DCT/FFT.
550 In Matrix Mode, skip allows dimensions to be skipped from being included
551 in the resultant output index. this allows sequences to be repeated:
552 ```0 0 0 1 1 1 2 2 2 ...``` or in the case of skip=0b11 this results in
553 modulo ```0 1 2 0 1 2 ...```
555 * **skip=0b00** indicates no dimensions to be skipped
556 * **skip=0b01** sets "skip 1st dimension"
557 * **skip=0b10** sets "skip 2nd dimension"
558 * **skip=0b11** sets "skip 3rd dimension"
560 invxyz will invert the start index of each of x, y or z. If invxyz[0] is
561 zero then x-dimensional counting begins from 0 and increments, otherwise
562 it begins from xdimsz-1 and iterates down to zero. Likewise for y and z.
564 offset will have the effect of offsetting the result by ```offset``` elements:
567 GPR(RT + remap(i) + SVSHAPE.offset) = ....
569 this appears redundant because the register RT could simply be changed by a compiler, until element width overrides are introduced. also
570 bear in mind that unlike a static compiler SVSHAPE.offset may
571 be set dynamically at runtime.
573 xdimsz, ydimsz and zdimsz are offset by 1, such that a value of 0 indicates
574 that the array dimensionality for that dimension is 1. any dimension
575 not intended to be used must have its value set to 0 (dimensionality
576 of 1). A value of xdimsz=2 would indicate that in the first dimension
577 there are 3 elements in the array. For example, to create a 2D array
578 X,Y of dimensionality X=3 and Y=2, set xdimsz=2, ydimsz=1 and zdimsz=0
580 The format of the array is therefore as follows:
582 array[xdimsz+1][ydimsz+1][zdimsz+1]
584 However whilst illustrative of the dimensionality, that does not take the
585 "permute" setting into account. "permute" may be any one of six values
586 (0-5, with values of 6 and 7 indicating "Indexed" Mode). The table
587 below shows how the permutation dimensionality order works:
589 | permute | order | array format |
590 | ------- | ----- | ------------------------ |
591 | 000 | 0,1,2 | (xdim+1)(ydim+1)(zdim+1) |
592 | 001 | 0,2,1 | (xdim+1)(zdim+1)(ydim+1) |
593 | 010 | 1,0,2 | (ydim+1)(xdim+1)(zdim+1) |
594 | 011 | 1,2,0 | (ydim+1)(zdim+1)(xdim+1) |
595 | 100 | 2,0,1 | (zdim+1)(xdim+1)(ydim+1) |
596 | 101 | 2,1,0 | (zdim+1)(ydim+1)(xdim+1) |
597 | 110 | 0,1 | Indexed (xdim+1)(ydim+1) |
598 | 111 | 1,0 | Indexed (ydim+1)(xdim+1) |
600 In other words, the "permute" option changes the order in which
601 nested for-loops over the array would be done. See executable
602 python reference code for further details.
604 *Note: permute=0b110 and permute=0b111 enable Indexed REMAP Mode,
607 With all these options it is possible to support in-place transpose,
608 in-place rotate, Matrix Multiply and Convolutions, without being
609 limited to Power-of-Two dimension sizes.
613 Indexed Mode activates reading of the element indices from the GPR
614 and includes optional limited 2D reordering.
615 In its simplest form (without elwidth overrides or other modes):
619 return GPR((SVSHAPE.SVGPR<<1)+i) + SVSHAPE.offset
622 element_result = ....
623 GPR(RT + indexed_remap(i)) = element_result
626 With element-width overrides included, and using the pseudocode
627 from the SVP64 [[sv/svp64/appendix#elwidth]] elwidth section
632 svreg = SVSHAPE.SVGPR << 1
633 srcwid = elwid_to_bitwidth(SVSHAPE.elwid)
634 offs = SVSHAPE.offset
635 return get_polymorphed_reg(svreg, srcwid, i) + offs
638 element_result = ....
639 rt_idx = indexed_remap(i)
640 set_polymorphed_reg(RT, destwid, rt_idx, element_result)
643 Matrix-style reordering still applies to the indices, except limited
644 to up to 2 Dimensions (X,Y). Ordering is therefore limited to (X,Y) or
645 (Y,X). Only one dimension may optionally be skipped. Inversion of either
646 X or Y or both is possible. Pseudocode for Indexed Mode (including elwidth
647 overrides) may be written in terms of Matrix Mode, specifically
648 purposed to ensure that the 3rd dimension (Z) has no effect:
651 def index_remap(ISHAPE, i):
652 MSHAPE.skip = 0b0 || ISHAPE.sk1
653 MSHAPE.invxyz = 0b0 || ISHAPE.invxy
654 MSHAPE.xdimsz = ISHAPE.xdimsz
655 MSHAPE.ydimsz = ISHAPE.ydimsz
656 MSHAPE.zdimsz = 0 # disabled
657 if ISHAPE.permute = 0b110 # 0,1
658 MSHAPE.permute = 0b000 # 0,1,2
659 if ISHAPE.permute = 0b111 # 1,0
660 MSHAPE.permute = 0b010 # 1,0,2
661 el_idx = remap_matrix(MSHAPE, i)
662 svreg = ISHAPE.SVGPR << 1
663 srcwid = elwid_to_bitwidth(ISHAPE.elwid)
665 return get_polymorphed_reg(svreg, srcwid, el_idx) + offs
668 The most important observation above is that the Matrix-style
669 remapping occurs first and the Index lookup second. Thus it
670 becomes possible to perform in-place Transpose of Indices which
671 may have been costly to set up or costly to duplicate
672 (waste register file space).
674 # svshape instruction <a name="svshape"> </a>
676 `svshape` is a convenience instruction that reduces instruction
677 count for common usage patterns, particularly Matrix, DCT and FFT. It sets up
678 (overwrites) all required SVSHAPE SPRs and also modifies SVSTATE
679 including VL and MAXVL. Using `svshape` therefore does not also
682 Form: SVM-Form SV "Matrix" Form (see [[isatables/fields.text]])
684 svshape SVxd,SVyd,SVzd,SVRM,vf
686 | 0.5|6.10 |11.15 |16..20 | 21..24 | 25 | 26..31| name |
687 | -- | -- | --- | ----- | ------ | -- | ------| -------- |
688 |OPCD| SVxd | SVyd | SVzd | SVRM | vf | XO | svshape |
692 * **SVxd** - SV REMAP "xdim"
693 * **SVyd** - SV REMAP "ydim"
694 * **SVzd** - SV REMAP "zdim"
695 * **SVRM** - SV REMAP Mode (0b00000 for Matrix, 0b00001 for FFT etc.)
696 * **vf** - sets "Vertical-First" mode
697 * **XO** - standard 6-bit XO field
699 *Note: SVxd, SVyz and SVzd are all stored "off-by-one". In the assembler
700 mnemonic the values `1-32` are stored in binary as `0b00000..0b11111`*
702 | SVRM | Remap Mode description |
704 | 0b0000 | Matrix 1/2/3D |
705 | 0b0001 | FFT Butterfly |
706 | 0b0010 | reserved |
707 | 0b0011 | DCT Outer butterfly |
708 | 0b0100 | DCT Inner butterfly, on-the-fly (Vertical-First Mode) |
709 | 0b0101 | DCT COS table index generation |
710 | 0b0110 | DCT half-swap |
711 | 0b0111 | Parallel Reduction |
712 | 0b1000 | reserved for svshape2 |
713 | 0b1001 | reserved for svshape2 |
714 | 0b1010 | reserved |
715 | 0b1011 | iDCT Outer butterfly |
716 | 0b1100 | iDCT Inner butterfly, on-the-fly (Vertical-First Mode) |
717 | 0b1101 | iDCT COS table index generation |
718 | 0b1110 | iDCT half-swap |
719 | 0b1111 | FFT half-swap |
721 Examples showing how all of these Modes operate exists in the online
722 [SVP64 unit tests](https://git.libre-soc.org/?p=openpower-isa.git;a=tree;f=src/openpower/decoder/isa;hb=HEAD)
723 and the full pseudocode setting up all SPRs
724 is in the [[openpower/isa/simplev]] page.
726 In Indexed Mode, there are only 5 bits available to specify the GPR
727 to use, out of 128 GPRs (7 bit numbering). Therefore, only the top
728 5 bits are given in the `SVxd` field: the bottom two implicit bits
729 will be zero (`SVxd || 0b00`).
731 `svshape` has *limited applicability* due to being a 32-bit instruction.
732 The full capability of SVSHAPE SPRs may be accessed by directly writing
733 to SVSHAPE0-3 with `mtspr`. Circumstances include Matrices with dimensions
734 larger than 32, and in-place Transpose. Potentially a future v3.1 Prefixed
735 instruction, `psvshape`, may extend the capability here.
737 # svindex instruction <a name="svindex"> </a>
739 `svindex` is a convenience instruction that reduces instruction
740 count for Indexed REMAP Mode. It sets up
741 (overwrites) all required SVSHAPE SPRs and can modify the REMAP
742 SPR as well. The relevant SPRs *may* be directly programmed with
743 `mtspr` however it is laborious to do so: svindex saves instructions
744 covering much of Indexed REMAP capability.
746 Form: SVI-Form SV "Indexed" Form (see [[isatables/fields.text]])
748 svindex SVG,rmm,SVd,ew,yx,mr,sk
750 | 0.5|6.10 |11.15 |16.20 | 21..25 | 26..31| name | Form |
751 | -- | -- | --- | ---- | ----------- | ------| -------- | ---- |
752 |OPCD| SVG | rmm | SVd | ew/yx/mm/sk | XO | svindex | SVI-Form |
756 * **SVd** - SV REMAP x/y dim
757 * **rmm** - REMAP mask: sets remap mi0-2/mo0-1 and SVSHAPEs,
759 * **ew** - sets element width override on the Indices
760 * **SVG** - GPR SVG<<2 to be used for Indexing
761 * **yx** - 2D reordering to be used if yx=1
762 * **mm** - mask mode. determines how `rmm` is interpreted.
763 * **sk** - Dimension skipping enabled
764 * **XO** - standard 6-bit XO field
766 *Note: SVd, like SVxd, SVyz and SVzd of `svshape`, are all stored
767 "off-by-one". In the assembler
768 mnemonic the values `1-32` are stored in binary as `0b00000..0b11111`*.
770 *Note: when `yx=1,sk=0` the second dimension is calculated as
775 * `rmm`, like REMAP.SVme, has bit 0
776 correspond to mi0, bit 1 to mi1, bit 2 to mi2,
777 bit 3 to mo0 and bit 4 to mi1
778 * all SVSHAPEs and the REMAP parts of SVSHAPE are first reset (initialised to zero)
779 * for each bit set in the 5-bit `rmm`, in order, the first
780 as-yet-unset SVSHAPE will be updated
781 with the other operands in the instruction, and the REMAP
783 * If all 5 bits of `rmm` are set then both mi0 and mo1 use SVSHAPE0.
784 * SVSTATE persistence bit is cleared
785 * No other alterations to SVSTATE are carried out
787 Example 1: if rmm=0b00110 then SVSHAPE0 and SVSHAPE1 are set up,
788 and the REMAP SPR set so that mi1 uses SVSHAPE0 and mi2
789 uses mi2. REMAP.SVme is also set to 0b00110, REMAP.mi1=0
790 (SVSHAPE0) and REMAP.mi2=1 (SVSHAPE1)
792 Example 2: if rmm=0b10001 then again SVSHAPE0 and SVSHAPE1
793 are set up, but the REMAP SPR is set so that mi0 uses SVSHAPE0
794 and mo1 uses SVSHAPE1. REMAP.SVme=0b10001, REMAP.mi0=0, REMAP.mo1=1
796 Rough algorithmic form:
798 marray = [mi0, mi1, mi2, mo0, mo1]
801 if not rmm[bit]: continue
803 SVSTATE{marray[bit]} = idx
804 idx = (idx+1) modulo 4
808 * bits 0-2 (MSB0 numbering) of `rmm` indicate an index selecting mi0-mo1
809 * bits 3-4 (MSB0 numbering) of `rmm` indicate which SVSHAPE 0-3 shall
811 * only the selected SVSHAPE is overwritten
812 * only the relevant bits in the REMAP area of SVSTATE are updated
813 * REMAP persistence bit is set.
815 Example 1: if `rmm`=0b01110 then bits 0-2 (MSB0) are 0b011 and
816 bits 3-4 are 0b10. thus, mo0 is selected and SVSHAPE2
817 to be updated. REMAP.SVme[3] will be set high and REMAP.mo0
820 Example 2: if `rmm`=0b10011 then bits 0-2 (MSB0) are 0b100 and
821 bits 3-4 are 0b11. thus, mo1 is selected and SVSHAPE3
822 to be updated. REMAP.SVme[4] will be set high and REMAP.mo1
825 Rough algorithmic form:
827 marray = [mi0, mi1, mi2, mo0, mo1]
831 SVSTATE{marray[bit]} = idx
834 In essence, `mm=0` is intended for use to set as much of the
835 REMAP State SPRs as practical with a single instruction,
836 whilst `mm=1` is intended to be a little more refined.
840 * **Disable 2D mapping**: to only perform Indexing without
841 reordering use `SVd=1,sk=0,yx=0` (or set SVd to a value larger
843 * **Modulo 1D mapping**: to perform Indexing cycling through the
844 first N Indices use `SVd=N,sk=0,yx=0` where `VL>N`. There is
845 no requirement to set VL equal to a multiple of N.
846 * **Modulo 2D transposed**: `SVd=M,sk=0,yx=1`, sets
847 `xdim=M,ydim=CEIL(MAXVL/M)`.
849 Beyond these mappings it becomes necessary to write directly to
850 the SVSTATE SPRs manually.
852 # svshape2 (offset) <a name="svshape2"> </a>
854 `svshape2` is an additional convenience instruction that prioritises
855 setting `SVSHAPE.offset`. Its primary purpose is for use when
856 element-width overrides are used. It has identical capabilities to `svindex` and
857 in terms of both options (skip, etc.) and ability to activate REMAP
858 (rmm, mask mode) but unlike `svindex` it does not set GPR REMAP,
859 only a 1D or 2D `svshape`, and
860 unlike `svshape` it can set an arbirrary `SVSHAPE.offset` immediate.
862 One of the limitations of Simple-V is that Vector elements start on the boundary
863 of the Scalar regfile, which is fine when element-width overrides are not
864 needed. If the starting point of a Vector with smaller elwidths must begin
865 in the middle of a register, normally there would be no way to do so except
866 through LD/ST. `SVSHAPE.offset` caters for this scenario and `svshape2`is
869 svshape2 offs,yx,rmm,SVd,sk,mm
871 | 0.5|6..9|10|11.15 |16..20 | 21..25 | 25 | 26..31| name |
872 | -- |----|--| --- | ----- | ------ | -- | ------| -------- |
873 |OPCD|offs|yx| rmm | SVd | 100/mm | sk | XO | svshape |
875 * **offs** (4 bits) - unsigned offset
876 * **yx** (1 bit) - swap XY to YX
877 * **SVd** dimension size
880 * **sk** (1 bit) skips 1st dimension if set
882 Dimensions are calculated exactly as `svindex`. `rmm` and
883 `mm` are as per `svindex`.
885 *Programmer's Note: offsets for `svshape2` may be specified in the range
886 0-15. Given that the principle of Simple-V is to fit on top of
887 byte-addressable register files and that GPR and FPR are 64-bit (8 bytes)
888 it should be clear that the offset may, when `elwidth=8`, begin an
889 element-level operation starting element zero at any arbitrary byte.
890 On cursory examination attempting to go beyond the range 0-7 seems
891 unnecessary given that the **next GPR or FPR** is an
892 alias for an offset in the range 8-15. Thus by simply increasing
893 the starting Vector point of the operation to the next register it
894 can be seen that the offset of 0-7 would be sufficient. Unfortunately
895 however some operations are EXTRA2-encoded it is **not possible**
896 to increase the GPR/FPR register number by one, because EXTRA2-encoding
897 of GPR/FPR Vector numbers are restricted to even numbering.
898 For CR Fields the EXTRA2 encoding is even more sparse.
899 The additional offset range (8-15) helps overcome these limitations.*
901 *Hardware Implementor's note: with the offsets only being immediates
902 and with register numbering being entirely immediate as well it is
903 possible to correctly compute Register Hazards without requiring
904 reading the contents of any SPRs. If however there are
905 instructions that have directly written to the SVSTATE or SVSHAPE
906 SPRs and those instructions are still in-flight then this position
907 is clearly **invalid**.*
911 * investigate https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6879380/#!po=19.6429
912 in https://bugs.libre-soc.org/show_bug.cgi?id=653
913 * UTF-8 <https://bugs.libre-soc.org/show_bug.cgi?id=794>
915 * Cross-Product REMAP (actually, skew Matrix: https://en.m.wikipedia.org/wiki/Skew-symmetric_matrix)