| SIMD-BF模型上的并行FWHT算法研究 |
| |
| 引用本文： | 林晓娴,王维欢.SIMD-BF模型上的并行FWHT算法研究[J].计算机时代,2011(1):30-32. |
| |
| 作者姓名： | 林晓娴 王维欢 |
| |
| 作者单位： | 西北师范大学数学与信息科学学院,甘肃兰州,730070 |
| |
| 摘 要： | 蝶形网络是并行计算中的一种重要的网络拓扑结构.并行计算模型是并行算法设计和分析的基础.文章以并行FFT算法的基本思想为基础,根据快速Walsh-Hadamard变换的两种蝶式计算流图,提出SIMD-BF模型上的两种并行FWHT算法.算法分析的结果表明:离散Walsh-Hadamard变换算法的复杂度为O(n2);快速W...
|
| 关 键 词： | 单指令流多数据流 蝶形网络 快速Walsh-Hadamard变换 并行算法 |
A Study of Parallel FWHT Algorithm Based on SIMD-BF Model |
| |
| LIN Xiao-xian,WANG Wei-huan.A Study of Parallel FWHT Algorithm Based on SIMD-BF Model[J].Computer Era,2011(1):30-32. |
| |
| Authors: | LIN Xiao-xian WANG Wei-huan |
| |
| Affiliation: | (College of Mathematics and Information Science, Northwest Normal University, Lanzhou, Gansa 730070, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | SIMD butterfly network FWHT parallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
