Инструкции перестановки (и перемешивания ), часть манипуляции с битами, а также векторная обработка , копируют неизмененное содержимое из исходного массива в целевой массив, где индексы задаются вторым исходным массивом. Размер (разрядность) исходных элементов не ограничен, но остается таким же, как и размер назначения.
Существует два важных варианта перестановки, известные как сбор и разброс, соответственно. Вариант сборки следующий:
для i = 0 до длины - 1 dest [ i ] = src [ index [ i ]]
где вариант разброса:
для я = 0 до длины - 1 точки назначения [ индексы [[ я ]] = SRC [ я ]
Обратите внимание, что в отличие от метода сборки -разброса на основе памяти, все три из dest, src и index являются регистрами (или частями регистров в случае перестановки на уровне битов), а не ячейками памяти.
Видно, что вариант разброса «разбрасывает» исходные элементы по (внутрь) к месту назначения, где вариант «собрать» собирает данные из проиндексированных исходных элементов.
Учитывая, что индексы могут повторяться в обоих вариантах, результирующий вывод не является строгой математической перестановкой, поскольку в выводе могут встречаться дубликаты. Инструкции перестановки, вводящие в заблуждение, фактически создают комбинации .
Особый случай перестановки также используется в « swizzling » графического процессора (опять же, что сбивает с толку, на самом деле комбинация ), который выполняет переупорядочение данных подвектора на лету, чтобы выровнять или дублировать элементы с соответствующей полосой SIMD .
Появление перестановочных инструкций
Команды перестановки выполняются как в скалярных процессорах, так и в механизмах векторной обработки, а также в графических процессорах . В наборах векторных команд они обычно называются операциями «Сбор / разброс регистров», например, в векторах RISC-V [1] , и принимают векторы в качестве входных данных как для исходных элементов, так и для исходного массива и выводят другой вектор.
В наборах скалярных инструкций скалярные регистры разбиты на более мелкие части (распакованные, стиль SIMD ), где фрагменты затем используются в качестве источников массива. Затем (небольшие, частичные) результаты объединяются (упаковываются) обратно в скалярный регистр в качестве результата.
Некоторые ISA, особенно для криптографических приложений, даже имеют операции перестановки на уровне битов , такие как bdep
(битовое депонирование) в RISC-V bitmanip [2] ; в Power ISA он известен как bpermd
и был включен в течение нескольких десятилетий, и все еще находится в спецификации Power ISA v.3.0 B. [3]
Также в некоторых не-векторных ISA из-за того, что иногда недостаточно места в одном исходном входном регистре для полного указания исходного массива перестановок (особенно, если операция включает перестановку на битовом уровне), будут включены инструкции частичного переупорядочения. Примеры включают в себя VSHUFF32x4
от AVX-512 .
Операции перестановки в различных формах на удивление часто встречаются в AltiVec , Power ISA , PowerPC G4 , AVX-512 , SVE2 [4] и в векторных процессорах, а также в графических процессорах . Они достаточно важны, чтобы LLVM включил внутренний объект shufflevector
[5] и gcc как __builtin_shuffle
[6] . Внутренняя функция GCC соответствует функциональности встроенной функции перестановки OpenCL . [7] . Обратите внимание, что все это математически комбинации, несмотря на использование слова «перестановка» в соответствующих спецификациях.