论文部分内容阅读
【摘 要】对于100*100阶以上的矩阵乘积运算，构造一种适用于多处理机系统的并行算法。此算法能很大程度上提高计算机的效率和速度，并同时给出了详细的运算程序和结果。
【关键词】并行算法；矩阵乘积
在很多的工程问题的计算中，会常遇到一些有关大型的高阶矩阵的计算，尤其是两矩阵相乘最为常见。当遇到高阶矩阵时，计算过程需要占用较多的工作资源和较大的计算机内存，计算效率受到影响。随着大型的具有多处理机的并行计算机系统的发展，一些大型计算可以构造相应的并行计算方法进行并行处理，从而减少计算机的工作单元，提高计算效率、节约资源。因此，对于矩阵的乘积和方阵求逆运算本文构造了一种并行算法，并给出了相应的实现方法。
1.矩阵乘法的并行算法
设A是一个M*100矩阵，B是一个100*N矩阵，记C=AB，M=N=100。又设有一个主机系统具有p台处理机。我们为建立在p台处理机下求解C=AB的并行算法。首先将矩阵A和B分块，每个矩阵分成体积相近的p块，如下：
A=（AT1，AT2，…ATp）T，B=（B1，B2，…，Bp）
其中Ai为Mi×100矩阵，Bi为100×Ni矩阵，i=1，2，…，p，ΣMi=M，ΣNi=N。则：
从C的结构可以看出，C是由P2个低阶矩阵乘积所组成。当A，B分块一定时，每个低阶矩阵乘积是独立的，可以并行计算。为了表述简单，不妨设m，n均可被p整除，即A，B可均匀地分为p块，并记mi=mp=mp，ni=np=np，i=1，2，…p。至此，我们来实现上述乘积运算的并行算法。
step 1：将Ai，Bi分别存入处理机i（i=1，2，…，p）的矩阵A1，B1中，其中A1为mp×100矩阵，B1为100×np为矩阵，并令k=1。
step 2：信息轮换传送。处理机i将B1中元素传送到第i+1台处理机（i=1，2，…，p-1）；第p台处理机将B1中元素传送到第1 台处理机。具体流程为：如果i+1>p，则令j =1，否则j=i+1，将处理机i中B1的元素传送给处理机j，其中i=1，2，…p。
step 3：每台处理机并行地计算A1×B1，并根据A1，B1中元素在A，B中位置，将计算结果存入其工作矩阵C1中相应单元，C1 是一个m p×n 矩阵。
step 4：信息接收，每台处理机接收上一台处理机传送来的信息，并存入其B1矩阵中，覆盖B1中原来的信息。具体流程：如果i21<1，令j=p，否则令j=i-1，处理机接收处理机i接收处理机j传送来的信息。
step 5：如果k 此时，每个处理机仅需要mp×100+100×np+mp×n=（m×100+100×n+n×m）/p个工作单元。计算结果C可由各处理机中工作矩阵C1的结果得到。具体运行过程如下：
第k次并行计算结果处理机i 处理机i
1 2 … p-1 p
K=1 A1B1 A2B2 … Ap-1Bp-1 ApBp
K=2 A1Bp A2B1 … Ap-1Bp-2 ApBp-1
…………… … … … … …
K=p A1B2 A2B3 … Ap-1Bp ApB1
2.算法（并行程序）实现
k=1
w h ile（k begin
fo r i=1 to p do
begin
If i+1>p then
send B 1 to P（1）；
else
send B 1 to P（i+1）；
end if
Fo r i1=1 to m p do
begin
Fo r j 1=（i21）3 np to i3 np do
Fo r k=1 to k do
c1（i1，j1）=c1（i1，j1）+A1（i1，k）3 B1（k，j1）
end
If i21<1 then
receive B 1 from P（p）；
else
receive B 1 from P（i21）；
end if
end
k=k+1
end
Fo r i=1 to m p do
begin
Fo r j=（p 21）3 np to p 3 np do
begin
Fo r l=1 to k do
c1（i，j）=c1（i，j）+A1（i，l）3B1（l，j）
end
end
参考文献：
[1]陈明逵，凌永祥.计算方法[M].西安交通大学出版社，1992.
[2]张新菊，刘羽，韩枭.行划分的矩阵相乘并行改进及其DSP实现[J].微计算机信息，2008（20）.
【关键词】并行算法；矩阵乘积
在很多的工程问题的计算中，会常遇到一些有关大型的高阶矩阵的计算，尤其是两矩阵相乘最为常见。当遇到高阶矩阵时，计算过程需要占用较多的工作资源和较大的计算机内存，计算效率受到影响。随着大型的具有多处理机的并行计算机系统的发展，一些大型计算可以构造相应的并行计算方法进行并行处理，从而减少计算机的工作单元，提高计算效率、节约资源。因此，对于矩阵的乘积和方阵求逆运算本文构造了一种并行算法，并给出了相应的实现方法。
1.矩阵乘法的并行算法
设A是一个M*100矩阵，B是一个100*N矩阵，记C=AB，M=N=100。又设有一个主机系统具有p台处理机。我们为建立在p台处理机下求解C=AB的并行算法。首先将矩阵A和B分块，每个矩阵分成体积相近的p块，如下：
A=（AT1，AT2，…ATp）T，B=（B1，B2，…，Bp）
其中Ai为Mi×100矩阵，Bi为100×Ni矩阵，i=1，2，…，p，ΣMi=M，ΣNi=N。则：
从C的结构可以看出，C是由P2个低阶矩阵乘积所组成。当A，B分块一定时，每个低阶矩阵乘积是独立的，可以并行计算。为了表述简单，不妨设m，n均可被p整除，即A，B可均匀地分为p块，并记mi=mp=mp，ni=np=np，i=1，2，…p。至此，我们来实现上述乘积运算的并行算法。
step 1：将Ai，Bi分别存入处理机i（i=1，2，…，p）的矩阵A1，B1中，其中A1为mp×100矩阵，B1为100×np为矩阵，并令k=1。
step 2：信息轮换传送。处理机i将B1中元素传送到第i+1台处理机（i=1，2，…，p-1）；第p台处理机将B1中元素传送到第1 台处理机。具体流程为：如果i+1>p，则令j =1，否则j=i+1，将处理机i中B1的元素传送给处理机j，其中i=1，2，…p。
step 3：每台处理机并行地计算A1×B1，并根据A1，B1中元素在A，B中位置，将计算结果存入其工作矩阵C1中相应单元，C1 是一个m p×n 矩阵。
step 4：信息接收，每台处理机接收上一台处理机传送来的信息，并存入其B1矩阵中，覆盖B1中原来的信息。具体流程：如果i21<1，令j=p，否则令j=i-1，处理机接收处理机i接收处理机j传送来的信息。
step 5：如果k
第k次并行计算结果处理机i 处理机i
1 2 … p-1 p
K=1 A1B1 A2B2 … Ap-1Bp-1 ApBp
K=2 A1Bp A2B1 … Ap-1Bp-2 ApBp-1
…………… … … … … …
K=p A1B2 A2B3 … Ap-1Bp ApB1
2.算法（并行程序）实现
k=1
w h ile（k
fo r i=1 to p do
begin
If i+1>p then
send B 1 to P（1）；
else
send B 1 to P（i+1）；
end if
Fo r i1=1 to m p do
begin
Fo r j 1=（i21）3 np to i3 np do
Fo r k=1 to k do
c1（i1，j1）=c1（i1，j1）+A1（i1，k）3 B1（k，j1）
end
If i21<1 then
receive B 1 from P（p）；
else
receive B 1 from P（i21）；
end if
end
k=k+1
end
Fo r i=1 to m p do
begin
Fo r j=（p 21）3 np to p 3 np do
begin
Fo r l=1 to k do
c1（i，j）=c1（i，j）+A1（i，l）3B1（l，j）
end
end
参考文献：
[1]陈明逵，凌永祥.计算方法[M].西安交通大学出版社，1992.
[2]张新菊，刘羽，韩枭.行划分的矩阵相乘并行改进及其DSP实现[J].微计算机信息，2008（20）.