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

本文研究ＬｏｇＰ模型上一类蝶式计算中的通信问题．以ＦＦＴ的并行计算为例，通过仔细安排消息的发送顺序，使得由有限带宽引起的延迟与局部计算重叠，在ｇ－ｌｏｇｇ＋１≤ｌｏｇｐ（ｐ为处理器数，ｇ为带宽因子）的条件下，只要输入长度ｎ满足最基本的要求（ｎ≥２ｐ２），ｇ便被完全隐含于局部计算中，算法时间复杂度可达到最优．最后与文献［１］的结果比较，分析了它们的优缺点及各自的适用范围．

一种基于二叉胖树模型的并行FFT算法

二叉胖树网络结构是一种易于实现蝶式计算的网络拓扑结构,基于这一特点,首先构造了一种二叉胖树的逻辑模型,并提出了一种基于该模型的并行快速傅立叶变换算法。该算法使得进程间有良好的负载平衡,相对于串行算法来说,大大降低了时间复杂度。在集群系统和MPI环境下,给出了该算法的实现及实验数据分析。