j=0,1,…,J-1 其中<n+2>表示叶+2k对于模M2的最小非负剩余。注意这时c和d是周期为M2的 周期序列。其逆变换为 从变换公式中可以看出,计算输出点c和d,需要输入序列e在m=2k附近的值( 般而言,L远远小于输入序列的长度)设处理器台数为p,将输入数据ch(n=01…,N/2/-1) 按块分配给p台处理器,处理器i得到数据m…(+1B,-,让处理器1负数 和d"(n=1P2…,(+1)p2m-D的计算,则不难看出,处理器;基本上只要用到局部数据, 只有L2个点的计算要用到处理器计1中的数据,这时做一步并行数据发送:将处理器+1 中前L-1个数据发送给处理器i,则各处理器的计算不再需要数据交换,关于本算法其它描 述可参见文献[]l 算法224离散小波变换并行算法 输入:h(i 输出:c(=0;…,M2-1,k>0 对所有处理器 my rank( my rank=0…,p-1)同时执行如下的算法: (1)= (2)while (<r)de (2.1)将数据c(n=0,…,N/2J-)按块分配给p台处理器 22)将处理器计+1中前L-1个数据发送给处理器i (23)处理器/负责cn和d(=、 ,…,(i+1) 1)的计算 end while 这里每一步分解后数据cn+和d〃艹已经是按块存储在P台处理器上,因此算法第一步 中的数据分配除了产=0时需要数据传送外,其余各步不需要数据传送(数据已经到位)。因 此,按LogP模型,算法的总的通信时间为:2(Lmax(o.g)+1),远小于计算时间ON。 MPI源程序请参见所附光盘。 − = + + = 1 0 2 1 L n n k j n j dk g d j = 0,1,  , J −1 其中<n+2k>表示 n+2k 对于模 N/2j 的最小非负剩余。注意这时 j k c 和 j dk 是周期为 N/2j 的 周期序列。其逆变换为 n k k Z j n k k k Z j k j cn c h 2 c g 2 1 −  −  − =  +  j = J ,  ,1 从变换公式中可以看出，计算输出点 j+1 k c 和 j+1 k d ，需要输入序列 j n c 在 n=2k 附近的值（一 般而言，L 远远小于输入序列的长度）。设处理器台数为 p，将输入数据 ( = 0,1, , / 2 −1) j j cn n  N 按块分配给 p 台处理器，处理器 i 得到数据 1) 2 , ,( 1) 2 ( = + − j j j n P N i P N c n i  ，让处理器 i 负责 j+1 n c 和 1) 2 , ,( 1) 2 ( 1 1 1 = + − + + + j j j n P N i P N d n i  的计算，则不难看出，处理器 i 基本上只要用到局部数据， 只有 L/2 个点的计算要用到处理器 i+1 中的数据，这时做一步并行数据发送：将处理器 i+1 中前 L-1 个数据发送给处理器 i，则各处理器的计算不再需要数据交换，关于本算法其它描 述可参见文献[1]。 算法 22.4 离散小波变换并行算法 输入：hi(i=0,…, L-1), gi(i=0,…, L-1), ci 0 (i=0,…, N-1) 输出：ci k (i=0,…, N/2 k -1,k>0) Begin 对所有处理器 my_rank(my_rank=0,…, p-1)同时执行如下的算法: (1)j=0; (2)while (j<r) do (2.1)将数据 ( = 0,1, , / 2 −1) j j cn n  N 按块分配给 p 台处理器 (2.2)将处理器 i+1 中前 L-1 个数据发送给处理器 i (2.3)处理器 i 负责 j+1 n c 和 1) 2 , ,( 1) 2 ( 1 1 1 = + − + + + j j j n p N i p N d n i  的计算 (2.4)j=j+1 end while End 这里每一步分解后数据 j+1 n c 和 j+1 dn 已经是按块存储在 P 台处理器上，因此算法第一步 中的数据分配除了 j=0 时需要数据传送外，其余各步不需要数据传送（数据已经到位）。因 此，按 LogP 模型，算法的总的通信时间为：2(Lmax(o,g)+l)，远小于计算时间 O(N)。 MPI 源程序请参见所附光盘