最让人惊艳的并行算法之一——矩阵算法

大家好，欢迎来到IT知识分享网。

最让人惊艳的算法之一——矩阵算法

对于图像处理来说，矩阵运行是其中必不可少的重要数学方法。当然，除图像处理外，矩阵运算在神经网络、模式识别等领域也有着广泛的用途。在这里，我将向大家介绍矩阵运算的典型代表—矩阵乘法的并行化实现。

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

矩阵相乘示意图

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

​

矩阵拆分进行并行计算

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

这里，我们使用Fork/Join框架来实现并行矩阵相乘的想法。为了方便矩阵计算，我们使用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所示。

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()方法并获得最终结果。

内容摘自《实战Java高并发程序设计（第3版）》，本书适合：所有java从业人员，所有数据库工程师阅读。

逻辑顺畅。全书脉络清晰，从Java高并发程序的设计基础开始由底层原理落实到具体案例，环环相扣，完整流畅。结构严谨。总体上循序渐进，逐步提升。每一章都各自有鲜明的侧重点，有利于读者快速抓住重点。

实用性强。本书注重实战，采用了理论结合实践的编写方法，给重要的知识点都安排了代码实例，帮助读者在工作中实战应用。