#define SIZE 16
void transpose(int a[SIZE][SIZE]) { // function to transpose matrix
// define a macro to swap two array elements:
#define swapd(x,y) {temp=x; x=y; y=temp;}
int r, c; int temp;
for (r = 1; r < SIZE; r++) {
for (c = 0; c < r; c++) {
swapd(a[r][c], a[c][r]);
}
}
}
2 回答
对于使用SIMD的两个操作数指令,您可以显示转置
nxn
矩阵所需的操作数是n*log_2(n)
,而使用标量操作时它是O(n^2)
. 实际上,稍后我将展示使用标量寄存器的读写操作数是2*n*(n-1)
. 下表显示了使用SSE,AVX,AVX512和AVX1024转换4x4
,8x8
,16x16
和32x32
矩阵与标量运算相比的运算次数其中SIMD r / w ops包括读写操作(
n*log_2(n) + 2*n
) .可以在
n*log_2(n)
操作中完成SIMD转置的原因是算法是:例如,对于
4x4
,有4行,因此您必须将32位通道4次置换,然后将64位通道置换4次 . 对于16x16
,您必须置换32位通道,64位通道,128位通道,最后通过256通道16次 .I already showed that 8x8 can be done with 24 operations with AVX . 所以问题是如何在64次操作中使用AVX512为
16x16
做这个?一般算法是:这是未经测试的代码
我通过查看使用
_mm_shuffle_ps
(这是MSVC在_MM_TRANSPOSE4_PS
但不是GCC和ICC中使用的)转置4x4
矩阵来获得使用_mm512_shufflei32x4
的想法 .同样的想法适用于
_mm512_shuffle_i32x4
但现在通道是128位而不是32位,有16行而不是4行 .最后,为了比较标量操作,我从Agner Fog的optimizing C++ manual修改了例9.5a
这确实是
n*(n-1)/2
交换(因为对角线不需要交换) . 16x16的装配交换看起来像所以使用标量寄存器的读/写操作数是
2*n*(n-1)
.我最近获得了拥有AVX512的Xeon Phi Knights Landing硬件 . 具体来说,我使用的硬件是Intel(R)Xeon Phi(TM)CPU 7250 @ 1.40GHz(http://ark.intel.com/products/94035/Intel-Xeon-Phi-Processor-7250-16GB-1_40-GHz-68-core) . 这不是辅助卡 . Xeon Phi是主要的计算机 .
我测试了AVX512收集指令与我的方法https://stackoverflow.com/a/29587984/2542702相比,看起来聚集仍然较慢 . 我在该答案中的代码首次尝试没有错误 .
我在大约3个月内没有编写内在函数,或者在这段时间内没有考虑优化,所以也许我的测试不够健壮 . 肯定会有一些开销,但我仍然相信结果清楚地表明在这种情况下聚集速度较慢 .
我只测试了ICC 17.0.0,因为目前安装的操作系统只有CentOS 7.2,Linux内核3.10和GCC 4.8.5,而GCC 4.8不支持AVX512 . 我可以说服HPC小组进行升级工作 .
我查看了程序集以确保它生成了AVX512指令,但我没有仔细分析它 .
在这种情况下
gather
函数需要1.5秒,tran
函数需要1.15秒 . 如果有人发现错误或对我的测试有任何建议,请告诉我 . 我刚开始获得AVX512和Knights Landing的经验 .我试图删除一些开销并成功然而聚集仍然似乎更慢
gather
函数耗时1.13秒,tran
函数耗时0.8秒 .根据Agner Fog的微架构手册,洗牌和置换说明使用KNL表现不佳 . 我的原始答案https://stackoverflow.com/a/29587984/2542702中使用的随机和解包指令的倒数吞吐量为2.我设法通过使用
vpermq
来改善性能,而后者的倒数吞吐量为1.另外,我改进了转置的前1/4 . 使用vinserti64x4
(见下面的tran_new2
) . 这是一个时代表 .tran
函数需要0.8秒,tran_new2
函数需要0.46秒 .