Question

我在第一章中已经提到，Linus认为并行程序目前只有在服务端程序和图像处理领域有发展的空间。且不论这种说法是否正确，但从中也可以看出并发对于这两个应用领域的重要性。而对于图像处理来说，矩阵运行是其中必不可少的重要数学方法。当然，除了图像处理，矩阵运算在神经网络、模式识别等领域也有着广泛的用途。在这里，我将向大家介绍矩阵运算的典型代表——矩阵乘法的并行化实现。

在矩阵乘法中，第一个矩阵的列数和第二个矩阵的行数必须是相同的。如图5.16所示，矩阵A和矩阵B相乘，其中矩阵A为4行2列，矩阵B为2行4列，它们相乘后，得到的是4行4列的矩阵，并且新矩阵中每一个元素为矩阵A和B对应行列的乘积求和。

图5.16　矩阵相乘示意图

如果需要进行并行计算，一种简单的策略是可以将A矩阵进行水平分割，得到子矩阵A1和A2，B矩阵进行垂直分割，得到子矩阵B1和B2。此时，我们只要分别计算这些子矩阵的乘积，将结果进行拼接，就能得到原始矩阵A和B的乘积。如图5.17所示，展示了这种并行计算的策略。

图5.17　矩阵拆分进行并行计算

当然，这个过程是可以反复进行的。为了计算A1*B1，我们还可以进一步将A1和B1进行分解，直到我们认为子矩阵的大小已经在可接受范围内。

这里，我们使用ForkJoin框架来实现这个并行矩阵相乘的想法。为了方便矩阵计算，我们使用jMatrices开源软件，作为矩阵计算的工具。其中，使用的主要API如下：

· Matrix：代表一个矩阵

· MatrixOperator.multiply(Matrix, Matrix)：矩阵相乘

· Matrix.row()：获得矩阵的行数

· Matrix.getSubMatrix()：获得矩阵的子矩阵

· MatrixOperator.horizontalConcatenation(Matrix,Matrix)：将两个矩阵进行水平连接

· MatrixOperator.verticalConcatenation(Matrix,Matrix)：将两个矩阵进行垂直连接

为了计算矩阵乘法，定义一个任务类MatrixMulTask。它会进行矩阵相乘的计算，如果输入矩阵的粒度比较大，则会再次进行任务分解：

01 public class MatrixMulTask extends RecursiveTask＜Matrix＞ {
02   Matrix m1;
03   Matrix m2;
04   String pos;
05
06   public MatrixMulTask(Matrix m1, Matrix m2, String pos) {
07     this.m1 = m1;
08     this.m2 = m2;
09     this.pos = pos;
10   }
11
12   @Override
13   protected Matrix compute() {
14     //System.out.println(Thread.currentThread().getId()+":"+Thread.currentThread().
getName() + " is start");
15     if (m1.rows() ＜= PMatrixMul.granularity || m2.cols() ＜= PMatrixMul.granularity) {
16       Matrix mRe = MatrixOperator.multiply(m1, m2);
17       return mRe;
18     } else {
19       // 如果不是，那么继续分割矩阵
20       int rows;
21       rows = m1.rows();
22       // 左乘的矩阵横向分割
23       Matrix m11 = m1.getSubMatrix(1, 1, rows / 2, m1.cols());
24       Matrix m12 = m1.getSubMatrix(rows / 2 + 1, 1, m1.rows(), m1.cols());
25       // 右乘矩阵纵向分割
26       Matrix m21 = m2.getSubMatrix(1, 1, m2.rows(), m2.cols() / 2);
27       Matrix m22 = m2.getSubMatrix(1, m2.cols() / 2 + 1, m2.rows(), m2.cols());
28
29       ArrayList＜MatrixMulTask＞ subTasks = new ArrayList＜MatrixMulTask＞();
30       MatrixMulTask tmp = null;
31       tmp = new MatrixMulTask(m11, m21, "m1");
32       subTasks.add(tmp);
33       tmp = new MatrixMulTask(m11, m22, "m2");
34       subTasks.add(tmp);
35       tmp = new MatrixMulTask(m12, m21, "m3");
36       subTasks.add(tmp);
37       tmp = new MatrixMulTask(m12, m22, "m4");
38       subTasks.add(tmp);
39       for (MatrixMulTask t : subTasks) {
40         t.fork();
41       }
42       Map＜String, Matrix＞ matrixMap = new HashMap＜String, Matrix＞();
43       for (MatrixMulTask t : subTasks) {
44         matrixMap.put(t.pos, t.join());
45       }
46       Matrix tmp1 = MatrixOperator.horizontalConcatenation(matrixMap.get("m1"),
matrixMap.get("m2"));
47       Matrix tmp2 = MatrixOperator.horizontalConcatenation(matrixMap.get("m3"),
matrixMap.get("m4"));
48       Matrix reM = MatrixOperator.verticalConcatenation(tmp1, tmp2);
49       return reM;
50     }
51   }
52 }

MatrixMulTask类由三个参数构成，分别是需要计算的矩阵双方，以及计算结果位于父矩阵相乘结果中的位置，如图5.18所示。

图5.18　矩阵分解方式

MatrixMulTask中的成员变量m1和m2表示要相乘的两个矩阵，pos表示这个乘积结果在父矩阵相乘结果中所处的位置，有m1、m2、m3和m4等四种。代码第23～27行先对矩阵进行分割，分割后得到m11、m12、m21和m22等四个矩阵，并将它们按照如图5.18所示的规则进行子任务的创建。在第39～41行，计算这些子任务。在子任务返回后，在第42～48行将返回的四个矩阵m1、m2、m3和m4拼接成新的矩阵作为最终结果。

如果矩阵的粒度足够小就直接进行运算而不进行分解（第16行）。

使用这个任务类可以很容易地进行矩阵并行运算，下面是使用方法：

01 public static final int granularity=3;
02 public static void main(String[] args) throws InterruptedException, ExecutionException
{
03   ForkJoinPool forkJoinPool = new ForkJoinPool();
04   Matrix m1=MatrixFactory.getRandomIntMatrix(300, 300, null);
05   Matrix m2=MatrixFactory.getRandomIntMatrix(300, 300, null);
06   MatrixMulTask task=new MatrixMulTask(m1,m2,null);
07   ForkJoinTask＜Matrix＞ result = forkJoinPool.submit(task);
08   Matrix pr=result.get();
09   System.out.println(pr);
10 }

上述代码中第4～5行创建两个300*300的随机矩阵。构造矩阵计算任务MatrixMulTask并将其提交给ForkJoinPool线程池。第8行执行ForkJoinTask.get()方法等待并获得最终结果。