11

我已经阅读了很多关于 Cache Oblivious Algorithms 和 Streaming trees 等的内容。我了解了我仍然无法看到的基础知识，为什么它们对并行编程有好处？我想我看到约翰哈罗普说他们是革命性的。

4

3 回答 3

8

在文章 http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms

他们指出

cache-oblivious 算法背后的想法是高效使用处理器缓存和减少内存带宽需求。这两件事对于单线程算法同样重要，但对于并行算法尤其重要，因为可用内存带宽通常在硬件线程之间共享，并且经常成为可扩展性的瓶颈。

对内存的访问可能是并行算法的瓶颈，因此尝试利用缓存内存的算法可能更有效。

在同一篇文章中，他们继续描述缓存遗忘算法如何利用可用缓存：

缓存遗忘算法通过递归地将问题的数据集划分为更小的部分，然后对每个部分进行尽可能多的计算来工作。最终子问题数据集适合缓存，我们可以在不访问内存的情况下对其进行大量计算

于 2011-05-08T11:30:28.377 回答
5

我只想指出，您的问题在多核架构中尤为重要，在这种架构中，多个处理器拥有自己的私有缓存和多个内核之间的共享缓存。为了能够实现高效率和可扩展性，并行算法必须在数据缓存中表现出良好的空间局部性和时间局部性。

在Harald Prokop 的硕士论文之前，算法和数据结构都是以缓存感知（cache-conscious）的方式设计的，以降低缓存未命中率，例如，B-tree 就是众所周知的缓存感知数据结构示例其中参数 B 通过使用 CPU 缓存大小进行调整。在缓存遗忘模型中，由于算法的递归性质，子问题最终适合缓存，并且操作此类子问题会导致少量缓存未命中。

cache-oblivious 算法的一些不错的属性独立于 CPU 缓存大小，在任何内存层次结构上都可以很好地工作，并且被证明在缓存复杂性方面是最佳的。随着多核并行性的兴起，不考虑缓存的算法可能在派生高性能并行程序方面发挥重要作用。我还在以下文章http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx中看到了一些关于递归数据结构和缓存遗忘算法的有趣讨论.

于 2011-05-09T13:01:58.207 回答
4

多核处理器每个内核的缓存较少。专用单核处理器中的缓存占用了硅片上的大量空间。你可以通过谷歌图片搜索自己看到；您会发现缓存大小很大，例如http://www.bit-tech.net/hardware/memory/2007/11/15/the_secrets_of_pc_memory_part_1/2

因此，如果您有 20 个内核，并且每个内核的缓存是普通处理器的 1/20，那么您最好希望您的算法在没有巨大缓存的情况下运行良好。=)

于 2011-05-08T11:25:18.013 回答