在並行比特碼中實現快速計數器

我正在尋找一種優化的計數器實現，可能類似於灰色代碼，這將使我能夠快速瀏覽比特數組中的數字。在並行比特碼中實現快速計數器

假設我有數組：

_m256 header[640];

我需要保持改變比特的計數器608 - 639的每一個256位的代表一個單獨的，並行計數器。

「增量」操作最多需要31次操作：AND計算進位，XOR計算值，對每個位置重複。格雷碼應該只需要xor，但我不知道計算索引的有效方式 - 它似乎需要多達31個操作來確定一個位的位置。

理想情況下，我想要一個計數器，它需要少量的ALU操作來確定要更改的位。有誰知道會有幫助的事情？

來源

2011-05-27 Xavier

這對我來說不是很清楚你想要做什麼。你說「每個256位代表一個單獨的並行計數器。」 1位計數器只在0,1,0,1，...之間振盪，而進位只是反相值。要計算進位，在「增加」之前，您只需計入每個計數器的當前值。要計算新的價值，你只是'不'櫃檯。這可以通過將多個計數器同時轉換爲大數據類型（例如int）並獲取按位補碼（〜值）來完成。 – Ponkadoodle 2011-05-27 19:43:07

有256個並行計數器，每個32位。 Counter0使用標題[608] ...標題[639]的位0，計數器255使用標題[608] ... [639]的位255。 – Xavier 2011-05-27 20:14:47

有趣的紙：The Gray Code。（它是PDF格式）

PDF的第16頁包含一個用於查找切換哪個位的算法。在一般情況下，它需要32個操作來確定哪個位要改變。如果您可以從計數器中取出一位（這將使其實際上成爲一個31位計數器），那麼您可以使增量時間的平均值減少操作次數。由於每當奇偶校驗爲偶數時，低位被切換，所以如果可以保持奇偶校驗位，那麼每隔一個增量操作將涉及剛剛切換低位。而且，當然，您可以在每次操作時切換奇偶校驗位。

當奇偶校驗爲奇數時，您只需執行發現該位切換的算法部分。但是既然你已經知道奇偶校驗是奇怪的，你不必檢查每一點。當你找到符合條件的位時，你可以停下來。

我對SIMD不夠熟悉，不知道是否有任何方法可以優化。

也就是說，我不清楚這樣的事情是否會改善「常規」二進制計數器所採用的「多達31次操作」。還有，你的一半操作只需要一次迭代。看起來使用格雷碼的主要優點是隻需要一次寫入內存（如果使用上面的奇偶校驗位方法，則需要兩次），而另一種方法可能需要多達32次寫入內存。

來源

2011-05-27 22:30:04

計算確切指數的速度也可能比分支懲罰更慢。我不需要覆蓋整個範圍，所以狀態較少的櫃檯就可以。 – Xavier 2011-05-27 23:18:33

一個LRS可以使用少量的XOR生成一個包含所有非零數字1..2^n-1的序列，但會移動每個階段剩下的所有位。有一些信息在http://www.ee.unb.ca/cgi-bin/tervo/sequence.pl?binary=11111。異或的數量取決於抽頭的數量。在http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr/32stages.txt有32位的幾個分支的LRS配置列表。當然，生成的序列無序 - 顯然是隨機的。

來源

2011-05-28 05:27:01 mcdowella

您可以實現256個並行Linear Shift Feedback Register這種方式（帶底座== 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。

來源

2011-05-29 08:06:25 hirschhornsalz

在並行比特碼中實現快速計數器

回答

相關問題