Jak*_* M. 11 theory algorithm parallel-processing performance
一个理论问题,也许很明显:
在以N个线程的并行方式实现后,算法的执行速度是否比原始的单线程算法快N倍？换句话说,增益是否可以更好地与线程数线性相关？
Jer*_*fin 11
这种情况并不常见,但最有可能.
例如,考虑构建一个软件管道,其中管道中的每个步骤执行相当少量的计算,但需要足够的静态数据来大致填充整个数据缓存 - 但每个步骤使用不同的静态数据.
在这种情况下,单个处理器上的串行计算通常主要受到主存储器带宽的限制.假设您(至少)有多个处理器/核心(每个都有自己的数据缓存)作为管道步骤,您可以加载每个数据缓存一次,然后处理一个接一个的数据包,为所有这些数据保留相同的静态数据.现在,您的计算可以以处理器的速度进行,而不是受到主存储器带宽的限制,因此速度提升很容易比线程数大10倍.
从理论上讲,你可以用一个只有一个非常大的缓存的单个处理器来完成相同的工作.但是,从实际的角度来看,处理器和高速缓存大小的选择相当有限,因此如果要使用更多高速缓存,则需要使用更多处理器 - 大多数系统提供的方法都是使用多个线程.
是.
我看到了一种算法,用于移动机器人手臂,通过复杂的操作,基本上分成N个线程,让每个线程或多或少地随机移动通过解空间.(这不是一个实用的算法.)统计数据清楚地显示了一个线程的超线性加速.显然,随着时间的推移,一个解决方案的概率上升得相当快,然后平了一些,所以优势在于有很多初始尝试.