矩阵乘法课件

1、算法1: for (i=1;i=n;i+) for (j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij + aik*bkj; T(n)=O(n3)S(n)=O(n2)1算法2: for (i=1;i=n;i+) par for(k=1,k=n;k+) cik=0; for (j=1;j=n;j+) par for(k=1;k=n;k+) cik=cik +aij *bjk ; T(n)=O(n2)S(n)=O(n2)P(n)=O(n)2for (i=1;i=n;i+) par for(k=1,k=n;k+) cik=0; for (j=1;j=n;j+) p

2、ar for(k=1;k=n;k+) cik=cik +aij *bjk ; 外循环 内循环 SIMD操作 k=1,2,n i j ci1=ci1+aijbj1 ci2=ci2+aijbj2 cin=cin+aijbjn 1 1 c11=c11+a11b11 c12=c12+a11b12 c1n=c1n+a11b1n 2 c11=c11+a12b21 c12=c12+a12b22 c1n=c1n+a12b2n . . n c11=c11+a1nbn1 c12=c12+a1nbn2 c1n=c1n+a1nbnn 局 存 PEM1 PEM2 PEMn3for (i=1;i=n;i+) par fo

3、r(k=1,k=n;k+) cik=0; for (j=1;j=n;j+) par for(k=1;k=n;k+) cik=cik +aij *bjk ; 外循环 内循环 SIMD操作 k=1,2,n i j ci1=ci1+aijbj1 ci2=ci2+aijbj2 cin=cin+aijbjn 2 1 c21=c21+a21b11 c22=c22+a21b12 c2n=c2n+a21b1n 2 c21=c21+a22b21 c22=c22+a22b22 c2n=c2n+a22b2n . . n c21=c21+a2nbn1 c22=c22+a2nbn2 c2n=c2n+a2nbnn 局 存

4、 PEM1 PEM2 PEMn4for (i=1;i=n;i+) par for(k=1,k=n;k+) cik=0; for (j=1;j=n;j+) par for(k=1;k=n;k+) cik=cik +aij *bjk ; 外循环 内循环 SIMD操作 k=1,2,n i j ci1=ci1+aijbj1 ci2=ci2+aijbj2 cin=cin+aijbjn n 1 cn1=cn1+an1b11 cn2=cn2+an1b12 cnn=cnn+an1b1n 2 cn1=cn1+an2b21 cn2=cn2+an2b22 cnn=cnn+an2b2n . . n cn1=cn1+a

5、nnbn1 cn2=cn2+annbn2 cnn=cnn+annbnn 局 存 PEM1 PEM2 PEMn5算法3: 采用n2个处理器，pij表示位于阵列第i行第j列的处理机. 以n=4为例。将初始分布变换为“1”分布，即每个pij 将aij向西（左）移到i-1个处理机中，将bij向北（上）移到j-1个处理机中，并将新的 aij *bi的结果加至 cij中。将“1”分布换为“2”分布，即每个pij 将aij向西移到相邻的处理机中，将bij向北移到相邻的处理机中，并将新的 aik *bkj的结果加至 cij中。将“2”分布换为“3”分布, 方法同（2）。将“3”分布换为“4”分布，方法同（2）

6、。6初始分布: a11b11 a12b12 a13b13 a14b14 a21b21 a22b22 a23b23 a24b24 a31b31 a32b32 a33b33 a34b34 a41b41 a42b42 a43b43 a44b44 “1”分布: a11b11 a12b22 a13b33 a14b44 a22b21 a23b32 a24b43 a21b14 a33b31 a34b42 a31b13 a32b24 a44b41 a41b12 a42b23 a43b34 7“3”分布: a13b31 a14b42 a11b13 a12b24 a24b41 a21b12 a22b23 a23b

7、34 a31b11 a32b22 a33b33 a34b44 a42b21 a43b32 a44b43 a41b14“4”分布: a14b41 a11b12 a12b23 a13b34 a21b11 a22b22 a23b33 a24b44 a32b21 a33b32 a34b43 a31b14 a43b31 a44b42 a41b13 a42b24 10“1”分布: a11b11 a12b22 a13b33 a14b44 a22b21 a23b32 a24b43 a21b14 a33b31 a34b42 a31b13 a32b24 a44b41 a41b12 a42b23 a43b34 “2”分布: a12b21 a13b32 a14b43 a11b14 a23b31 a24b42 a21b13 a22b24 a34b41 a31b12 a32b23 a33b34 a41b11 a42b22 a43b33 a44b44 “3”分布: a13b31 a14b42 a11b13 a12b24 a24b41 a21b12 a22b23 a23b34 a31b11 a32b22 a33b33 a34b44 a42b21 a43b32 a44b43 a41b1