2.9.2 FFT矩阵并行算法

更新于 2026年11月21日 版权声明
2.9.2 FFT矩阵并行算法

如果按行数序号的奇偶把多项式分成两个表,根据定理2.1可知,序号为偶数的多项式可以合并相邻同类项,多项式的基向量减少了一半,因此运算量也可以减少一半[36]。设有图示图示。处理器有Ω个同构的核,且Ωmod2=0。考虑到序列号为偶数的多项式的基的数量最多只有奇数项的一半,如果按如下方法进行任务分配:对于多项式图示基向量,将其中图示个基向量分配给第K个核处理,那么编号为偶数的核所分担的计算量,最多只有编号为奇数的核所分担的计算量的一半。为实现负载均衡,本书把一个偶数项与相邻一奇数项合并为一项任务,每隔Ω个任务进行抽取分配,再映射到处理器的核,如图2-8 所示。

图示

图2-8 任务分配示意图

对于处理器的第P个核,计算过程如算法2.4 所示。(https://www.daowen.com)

算法2.4 FFT矩阵并行算法

图示

根据多项式FFT并行算法2.4,在处理器的运算过程中,每个核可以独立完成计算,无需与其他核的任务同步,因此减少了同步产生的时间消耗,处理器同步开销得到了有效的降低。

✍AI写作