旋轉AVX寄存器內的一個字節的有效方法

Question

摘要/ tl; dr：除了進行2次移位並將結果混合在一起之外，是否有任何方法可以逐位旋轉YMM寄存器中的一個字節（使用AVX）？

對於YMM寄存器中的每8個字節，我需要在其中左轉7個字節。每個字節需要比前者向左多旋轉一圈。因此1字節應該旋轉0位，第7位應該旋轉6位。

目前，我已經做了一個這樣做的實現[我在這裏使用1位旋轉作爲示例]將寄存器1位向左和向右移位7個單獨。然後，我使用混合操作（內部操作_mm256_blend_epi16）從第一個和第二個臨時結果中選擇正確的位，以獲得最終的旋轉字節。
這花費了總共2個移位操作和每個字節1個混合操作，並且需要旋轉6個字節，因此每個字節有18個操作（移位和混合具有幾乎相同的性能）。

要做到這一點，必須有比使用18個操作旋轉單個字節更快的方法！

此外，我需要在新的寄存器中組裝所有的字節。我通過將7個帶有「set」指令的掩碼加載到寄存器中來實現這一點，所以我可以從每個寄存器中提取正確的字節。我和這些掩碼與寄存器從它們中提取正確的字節。之後，我將單字節寄存器XOR異或，以獲得包含所有字節的新寄存器。 這需要總共7 + 7 + 6次操作，所以還有20次操作（每個寄存器）。

我可以使用提取內在（_mm256_extract_epi8）來獲取單個字節，然後使用_mm256_set_epi8來組裝新的寄存器，但我不知道這是否會更快。 （在英特爾內核指南中沒有列出這些功能的性能，所以也許我在這裏誤解了一些東西。）

這給每個寄存器總共38個操作，這似乎不是最優的，寄存器。

我希望有更精通AVX/SIMD的人可以在這裏指導我 - 無論我是否以這種錯誤的方式去做 - 因爲我覺得我現在可能會這樣做。

Answer 1

XOP instruction set確實提供_mm_rot_epi8()（這不是微軟特有的;它自4.4或更早版本以後也可在GCC中使用，並且最近也應該可用）。它可以用來以128位爲單位執行所需的任務。不幸的是，我沒有支持XOP的CPU，所以我無法測試它。

在AVX2上，將256位寄存器分成兩部分，一部分包含偶數字節，另一部分奇數字節右移8位，允許16位向量乘。給定常數（使用GCC 64位元件陣列格式）

static const __m256i epi16_highbyte = { 0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL }; 
static const __m256i epi16_lowbyte = { 0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL }; 
static const __m256i epi16_oddmuls = { 0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL }; 
static const __m256i epi16_evenmuls = { 0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL }; 

旋轉操作可被寫爲

__m256i byteshift(__m256i value) 
{ 
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_lowbyte), epi16_oddmuls), 8), 
          _mm256_and_si256(_mm256_mullo_epi16(_mm256_and_si256(_mm256_srai_epi16(value, 8), epi16_lowbyte), epi16_evenmuls), epi16_highbyte)); 
} 

這已被證實使用GCC-上的Intel Core i5-4200U得到正確的結果4.8.4。作爲一個例子，輸入矢量（作爲單個256位的16進制數）

88 87 86 85 84 83 82 81 38 37 36 35 34 33 32 31 28 27 26 25 24 23 22 21 FF FE FD FC FB FA F9 F8 

被旋轉到

44 E1 D0 58 24 0E 05 81 1C CD C6 53 A1 CC 64 31 14 C9 C4 52 21 8C 44 21 FF BF BF CF DF EB F3 F8 

在最左側的八比特組向左旋轉由7位，接下來的6個比特，和等等;第七個字節不變，第八個八位字節旋轉7位，依此類推，全部32個八位字節。

我不確定上述函數定義是否編譯爲最佳機器碼 - 取決於編譯器 - ，但我對它的性能感到滿意。

因爲你很可能不喜歡上面的簡明格式的功能，這在程序上，展開形式：

static __m256i byteshift(__m256i value) 
{ 
    __m256i low, high; 
    high = _mm256_srai_epi16(value, 8); 
    low = _mm256_and_si256(value, epi16_lowbyte); 
    high = _mm256_and_si256(high, epi16_lowbyte); 
    low = _mm256_mullo_epi16(low, epi16_lowmuls); 
    high = _mm256_mullo_epi16(high, epi16_highmuls); 
    low = _mm256_srli_epi16(low, 8); 
    high = _mm256_and_si256(high, epi16_highbyte); 
    return _mm256_or_si256(low, high); 
} 

---

在評論，Peter Cordes建議用srli更換srai + and，並可能最後and + or與blendv。前者具有很大的意義，因爲它純粹是一種優化，但後者可能不會（現在的英特爾CPU上）實際上會更快。

我嘗試了一些microbenchmarking，但無法獲得可靠的結果。我通常在x86-64上使用TSC，並使用存儲在數組中的輸入和輸出進行數十萬次測試的中位數。

我認爲這是最有用的，如果我只是在這裏列出變體，所以任何需要這種功能的用戶都可以在他們的實際工作負載上做一些基準測試，並測試是否有任何可測量的差異。

我還與他的建議同意使用的high和lowodd和even代替，但要注意的是，由於在向量的第一個元素的編號爲第0個元素，第一個元素是甚至，第二奇，等等。

#include <immintrin.h> 

static const __m256i epi16_oddmask = { 0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL }; 
static const __m256i epi16_evenmask = { 0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL }; 
static const __m256i epi16_evenmuls = { 0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL }; 
static const __m256i epi16_oddmuls = { 0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL }; 

/* Original version suggested by Nominal Animal. */ 
__m256i original(__m256i value) 
{ 
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8), 
          _mm256_and_si256(_mm256_mullo_epi16(_mm256_and_si256(_mm256_srai_epi16(value, 8), epi16_evenmask), epi16_oddmuls), epi16_oddmask)); 
} 

/* Optimized as suggested by Peter Cordes, without blendv */ 
__m256i no_blendv(__m256i value) 
{ 
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8), 
          _mm256_and_si256(_mm256_mullo_epi16(_mm256_srli_epi16(value, 8), epi16_oddmuls), epi16_oddmask)); 
} 

/* Optimized as suggested by Peter Cordes, with blendv. 
* This is the recommended version. */ 
__m256i optimized(__m256i value) 
{ 
    return _mm256_blendv_epi8(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8), 
           _mm256_mullo_epi16(_mm256_srli_epi16(value, 8), epi16_oddmuls), epi16_oddmask); 
} 

下面是以顯示各個操作的方式編寫的相同功能。儘管它不會影響到理智的編譯器，但我已經標記了函數參數和每個臨時值const，這樣就很明顯如何將每個表達式插入到後續表達式中，以便將函數簡化爲上述簡潔形式。

__m256i original_verbose(const __m256i value) 
{ 
    const __m256i odd1 = _mm256_srai_epi16(value, 8); 
    const __m256i even1 = _mm256_and_si256(value, epi16_evenmask); 
    const __m256i odd2 = _mm256_and_si256(odd1, epi16_evenmask); 
    const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls); 
    const __m256i odd3 = _mm256_mullo_epi16(odd3, epi16_oddmuls); 
    const __m256i even3 = _mm256_srli_epi16(even3, 8); 
    const __m256i odd4 = _mm256_and_si256(odd3, epi16_oddmask); 
    return _mm256_or_si256(even3, odd4); 
} 

__m256i no_blendv_verbose(const __m256i value) 
{ 
    const __m256i even1 = _mm256_and_si256(value, epi16_evenmask); 
    const __m256i odd1 = _mm256_srli_epi16(value, 8); 
    const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls); 
    const __m256i odd2 = _mm256_mullo_epi16(odd1, epi16_oddmuls); 
    const __m256i even3 = _mm256_srli_epi16(even2, 8); 
    const __m256i odd3 = _mm256_and_si256(odd2, epi16_oddmask); 
    return _mm256_or_si256(even3, odd3); 
} 

__m256i optimized_verbose(const __m256i value) 
{ 
    const __m256i even1 = _mm256_and_si256(value, epi16_evenmask); 
    const __m256i odd1 = _mm256_srli_epi16(value, 8); 
    const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls); 
    const __m256i odd2 = _mm256_mullo_epi16(odd1, epi16_oddmuls); 
    const __m256i even3 = _mm256_srli_epi16(even2, 8); 
    return _mm256_blendv_epi8(even3, odd2, epi16_oddmask); 
} 

我親手做的寫我的測試功能最初在其上面詳細的形式，形成簡潔的版本是一個微不足道的一組的複製粘貼的。不過，我確實測試了兩個版本，以驗證是否引入任何錯誤，並保持冗長的版本可以訪問（作爲評論等），因爲簡潔版本基本上是隻寫的。編輯詳細版本比簡化版本更容易，然後簡化爲簡潔版本。

Answer 2

[基於第一條評論和一些編輯，最終的解決方案有點不同。我將首先介紹，然後保留下面的原始思想]

這裏的主要思想是使用乘以2的冪來完成移位，因爲這些常數可以在矢量上變化。 @harold指出了下一個想法，即兩個重複字節的乘法會自動將移出的位「旋轉」回低位。

1. 拆開包裝並重復字節到16位值[... d c b a] -> [... dd cc bb aa]
2. 生成一個16位的常數[128 64 32 16 8 4 2 1]
3. 乘
4. 你想要的是每個16位值的高八位字節，所以右移並重新打包

假設__m128i源（您只有8個字節，對吧？）：

__m128i duped = _mm_unpacklo_epi8(src, src); 
__m128i res = _mm_mullo_epi16(duped, power_of_two_vector); 
__m128i repacked = _mm_packus_epi16(_mm_srli_epi16(res, 8), __mm_setzero_si128()); 

---

[保存比較這個最初的想法]

這個怎麼樣：由2的冪用乘法來完成轉變，使用16位產品。然後或者產品的上半部分和下半部分完成旋轉。

1. 將字節解包爲16位字。
2. 生成一個16位的[128 64 32 16 8 4 2 1]
3. 乘以16位字
4. 重新打包的16位爲兩個八比特向量，高字節矢量和低字節向量
5. OR這兩個向量來完成旋轉。

我對可用的乘法選項和您的指令集限制有點模糊，但理想情況是8位乘以8位乘法產生16位乘積。據我所知，它不存在，這就是爲什麼我建議首先解包，但我已經看到了這樣做的其他整潔的算法。