论文部分内容阅读
本文研究LogP模型上一类蝶式计算中的通信问题。以FFT的并行计算为例,通过仔细安排消息的发送顺序,使得由有限带宽引起的延迟与局部计算重叠,在g-logg+1≤logp(p为处理器数,g为带宽因子)的条件下,只要输入长度n满足最基本的要求(n≥2p^2),g便被完全隐含于局部计算中,算法时间复杂度可达到最优。最后与文献[1]的结果比较,分析了它们的优缺点及各自的适用范围。