如何优化给定多核体系结构的算法

Question

我想知道我应该查找哪些技术-为给定的体系结构优化给定的算法。如何使用更好的缓存来提高性能。如何减少缓存一致性，或者在算法/程序中应避免哪些访问模式，从而使缓存一致性不影响我的性能？

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

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

Answer 1

我应该查找哪些技术来为给定的架构优化给定的算法？

微体系结构各不相同，因此了解具体处理器的细节。英特尔在他们的优化指南中提供了很好的文档。如果您使用的是Intel处理器，您需要阅读8.3和8.6节：

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

• 线程同步
• 总线利用率
• 内存优化
• 前端优化
• 执行资源优化

本节列出了与每个领域相关的实践。每个领域的指导方针将在下面的章节中进行更深入的讨论。大多数编码建议都提高了处理器核心的性能扩展，并且由于HT技术的应用而进行了扩展。注意到只适用于一种环境的技术。

8.6内存优化

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

• 缓存阻塞
• 共享内存优化
• 消除64-KByte别名数据访问
• 防止一级缓存中的过度驱逐

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

利用

当缓存已满且缓存中的访问丢失时，缓存必须为新的数据/代码腾出空间，被逐出的通常是基于最近使用最少的(LRU)的近似值。如果可能的话，那么您的代码应该具有强参考地点。

• 尝试将算法中在时间上使用接近的数据打包，使其在空间(地址)上接近。
• 严格打包数据，例如，当32位整数完成时，不要使用64位整数。
• 有时，“对象”(相关数据)相对于缓存行的对齐很重要。例如，如果每个64字节的对象都有一个数组，并且它们被随机访问，那么在64字节的边界对齐将提高缓存效率，因为不引入未使用的数据。如果对象没有对齐，那么每个接触的对象都会引入两条缓存行，但只需要64字节，因此不使用传输的数据的50% (假设缓存行为64字节)。
• 正如@PaulA.Clayton在注释中指出的那样，预取数据非常重要，因为它隐藏了部分或全部内存延迟。“此外，利用基于步长的硬件预取可能非常有益。(软件预取在某些情况下也很有用。)尽早获取指针有助于提高内存级并行性。”
• 为了方便硬件预取程序和提高缓存中数据的利用率，请注意矩阵和其他大型结构是如何存储和访问的。见维基百科上的文章-主要订购。

避免

• 不经常使用的数据不应该接近经常使用的数据
• 避免虚假共享。如果两个或多个线程访问相同的缓存行，但在高速缓存行中没有共享相同的数据，并且其中至少有一个线程是写入器，则存在错误共享.与缓存一致性协议相关的负担和延迟都是不必要的。
• 在处理完旧数据之前，不要使用新数据。

测度

正如Alexandrescu所说，在这次演讲中 --当谈到性能调优时，唯一正确的直觉是“我应该测量这一点”。熟悉缓存性能监视工具，例如：

• perf
• 卡舍尔

Answer 2

关键原则是局部性:当您有选择时，首先处理附近的数据(避免稀疏访问)，并尽快执行数据重用(对相同数据重新分组)。

对于多线程程序，原则是独立的:确保线程在不相交的数据集上工作(使用不同的副本是必要的/可能的)。

除非您有很好的理由这样做，否则请远离硬件的特性。

Answer 3

应该指出，代码也是以与数据相同的方式缓存的。具有大量内联和很少跳转/调用的小而密集的代码将减轻L1C缓存的压力，并最终在与数据获取发生冲突的地方产生L2、L3和RAM。

如果您正在使用超线程，那么似乎有证据表明，在内核中的两个超线程上，一个较低的优化级别(O1)将比单个高度优化的线程(O2和更高的线程)完成更多的工作。