multithreading - 如何针对给定的多核架构优化算法

Question

我想知道我应该采用哪些技术来优化给定架构的给定算法。如何使用更好的缓存来提高性能。如何减少缓存一致性或我应该在算法/程序中避免哪些访问模式，以便缓存一致性不会影响我的性能？

我了解一些使用 L1 中最近缓存的数据的标准技术，但是我将如何有效地使用多核上共享缓存(比如 L2)中的数据，从而避免更昂贵的主内存访问？

基本上，我对我应该尝试利用或避免哪些数据访问模式感兴趣，以便更好地映射到我的给定架构。我可以使用什么数据结构，在什么场景下什么架构(具有不同级别的私有(private)缓存和共享缓存)来提高性能。谢谢。

Answer 1

我应该采用哪些技术来优化给定架构的给定算法？

微架构各不相同，因此请了解您的特定处理器的详细信息。英特尔在他们的 optimization guide 中提供了很好的文档。 .如果您使用的是 Intel 处理器，您需要阅读第 8.3 和 8.6 节:

8.3 优化指南
本节总结了调整多线程应用程序的优化指南。列出了五个领域(按重要性排序):

线程同步

公交利用率

内存优化

前端优化

执行资源优化

本节列出了与每个领域相关的实践。在接下来的部分中更深入地讨论了每个领域的指南。大多数编码建议都提高了处理器内核的性能扩展；和扩展由于 HT 技术。仅适用于一种环境的技术被记录下来。

8.6 内存优化

高速缓存的高效操作是内存优化的一个关键方面。缓存的高效运行需要解决以下问题:

缓存阻塞

共享内存优化

消除 64 KB 别名数据访问

防止一级缓存中的过度驱逐

为了更好地映射到给定的体系结构，我应该尝试利用或避免哪些数据访问模式？

漏洞利用

当缓存已满并且缓存中的访问未命中时，缓存必须驱逐某些内容为新数据/代码腾出空间，驱逐的内容通常基于最近最少使用 (LRU) 的近似值。如果可能，那么您的代码应该具有强大的 locality of reference :

尝试将算法中使用的接近时间的数据打包，使其在空间(地址)上接近

压缩数据，当 32 位整数可以时不要使用 64 位整数，例如

有时，“对象”(相关数据)相对于缓存行的对齐很重要。例如，如果有一个对象数组，每个对象为 64 字节并且它们被随机访问，那么在 64 字节边界对齐将通过不引入未使用的数据来提高缓存效率。如果对象没有对齐，那么每个接触的对象都会带来两个缓存行，但只需要 64 字节，所以 50% 的数据传输没有使用(假设缓存行是 64 字节)。

正如@PaulA.Clayton 在评论中指出的那样，预取数据非常重要，因为它隐藏了部分或全部内存延迟。 “此外，利用基于步幅的硬件预取可能非常有益。(软件预取在某些情况下也很有用。)尽早获取指针有助于提高内存级并行性。”

为了方便硬件预取器并提高带入缓存的数据的利用率，请仔细注意矩阵和其他大型结构的存储和访问方式...请参阅 Wikipedia article on row-major order .

避免

你不经常使用的数据不应该靠近你经常使用的数据

避免 false sharing .如果两个或多个线程访问相同的缓存行，但未在缓存行内共享相同的数据，并且其中至少一个是写入者，则您存在错误共享...将有与 cache coherency protocol 相关的不必要的负担和延迟命中。 .

在处理完旧数据之前，尽量不要使用新数据

测量

正如安德烈·亚历山大雷斯库所说 in this talk - 当谈到性能调优时，唯一正确的直觉是“我应该衡量这个”。熟悉缓存性能监控工具，例如:

perf

Cachegrind