/*第一阶段,第logn-l步至第logm步各处理器之间需要通信* 1.1)F=2,=2g),q=m,=n92,j=+1,1=2/开始户=0* (.2)if((my rank mod n=(my rank mod 2n)) then /*本处理器的数据作为变换的前项数据* (i)接收由号处理器发来的数据块,并将接收的数据块存于 cmy rank*mm/到 cmy rank*m+ny+m之中 (infor k-=0 to m-I do c{灯]=c[幻]+c[+m c[k+m/=(c灯]-c[k+m)*吗m end for (iv)将存于c[ my rank*m+m小到 cmy rank*m+m+m]之中的数据块发送 到t号处理器 else/*本处理器的数据作为变换的后项数据* (V)将存于之中的数据块发送到 my rank-p/号处理器 ()接收由 my rank-p/v号处理器发来的数据块存于c中 (2) for i=logn- I downto o do/*第二阶段,第logm-1步至第0步各处理器之间 不需要通信* (2.1)=2 (2. 2)for k=0 to m-l do if((k mod /=(k mod 2D)) ck=ck+ck+/ c[+/=(c-c[+门)* my rank.m+h) mod I end if nd f 由于各处理器对其局部存储器中的m维子向量做变换计算,计算时间为mogn;点对 点通信2logp次,每次通信量为m,通信时间为2(;+mr)logp,因此快速傅里叶变换的并 行计算时间为Tp= m logn+2(y+mr) log po MPI源程序请参见章末附录。 12离散小波变换DWT 121离散小波变换DWT及其串行算法 先对一维小波变换作一简单介绍。设(x)为一维输入信号,记中k(x)=2-122-1x-k), (x)=212(2x-k),这里x)与v(x)分别称为定标函数与子波函数,(x)}与/* 第一阶段，第 logn-1 步至第 logm 步各处理器之间需要通信*/ (1.1) t=2i, ,l=2(i+logm) ,q=n/l , z=w q/2 , j= j+1 ,v=2j /*开始 j=0*/ (1.2)if ((my_rank mod t)=(my_rank mod 2t)) then /*本处理器的数据作为变换的前项数据*/ (i) tt= my_rank+p/v (ii)接收由 tt 号处理器发来的数据块，并将接收的数据块存于 c[my_rank*m+n/v]到 c[my_rank*m+n/v+m]之中 (iii)for k=0 to m-1 do c[k]=c[k]+c[k+n/v] c[k+n/v]=( c[k]- c[k+n/v])*z (my_rank*m+k) mod l end for (iv)将存于 c[my_rank*m+n/v]到 c[my_rank*m+n/v+m]之中的数据块发送 到 tt 号处理器 else /*本处理器的数据作为变换的后项数据*/ (v)将存于之中的数据块发送到 my_rank-p/v 号处理器 (vi)接收由 my_rank-p/v 号处理器发来的数据块存于 c 中 end if end for (2)for i=logm-1 downto 0 do /*第二阶段，第 logm-1 步至第 0 步各处理器之间 不需要通信*/ (2.1) l=2i ,q=n/l , z=w q/2 (2.2)for k=0 to m-1 do if ((k mod l)=(k mod 2l)) then c[k]=c[k]+c[k+l] c[k+l]=( c[k]- c[k+l])*z (my_rank*m+k) mod l end if end for end for End 由于各处理器对其局部存储器中的 m 维子向量做变换计算，计算时间为 mlog n ；点对 点通信 2log p 次，每次通信量为 m，通信时间为 2(ts + mtw)log p ，因此快速傅里叶变换的并 行计算时间为 Tp = mlog n + 2(ts + mt w )log p 。 MPI 源程序请参见章末附录。 1.2 离散小波变换 DWT 1.2.1 离散小波变换 DWT 及其串行算法 先对一维小波变换作一简单介绍。设 f(x)为一维输入信号，记 ( ) 2 (2 ) / 2 x x k j j jk = − − −   ， ( ) 2 (2 ) / 2 x x k j j jk = − − −   ，这里 (x) 与 (x) 分别称为定标函数与子波函数， { (x)}  jk 与