SIMD-BF模型上的并行FWHT算法研究
2011-01-01 00:00:00林曉嫻王維歡
計算機時代 2011年1期
摘要：蝶形網(wǎng)絡是并行計算中的一種重要的網(wǎng)絡拓撲結構。并行計算模型是并行算法設計和分析的基礎。文章以并行FFT算法的基本思想為基礎，根據(jù)快速Waish-Hadamard變換的兩種蝶式計算流圖，提出SIMD-BF模型上的兩種并行FWHT算法。算法分析的結果表明：離散Walsh-Hadamard變換算法的復雜度為O(n2)；快速Walsh-Hadamard變換算法的復雜度減少為O(nlogn)；SIMD-BF模型上的并行FWHT算法的復雜度則進一步降低為O(logn)，且其綜合指標較好。這說明，SIMD-BF模型上的并行FWHT算法是一種較為高效的并行算法。
關鍵詞：單指令流多數(shù)據(jù)流；蝶形網(wǎng)絡；快速WaSh-Hadarnard變換；并行算法
