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

Question

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

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

_m256 header[640];  

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

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

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

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

Answer 1

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. Конечно, сгенерированная последовательность не в порядке - она, по-видимому, случайна.

Answer 2

Вы можете реализовать 256 параллельных регистров обратной связи с линейным сдвигом таким образом (с основанием == 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.

Answer 3

Интересная бумага: Серый код .(Это PDF)

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

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

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

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