Быстрое симметричное двоичное матричное умножение с использованием векторных расширений - PullRequest
Новая
       16

Быстрое симметричное двоичное матричное умножение с использованием векторных расширений

0 голосов
/ 01 февраля 2019

Я использую двоичную матрицу, представляющую неориентированный граф, и играю с векторными расширениями gcc, чтобы посмотреть, что можно сделать, чтобы эффективно создать матричный продукт (заменяя операции + / * на | / &).

Следующая попытка предполагает, что обе входные матрицы симметричны относительно диагонали: 

typedef unsigned char __attribute__((vector_size(8))) vec;
vec example_input = {
  0b11001000
, 0b11001001
, 0b00100100
, 0b00010000
, 0b11001000
, 0b00100100
, 0b00000010
, 0b01000001
};

void symmetric_product( const vec& left, const vec& right, vec& result ) {
  for( unsigned ii = 0; ii < 8; ++ii ) {
    vec tmp{};
    // broadcast row ii across all rows
    tmp -= 1;
    tmp &= left[ii];
    // compute first half of dot product of
    // all rows in 'right' with row 'ii'
    tmp &= right;
    // The rest does the 'tallying'; I believe
    // the rest could be replaced with the
    // pext intrinsic
    result[ii] = 0;
    for( unsigned jj = 0; jj < 8; ++jj ) {
      result[ii] |= (0 != tmp[ii]) << jj;
    }
  }
}

Я исследовал нечто подобное несколько месяцев назад и подумал, что видел хитрый способ осуществить это, но все, что я нахожутеперь это семейство инструкций pext *.

Если это единственный путь, пусть будет так;Я надеюсь, что кто-то знает другой способ, который не требует аппаратных встроенных функций.

...