行划分的矩阵相乘并行改进及其DSP实现

　　一、引言

　　并行算法可以根据算法的特点进行算法分解,首先需要分析数据的依存关系和依赖关系,寻找任务的并行性,将多个操作合并成一个任务,然后将整个程序分解为单个任务,同时还可以分析目标的结构通信连接和时序关系,进行并行处理。而工作站机群能充分利用现有的工作站资源和局域网，在工作站机群上，对传统的并行数值计算算法进行优化和改进，可以大幅度提高计算的效率，缩短计算的时间。

　　数字信号处理对信号在时域及变换域的特性进行分析、处理，能使我们对信号的特性和本质有更清楚的认识和理解，在阵列信号处理中需要大量的矩阵运算，而其中最基本的就是矩阵乘法运算。本文就矩阵相乘在PVM环境下进行了并行化改进实现，并在数字信号处理器中得以实现。

　　二、问题的提出

　　在文献[1]和[2]中介绍了一种矩阵相乘的算法。为了提高矩阵相乘的效率，我们将其进行并行化改进，其中矩阵A采用按行划分，矩阵B整个的传给每个工作进程。而PVM程序采用Master/Slave编程模式。首先，主进程产生n个工作进程，其中第一个工作进程指定在某台机器，其余工作进程由PVM选择合适的机器产生。每个工作进程完成矩阵乘积后，将计算结果返回Master进程。

　　假设矩阵A、B、C均是n阶方阵，其中A被划分为n个n阶的子矩阵，A、B是将进行乘法运算的初始矩阵，C存放运算结果，C在运算前为零矩阵。现在假设有n个处理机Pi,n(1

　　而在矩阵相乘的直接实现中，将A矩阵的一行和B矩阵的一列传送到一台处理机，这样就需要n2台处理机，实现框图和过程如下所示：

　　矩阵的串行实现代码如下[2,3]：

　　for(i←1) to n do

　　for(j←1) to n do

　　t←0

　　for(k←1) to j do

　　t←t+ai,k*bk,j

　　repeat

　　ci,j←t

　　在单个DSP中实现需要三个循环,使得算法复杂度为N (O 3) 。

　　矩阵相乘的直接实现图

　　三、矩阵相乘任务分配及并行PVM程序

　　3.1 子任务分配策略

　　现在考虑矩阵的分配问题。假设有n个处理机，且在工作站机群上，采用PVM并行编程环境实现矩阵相乘的并行算法，必须将n个处理机对应于n个并行子任务，每个子任务可以独立地进行局部矩阵运算并相互传送数据。这n个子任务将被分配到工作站机群的有限个工作站上进行，此时，一个工作站上可能同时运行多个子任务。一般情况下，工作站机群中所包含的工作站个数不会恰好等于n。但是，若工作站个数大于n,则并行子任务个数小于工作站个数，机群的全部资源不能得到充分利用，这时应该增加对矩阵的划分数，既增加n的值，使工作站个数小于或等于n。此时，就存在如何将n个子任务分配到小于n个工作站上去的问题，具体分配的策略必须满足下面两个规则：