前一篇给出的代码有错,正在修正中。
这里先给出循环版本
__m512i sieve_sort32x16_loop(__m512i a, uint32_t* result = nullptr) {uint32_t buffer[16] = { 0 };if (result == nullptr) _mm512_store_epi32(result = buffer, a);__mmask16 mask = 0xffff;uint32_t _min = 0, _max = 0;__mmask16 _min_mask = 0, _max_mask = 0;int i = 0, j = 15;while (sieve_get_min_max(mask, a, _min, _max, _min_mask, _max_mask)) {int c_min = __popcnt16(_min_mask);int c_max = __popcnt16(_max_mask);for (int t = 0; t < c_min; t++) {result[i++] = _min;}for (int t = 0; t < c_max; t++) {result[j--] = _max;}mask &= ~(_min_mask | _max_mask);}return _mm512_loadu_epi32(result);
}
目标显然是,追求性能的极致。而这个版本里面有循环,性能恐怕有损失,但是容易阅读和理解。
同样是每次都获取最大值和最小值,然后分别从两头往中间填充结果。这里__popcnt16函数起到了求参数中1的个数的作用,而这些1就对应了里面的最大值和最小值的位置。所以有几个1,这一次就找到了几个最大值或者最小值。最后用
mask &= ~(_min_mask | _max_mask);
把这些找到的最大值和最小值都屏蔽掉,下次就不考虑它们了。基本的布尔运算就不细说了,你懂的。
需要说明的是,函数sieve_get_min_max查找最大最小值的时候,有可能重复,所以它必须改成最大和最小值相关联的形式,
bool sieve_get_min_max(__mmask16 mask, __m512i a, uint32_t& _min, uint32_t& _max, __mmask16& _mask_min, __mmask16& _mask_max) {if (mask != 0) {_mask_max = _mm512_mask_cmpeq_epi32_mask(mask, a, _mm512_set1_epi32(_max = _mm512_mask_reduce_max_epu32(mask, a)));_mask_min = _mm512_mask_cmpeq_epi32_mask(mask & (~_mask_max), a, _mm512_set1_epi32(_min = _mm512_mask_reduce_min_epu32(mask & (~_mask_max), a)));return true;}return false;
}
也就是说最大值的查找会影响最小值的查找结果。查找最小值的时候必须排除排除最大值,不然可能出现重复计算。上一章给出的代码出错,就是重复计算造成的。
改动在这里:
_mask_min = _mm512_mask_cmpeq_epi32_mask(mask & (~_mask_max), a, _mm512_set1_epi32(_min = _mm512_mask_reduce_min_epu32(mask & (~_mask_max), a)));
为了尽可能快,就要尽量去除循环,所以进一步简化可以得出如下版本,
__m512i sieve_sort32x16_loop(__m512i a, uint32_t* result = nullptr) {__m512i target = zero;__mmask16 mask = 0xffff;__mmask16 _min_mask = 0, _max_mask = 0;uint32_t _min = 0, _max = 0;int i = 0, j = 16;while (sieve_get_min_max(mask, a, _min, _max, _min_mask, _max_mask)) {int c_min = __popcnt16(_min_mask);int c_max = __popcnt16(_max_mask);target = _mm512_mask_blend_epi32((-(!!c_min)) & ((~((~0U) << c_min)) << i),target, _mm512_set1_epi32(_min));target = _mm512_mask_blend_epi32((-(!!c_max)) & ((~((~0U) << c_max)) << (j - c_max)),target, _mm512_set1_epi32(_max));i += c_min;j -= c_max;mask &= ~(_min_mask | _max_mask);}if (result != nullptr) {_mm512_storeu_epi32(result, target);}return target;
}
用位运算代替判断:"(-(!!c_min))&"这保证了若c_min为0,则整个mask都为0;用移位设置mask,比如(~0U)=0b1111111111111111,对其左移就可以获得0b111...1000...然后再翻转就可以获得需要的个数的1的序列,然后再把它放在正确的位置上。最后用混合操作,将最小值或者最大值混入结果。
这就消去了循环的影响。
毕竟循环最终也只是为了实现最小值或者最大值多次出现在不同的位置。显然用组合逻辑电路的思路来编程,就可以最大化的实现并行性。