摘要
蝶形网络是并行计算中的一种重要的网络拓扑结构。并行计算模型是并行算法设计和分析的基础。文章以并行FFT算法的基本思想为基础,根据快速Walsh-Hadamard变换的两种蝶式计算流图,提出SIMD-BF模型上的两种并行FWHT算法。算法分析的结果表明:离散Walsh-Hadamard变换算法的复杂度为O(n2);快速Walsh-Hadamard变换算法的复杂度减少为O(nlogn);SIMD-BF模型上的并行FWHT算法的复杂度则进一步降低为O(logn),且其综合指标较好。这说明,SIMD-BF模型上的并行FWHT算法是一种较为高效的并行算法。
Butterfly network is an important network topology structure in parallel computing. Parallel computing model is the foundation of parallel algorithm design and analysis. Based on the essential idea of parallel fast Fourier transformation algorithm, according to the two butterfly computation flow diagram of fast Walsh-Hadamard transformation （FWHT）, we present the two parallel FWHT algorithms based on SIMD-BF model. The results of algorithm analysis show that the complexity of discrete Walsh-Hadamard transformation algorithm is O（n2）, FWHT algorithm reduces to O（ntogn）, and the parallel FWHT algorithm based on SIMD-BF model decreases to O（logn） further and its comprehensive indices are preferable. This indicates that the parallel FWHT algorithm based on SIMD-BF model is a high-efficiency parallel algorithm.
出处
《计算机时代》
2011年第1期30-32,共3页
Computer Era
