最讓人驚豔的算法之一——矩陣算法
對于圖像處理來說，矩陣運作是其中必不可少的重要數學方法。當然，除圖像處理外，矩陣運算在神經網絡、模式識别等領域也有着廣泛的用途。在這裡，我将向大家介紹矩陣運算的典型代表—矩陣乘法的并行化實作。
在矩陣乘法中，第一個矩陣的列數和第二個矩陣的行數必須是相同的。矩陣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高并發程式的設計基礎開始由底層原理落實到具體案例，環環相扣，完整流暢。結構嚴謹。總體上循序漸進，逐漸提升。每一章都各自有鮮明的側重點，有利于讀者快速抓住重點。
實用性強。本書注重實戰，采用了理論結合實踐的編寫方法，給重要的知識點都安排了代碼執行個體，幫助讀者在工作中實戰應用。