Las instrucciones de permutación (y reproducción aleatoria), que forman parte de la manipulación de bits y del procesamiento de vectores , copian contenidos inalterados de una matriz de origen a una matriz de destino, donde los índices se especifican mediante una segunda matriz de origen. [1] El tamaño (ancho de bits) de los elementos de origen no está restringido, pero sigue siendo el mismo que el tamaño de destino.
Existen dos variantes de permutación importantes, conocidas como reunión y dispersión, respectivamente. La variante de recolección es la siguiente:
para i = 0 a longitud - 1 destino [ i ] = src [ índices [ i ]]
donde la variante de dispersión es:
para i = 0 a longitud - 1 destino [ índices [ i ]] = src [ i ]
Tenga en cuenta que, a diferencia de la recopilación-dispersión basada en memoria, los tres de dest
, src
y indices
son registros (o partes de registros en el caso de permutación a nivel de bits), no ubicaciones de memoria.
Se puede ver que la variante de dispersión "dispersa" los elementos de origen hacia el destino, donde la variante de "reunión" recopila datos de los elementos de origen indexados.
Dado que los índices pueden repetirse en ambas variantes, el resultado resultante no es una permutación matemática estricta porque pueden ocurrir duplicados en el resultado.
También se utiliza un caso especial de permutación en el " swizzling " de GPU (nuevamente, no es estrictamente una permutación) que realiza una reordenación sobre la marcha de datos de subvectores para alinear o duplicar elementos con el carril SIMD apropiado .
Las instrucciones de permutación ocurren tanto en procesadores escalares como en motores de procesamiento vectorial y GPU . En los conjuntos de instrucciones vectoriales, normalmente se denominan operaciones "Registrar recopilación/dispersión", como en los vectores RISC-V , [2] y toman vectores como entrada tanto para los elementos fuente como para la matriz fuente, y generan otro vector.
En los conjuntos de instrucciones escalares, los registros escalares se dividen en secciones más pequeñas (desempaquetadas, estilo SIMD ) donde los fragmentos se utilizan luego como fuentes de matriz. Los resultados (pequeños, parciales) luego se concatenan (empaquetan) nuevamente en el registro escalar como resultado.
Algunas ISA, particularmente para aplicaciones criptográficas , incluso tienen operaciones de permutación a nivel de bits , como bdep
(depósito de bits) en bitmanip RISC-V; [3] en Power ISA se le conoce bpermd
y se ha incluido durante varias décadas, y todavía se encuentra en la especificación Power ISA v.3.0 B. [4]
Además, en algunos ISA no vectoriales, debido a que a veces no hay suficiente espacio en el registro de entrada de un origen para especificar la matriz de origen de permutación en su totalidad (particularmente si la operación implica permutación a nivel de bits), se incluirán instrucciones de reordenamiento parcial. Los ejemplos incluyen VSHUFF32x4
AVX -512 .
Las operaciones de permutación en diferentes formas son sorprendentemente comunes y ocurren en AltiVec , Power ISA , PowerPC G4 , AVX-512 , SVE2 , [5] procesadores vectoriales y GPU . Son lo suficientemente importantes como para que LLVM agregue el shufflevector
[6] intrínseco y GCC agregue el __builtin_shuffle
intrínseco. [7] El intrínseco de GCC coincide con la funcionalidad del intrínseco aleatorio de OpenCL . [8] Tenga en cuenta que todos estos, matemáticamente, no son permutaciones porque pueden ocurrir duplicados en la salida.