algorithm - 缓存友好的离线随机读取

Question

考虑一下C ++中的以下函数：

void foo(uint32_t *a1, uint32_t *a2, uint32_t *b1, uint32_t *b2, uint32_t *o) {
    while (b1 != b2) {
        // assert(0 <= *b1 && *b1 < a2 - a1)
        *o++ = a1[*b1++];
    }
}

其目的应该足够清楚。不幸的是， b1包含随机数据并破坏了缓存，这使 foo成为了我程序的瓶颈。无论如何，我可以对其进行优化吗？

这是一个SSCCE，应类似于我的实际代码：

#include <iostream>
#include <chrono>
#include <algorithm>
#include <numeric>

namespace {
    void foo(uint32_t *a1, uint32_t *a2, uint32_t *b1, uint32_t *b2, uint32_t *o) {
        while (b1 != b2) {
            // assert(0 <= *b1 && *b1 < a2 - a1)
            *o++ = a1[*b1++];
        }
    }

    constexpr unsigned max_n = 1 << 24, max_q = 1 << 24;
    uint32_t data[max_n], index[max_q], result[max_q];
}

int main() {
    uint32_t seed = 0;
    auto rng = [&seed]() { return seed = seed * 9301 + 49297; };
    std::generate_n(data, max_n, rng);
    std::generate_n(index, max_q, [rng]() { return rng() % max_n; });

    auto t1 = std::chrono::high_resolution_clock::now();
    foo(data, data + max_n, index, index + max_q, result);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration<double>(t2 - t1).count() << std::endl;

    uint32_t hash = 0;
    for (unsigned i = 0; i < max_q; i++)
        hash += result[i] ^ (i << 8) ^ i;
    std::cout << hash << std::endl;
}

这不是 Cache-friendly copying of an array with readjustment by known index, gather, scatter，它询问随机写入，并假定 b是排列。

Answer 1

首先，让我们看一下上面代码的实际性能：

$ sudo perf stat ./offline-read
0.123023
1451229184

 Performance counter stats for './offline-read':

        184.661547      task-clock (msec)         #    0.997 CPUs utilized          
                 3      context-switches          #    0.016 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               717      page-faults               #    0.004 M/sec                  
       623,638,834      cycles                    #    3.377 GHz                    
       419,309,952      instructions              #    0.67  insn per cycle         
        70,803,672      branches                  #  383.424 M/sec                  
            16,895      branch-misses             #    0.02% of all branches        

       0.185129552 seconds time elapsed

IPC为0.67，这可能几乎完全是由于DRAM5的负载丢失引起的。让我们确认一下：

sudo ../pmu-tools/ocperf.py stat -e cycles,LLC-load-misses,cycle_activity.stalls_l3_miss ./offline-read
perf stat -e cycles,LLC-load-misses,cpu/event=0xa3,umask=0x6,cmask=6,name=cycle_activity_stalls_l3_miss/ ./offline-read
0.123979
1451229184

 Performance counter stats for './offline-read':

       622,661,371      cycles                                                      
        16,114,063      LLC-load-misses                                             
       368,395,404      cycle_activity_stalls_l3_miss                                   

       0.184045411 seconds time elapsed

因此，在620k中，约有370k周期会因未命中而直接停顿。实际上，在 foo()中以这种方式停顿的那部分周期要高得多，接近90％，因为 perf还在测量init和 accumulate代码，这大约占运行时间的三分之一（但没有L3未命中率）。

这并不是什么意外的事情，因为我们知道随机读取模式 a1[*b1++]基本上将具有零局部性。实际上， LLC-load-misses的数量为1600万，几乎完全对应于 a1 .2的1600万随机读取。

如果仅假设 foo()的100％花费在等待内存访问上，则可以了解每次未命中的总成本： 0.123 sec / 16,114,063 misses == 7.63 ns/miss。在我的盒子上，在最佳情况下，内存延迟大约为60 ns，因此每次未命中少于8 ns意味着我们已经在提取很多内存级并行性（MLP）：大约8个未命中必须重叠，并且-平均而言就可以实现这一目标（甚至完全忽略了 b1的流负载和 o的流写入带来的额外流量）。

因此，我认为您可以对简单循环进行许多调整以使其做得更好。尽管如此，两种可能性是：


如果平台支持，则将非临时性存储用于写入 o。这将消除 RFO对常规存储的隐含读取。因为 o再也不会被读取（在定时部分内！），这应该是直接的胜利。
软件预取。仔细调整 a1或 b1的预取可能会有所帮助。但是，由于我们已经接近如上所述的MLP限制，因此影响将是相当有限的。另外，我们希望 b1的线性读取几乎可以完全由硬件预取器预取。 a1的随机读取似乎可以进行预取，但是实际上，循环中的ILP通过无序处理（至少在像最近的x86这样的大型OoO处理器上）会导致足够的MLP。

用户harold在评论中已经提到他尝试预取的效果很小。


因此，由于简单的调整不太可能取得成果，因此您需要转换循环。一种“显而易见的”转换是对索引 b1进行排序（以及索引元素的原始位置），然后按排序顺序从 a1进行读取。这将 a1的读取从完全随机转换为几乎3个线性，但现在写入都是随机的，这再好不过了。

排序然后取消排序

关键问题是在 a1的控制下 b1的读取是随机的，而 a1很大，因此每次读取都会导致DRAM丢失。我们可以通过对 b1进行排序，然后读取 a1来解决此问题，以获得排列结果。现在，您需要“取消置换”结果 a1以获得最终顺序的结果，这只是另一种形式，这次是在“输出索引”上。

这是一个使用给定的输入数组 a，索引数组 b和输出数组 o和 i的工作示例，其中 b是每个元素的（隐式）位置：

  i =   0   1   2   3
  a = [00, 10, 20, 30]
  b = [ 3,  1,  0,  1]
  o = [30, 10, 00, 10] (desired result)

首先，对数组 i进行排序，将原始数组位置 (b[0], 0), (b[1], 1), ...作为辅助数据（或者，您可能将其视为排序元组 b），这将为您提供排序后的 b'数组 i'和排序后的索引列表 o'如下所示：

  i' = [ 2, 1, 3, 0]
  b' = [ 0, 1, 1, 3]

现在，您可以在 a的控制下从 b'读取排列的结果数组 memcpy。严格按顺序增加此读取，并且应该能够以接近 o'的速度运行。实际上，您可能可以利用宽范围的连续SIMD读取和一些改组来进行几次读取，然后一次将4字节的元素移到正确的位置（复制某些元素而跳过其他元素）：

  a  = [00, 10, 20, 30]
  b' = [ 0,  1,  1,  3]
  o' = [00, 10, 10, 30]

最后，从概念上简单地通过对排列后的索引 o排序 o'来取消对 i'的置换以获得 b：

  i' = [ 2,  1,  3,  0]
  o' = [00, 10, 10, 30]
  i  = [ 0,  1,  2,  3]
  o  = [30, 10, 00, 10]

完蛋了！

现在，这是该技术的最简单概念，并且并不是特别适合缓存（每次传递在概念上都迭代一个或多个2 ^ 26字节数组），但它至少会完全使用它读取的每个缓存行（与原始循环不同）只能从缓存行中读取单个元素，这就是为什么即使数据仅占用一百万个缓存行也有1600万次未命中的原因！）。所有读取或多或少是线性的，因此硬件预取将有很大帮助。

您获得多少加速可能很大取决于您将如何实现排序：它们需要快速并且对缓存敏感。几乎可以肯定，某种类型的可识别缓存的基数排序将最有效。

以下是一些有关进一步改进此方法的注意事项：

优化排序量

您实际上不需要完全对 a进行排序。您只想对其进行“足够的”排序，以使在 b'的控制下对 0, 1, 3, 2, 5, 4, 6, 7的后续读取或多或少是线性的。例如，高速缓存行中可容纳16个元素，因此根本不需要基于最后4位进行排序：无论如何，都将读取相同的线性高速缓存行序列。您还可以对更少的位进行排序：例如，如果忽略了5个最低有效位，则将以“几乎线性”的方式读取高速缓存行，有时会从完全线性的模式中交换两条高速缓存行，例如： b 。在这里，您仍将获得L1高速缓存的全部好处（随后对高速缓存行的读取将始终有效），而且我怀疑这样的模式仍会被良好地预取，如果不能，则始终可以通过软件预取来帮助它。

您可以在系统上测试忽略比特的最佳数量。忽略位有两个好处：


在基数搜索中要做的工作更少，或者需要的遍数更少，或者一次或多次遍中需要更少的存储桶（这有助于缓存）。
在最后一步中“撤消”排列的工作量可能更少：如果通过检查原始索引数组 a来撤消，则忽略位意味着在撤消搜索时您将获得相同的节省。


缓存阻止工作

上面的描述以几个顺序的，不相交的过程列出了所有内容，每个过程都对整个数据集起作用。在实践中，您可能希望对它们进行交错以获得更好的缓存行为。例如，假设您使用MSD radix-256排序，则可以进行第一遍，将数据排序到256个存储桶中，每个存储桶中大约有256K个元素。

然后，您可以只对前几个（或前几个）存储桶进行排序，而不是进行完整的第二遍处理，然后根据生成的 b'块继续读取 o'。您可以确保此块是连续的（即，最后排序的序列的后缀），因此您不会在读取中放弃任何局部性，并且通常会缓存您的读取。由于 o'的块在高速缓存中也很热，因此您也可以进行第一次置换 o'的过程（也许您可以将后两个阶段组合成一个循环）。

智能置换

优化的领域之一是 i的去置换是如何实现的。在上面的描述中，我们假设一些索引数组 [0, 1, 2, ..., max_q]最初的值是 b，并与 i一起排序。从概念上讲，它是如何工作的，但是您可能不需要立即实际实现 i并将其作为辅助数据进行排序。例如，在基数排序的第一遍中， b的值是隐式已知的（因为您正在遍历数据），因此可以为free4计算它并在第一遍中将其写出，而无需出现所有内容排序顺序。

进行“非排序”操作可能比保持完整索引更有效。例如，原始未排序的 max_n数组从概念上讲具有执行取消排序所需的所有信息，但是我很清楚如何使用它来有效地进行排序。

会更快吗？

那么，这实际上会比幼稚的方法快吗？它在很大程度上取决于实现细节，特别是包括实现的排序效率。在我的硬件上，幼稚的方法每秒处理约1.4亿个元素。可以识别缓存的基数种类的在线描述似乎从200到6亿个元素/秒不等，并且由于您需要其中两个，因此，如果您相信这些数字，则实现大幅提速的机会似乎就很有限。另一方面，这些数字来自较旧的硬件，并且用于更一般的搜索（例如，对于密钥的所有32位，而我们可能只能使用16位）。

只有仔细的实施才能确定它是否可行，并且可行性还取决于硬件。例如，在不能支持那么多MLP的硬件上，排序-不排序方法变得相对更有利。

最佳方法还取决于 max_q和 max_n >> max_q的相对值。例如，如果使用 max_n << max_q，则即使具有最佳排序，读取结果也将是“稀疏”的，因此，幼稚的方法会更好。另一方面，如果 foo()，则通常将多次读取同一索引，因此排序方法将具有良好的读取位置，排序步骤本身将具有更好的位置，并且可能有可能进一步进行优化以显式处理重复读取。

多核

从这个问题尚不清楚您是否对并行化感兴趣。 a的幼稚解决方案确实已经接受了“直接”并行化，其中您只需将 b和 LLC-load-misses数组划分为相等大小的块，并为每个线程分配，这似乎可以提供完美的加速。不幸的是，您可能会发现比线性缩放更糟，因为您将遇到内存控制器中的资源争用以及套接字上所有内核之间共享的相关非核心/非核心资源。因此，当您添加更多核心时，尚不清楚纯粹并行并行读取加载到内存将获得多少吞吐量6。

对于基数排序版本，大多数瓶颈（存储吞吐量，总指令吞吐量）都在内核中，因此我希望它可以随着其他内核而合理扩展。正如Peter在评论中提到的那样，如果您使用超线程，则排序可能在核心本地L1和L2缓存中具有良好局部性的额外好处，可有效地使每个同级线程使用整个缓存，而不是将有效容量减少一半。当然，这涉及到仔细管理线程的亲和力，以便同级线程实际使用附近的数据，而不仅仅是让调度程序执行它的工作。



1您可能会问为什么 b1没有说32或4,800万，因为我们还必须读取 accumulate()的所有1600万个元素，然后 result调用读取所有的 LLC-load-misses。答案是 a1仅计算L3中实际未命中的需求未命中。上面提到的其他读取模式完全是线性的，因此预取器将始终在需要时将线引入L3。根据perf使用的定义，这些不算作“ LLC未命中”。

2您可能想知道我是怎么知道所有未命中的负载都来自 foo中的 perf record读取：我只是使用 perf mem和 b1来确认这些不命中来自预期的汇编指令。

3几乎线性，因为 i并非所有索引的排列，因此原则上可以跳过和重复索引。但是，在高速缓存行级别，很有可能会按顺序读取每条高速缓存行，因为每个元素被包含的机率约为63％，并且高速缓存行有16个4字节元素，因此只有任何给定的缓存具有零元素的概率约为1千万分之一。因此，在高速缓存行级别上起作用的预取将正常工作。

4这里我的意思是价值的计算是免费的或接近免费的，但是当然写仍然要花钱。但是，这仍然比“前期实现”方法好得多，该方法首先创建需要 [0, 1, 2, ...]写入的 max_q数组 max_q，然后再次需要另一个 foo()写入以将其按第一个基数排序通过。隐式实现仅导致第二次写入。

5实际上，实际计时段 的IPC较低：根据我的计算，约为0.15。整个过程的报告IPC是定时段IPC以及初始化和累积代码之前和之后的IPC的平均值，IPC更高。

6值得注意的是，这与依赖负载延迟绑定工作流的扩展方式不同：正在执行随机读取但只能进行一个负载的负载，因为每个负载都取决于最后的结果，因此非常好地扩展到多个内核，因为负载的串行性质不会使用很多下游资源（但是，即使在单个内核上，也可以通过更改内核循环以并行处理多个相关的负载流来加快此类负载的速度）。