用于旋转或转置阵列的最佳SIMD算法

Question

我正在研究一个数据结构,我有一个16 uint64的数组.它们在内存中的布局如下(每个下面代表一个int64):

A0 A1 A2 A3 B0 B1 B2 B3 C0 C1 C2 C3 D0 D1 D2 D3

期望的结果是将数组转换为:

A0 B0 C0 D0 A1 B1 C1 D1 A2 B2 C2 D2 A3 B3 C3 D3

阵列旋转90度也是未来循环的可接受解决方案:

D0 C0 B0 A0 D1 C1 B1 A1 D2 C2 B2 A2 D3 C3 B3 A3

我需要这个以便稍后快速操作箭头(按顺序遍历另一个SIMD行程,一次4个).

到目前为止,我试图通过加载A的4 x 64位向量,比特掩码和混洗元素并用B等进行OR运算来"混合"数据,然后对C进行重复...不幸的是,这是数组中4个元素的每个段的5 x 4个SIMD指令(一个加载,一个掩码,一个shuffle,一个或下一个元素,最后一个存储).看来我应该能够做得更好.

我有AVX2可用,我用clang编译.

Answer 1

uint64_t A[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
__m256i row0 = _mm256_loadu_si256((__m256i*)&A[ 0]); //0 1 2 3
__m256i row1 = _mm256_loadu_si256((__m256i*)&A[ 4]); //4 5 6 7
__m256i row2 = _mm256_loadu_si256((__m256i*)&A[ 8]); //8 9 a b
__m256i row3 = _mm256_loadu_si256((__m256i*)&A[12]); //c d e f

我现在没有硬件来测试它,但是类似下面的东西应该做你想要的

__m256i tmp3, tmp2, tmp1, tmp0;
tmp0 = _mm256_unpacklo_epi64(row0, row1);            //0 4 2 6
tmp1 = _mm256_unpackhi_epi64(row0, row1);            //1 5 3 7
tmp2 = _mm256_unpacklo_epi64(row2, row3);            //8 c a e
tmp3 = _mm256_unpackhi_epi64(row2, row3);            //9 d b f
//now select the appropriate 128-bit lanes
row0 = _mm256_permute2x128_si256(tmp0, tmp2, 0x20);  //0 4 8 c
row1 = _mm256_permute2x128_si256(tmp1, tmp3, 0x20);  //1 5 9 d
row2 = _mm256_permute2x128_si256(tmp0, tmp2, 0x31);  //2 6 a e
row3 = _mm256_permute2x128_si256(tmp1, tmp3, 0x31);  //3 7 b f

该

__m256i _mm256_permute2x128_si256 (__m256i a, __m256i b, const int imm)

内在选择来自两个来源的128位通道.您可以在英特尔Intrinsic指南中阅读相关内容.有一个版本_mm256_permute2f128_si256只需要AVX并在浮点域中起作用.我用它来检查我是否使用了正确的控制字.