Как бы вы переставили двоичную матрицу?

Мое предложение состоит в том, что вы не выполняете транспонирование, а добавляете однобитовую информацию к своим данным матрицы, указывая, транспонирована ли матрица или нет.

Теперь, если вы хотите умножить матрицу транспонирования на вектор, это будет то же самое, что и умножение матрицы. налево вектором (а затем транспонировать). Это легко: только некоторые xor операции ваших 8-битных чисел.

Это, однако, усложняет некоторые другие операции (например, добавление двух матриц). Но в комментарии вы говорите, что умножение — это именно то, что вы хотите оптимизировать.

Мое предложение будет использовать справочную таблицу для ускорения обработки.

Еще одна вещь, которую стоит отметить, — при текущем определении вашей матрицы максимальный размер будет 8×8 бит. Это вписывается в uint64_t, поэтому мы можем использовать это в наших интересах, особенно при использовании 64-битной платформы.

Я разработал простой пример, используя таблицу поиска, которую вы можете найти ниже и запустите, используя: http://www.tutorialspoint.com/compile_cpp11_online.php онлайн компилятор.

Пример кода

#include <iostream>
#include <bitset>
#include <stdint.h>
#include <assert.h>

using std::cout;
using std::endl;
using std::bitset;

/* Static lookup table */
static uint64_t lut[256];

/* Helper function to print array */
template<int N>
void print_arr(const uint8_t (&arr)[N]){
for(int i=0; i < N; ++i){
cout << bitset<8>(arr[i]) << endl;
}
}

/* Transpose function */

template<int N>
void transpose_bitmatrix(const uint8_t (&matrix)[N], uint8_t (&transposed)[8]){
assert(N <= 8);

uint64_t value = 0;
for(int i=0; i < N; ++i){
value = (value << 1) + lut[matrix[i]];
}

/* Ensure safe copy to prevent misalignment issues */
/* Can be removed if input array can be treated as uint64_t directly */
for(int i=0; i < 8; ++i){
transposed[i] = (value >> (i * 8)) & 0xFF;
}
}

/* Calculate lookup table */
void calculate_lut(void){
/* For all byte values */
for(uint64_t i = 0; i < 256; ++i){
auto b = std::bitset<8>(i);
auto v = std::bitset<64>(0);

/* For all bits in current byte */
for(int bit=0; bit < 8; ++bit){
if(b.test(bit)){
v.set((7 - bit) * 8);
}
}

lut[i] = v.to_ullong();
}
}

int main()
{
calculate_lut();

const uint8_t matrix[] = {
0b01010101,
0b00110011,
0b00001111,
};

uint8_t transposed[8];

transpose_bitmatrix(matrix, transposed);
print_arr(transposed);

return 0;
}

Как это устроено

Ваша матрица 3×8 будет транспонирована в матрицу 8×3, представленную в массиве 8×8.
Проблема в том, что вы хотите преобразовать биты, ваше «горизонтальное» представление в вертикальное, разделенное на несколько байтов.

Как я упоминал выше, мы можем воспользоваться тем фактом, что выходные данные (8×8) всегда будут помещаться в uint64_t. Мы будем использовать это для нашего преимущества, потому что теперь мы можем использовать uint64_t для записи 8-байтового массива, но мы также можем использовать его для сложения, xor и т. Д., Поскольку мы можем выполнять основные арифметические операции над 64-битным целым числом.

Каждая запись в вашей матрице 3×8 (входная) имеет ширину 8 бит, чтобы оптимизировать обработку, мы сначала генерируем таблицу поиска по 256 записей (для каждого значения байта). Сама запись является uint64_t и будет содержать повернутую версию битов.

пример:

байт = 0b01001111 = 0x4F
lut [0x4F] = 0x0001000001010101 = (uint8_t []) {0, 1, 0, 0, 1, 1, 1, 1}

Теперь для расчета:

Для расчетов мы используем uint64_t, но имейте в виду, что под водой он будет представлять массив uint8_t [8]. Мы просто сдвигаем текущее значение (начинаем с 0), ищем наш первый байт и добавляем его к текущему значению.

«Волшебство» здесь в том, что каждый байт uint64_t в таблице поиска будет либо 1, либо 0, поэтому он будет устанавливать только младший значащий бит (каждого байта). Сдвиг uint64_t будет сдвигать каждый байт, если мы уверены, мы делаем это не более 8 раз! мы можем выполнять операции с каждым байтом индивидуально.

вопросы

Как кто-то отметил в комментариях: Переведите (Translate (M))! = M, поэтому, если вам это нужно, вам понадобится дополнительная работа.

Производительность может быть улучшена путем прямого сопоставления массивов uint64_t вместо массивов uint8_t [8], поскольку в нем отсутствует «безопасное копирование» для предотвращения проблем с выравниванием.

Вот текст электронного письма Джея Фоуда о быстрой булевой матрице
транспонировать:

Сердцем булева алгоритма транспонирования является функция, которую я назову transpose8x8 которая транспонирует булеву матрицу 8×8, упакованную в 64-битное слово (в старшем порядке строк от MSB к LSB). Чтобы транспонировать любую прямоугольную матрицу, ширина и высота которой кратны 8, разбейте ее на блоки 8×8, транспонируйте каждый в отдельности и сохраните их в соответствующем месте на выходе. Чтобы загрузить блок 8×8, вам нужно загрузить 8 отдельных байтов, сдвинуть их и ИЛИ в 64-битное слово. То же самое, что для хранения.

Простая C реализация transpose8x8 опирается на тот факт, что все биты на любой диагональной линии, параллельной ведущей диагонали, перемещаются на одинаковое расстояние вверх / вниз и влево / вправо. Например, все биты чуть выше начальной диагонали должны сдвинуться на одно место влево и на одно место вниз, то есть на 7 бит вправо в упакованном 64-битном слове. Это приводит к такому алгоритму:

transpose8x8(word) {

return
(word & 0x0100000000000000) >> 49 // top right corner

| (word & 0x0201000000000000) >> 42

| ...

| (word & 0x4020100804020100) >> 7 // just above diagonal

| (word & 0x8040201008040201) // leading diagonal

| (word & 0x0080402010080402) << 7 // just below diagonal

| ...
| (word & 0x0000000000008040) << 42

| (word & 0x0000000000000080) << 49; // bottom left corner

}

Это работает примерно в 10 раз быстрее, чем предыдущая реализация, которая копировала каждый бит отдельно из исходного байта в памяти и объединяла его с целевым байтом в памяти.

В качестве альтернативы, если у вас есть инструкции PDEP и PEXT, вы можете реализовать идеальный случайный порядок воспроизведения и использовать его для транспонирования, как указано в «Хакерском восторге». Это значительно быстрее (но у меня нет времени):

shuffle(word) {
return pdep(word >> 32, 0xaaaaaaaaaaaaaaaa) | pdep(word, 0x5555555555555555);
} // outer perfect shuffle

transpose8x8(word) { return shuffle(shuffle(shuffle(word))); }

электроинструмента vgbbd инструкция эффективно реализует весь transpose8x8 в одной инструкции (и поскольку это 128-битная векторная инструкция, она делает это дважды независимо от младших 64 битов и старших 64 битов). Это дало около 15% ускорения по сравнению с простой реализацией Си. (Только 15%, потому что, хотя битовое перемешивание происходит намного быстрее, общее время выполнения теперь определяется временем, которое требуется для загрузки 8 байтов и объединения их в аргумент transpose8x8и взять результат и сохранить его как 8 отдельных байтов.)

Я добавил новый awnser вместо того, чтобы редактировать свой оригинальный, чтобы сделать его более заметным (к сожалению, нет прав на комментарии).

В свой собственный awnser вы добавляете дополнительное требование, которого нет в первом: Должен работать на ARM Cortex-M

Я предложил альтернативное решение для ARM в своем оригинальном awnser, но пропустил его, поскольку это не было частью вопроса и казалось не по теме (в основном из-за тега C ++).

ARM Специальное решение Cortex-M:

Некоторые или большинство Cortex-M 3/4 имеют область битовой полосы, которая может использоваться именно для того, что вам нужно, она расширяет биты в 32-битные поля, эта область может использоваться для выполнения атомарных битовых операций.

Если вы поместите ваш массив в область битовых полос, у него будет «взорванное» зеркало в области битовых полос, где вы можете просто использовать операции перемещения для самих битов. Если вы сделаете цикл, компилятор наверняка сможет развернуть и оптимизировать, чтобы просто перенести операции.

Если вы действительно этого хотите, вы можете даже настроить контроллер DMA для обработки всего пакета операций транспонирования с небольшим усилием и полностью выгружать его из процессора 🙂

Возможно, это все еще может помочь вам.

Вот что я написал на gitub (mischasan / sse2 / ssebmx.src)
Изменение INP () и OUT () для использования индукционных переменных сохраняет IMUL каждый.
AVX256 делает это в два раза быстрее.
AVX512 не вариант, потому что нет _mm512_movemask_epi8 ().

#include <stdint.h>
#include <emmintrin.h>

#define INP(x,y) inp[(x)*ncols/8 + (y)/8]
#define OUT(x,y) out[(y)*nrows/8 + (x)/8]

void ssebmx(char const *inp, char *out, int nrows, int ncols)
{
int rr, cc, i, h;
union { __m128i x; uint8_t b[16]; } tmp;

// Do the main body in [16 x 8] blocks:
for (rr = 0; rr <= nrows - 16; rr += 16)
for (cc = 0; cc < ncols; cc += 8) {
for (i = 0; i < 16; ++i)
tmp.b[i] = INP(rr + i, cc);
for (i = 8; i--; tmp.x = _mm_slli_epi64(tmp.x, 1))
*(uint16_t*)&OUT(rr, cc + i) = _mm_movemask_epi8(tmp.x);
}

if (rr == nrows) return;

// The remainder is a row of [8 x 16]* [8 x 8]?

//  Do the [8 x 16] blocks:
for (cc = 0; cc <= ncols - 16; cc += 16) {
for (i = 8; i--;)
tmp.b[i] = h = *(uint16_t const*)&INP(rr + i, cc),
tmp.b[i + 8] = h >> 8;
for (i = 8; i--; tmp.x = _mm_slli_epi64(tmp.x, 1))
OUT(rr, cc + i) = h = _mm_movemask_epi8(tmp.x),
OUT(rr, cc + i + 8) = h >> 8;
}

if (cc == ncols) return;

//  Do the remaining [8 x 8] block:
for (i = 8; i--;)
tmp.b[i] = INP(rr + i, cc);
for (i = 8; i--; tmp.x = _mm_slli_epi64(tmp.x, 1))
OUT(rr, cc + i) = _mm_movemask_epi8(tmp.x);
}

НТН.

Это немного поздно, но я только сегодня наткнулся на этот обмен.
Если вы посмотрите на Восхищение Хакера, 2-е издание, есть несколько алгоритмов для эффективного транспонирования логических массивов, начиная со страницы 141.

Они довольно эффективны: мой коллега получил коэффициент в 10 раз больше
ускорение по сравнению с наивным кодированием на X86.