快速合并L1/L2中4K浮点数的排序子集

Question

在现代(SSE2 +)x86处理器上合并多达4096个32位浮点数的数组的排序子集的快速方法是什么？

请假设以下内容:

• 整套的大小最多为4096件
• 子集的大小可以讨论,但我们假设最初在16-256之间
• 通过合并使用的所有数据应该优选地适合L1
• L1数据高速缓存大小为32K.16K已经用于数据本身,因此您可以使用16K
• 所有数据都已经在L1中(具有尽可能高的置信度) - 它刚刚通过一种操作进行操作
• 所有数据都是16字节对齐的
• 我们想尽量减少分支(原因很明显)

可行性的主要标准:比in-L1 LSD基数排序更快.

考虑到上述参数,我很想知道是否有人知道这样做的合理方法!:)

Answer 1

这是一种非常天真的方式.(请原谅任何凌晨4点谵妄引起的伪代码错误;)

//4x sorted subsets
data[4][4] = {
  {3, 4, 5, INF},
  {2, 7, 8, INF},
  {1, 4, 4, INF},
  {5, 8, 9, INF}
}

data_offset[4] = {0, 0, 0, 0}

n = 4*3

for(i=0, i<n, i++):
  sub = 0
  sub = 1 * (data[sub][data_offset[sub]] > data[1][data_offset[1]])
  sub = 2 * (data[sub][data_offset[sub]] > data[2][data_offset[2]])
  sub = 3 * (data[sub][data_offset[sub]] > data[3][data_offset[3]])

  out[i] = data[sub][data_offset[sub]]
  data_offset[sub]++

编辑:
使用AVX2及其聚集支持,我们可以同时比较多达8个子集.

编辑2:
根据类型转换,有可能在Nehalem上每次迭代削减3个额外的时钟周期(mul:5,shift + sub:4)

//Assuming 'sub' is uint32_t
sub = ... << ((data[sub][data_offset[sub]] > data[...][data_offset[...]]) - 1)

编辑3:
有可能在某种程度上利用无序执行,特别是当K变大时,使用两个或更多max值:

max1 = 0
max2 = 1
max1 = 2 * (data[max1][data_offset[max1]] > data[2][data_offset[2]])
max2 = 3 * (data[max2][data_offset[max2]] > data[3][data_offset[3]])
...
max1 = 6 * (data[max1][data_offset[max1]] > data[6][data_offset[6]])
max2 = 7 * (data[max2][data_offset[max2]] > data[7][data_offset[7]])

q = data[max1][data_offset[max1]] < data[max2][data_offset[max2]]

sub = max1*q + ((~max2)&1)*q

编辑4:

根据编译器的智能,我们可以使用三元运算符完全删除乘法:

sub = (data[sub][data_offset[sub]] > data[x][data_offset[x]]) ? x : sub

编辑5:

为了避免代价高昂的浮点比较,我们可以简单地reinterpret_cast<uint32_t*>()使用数据,因为这会导致整数比较.

另一种可能性是利用SSE寄存器,因为它们不是键入的,并且明确地使用整数比较指令.

这是因为操作符< > ==在解释二进制级别的浮点时产生相同的结果.

编辑6:

如果我们充分展开循环以使值的数量与SSE寄存器的数量相匹配,我们就可以对正在进行比较的数据进行分级.

在迭代结束时,我们将重新传输包含所选最大/最小值的寄存器,并将其移位.

虽然这需要稍微重新编写索引,但它可能比使用LEAs 乱丢循环更有效.