Реализация быстрого счетчика в коде с параллельными битовыми нарезками

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

Предполагая, что у меня есть массив:

_m256 header[640];

Мне нужно постоянно менять счетчик в битах 608–639. Каждый из 256 бит представляет собой отдельный параллельный счетчик.

Операция приращения занимает до 31 операции: И для вычисления переноса, XOR для вычисления значения, повторяется для каждой позиции.

Для кода Грея требуется только xor, но я не знаю эффективного способа вычисления индекса — похоже, для определения позиции бита требуется до 31 операции.

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


optimization algorithm simd assembly
person Xavier    schedule 27.05.2011    source источник
comment
Мне не очень понятно, что вы пытаетесь сделать. Вы говорите, что каждый из 256 бит представляет собой отдельный параллельный счетчик. 1-битный счетчик просто колеблется между 0, 1, 0, 1, ... И перенос - это просто инвертированное значение. Чтобы вычислить перенос, перед «инкрементированием» вы просто берете текущее значение каждого счетчика. Чтобы вычислить новое значение, вы просто «не» считаете счетчик. Это можно сделать одновременно с несколькими счетчиками путем приведения к большому типу данных (например, int) и взятия побитового дополнения (~значение).   -  person Ponkadoodle    schedule 27.05.2011
comment
Имеется 256 параллельных счетчиков по 32 бита каждый. Счетчик0 использует бит 0 заголовка[608]..заголовок[639], счетчик255 использует бит 255 заголовка[608]..[639].   -  person Xavier    schedule 28.05.2011

Ответы (3)


arrow_upward
1
arrow_downward

LRS может генерировать последовательность, содержащую все ненулевые числа 1..2^n-1, используя небольшое количество XOR, но сдвигая все оставшиеся биты на каждом этапе. Некоторая информация есть на http://www.ee.unb.ca/cgi-bin/tervo/sequence.pl?binary=11111. Количество операций XOR зависит от количества нажатий. Список конфигураций LRS для 32-битной версии с несколькими касаниями можно найти по адресу http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr/32stages.txt. Конечно, сгенерированная последовательность не по порядку - она, по-видимому, случайна.

person mcdowella    schedule 28.05.2011

arrow_upward
0
arrow_downward

Интересная статья: Код Грея. (Это PDF)

Страница 16 PDF-файла содержит алгоритм определения того, какой бит переключать. В общем случае требуется 32 операции, чтобы определить, какой бит следует изменить. Если вы можете выделить один бит из своего счетчика (что сделает его фактически 31-битным счетчиком), вы можете сократить среднее время приращения за меньшее количество операций.

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

Когда четность нечетная, вам просто нужно выполнить часть алгоритма, которая находит бит для переключения. Но поскольку вы уже знаете, что четность нечетная, вам не нужно проверять каждый бит. Вы можете остановиться, когда найдете бит, соответствующий условию.

Я недостаточно знаком с SIMD, чтобы сказать, можно ли это как-то оптимизировать.

Тем не менее, мне не ясно, будет ли такая вещь улучшением по сравнению с «до 31 операции», которую выполнит «обычный» двоичный счетчик. Опять же, половина ваших операций потребует всего одной итерации. Кажется, что основное преимущество использования кода Грея заключается в том, что требуется только одна запись в память (две, если вы используете описанный выше подход с битами четности), тогда как другой метод может потребовать до 32 записей в память.

person Jim Mischel    schedule 27.05.2011
comment
Вычисление точного индекса также может быть медленнее из-за штрафов за ветвление. Мне не нужно покрывать весь диапазон, поэтому счетчик с меньшим количеством состояний будет в порядке. - person Xavier; 28.05.2011

arrow_upward
0
arrow_downward

Вы можете реализовать 256 параллельных регистров обратной связи с линейным сдвигом таким образом (с base==608)

calculate x := header[base+0] XOR header[base+1] XOR header[base+21] XOR header[base+31]
move all elements header[base]...header[base+30] to header[base+1]...header[base+31]
set header[base] := x

Это будет иметь 2 ^ 32-1 различных состояний. Если 2^31-1 достаточно, используйте ответвления 27 и 30 вместо 0,1,21,31. Магические числа взяты с http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf.

person Gunther Piez    schedule 29.05.2011