c++ - 在 L1/L2 中快速合并 4K float 的排序子集

Question

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

请假设:

• 整个集合的大小最多为 4096 个项目
• 子集的大小有待讨论，但我们最初假设在 16-256 之间
• 通过合并使用的所有数据最好适合 L1
• L1 数据缓存大小为 32K。 16K 已经用于数据本身，因此您可以使用 16K
• 所有数据都已经在 L1 中(尽可能高的置信度) - 它刚刚被排序操作
• 所有数据都是 16 字节对齐的
• 我们希望尽量减少分支(原因很明显)

可行性的主要标准:比 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:
通过使用两个或多个 max 可以在某种程度上利用乱序执行，尤其是当 K 变大时。值(value)观:

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 寄存器，因为它们没有类型，并明确使用整数比较指令。

这得益于运营商 < > ==在二进制级别解释 float 时产生相同的结果。

编辑 6:

如果我们充分展开循环以使值的数量与 SSE 寄存器的数量相匹配，我们就可以暂存正在比较的数据。

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

虽然这需要稍微修改索引，但它可能比在循环中乱扔LEA 更有效。的。