SIMD相关
原理
字符查找
基数排序
- Bitwise MSB Radix Sort on AVX-512
- 基于bit的MSB基数排序,从高位开始每bit做比较像快排一样做左右划分,这样不需要额外的空间去做基数归类
- simd排序有个麻烦的点是怎样搬动比较key之外的数据,这里的做法是看成kv并打包在一起,如果v是64位指针kv就是128位,512位的vector可以放4个,如果v是32位的位置kv是64位放8个
- 每次拿vector中所有key中的一位进行比较得到一个mask, testAndCount(bitMaskVec, keyPayload, sortBits, popcnt)
- 然后关键点是mask_compressstoreu这个指令,通过sortBits,把keyPayload符合条件的位对应的数据写到d + writePos[0],这样就实现了搬动数据
- 但是感觉一位一位排序似乎效率有点低,把simd的优势又还回去了?
排序网络(Bitonic Sorting Network)
- Fast Quicksort Implementation Using AVX Instructions
- 假设一次操作4个数,VBROADCASTSS (pivot), P (设置pivot)
- VMOVDQU (in), D (取数组成向量)
- VPCMPGTD D, P, C (向量和pivot比较)
- VMOVMSKPS C, r (生成按bit的mask)
- SHL $4, r
VPERMILPS permTableLesser(, r), D, L
VPERMILPS permTableGreater(, r), D, G (用mask查表得到两个向量内位置list,然后用vpermilps指令从源向量取数到目标寄存器,完成了partition这一步)
- permTableLesser这种表是预先构建好的,因为mask寄存器只有16种可能对应的位置都是确定的
- POPCNT r, r0
MOV $4, r1
SUB r0, r1 (计算partition后两边各有几个数)
- VMOVDQU L, (Lptr)
VMOVDQU G, (Gptr) (寄存器写回内存比如数组里面)
- LEA (Lptr, r0, 4), Lptr
LEA (Gptr, r1, 4), Gptr (移动数组指针)
- 256位的AVX2增加了VPGATHERQQ指令,这样源向量里面可以存kv然后VPGATHERQQ只取出key来比较
- AVX512增加了VCOMPRESSPS指令,直接通过mask写无需查表
- 存kv始终是个痛点,放一起会减少向量里面的记录数,A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake 给的一个解决办法是value单独放一个等长的数组,根据mask partition的时候也给value数组操作一次
没有评论:
发表评论