Самый быстрый способ транспонировать матрицу 4x4 байта

У меня есть блок байтов 4x4, который я хотел бы перенести с использованием аппаратного обеспечения общего назначения. Другими словами, для байтов AP я ищу наиболее эффективный (с точки зрения количества инструкций) способ перехода от

A B C D
E F G H
I J K L
M N O P

в

A E I M
B F J N
C G K O
D H L P

Мы можем предположить, что у меня есть действительные указатели, указывающие на A, E, I, а также M в памяти (такой, что чтение 32-битного из A даст мне целое число, содержащее байты ABCD).

Это не дубликат этого вопроса из-за ограничений по размеру и типу данных. Каждая строка моей матрицы может вписаться в 32-разрядное целое число, и я ищу ответы, которые могут быстро выполнить транспонирование с использованием аппаратного обеспечения общего назначения, аналогично реализации макроса SSE _MM_TRANSPOSE4_PS,

Источник

5 ответов

Решение

Позвольте мне перефразировать ваш вопрос: вы запрашиваете решение на C- или C++, которое является переносимым. Затем:

void transpose(uint32_t const in[4], uint32_t out[4]) {
  // A B C D    A E I M
  // E F G H    B F J N
  // I J K L    C G K O
  // M N O P    D H L P

  out[0] = in[0] & 0xFF000000U; // A . . .
  out[1] = in[1] & 0x00FF0000U; // . F . .
  out[2] = in[2] & 0x0000FF00U; // . . K .
  out[3] = in[3] & 0x000000FFU; // . . . P

  out[1] |= (in[0] <<  8) & 0xFF000000U; // B F . .
  out[2] |= (in[0] << 16) & 0xFF000000U; // C . K .
  out[3] |= (in[0] << 24);               // D . . P

  out[0] |= (in[1] >>  8) & 0x00FF0000U; // A E . .
  out[2] |= (in[1] <<  8) & 0x00FF0000U; // C G K .
  out[3] |= (in[1] << 16) & 0x00FF0000U; // D H . P

  out[0] |= (in[2] >> 16) & 0x0000FF00U; // A E I .
  out[1] |= (in[2] >>  8) & 0x0000FF00U; // B F J .
  out[3] |= (in[2] <<  8) & 0x0000FF00U; // D H L P

  out[0] |= (in[3] >> 24);               // A E I M
  out[1] |= (in[3] >>  8) & 0x000000FFU; // B F J N
  out[2] |= (in[3] <<  8) & 0x000000FFU; // C G K O
}

Я не понимаю, как на него можно было бы ответить каким-либо другим способом, так как тогда вы зависите от конкретного компилятора, который его компилирует определенным образом, и т. Д.

Конечно, если сами эти манипуляции можно как-то упростить, это поможет. Так что это единственный путь дальнейшего преследования здесь. Пока ничего не выделяется, но тогда это был длинный день для меня.

Пока что стоимость составляет 12 смен, 12 OR, 16 AND. Если компилятор и платформа хороши, это можно сделать в 9 32-битных регистрах.

Если компилятор очень огорчен, или у платформы нет переключателя стволов, то некоторое приведение может помочь превознести тот факт, что сдвиги и маски - это просто извлечение байтов:

void transpose(uint8_t const in[16], uint8_t out[16]) {
  // A B C D    A E I M
  // E F G H    B F J N
  // I J K L    C G K O
  // M N O P    D H L P

  out[0]  = in[0];  // A . . .
  out[1]  = in[4];  // A E . .
  out[2]  = in[8];  // A E I .
  out[3]  = in[12]; // A E I M
  out[4]  = in[1];  // B . . .
  out[5]  = in[5];  // B F . .
  out[6]  = in[9];  // B F J .
  out[7]  = in[13]; // B F J N
  out[8]  = in[2];  // C . . .
  out[9]  = in[6];  // C G . .
  out[10] = in[10]; // C G K .
  out[11] = in[14]; // C G K O
  out[12] = in[3];  // D . . .
  out[13] = in[7];  // D H . .
  out[14] = in[11]; // D H L .
  out[15] = in[15]; // D H L P
}

Если вы действительно хотите перетасовать его на месте, то подойдет следующее.

void transpose(uint8_t m[16]) {
  std::swap(m[1], m[4]);
  std::swap(m[2], m[8]);
  std::swap(m[3], m[12]);
  std::swap(m[6], m[9]);
  std::swap(m[7], m[13]);
  std::swap(m[11], m[14]);
}

Байт-ориентированные версии могут создавать худший код на современных платформах. Только эталон может сказать.

Источник

Вы хотите мобильности и эффективности. Ну, вы не можете иметь это в обоих направлениях. Вы сказали, что хотите сделать это с наименьшим количеством инструкций. Ну, это возможно сделать только с одной инструкцией с SSE3, используя инструкцию pshufb (см. Ниже) из набора команд x86.

Может быть, ARM Neon имеет что-то эквивалентное. Если вам нужна эффективность (и вы уверены, что она вам нужна), изучите оборудование.

SSE эквивалент _MM_TRANSPOSE4_PS для байтов это использовать _mm_shuffle_epi8 (свойственный pshufb) с маской. Определите маску за пределами вашего основного цикла.

//use -msse3 with GCC or /arch:SSE2 with MSVC
#include <stdio.h>
#include <tmmintrin.h> //SSSE3
int main() {
    char x[] = {0,1,2,3, 4,5,6,7, 8,9,10,11, 12,13,15,16};
    __m128i mask = _mm_setr_epi8(0x0,0x04,0x08,0x0c, 0x01,0x05,0x09,0x0d, 0x02,0x06,0x0a,0x0e, 0x03,0x07,0x0b,0x0f);

    __m128i v = _mm_loadu_si128((__m128i*)x);
    v = _mm_shuffle_epi8(v,mask);
    _mm_storeu_si128((__m128i*)x,v);
    for(int i=0; i<16; i++) printf("%d ", x[i]); printf("\n");
    //output: 0 4 8 12 1 5 9 13 2 6 10 15 3 7 11 16   
}
Источник

Я отправил ответ на эту же проблему некоторое время назад для SSE здесь.

Единственное, что нужно добавить - это векторизованные операции загрузки / сохранения.

Этот ответ аналогичен ответу Z-бозона на этот вопрос. Примеры загрузки / хранения можно увидеть там. Этот ответ отличается, потому что в дополнение к реализации SSE3 есть реализация SSE2, которая гарантированно будет работать на любом процессоре x64.

Стоит отметить, что оба эти решения предполагают, что вся матрица является основной строкой в ​​памяти, но вопрос OP гласит, что у каждой строки может быть свой собственный указатель, который подразумевает, что массив может быть фрагментирован.

Источник

Эффективное решение возможно на 64-битной машине, если вы принимаете это. Сначала сдвиньте 32-битные целочисленные константы на (0,) 1, 2 и 3 байта соответственно [3 shitfs]. Затем замаскируйте нежелательные биты и выполните логическое ИЛИ [12 И с константой, 12 ИЛИ]. Наконец, вернитесь к 32 битам [3 смены] и считайте 32 бита.

ABCD
EFGH
IJKL
MNOP

ABCD
 EFGH
  IJKL
   MNOP

A---
 E---
  I---
   MNOP
=======
AEIMNOP
AEIM

AB--
 -F--
  -J--
   -NOP
=======
ABFJNOP
BFJN

ABC-
 --G-
  --K-
   --OP
=======
ABCGKOP
CGKO

ABCD
 ---H
  ---L
   ---P
=======
ABCDHLP
DHLP
Источник

Не уверен насчет скорости, но это нормально.

template<typename T, std::size_t Size>
void Transpose(T (&Data)[Size][Size])
{
    for (int I = 0; I < Size; ++I)
    {
        for (int J = 0; J < I; ++J)
        {
            std::swap(Data[I][J], Data[J][I]);
        }
    }
}

template<typename T, std::size_t Size>
void Transpose(T (&Data)[Size * Size])
{
    for (int I = 0; I < Size; ++I)
    {
        for (int J = 0; J < I; ++J)
        {
            std::swap(Data[I * Size + J], Data[J * Size + I]);
        }
    }
}
Источник
Другие вопросы по тегам