在并行位切片代码中实现快速计数器

Question

我正在寻找一个计数器的优化实现，可能类似于格雷码，它将允许我快速遍历位片数组中的数字。

假设我有数组：

_m256 header[640];  

我需要不断改变608 - 639位中的计数器。256位中的每一位代表独立的并行计数器。

一个“增量”操作需要多达31次操作:和计算进位，异或计算值，对每个位置重复。

Gray-code应该只需要xor，但我不知道有一种有效的方法来计算索引-它似乎需要多达31次操作来确定位的位置。

理想情况下，我想要一个计数器，它需要少量的ALU操作来确定要更改的位。有没有人知道什么会对你有帮助？

Answer 1

一个LRS可以生成一个包含所有非零数1..2^n-1的序列，使用少量的XOR，但是移位每一级剩下的所有位。在http://www.ee.unb.ca/cgi-bin/tervo/sequence.pl?binary=11111上有一些信息。XOR的数量取决于抽头的数量。在http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr/32stages.txt上有一个32位的LRS配置列表，只有很少的抽头。当然，生成的序列是无序的-它显然是随机的。

Answer 2

有趣的论文：The Gray Code。(这是PDF格式)

PDF的第16页包含一个算法，用于查找要切换的位。一般情况下，需要32次操作才能确定要更改的位。如果您可以从计数器中腾出一位(这将使其有效地成为31位计数器)，您可以使平均增量时间采取更少的操作。

因为只要奇偶校验是偶数，低位就会被触发，如果你能保留一个奇偶校验位，那么每隔一次增量操作就会涉及到低位的切换。当然，您需要在每次操作时切换奇偶校验位。

当奇偶校验是奇数时，您只需执行算法中找到要切换的位的部分。但是由于您已经知道奇偶校验是奇数，所以不必检查每一个比特。当您找到满足条件的位时，您可以停止。

我对SIMD还不够熟悉，不知道有没有什么方法可以优化它。

也就是说，我不清楚这样的事情会不会比“常规”二进制计数器需要的“多达31次操作”有所改善。同样，您的一半操作将只需要一次迭代。似乎使用格雷码的主要优点是只需要一次写入内存(如果使用上面的奇偶校验位方法，则需要两次写入)，而另一种方法可能需要多达32次写入内存。

Answer 3

您可以通过这种方式(使用base==608)实现256个并行Linear Shift Feedback Register

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。