众所周知,当使用几个处理器作为问题的每个分区完全适合时,由于高速缓存效应,可以出现超线性加速,与将换入和换出若干次的顺序算法相比,加速了存储器事务。我已经看到了几十个例子,对于并行部分,其背后的逻辑非常清晰,并得到了很好的解释。
然而,每次他们与顺序算法进行比较时,顺序算法都是一个非常幼稚的解决方案,具有从0...N开始的大循环。
是否考虑过顺序解决方案可以与并行解决方案做同样的事情??(即对问题进行分区,并按顺序解决每个分区,以使其适合缓存)。换句话说,只需在一个线程中运行并行解决方案。通过这样做,可以预期线性加速,而不是最初认为的超线性。
我在这里错过了什么?对于一个已经存在了几十年的概念来说,这种反逻辑似乎太简单了。
这个问题是在一位老师告诉我“超线性加速是不可能的,你总是可以改进顺序加速,以便再次有线性加速”之后提出的。我不能证明相反的情况。
发布于 2014-06-23 22:31:46
超线性加速可能来自这样一个事实:不仅处理器的数量增加了,而且高速缓存的数量也增加了。顺序情况下拆分数据的方法不会增加高速缓存。
https://stackoverflow.com/questions/13235543
复制相似问题