algorithm - 用于并行编程的缓存不经意算法？

Question

我已经阅读了很多关于缓存不经意算法和流式树等的内容。我了解基础知识，但我仍然无法理解为什么它们适用于并行编程？我想我看到 John Harrop 说他们在这方面是革命性的。

Answer 1

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

他们指出

The idea behind cache-oblivious algorithms is efficient usage of processor caches and reduction of memory bandwidth requirements. Both things are equally important for single-threaded algorithms, but especially crucial for parallel algorithms, because available memory bandwidth is usually shared between hardware threads and frequently becomes a bottleneck for scalability.

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

在同一篇文章中，他们继续描述无缓存算法如何利用可用的缓存:

Cache-oblivious algorithms work by recursively dividing a problem's dataset into smaller parts and then doing as much computations of each part as possible. Eventually subproblem dataset fits into cache, and we can do significant amount of computations on it without accessing memory