哈达玛变换的并行算法

《哈达玛变换的并行算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章哈达玛变换的并行算法前言一串行算法1公式：2复杂度：N×(N-1)次加(减)法和N次除法。3快速算法（FHT）：规律：二并行算法设计1对数据直接分块，采用图10-1和图10-2的方式：网络拥挤；空闲等待；数据交换量大；2初步思路（以2个处理机来考虑图10-1的并行算法）：在分配原始数据的时候，不是按顺序依次分段，而是以步长为pe进行数据选择；总共的数据交换量为4(而直接按图10-1的计算方式需要的数据交换量为8)。3计算和通信相重叠的技术应用：Pe=4，N=32：P0：f0(0)f0(4)f0(8)f0(12)f0(16)f0(20)f0(24)f0(28)P1：f0(1)f0(5)f0

2、(9)f0(13)f0(17)f0(21)f0(25)f0(29)P2：f0(2)f0(6)f0(10)f0(14)f0(18)f0(22)f0(26)f0(30)P3：f0(3)f0(7)f0(11)f0(15)f0(19)f0(23)f0(27)f0(31)N=2P，pe=2E（1）前端机将原始数据按步长为pe发送给各处理机(第0号处理机得数据为0,pe,2pe,3pe,…；第1号处理机得数据为1,pe+1,2pe+1,3pe+1,…；……第pe-1号处理机得数据为pe-1,2pe-1,3pe-1,…)；（2）第x(0

3、x号处理机将数据平均分成pe段，分别为第0段，第1段，…。接着，该处理机依次将第y段发送给第y号处理机。（4）第x号处理机对自己的第x段进行P-2E个处理步。（5）第x号处理机接收来自第y号(0

4、1）每个处理机在数据交换前都有一部分计算工作，因此避免了交换数据与原始数据的传输冲突；（2）通过推迟接收，数据有充足的时间从一个处理机向另一个处理机传送，使得计算与通信重叠，并行计算时间对当时的网络状况不敏感；（3）虽然每个处理机都要接收其它所有处理机上的数据，但逻辑上只有一次同步过程，并且，只要接收到一个处理机上的数据，就能往后进行一部分计算，减少了速度较慢的处理机对整个处理时间的影响；（4）直接按照图10-1所示算法需要的交换量：每个处理步，每个处理机都接收来自其它处理机的全部数据(N/pe个)，这样的处理步有E个，而总共有pe个处理机，所以，总的数据交换量为；新算法所需要的数据交换量：只

5、有一个处理步需要交换数据，在该处理步中，每个处理机总共要发送个数据到其它处理机，而一共有个处理机，所以，总的数据交换量为。三试验分析四.思考：如果按照图10－2的形式设计并行算法，怎样设计？【如N＝8，pe＝2，初始时每个处理器依次接收4个连续的数据(f(0),f(1),f(2),f(3);f(4),f(5),f(6),f(7))。然后每个处理器分别对其上的四个数据进行处理，但是要注意的是第一个处理器先计算出f1(1),f1(3),并把它们发送给第二个处理器，然后再计算f1(0),f1(2),类似地，第二个处理器先计算出f1(4),f1(6),并把它们发送给第一个处理器，然后再计算f1(5),

6、f1(7)；接下来，第一个处理器根据其上的f1(0)和f1(2)先计算出f2(0),f2(2)，然后再接收f1(4)和f1(6)，并计算出f2(4)和f2(6)，类似地，第二个处理器根据其上的f1(5)和f1(7)先计算出f2(5),f2(7)，然后再接收f1(1)和f1(3)，并计算出f2(1)和f2(3)；然后，第一个处理器根据其上的f2(0)，f2(2)，f2(4)和f2(6)计算出f3(0)，f3(2)，f3(4)和f3(6)，类似地，第二个处理器根据其上的f2(1)，f2(3)，f2(5)和f2(7)计算出f3(1)，f3(3)，f3(5)和f3(7)。】2.根据本章的并行算法设计思

7、想设计FFT的并行算法。