Permute instruction

Permute (and Shuffle) instructions, part of bit manipulation as well as vector processing, copy unaltered contents from a source array to a destination array, where the indices are specified by a second source array.[1] The size (bitwidth) of the source elements is not restricted but remains the same as the destination size.

There exists two important permute variants, known as gather and scatter, respectively. The gather variant is as follows:

for i = 0 to length-1
dest[i] = src[indices[i]]

where the scatter variant is:

for i = 0 to length-1
dest[indices[i]] = src[i]

Note that unlike in memory-based gather-scatter all three of `dest`, `src`, and `indices` are registers (or parts of registers in the case of bit-level permute), not memory locations.

The scatter variant can be seen to "scatter" the source elements across (into) to the destination, where the "gather" variant is gathering data from the indexed source elements.

Given that the indices may be repeated in both variants, the resultant output is not a strict mathematical permutation because duplicates can occur in the output.

A special case of permute is also used in GPU "swizzling" (again, not strictly a permutation) which performs on-the-fly reordering of subvector data so as to align or duplicate elements with the appropriate SIMD lane.

## Contents

* 1 Occurrences of permute instructions
* 2 See also
* 3 References
* 4 External links

## Occurrences of permute instructions

Permute instructions occur in both scalar processors as well as vector processing engines as well as GPUs. In vector instruction sets they are typically named "Register Gather/Scatter" operations such as in RISC-V vectors,[2] and take Vectors as input for both source elements and source array, and output another Vector.

In scalar instruction sets the scalar registers are broken down into smaller sections (unpacked, SIMD style) where the fragments are then used as array sources. The (small, partial) results are then concatenated (packed) back into the scalar register as the result.

Some ISAs, particularly for cryptographic applications, even have bit-level permute operations, such as `bdep` (bit deposit) in RISC-V bitmanip;[3] in the Power ISA it is known as `bpermd` and has been included for several decades, and is still in the Power ISA v.3.0 B spec.[4]

Also in some non-vector ISAs, due to there sometimes being insufficient space in the one source input register to specify the permutation source array in full (particularly if the operation involves bit-level permutation), will include partial reordering instructions. Examples include `VSHUFF32x4` from AVX-512.

Permute operations in different forms are surprisingly common, occurring in AltiVec, Power ISA, PowerPC G4, AVX-512, SVE2,[5] vector processors, and GPUs. They are sufficiently important that LLVM added the `shufflevector`[6] intrinsic and GCC added the `__builtin_shuffle` intrinsic.[7] GCC's intrinsic matches the functionality of OpenCL's shuffle intrinsics.[8] Note that all of these, mathematically, are not permutations because duplicates can occur in the output.

## See also

* Kepler (microarchitecture) § Shuffle Instructions
* GeForce 700 series § New shuffle Instructions

## References

1. ↑ Intel® 64 and IA-32 architectures software developer’s manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4. Intel. June 2021. p. 5-356 Vol. 2C. https://software.intel.com/content/dam/develop/external/us/en/documents-tps/325462-sdm-vol-1-2abcd-3abcd.pdf.
2. ↑ "RISC-V "V" Vector Extension – 16.4. Vector Register Gather Instructions". https://github.com/riscv/riscv-v-spec/blob/master/v-spec.adoc#vector-register-gather-instructions.
3. ↑ "riscv/riscv-bitmanip". https://github.com/riscv/riscv-bitmanip.
4. ↑ "Power ISA Version 3.0 B". Power.org. 2017-03-27. https://openpowerfoundation.org/?resource_lib=power-isa-version-3-0.
5. ↑ ARM HPC, SVE2 Extension summary, p32
6. ↑ "LLVM 13 documentation: shufflevector". https://llvm.org/docs/LangRef.html#shufflevector-instruction.
7. ↑ "Vector Extensions (Using the GNU Compiler Collection (GCC))". https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html.
8. ↑ "OpenCL Specification: shuffle, shuffle2". https://www.khronos.org/registry/OpenCL/sdk/2.1/docs/man/xhtml/shuffle.html.

## External links

* Unofficial convenient list of AVX-512 shuffle instructions
* Official Intel AVX-512 ISA Manual
* ARM NEON tutorial on data rearrangement

* v
* t
* e

Instruction set extensions

SIMD (RISC)|

* Alpha
* MVI
* ARM
* NEON
* SVE
* MIPS
* MDMX
* MIPS-3D
* MXU
* MIPS SIMD
* PA-RISC
* MAX
* Power ISA
* VMX
* SPARC
* VIS

SIMD (x86)|

* MMX (1996)
* 3DNow! (1998)
* SSE (1999)
* SSE2 (2001)
* SSE3 (2004)
* SSSE3 (2006)
* SSE4 (2006)
* SSE5 ~~(2007)~~
* AVX (2008)
* F16C (2009)
* XOP (2009)
* FMA (FMA4: 2011, FMA3: 2012)
* AVX2 (2013)
* AVX-512 (2015)

Bit manipulation|

* BMI (ABM: 2007, BMI1: 2012, BMI2: 2013, TBM: 2012)
* ADX (2014)

Compressed instructions|

* Thumb
* MIPS16e ASE

Security and cryptography|

* AES-NI (2008); 32- and 64-bit ARMv8 also has AES instructions
* CLMUL (2010)
* RDRAND (2012)
* SHA (2013)
* MPX (2015)
* SGX (2015)

Transactional memory|

* TSX (2013)
* ASF

Virtualization|

* VT-x (2005)
* AMD-V (2006)

Suspended extensions' dates have been ~~struck through~~.

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Permute_instruction&oldid=3907660"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template