超线性加速比从何而来？
在并行计算中，理论上超线性加速是不可能的。但在实践中我们确实看到这样的例子。 一个原因是缓存效应，但我无法理解它的作用。此外，还涉及其他事情，但它们是什么？总之，
如何实现超线性加速？
我是并行计算方面的初学者。
In parallel computing theoretically super-linear speedup is not possible. But in practice we do see such cases. One reason is cache effect but I fail to understand what does it play. Also, there are other things involved but what are they? In summary,
How are super-linear speedups possible?
I'm a beginner with respect to parallel computing.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
假设您有一台 8 处理器机器，每个处理器有 1MB 缓存，并且您的计算使用 6MB 数据。
在 1 个处理器上，计算将在 CPU、高速缓存和 RAM 之间进行大量数据移动。在 8 个处理器上，计算只需在 CPU 和缓存之间移动数据。这样你就可以实现超线性加速。
这些数字和分析已经过简化，以便为初学者进行说明。
Suppose you have an 8 processor machine, each processor has a 1MB cache, and your computation uses 6MB of data.
On 1 processor the computation will be doing a lot of data movement between CPU, cache and RAM. On 8 processors the computation will only have to move data between CPU and cache. This way you can achieve super-linear speedup.
These figures and this analysis have been simplified for exposition for a beginner.
简而言之，当处理器执行的总工作量严格小于单个处理器执行的总工作量时，即可实现超线性加速。
这可以通过三种方式发生：
原始的顺序算法非常糟糕，在一个处理器上使用算法的并行版本通常会消除超线性加速。
并行算法使用一些搜索，例如随机行走，正在行走的处理器越多，在到达您要查找的内容之前总共需要行走的距离就越短。
现代处理器具有更快和更慢的内存。通常，它会尝试将您正在使用的数据保留在快速内存中。我们可以有把握地说您的数据量大于快速内存的量。如果您使用 n 个处理器，那么您将拥有 n 倍更快的内存。快速内存可容纳更多数据，从而可以在同一任务上花费更少的时间（从而减少工作量）。
In short, superlinear speedup is achieved when the total amount of work processors do is strictly less than the total work performed by a single processor.
This can happen in three ways:
The original sequential algorithm was really bad, using the parallel version of the algorithm on one processor will usually do away with the superlinear speedup.
The parallel algorithm uses some search like a random walk, the more processors that are walking, the less distance has to be walked in total before you reach what you are looking for.
Modern processors have faster and slower memories. Typically it will try to keep the data you are using in the fast memory. We can safely say your amount of data is larger than the amount of fast memory. If you use n processors you have n times the amount of faster memory. More data fits in the fast memory which makes it possible to take less time (thus amount of work) on the same task.