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
2、(24) f0(28)P1：f0(1) f0(5) f0(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,)；
3、（2）第x(0xpe)号处理机接收到数据后，对所有数据整体进行E个处理步；,（3）第x号处理机将数据平均分成pe段，分别为第0段，第1段，。接着，该处理机依次将第y段发送给第y号处理机。（4）第x号处理机对自己的第x段进行P-2E个处理步。（5）第x号处理机接收来自第y号(0ype，且yx)处理机传来的数据，并对该数据段进行P-2E个处理步。该过程将持续到第x号处理机接收完其它所有处理机传来的数据。,（5）每个处理机对自己所拥有的数据进行图10-1所示的最后E个处理步。需要注意的是，在该步骤中，由于数据的排列顺序与编号不同，在计算时需要考虑位置。（6）处理机将结果返回到前端机。注意:1)当P-
4、2E0时怎样处理？2)第（2）步能否计算P-E-1步？,4 该并行算法的优点：（1）每个处理机在数据交换前都有一部分计算工作，因此避免了交换数据与原始数据的传输冲突；（2）通过推迟接收，数据有充足的时间从一个处理机向另一个处理机传送，使得计算与通信重叠，并行计算时间对当时的网络状况不敏感；,（3）虽然每个处理机都要接收其它所有处理机上的数据，但逻辑上只有一次同步过程，并且，只要接收到一个处理机上的数据，就能往后进行一部分计算，减少了速度较慢的处理机对整个处理时间的影响；,（4）直接按照图10-1所示算法需要的交换量：每个处理步，每个处理机都接收来自其它处理机的全部数据(N/pe个)，这样的处理
5、步有E个，而总共有pe个处理机，所以，总的数据交换量为 ； 新算法所需要的数据交换量：只有一个处理步需要交换数据，在该处理步中，每个处理机总共要发送 个数据到其它处理机，而一共有个 处理机，所以，总的数据交换量为 。,三 试验分析,四. 思考：如果按照图102的形式设计并行算法，怎样设计？【如N8，pe2，初始时每个处理器依次接收4个连续的数据(f(0), f(1), f(2), f(3); f(4), f(5), f(6), f(7)。然后每个处理器分别对其上的四个数据进行处理，但是要注意的是第一个处理器先计算出f1(1), f1(3),并把它们发送给第二个处理器，然后再计算f1(0), f
6、1(2),类似地，第二个处理器先计算出f1(4), f1(6),并把它们发送给第一个处理器，然后再计算f1(5), 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. 根据本章的并行算法设计思想设计FFT的并行算法。,
