LogP模型上一类蝶式计算的通信策略  

COMMUNICATION STRATEGY OF BUTTERFLYCOMPUTATION ON THE LogP MODEL

作　　者：陈国良[1] 许锦波[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系

出　　处：《计算机学报》1997年第8期695-701,共7页Chinese Journal of Computers

基　　金：国家教委博士点基金

摘　　要：本文研究ＬｏｇＰ模型上一类蝶式计算中的通信问题．以ＦＦＴ的并行计算为例，通过仔细安排消息的发送顺序，使得由有限带宽引起的延迟与局部计算重叠，在ｇ－ｌｏｇｇ＋１≤ｌｏｇｐ（ｐ为处理器数，ｇ为带宽因子）的条件下，只要输入长度ｎ满足最基本的要求（ｎ≥２ｐ２），ｇ便被完全隐含于局部计算中，算法时间复杂度可达到最优．最后与文献［１］的结果比较，分析了它们的优缺点及各自的适用范围．This paper discusses communication problem of butterfly computationusing the LogP model of computation. In order to mask communication time causedby bandwidth-limited as much as possible,the authors carefully overlap interprocessor communication steps with local computation, and give FFT algorithm as an example. Analysis shows that the technique is suitable for butterfly computation. Letn22p' and g-logg+1≤logp, the running time of the algorithm is optimal. Finally, the author's result is compared with Sahay's and their adaptabilities are analyzed respectively.

关 键 词：蝶式计算 LOGP模型 通信 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]