15

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

请假设以下情况：

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

可行性的主要标准：比 L1 LSD 基数排序更快。

鉴于上述参数，我很想看看是否有人知道这样做的合理方法！:)

4

6 回答 6

8

这是一种非常幼稚的方法。（请原谅任何凌晨 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 寄存器的数量相匹配，我们就可以暂存正在比较的数据。

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

尽管这需要稍微修改索引，但它可能比在循环中乱扔LEA's 更有效。

于 2012-07-19T02:45:31.303 回答
3

这更像是一个研究主题，但我确实找到了这篇论文，它讨论了使用 d-way 合并排序最小化分支错误预测。

于 2012-07-18T23:46:19.220 回答
2

想到的最明显的答案是使用堆的标准 N 路合并。那将是 O(N log k)。子集的数量在 16 到 256 之间，因此最坏情况下的行为（256 个子集，每个子​​集 16 个项目）将是 8N。

缓存行为应该是……合理的，尽管并不完美。大部分操作所在的堆可能会始终保留在缓存中。被写入的输出数组部分也很可能在缓存中。

您拥有的是 16K 的数据（具有已排序子序列的数组）、堆（1K，最坏的情况）和已排序的输出数组（再次为 16K），并且您希望它适合 32K 缓存。听起来像一个问题，但也许不是。最有可能被换出的数据是插入点移动后输出数组的前面。假设排序后的子序列是相当均匀分布的，它们应该被足够频繁地访问以将它们保存在缓存中。

于 2012-07-20T03:15:48.103 回答
2

您可以免费合并 int 数组（昂贵的）分支。

typedef unsigned uint;
typedef uint* uint_ptr;

void merge(uint*in1_begin, uint*in1_end, uint*in2_begin, uint*in2_end, uint*out){

  int_ptr in [] = {in1_begin, in2_begin};
  int_ptr in_end [] = {in1_end, in2_end};

  // the loop branch is cheap because it is easy predictable
  while(in[0] != in_end[0] && in[1] != in_end[1]){
    int i = (*in[0] - *in[1]) >> 31;
    *out = *in[i];
    ++out;
    ++in[i];
  }

  // copy the remaining stuff ...
}

注意 (*in[0] - *in[1]) >> 31 等价于 *in[0] - *in[1] < 0 等价于 *in[0] < *in[1]。我使用位移技巧而不是

int i = *in[0] < *in[1];

是不是所有的编译器都会为 < 版本生成无分支代码。

不幸的是，您使用的是浮点数而不是整数，这起初看起来像是一个炫技，因为我看不到如何真正实现 *in[0] < *in[1] 分支免费。然而，在大多数现代架构上，您将正浮点数的位模式（也不是 NAN、INF 或其他奇怪的东西）解释为整数并使用 < 进行比较，您仍然会得到正确的结果。也许您将此观察扩展到任意浮点数。

于 2012-07-21T21:51:41.310 回答
2

SIMD 排序算法已经被详细研究过。论文Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture描述了一种高效算法，用于执行您所描述的（以及更多）。

核心思想是，您可以减少合并两个任意长的列表以合并k个连续值的块（其中k的范围可以从 4 到 16）：第一个块是z[0] = merge(x[0], y[0]).lo. 为了获得第二个块，我们知道剩余部分merge(x[0], y[0]).hi包含来自 的nx元素x和ny来自 的元素y，其中nx+ny == k。但是z[1]不能同时包含x[1]and中的元素y[1]，因为这需要z[1]包含多个nx+ny元素：所以我们只需要找出需要添加的x[1]和。y[1]具有较低第一个元素的元素必然首先出现在z，所以这只是通过比较它们的第一个元素来完成。我们只是重复这一点，直到没有更多的数据可以合并。

伪代码，假设数组以一个+inf值结尾：

a := *x++
b := *y++
while not finished:
    lo,hi := merge(a,b)
    *z++ := lo
    a := hi
    if *x[0] <= *y[0]:
        b := *x++
    else:
        b := *y++

（注意这与合并的通常标量实现有多么相似）

在实际实现中当然不需要条件跳转：例如，您可以有条件地交换x和y使用xor技巧，然后无条件地读取*x++。

merge本身可以用双调排序来实现。但是如果k低，就会有很多指令间依赖，导致高延迟。根据您必须合并的数组数量，您可以选择足够高的k以便merge屏蔽 的延迟，或者如果可能的话，可以交错几个双向合并。有关详细信息，请参阅论文。

编辑：下图是k = 4 时的图表。所有渐近线都假设k是固定的。

  • 大的灰色框正在合并两个大小为n = m * k的数组（在图片中，m = 3）。

    在此处输入图像描述

    1. 我们对大小为k的块进行操作。
    2. “整体块合并”框通过比较两个数组的第一个元素逐块合并两个数组。这是一个线性时间操作，它不消耗内存，因为我们将数据流式传输到块的其余部分。性能并不重要，因为延迟将受到“merge4”块延迟的限制。
    3. 每个“merge4”框合并两个块，输出下面的k个元素，并将上面的k个元素馈送到下一个“merge4”。每个“merge4”框执行有限数量的操作，“merge4”的数量在n中是线性的。
    4. 所以合并的时间成本在n中是线性的。并且由于“merge4”的延迟比执行 8 次串行非 SIMD 比较低，因此与非 SIMD 合并相比会有很大的加速。

  • 最后，为了扩展我们的 2 路合并以合并许多数组，我们以经典的分而治之的方式排列大灰色框。每个级别的复杂度与元素数量呈线性关系，因此总复杂度为 O( n log ( n / n0 ))，其中n0是排序数组的初始大小，n是最终数组的大小。

    图表

于 2012-07-22T12:01:23.400 回答
1

你可以做一个简单的合并内核来合并 K 个列表：

float *input[K];
float *output;

while (true) {
  float min = *input[0];
  int min_idx = 0;
  for (int i = 1; i < K; i++) {
    float v = *input[i];
    if (v < min) {
      min = v;     // do with cmov
      min_idx = i; // do with cmov
    }
  }
  if (min == SENTINEL) break;
  *output++ = min;
  input[min_idx]++;
}

没有堆，所以很简单。不好的部分是它是 O(NK)，如果 K 很大，这可能会很糟糕（与 O(N log K) 的堆实现不同）。因此，您只需选择一个最大 K（4 或 8 可能很好，然后您可以展开内部循环），并通过级联合并来做更大的 K（通过对列表组进行 8 路合并来处理 K=64，然后结果的8路合并）。

于 2012-07-21T04:34:16.033 回答