异构环境HBSP模型及其在FFT算法中的应用

HBSP Model in Heterogeneous Environment and Its Application in FFT

提出了异构块同步并行 ( HBSP)模型和程序开销计算方法 ,依据通信开销线性模型和处理机利用率来研究异构环境中算法的设计和分析 .以快速傅立叶变换 ( FFT)为例 ,给出了相应的算法设计和分析结果 .当构成块同步并行 ( BSP)计算机的各处理机速度相同 ,且原有 BSP算法达到最优 (即各处理机上所分配的计算量与通信量完全均衡 )时 。

Heterogeneous concurrent computing has been widely addressed for highperformance scientific computing as well as for “general purpose” applications in recent years. In this paper, heterogeneous bulk synchronous parallel (HBSP) model was proposed. The algorithm design and analysis in heterogeneous environment were studied based on the linear model of communication cost prediction and utilization ratio model of processor. To prove the efficacy of HBSP, an FFT algorithm was studied as an example. The HBSP model will be same as the original BSP when the processor speed of BSP computer is all the same and the original BSP algorithm is optimized (e.g. the computation load and communication load are totally balanced).