并行FFT算法在3种并行计算模型上的设计和分析.PDF

维普资讯 软 件 学 报 第 7卷 增刊 JOURNALOFSOFTWARE Vo1．7，Supplement 一 ‘ 并行FFT算法在 3种 并行计算模型上的设计和分析 黄伟民／弋 3o1毛· 陈国良 李晓峰 (中国科技大学计算机系 台肥 230027) (中国科学院舍肥智能研究所 台肥 230031) 摘要 本文研究在APRAM ．BSP和 LogP等 3种并行计算模型上并行 FFT算法的设计和分 ’ 析 ；分析这 3种模型的内在特性及其相互关 系；评价它们在设计和分析并行算法耐的可甩性和 可操作性． 关-词 茎堑 兰夔 ，旦 墨 ，翌! · 当代典型的并行处理系统有多向量处理机系统 (如YMPC--90，VP2O00等)、多处理机 系统 (如 S一81，KSR1等)、巨量并行处理 MPP(massivelyparallelprocessing)系统 (如 Paragon，CM一5等)和工作站网络NOW (networkofworkstations)系统 (如 Livermore和 OakRidge国立实验室所构造 的PVM 系统等)．与此相应的典型的并行计算模型有基于共 享存储的SIMD模型 (如 PRAM)、基于共享存储的MIMD模型 (如 APRAM)、基于分布存 储的MIMD模型 (如BSP和LogP)和基于工作机群的粗粒度并行计算模型 (如C。)． 这些 新近提出的更为实际的并行计算模型，均在不同程度上更加真实地反映了近代并行机的特 性，从而在它们之上所设计的并行算法在实际并行机上运行时表现出较好的性能．但是这些 新模型在设计并行算法时的可操作性仍待 由大量 的算法实例所证实．本文 以FFT算法为 例 ，来说 明其在异步 PRAM (即APRAM)模型、大同步 BSP(叉叫XPRAM)模型和分布存 储LogP模型上的设计和分析方法；阐明这些模型的演变发展过程 ；分析它们的内在特性和 相互关系；评价它们在设计和分析并行算法时的可用性和可操作性． 本文第 1节先简单介绍PRAM 模型上算法设计的特点；第2～4节分别讨论APRAM ， BSP，LogP模型上的FFT算法的设计和分析方法；最后是结论． 1 PRAM 模型上算法设计特点 对于图 1所示的 1个 一8的FFT蝶式计算图，行从 0到 一1进行编号，列从 0到 *本文研究得到高校博士学科点专项基金资助．作者阵国良，1938年生，毂授t博士导师 ·主要研究领域为并行分布 式算法 ．智幄计算．李晓●．1971年生，博士生 ，主要研究领域为并行处理．黄伟民 ，1971年生，硬士，主要研究领 域为智能 机器 』、及并行处理． 本文通讯联系』、：睬国良，舍肥 230027冲 国科技大学计算机车 本文 1995一O7一O7收到修改稿 维普资讯 一 58 软 件 学 报 1996年 logn(本文对数以2为底)进行编号．一个第 r行，第 i列的点将分别连到第r行 ，第 +1列 和第 rT行 ．第 +1列的点上 ，其中r一r+n／2 (MODn／2。)．在串行机上一个 点的FFT 算法的时间复杂度为O(nlogn)． 列 PRAM 是一种共享存储的同步计算模型，各处理器 均可在单位时间内进行读、写共享 内存，而它们之间的同 步是在一个全局时钟下以锁步(Lockstep)方式实现的，因 而在进行算法的设计和分析时同步是隐含的，无需在算法 中明确设置同步点．在PRAM 中进行FFT计算时