use*_*842 11 algorithm concurrency cache-oblivious
我已经阅读了很多关于Cache Oblivious Algorithms和Streaming树等的内容.我理解我仍然无法看到的基础知识是什么它们对并行编程有好处？我想我看到John Harrop说他们是革命性的.
在文章 http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms中
他们指出了这一点
缓存遗忘算法背后的想法是有效使用处理器缓存和减少内存带宽要求.这两者对于单线程算法同样重要,但对于并行算法尤为重要,因为可用内存带宽通常在硬件线程之间共享,并且经常成为可伸缩性的瓶颈.
访问内存可能是并行算法的瓶颈,因此使用尝试利用缓存内存的算法可能更有效.
在同一篇文章中,他们继续描述缓存遗忘算法如何利用可用的缓存:
缓存无关的算法通过递归地将问题的数据集划分为更小的部分,然后对每个部分进行尽可能多的计算来工作.最终子问题数据集适合缓存,我们可以在其上进行大量计算而无需访问内存
我只是想指出,您的问题在多核架构中尤为重要,因为多核处理器在多个核心之间拥有自己的私有缓存和共享缓存.为了能够实现高效率和可伸缩性,并行算法必须在数据高速缓存中展示良好的空间局部性和时间局部性.
前哈拉尔德普罗科普的硕士论文,算法和数据结构被设计在一个高速缓存感知(缓存意识)的方式来降低高速缓存未命中的比例,例如,B-树是高速缓存感知的数据结构的一个众所周知的例子中其中参数B使用CPU缓存大小进行调整.在缓存忘却模型,由于算法的递归特性,子问题最终适应高速缓存和操纵这样子问题招致少数高速缓存未命中的.
缓存遗忘算法的一些不错的属性独立于CPU缓存大小,在任何内存层次结构上运行良好,并证明在缓存复杂性方面是最佳的.随着多核并行性的兴起,缓存无关的算法可能在导出高性能并行程序中发挥重要作用.我还在下面的文章http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx中看到了一些关于递归数据结构和缓存遗忘算法的有趣讨论..