我已经阅读了很多关于Cache Oblivious算法和Streaming树等相关内容。我理解了基本概念，但我仍然不明白它们为什么对并行编程有好处？我记得John Harrop说过这些算法在这方面是革命性的。
3个回答
8
在这篇文章中http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms, 作者指出，缓存无关算法的思想是高效利用处理器缓存和降低内存带宽需求。对于单线程算法来说，这两个方面同等重要，但对于并行算法来说尤其关键，因为可用内存带宽通常在硬件线程之间共享，并经常成为可扩展性的瓶颈。
访问内存可能成为并行算法的瓶颈，因此具有试图利用缓存内存的算法可以更有效率。在同一篇文章中，他们继续描述了缓存无关算法如何利用可用缓存：缓存无关算法通过递归地将问题数据集分成较小的部分，然后尽可能多地计算每个部分。最终，子问题数据集适合于缓存中，我们可以在不访问内存的情况下对其进行大量计算。
访问内存可能成为并行算法的瓶颈，因此具有试图利用缓存内存的算法可以更有效率。在同一篇文章中，他们继续描述了缓存无关算法如何利用可用缓存：缓存无关算法通过递归地将问题数据集分成较小的部分，然后尽可能多地计算每个部分。最终，子问题数据集适合于缓存中，我们可以在不访问内存的情况下对其进行大量计算。
- ditkin
5
我只想指出你的问题在多核架构中尤其重要，其中多个处理器拥有自己的私有缓存和在几个核之间共享的缓存。为了实现高效率和可伸缩性，并行算法必须在数据缓存中表现出良好的空间局部性和时间局部性。
在Harald Prokop的硕士论文之前，算法和数据结构是以缓存感知的方式设计的，以减少缓存未命中的比率，例如B树是缓存感知数据结构的一个著名例子，其中参数B通过使用CPU缓存大小进行调整。在缓存无关模型中，由于算法的递归性质，子问题最终适合缓存，并且操作这些子问题会产生少量的缓存未命中。
一些缓存无关算法的优点独立于CPU缓存大小，适用于任何内存层次结构，并被证明在缓存复杂性方面是最优的。随着多核并行技术的兴起，缓存无关算法可能在推导出高性能并行程序方面发挥重要作用。我也看到了以下文章中有关递归数据结构和缓存无关算法的有趣讨论 http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx。
在Harald Prokop的硕士论文之前，算法和数据结构是以缓存感知的方式设计的，以减少缓存未命中的比率，例如B树是缓存感知数据结构的一个著名例子，其中参数B通过使用CPU缓存大小进行调整。在缓存无关模型中，由于算法的递归性质，子问题最终适合缓存，并且操作这些子问题会产生少量的缓存未命中。
一些缓存无关算法的优点独立于CPU缓存大小，适用于任何内存层次结构，并被证明在缓存复杂性方面是最优的。随着多核并行技术的兴起，缓存无关算法可能在推导出高性能并行程序方面发挥重要作用。我也看到了以下文章中有关递归数据结构和缓存无关算法的有趣讨论 http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx。
- pad
4
多核处理器每个核心的缓存要少一些。专用单核处理器中的缓存占据硅上的大量空间。你可以通过谷歌图片搜索自己看到，你会发现缓存大小很大，例如：http://www.bit-tech.net/hardware/memory/2007/11/15/the_secrets_of_pc_memory_part_1/2
因此，如果你有20个核心，它们每个都只有一个普通处理器1/20的缓存，你最好希望你的算法在没有巨大缓存的情况下表现良好。=)
- ninjagecko
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接