如何针对给定的多核架构优化算法
How to optimize an algorithm for a given multi-core architecture
我想知道我应该研究哪些技术来优化给定体系结构的给定算法。如何使用更好的缓存来提高性能。如何降低缓存一致性或我应该在我的 algorithm/program 中避免哪些访问模式，以便缓存一致性不会影响我的性能？
我了解一些在 L1 中使用最近缓存的数据的标准技术，但我如何有效地在多核上使用共享缓存（比如 L2）中的数据，从而避免主内存访问，这甚至是更贵？
基本上，我感兴趣的是我应该尝试利用或避免哪些数据访问模式，以便更好地映射到我给定的体系结构。我可以使用什么数据结构，在什么场景下使用什么架构（具有不同级别的私有缓存和共享缓存）来提高性能。谢谢。
我应该学习哪些技术来优化给定架构的给定算法？
微体系结构各不相同，因此请了解您的特定处理器的详细信息。英特尔在其 optimization guide 中提供了很好的文档。如果您使用的是 Intel 处理器，则需要阅读第 8.3 和 8.6 节：
8.3 优化指南
本节总结了用于调整多线程应用程序的优化指南。列出了五个领域（按重要性排序）：
- 线程同步
- 公交车利用率
- 内存优化
- 前端优化
- 执行资源优化
本节列出了与每个领域相关的实践。每个领域的指导方针将在接下来的章节中进行更深入的讨论。大多数编码建议提高了处理器内核的性能扩展；和缩放由于 HT 技术。仅适用于一种环境的技术已注明。
8.6 内存优化
缓存的高效运行是内存优化的一个重要方面。缓存的高效运行需要解决以下问题：
- 缓存阻塞
- 共享内存优化
- 消除 64 KB 别名数据访问
- 防止一级缓存中的过度逐出
为了更好地映射到我给定的体系结构，我应该尝试利用或避免哪些数据访问模式？
利用
当缓存已满并且缓存中的访问未命中时，缓存必须逐出某些内容以为新内容腾出空间data/code，逐出的内容通常基于最近最少使用 (LRU) 的近似值.如果可能，那么您的代码应该具有强大的 locality of reference:
- 尝试打包在算法中及时使用的数据，使其在space（地址）
中接近
- 将数据紧密打包，不要使用 64 位整数，而 32 位整数就可以，例如
- 有时 "object"（相关数据）相对于缓存行的对齐很重要。例如，如果有一个对象数组，每个对象都是 64 字节，并且它们是随机访问的，那么在 64 字节边界对齐将通过不引入未使用的数据来提高缓存效率。如果对象未对齐，则每个接触的对象都会引入两个缓存行，但只需要 64 字节，因此不会使用 50% 的传输数据（假设缓存行为 64 字节）。
- 正如@PaulA.Clayton在评论中指出的那样，预取数据非常重要，因为它隐藏了部分或全部内存延迟。 “此外，利用基于步幅的硬件预取可能非常有益。（软件预取在某些情况下也很有用。）尽早获取指针有助于提高内存级并行性。”
- 为了便于硬件预取并提高带入缓存的数据的利用率，请特别注意矩阵和其他大型结构的存储和访问方式...参见 Wikipedia article on row-major order.
避免
- 不经常使用的数据不应与经常使用的数据接近
- 避免false sharing. If two or more threads access the same cache line but are not sharing the same data within the cache line and at least one of them is a writer you have false sharing... there will be unnecessary burden and latency hit associated with cache coherency protocol.
- 在用完旧数据之前尽量不要使用新数据
测量
正如 Andrei Alexandrescu 所说 in this talk - 在性能调优方面，唯一正确的直觉是 "I should measure this." 熟悉缓存性能监控工具，例如：
关键原则是局部性：当您有选择时，首先处理附近的数据（避免稀疏访问），并尽快执行数据重用（重新组合相同数据的连续传递）。
对于多线程程序，原则是局部分离：确保线程在不相交的数据集上工作（使用不同的副本是necessary/possible）。
除非您有充分的理由这样做，否则请远离硬件的特殊性。
应该提到的是，代码也以与数据相同的方式缓存。具有大量内联和少量 jumps/calls 的小而密集的代码将减轻 L1C 缓存的压力，并最终减轻 L2、L3 和 RAM 的压力，这些地方会与数据获取发生冲突。
如果您正在使用超线程，似乎有证据表明，与单个高度优化（O2 和更高）的线程相比，内核中两个超线程的较低优化级别 (O1) 总体上完成的工作更多。
我想知道我应该研究哪些技术来优化给定体系结构的给定算法。如何使用更好的缓存来提高性能。如何降低缓存一致性或我应该在我的 algorithm/program 中避免哪些访问模式，以便缓存一致性不会影响我的性能？
我了解一些在 L1 中使用最近缓存的数据的标准技术，但我如何有效地在多核上使用共享缓存（比如 L2）中的数据，从而避免主内存访问，这甚至是更贵？
基本上，我感兴趣的是我应该尝试利用或避免哪些数据访问模式，以便更好地映射到我给定的体系结构。我可以使用什么数据结构，在什么场景下使用什么架构（具有不同级别的私有缓存和共享缓存）来提高性能。谢谢。
我应该学习哪些技术来优化给定架构的给定算法？
微体系结构各不相同，因此请了解您的特定处理器的详细信息。英特尔在其 optimization guide 中提供了很好的文档。如果您使用的是 Intel 处理器，则需要阅读第 8.3 和 8.6 节：
8.3 优化指南 本节总结了用于调整多线程应用程序的优化指南。列出了五个领域（按重要性排序）：
- 线程同步
- 公交车利用率
- 内存优化
- 前端优化
- 执行资源优化
本节列出了与每个领域相关的实践。每个领域的指导方针将在接下来的章节中进行更深入的讨论。大多数编码建议提高了处理器内核的性能扩展；和缩放由于 HT 技术。仅适用于一种环境的技术已注明。
8.6 内存优化
缓存的高效运行是内存优化的一个重要方面。缓存的高效运行需要解决以下问题：
- 缓存阻塞
- 共享内存优化
- 消除 64 KB 别名数据访问
- 防止一级缓存中的过度逐出
为了更好地映射到我给定的体系结构，我应该尝试利用或避免哪些数据访问模式？
利用
当缓存已满并且缓存中的访问未命中时，缓存必须逐出某些内容以为新内容腾出空间data/code，逐出的内容通常基于最近最少使用 (LRU) 的近似值.如果可能，那么您的代码应该具有强大的 locality of reference:
- 尝试打包在算法中及时使用的数据，使其在space（地址） 中接近
- 将数据紧密打包，不要使用 64 位整数，而 32 位整数就可以，例如
- 有时 "object"（相关数据）相对于缓存行的对齐很重要。例如，如果有一个对象数组，每个对象都是 64 字节，并且它们是随机访问的，那么在 64 字节边界对齐将通过不引入未使用的数据来提高缓存效率。如果对象未对齐，则每个接触的对象都会引入两个缓存行，但只需要 64 字节，因此不会使用 50% 的传输数据（假设缓存行为 64 字节）。
- 正如@PaulA.Clayton在评论中指出的那样，预取数据非常重要，因为它隐藏了部分或全部内存延迟。 “此外，利用基于步幅的硬件预取可能非常有益。（软件预取在某些情况下也很有用。）尽早获取指针有助于提高内存级并行性。”
- 为了便于硬件预取并提高带入缓存的数据的利用率，请特别注意矩阵和其他大型结构的存储和访问方式...参见 Wikipedia article on row-major order.
避免
- 不经常使用的数据不应与经常使用的数据接近
- 避免false sharing. If two or more threads access the same cache line but are not sharing the same data within the cache line and at least one of them is a writer you have false sharing... there will be unnecessary burden and latency hit associated with cache coherency protocol.
- 在用完旧数据之前尽量不要使用新数据
测量
正如 Andrei Alexandrescu 所说 in this talk - 在性能调优方面，唯一正确的直觉是 "I should measure this." 熟悉缓存性能监控工具，例如：
关键原则是局部性：当您有选择时，首先处理附近的数据（避免稀疏访问），并尽快执行数据重用（重新组合相同数据的连续传递）。
对于多线程程序，原则是局部分离：确保线程在不相交的数据集上工作（使用不同的副本是necessary/possible）。
除非您有充分的理由这样做，否则请远离硬件的特殊性。
应该提到的是，代码也以与数据相同的方式缓存。具有大量内联和少量 jumps/calls 的小而密集的代码将减轻 L1C 缓存的压力，并最终减轻 L2、L3 和 RAM 的压力，这些地方会与数据获取发生冲突。
如果您正在使用超线程，似乎有证据表明，与单个高度优化（O2 和更高）的线程相比，内核中两个超线程的较低优化级别 (O1) 总体上完成的工作更多。