资源描述：
《并行计算-习题及答案-例题习题讲解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、例题习题讲解例1SIMD-SM上求最大值算法Beginfork=m-1to0doforj=2kto2k+1-1par-doA[j]=max{A[2j],A[2j+1]}endforendforend时间分析t(n)=m×O(1)=O(logn)p(n)=n/2c(n)=O(nlogn)非成本最优例2令n=2k(k>=0)，求n个数和的并行算法算法运行时间：t(n)=O(logn)§总运算量:W(n)=W(1)(n)+W(2)(n)+W(3)(n)=n+∑n/2h+1=O(n)§由Brent定理知:t(n)=O(n/p+logn)例3设A为矩阵，有如下串行程序段：fori=1tondo
2、forj=1tondoa[3i,2j]=a[3i-2,2j-1]endforendfor其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分和方块划分.在行划分的情况下令m=┌n/p┐,例1的串行程序段可以转化为如下的并行程序段：fork=1toPPar-dofori1=1tomdoforj=1tondoa[3(k-1)m+3i1,2j]=a[3(k-1)m+3i1-2,2j-1]endforendforendfor例4设A为一个n阶方阵，有如下串行程序段：fori=1tondoforj=1tondoa[i,j]=a[i-1,j]endforendfor分析
3、矩阵A的元素下标i和j，则i和j的相关方向向量为，各列之间数据无任何相关关系。因此对矩阵A可按列划分。串行程序段可转化为如下并行程序段：fork=1toPPar-doforj1=1tomdofori=1tondoa[i,(k-1)m+j1]=a[i-1,(k-1)m+j1]endforendforendfor例5注：本例无链路竞争和死锁现象例6E立方选路 0110(S)1101(D)1011(R)例7DNS乘法示例C00=1×(-5)+2×7=9C01=1×(-6)+2×8=10C10=3×(-5)+4×7=13C11=3×(-6)+4×8=14例8上三角方程组的回代解法并行化(1
4、)SISD上的回代算法Begin(1)fori=ndownto1do(1.1)xi=bi/aii(1.2)forj=1toi-1dobj=bj-ajixiaji=0endforendforEnd(2)SIMD-CREW上的并行回代算法-划分:p个处理器行循环带状划分-算法Beginfori=ndownto1doxi=bi/aiiforallPj,where1≤j≤pdofork=jtoi-1steppdobk=bk-akixiaki=0endforendforendforEnd//p(n)=n,t(n)=n例9n=8的BF网络表示Pr,i与上层Pr-1,i,Pr-1,j相连,这里j与
5、i仅在第r位不同例10一个在MPI中创建新通信域的例子§MPI_CommMyWorld,SplitWorld;§intmy_rank,group_size,Color,Key;§MPI_Init(&argc,&argv);§MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld);§MPI_Comm_rank(MyWorld,&my_rank);§MPI_Comm_size(MyWorld,&group_size);§Color=my_rank%3;§Key=my_rank/3;§MPI_Comm_split(MyWorld,Color,Key,&SplitWorl
6、d);例11考虑如下程序段：L1:forI=1to50do...S:X(2*I)=......T:...=...X(3*I+1)......endfor这里：f1(I)=2*I；g1(J)=3*J+1。依赖方程为：f1(I)-g1(J)=0è2*I–3*J=1,而依赖约束为：1≤I≤50，1≤J≤50。该方程的解（I,J）对应的数组变量会导致S和T之间的依赖。例12考查以下循环可向量化的情况.（1）forI=2toN–1doforJ=2toN–1doS:A(I,J)=B(I-1,J)+CT:B(I,J)=A(I,J+1)*2 endforendfor（a）存在依赖Tdf
7、S,方向为（1，0）（b）存在依赖TdaS,方向为（0,1） （2）forI=1toNdoforJ=1toNdoS:D(I,J)=A(I,J)+CT:A(I+1,J+1)=B(I,J)*2endforendfor存在依赖TdfS,方向为（1，1）
