View source for Permute instruction


'''Permute''' (and Shuffle) instructions, part of [[Bit manipulation|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.<ref>{{cite book |title=Intel® 64 and IA-32 architectures software developer’s manual combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4 |date=June 2021 |publisher=Intel |page=5-356 Vol. 2C |url=https://software.intel.com/content/dam/develop/external/us/en/documents-tps/325462-sdm-vol-1-2abcd-3abcd.pdf}}</ref> 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:

<source lang="python">
for i = 0 to length-1
    dest[i] = src[indices[i]]
</source>

where the scatter variant is:

<source lang="python">
for i = 0 to length-1
    dest[indices[i]] = src[i]
</source>

Note that unlike in memory-based [[Gather-scatter (vector addressing)|gather-scatter]] all three of <code>dest</code>, <code>src</code>, and <code>indices</code> 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|permutation]] because duplicates can occur in the output.

A special case of permute is also used in GPU "[[Swizzling (computer graphics)|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. 

== Occurrences of permute instructions ==

Permute instructions occur in both [[Scalar processor|scalar processor]]s as well as vector processing engines as well as [[Graphics processing unit|GPUs]].  In vector instruction sets they are typically named "Register Gather/Scatter" operations such as in [[Engineering:RISC-V|RISC-V]] vectors,<ref>{{cite web | title=RISC-V "V" Vector Extension – 16.4. Vector Register Gather Instructions | website=GitHub – riscv/riscv-v-spec | url=https://github.com/riscv/riscv-v-spec/blob/master/v-spec.adoc#vector-register-gather-instructions | access-date=2021-07-10}}</ref> 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  
<code>bdep</code> (bit deposit) in RISC-V bitmanip;<ref>{{cite web | title=riscv/riscv-bitmanip | website=GitHub | url=https://github.com/riscv/riscv-bitmanip | access-date=2021-07-10}}</ref> in the [[Power ISA]] it is known as {{code|bpermd}} and has been included for several decades, and is still in the Power ISA v.3.0 B spec.<ref name="isa307b">{{cite web | title=Power ISA Version 3.0 B | publisher=Power.org | date=2017-03-27 | url=https://openpowerfoundation.org/?resource_lib=power-isa-version-3-0 | access-date=2019-08-11}}</ref>

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 <code>VSHUFF32x4</code> from [[AVX-512#Permute|AVX-512]].

Permute operations in different forms are surprisingly common, occurring in [[Engineering:AltiVec|AltiVec]], [[Power ISA]], [[Engineering:PowerPC G4|PowerPC G4]], [[AVX-512]], SVE2,<ref>[https://indico.ph.ed.ac.uk/event/69/contributions/892/attachments/734/910/Arm_Exascale.pdf ARM HPC, SVE2 Extension summary, p32]</ref> vector processors, and [[Graphics processing unit|GPUs]]. They are sufficiently important that [[Software:LLVM|LLVM]] added the {{code|shufflevector}}<ref name="LLVM Language Reference Manual">{{cite web | title=LLVM 13 documentation: shufflevector | website=LLVM Language Reference Manual | url=https://llvm.org/docs/LangRef.html#shufflevector-instruction | access-date=2021-07-10}}</ref> intrinsic and [[Software:GNU Compiler Collection|GCC]] added the {{code|__builtin_shuffle}} intrinsic.<ref>{{cite web | title=Vector Extensions (Using the GNU Compiler Collection (GCC)) | website=GCC, the GNU Compiler Collection - GNU Project - Free Software Foundation (FSF) | url=https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html | access-date=2021-07-10}}</ref> GCC's intrinsic matches the functionality of [[OpenCL]]'s shuffle intrinsics.<ref>{{cite web | title=OpenCL Specification: shuffle, shuffle2 | website=The Khronos Group Inc | url=https://www.khronos.org/registry/OpenCL/sdk/2.1/docs/man/xhtml/shuffle.html | access-date=2021-07-10}}</ref> Note that all of these, mathematically, are not permutations because duplicates can occur in the output.

== See also ==
* {{slink|Kepler (microarchitecture)|Shuffle Instructions}}
* {{slink|GeForce 700 series|New shuffle Instructions}}

== References ==
{{Reflist}}

==External links==
* [https://www.felixcloutier.com/x86/vshuff32x4:vshuff64x2:vshufi32x4:vshufi64x2 Unofficial convenient list of AVX-512 shuffle instructions]
* [https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf Official Intel AVX-512 ISA Manual]
* [https://community.arm.com/developer/ip-products/processors/b/processors-ip-blog/posts/coding-for-neon---part-5-rearranging-vectors ARM NEON tutorial on data rearrangement]

{{Multimedia extensions}}

[[Category:Binary arithmetic]]
[[Category:Computer arithmetic]]

{{Sourceattribution|Permute instruction}}