Nov 26, 2020

Java实现多线程矩阵相乘

单线程计算矩阵相乘

开发一个单线程的程序，分别计算不同规模矩阵的乘积，并记录矩阵相乘花费的时间；

从文件中读取矩阵的方法

public static void readMatrix(double[][] matrix, String fileName) {
    String pathName = "./mx/" + fileName + ".txt";
    try (FileReader fr = new FileReader(pathName); BufferedReader br = new BufferedReader(fr)) {
        String line;
        int cntLine = 0;
        while ((line = br.readLine()) != null) {
            String[] nums = line.split(" ");
            for (int i = 0; i < nums.length; i++) {
                matrix[cntLine][i] = Double.valueOf(nums[i]).doubleValue();
            }
            cntLine++;
        }
    } catch (IOException e) {
        e.printStackTrace();
    }
}

两矩阵相乘的方法

public static double[][] multiple(double[][] matrixA, double[][] matrixB) {
    // 串行进行矩阵乘法
    int rows = matrixA.length;
    int cols = matrixA[0].length;
    double[][] res = new double[rows][cols];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            for (int k = 0; k < cols; k++) {
                res[i][j] += matrixA[i][k] * matrixB[k][j];
            }
        }
    }
    return res;
}

main函数

根据不同的规格读取矩阵文件
进行矩阵乘法计算
输出计算的耗时

public static void main(String[] args) {
    int[] sizes = {64,128,512,1024};
    Date start,end;
    double[][] matrixA= new double[size][size];;
    double[][] matrixB= new double[size][size];;
    for(int i = 0;i<sizes.length;i++){
        size = sizes[i];
        matrixA = new double[size][size];
        matrixB = new double[size][size];
        start = new Date();
        readMatrix(matrixA, "M" + size + "A");
        readMatrix(matrixB, "M" + size + "B");
        double[][] ans = multiple(matrixA, matrixB);
        end = new Date();
        System.out.println("单线程串行计算" + size + "x" + size + "矩阵乘法耗时：" + (end.getTime() - start.getTime()) + "ms");
    }
}

运行结果

结果分析

算法复杂度分析

矩阵相乘的时间复杂度为O(N³)
64x64矩阵相乘大约需要运算260 000次=2.6x10^5^
128x128矩阵相乘大约需要运算2 100 000次=2.1x10^6^
512x512矩阵相乘大约需要运算130 000 000次=1.3x10^8^
1024x1024矩阵相乘大约需要运算1 070 000 000次=1.07x10^9^

运行环境分析

笔记本CPU i5-8250U 四核八线程主频1.6GHz = 每秒计算上限为1.6x10^9^
由于当前是单线程运行，所以理论上限应该是每秒运算2x10^8^次
加上笔记本CPU会自动降频以减少能耗，所以实际的运算速度会比理论上限低

运行结果分析

各规格矩阵相乘耗时 基本和 理论计算值÷理论计算速度 吻合

四线程计算矩阵相乘

开发一个 4 线程的程序，分别计算 16x16 128x128 512x512 矩阵的乘积，并记录矩阵相乘花费的时间；

定义运算线程类

每个线程需要被分配各自的任务来实现多线程矩阵计算
比如新建2个线程，一个矩阵应该负责1,3,5…列的计算，另一个矩阵负责2,4,6…列的计算

class MatrixThread implements Runnable {
    private int start;
    private double[][] A;
    private double[][] B;
    private double[][] C;

    public MatrixThread(int start, double[][] A, double[][] B, double[][] C) {
        this.start = start;
        this.A = A;
        this.B = B;
        this.C = C;
    }

    @Override
    public void run() {
        // 根据线程数量划分线程任务
        for (int i = start; i < MatrixMultiple.size; i += MatrixMultiple.totalThreads) {
            for (int j = 0; j < MatrixMultiple.size; j++) {
                for (int k = 0; k < MatrixMultiple.size; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
    }
}

使用所定义的线程计算矩阵

建立线程数组
初始化每个线程
启动每个线程
在线程运行完之后终止线程
检验多线程计算的矩阵结果和单线程计算的结果是否相同

public static void main(String[] args) {
    int[] sizes = { 64, 128, 512, 1024 };
    Date start, end;
    double[][] matrixA = new double[size][size];
    double[][] matrixB = new double[size][size];
    for (int k = 0; k < sizes.length; k++) {
        size = sizes[k];
        matrixA = new double[size][size];
        matrixB = new double[size][size];
        start = new Date();
        readMatrix(matrixA, "M" + size + "A");
        readMatrix(matrixB, "M" + size + "B");
        double[][] ans = multiple(matrixA, matrixB);
        end = new Date();
        long time1 = end.getTime() - start.getTime();
        System.out.println("单线程串行计算" + size + "x" + size + "矩阵乘法耗时：" + time1 + "ms");

        Thread[] threads = new Thread[totalThreads]; // 线程组
        double[][] matrixC = new double[size][size]; // 存放答案数组
        for (int i = 0; i < totalThreads; i++) {
            threads[i] = new Thread(new MatrixThread(i, matrixA, matrixB, matrixC)); // 初始化每个线程
        }
        start = new Date();
        for (int i = 0; i < totalThreads; i++) {
            threads[i].start(); // 启动每个线程
        }
        for (int i = 0; i < totalThreads; i++) {
            try {
                threads[i].join(); // 当线程结束时就终止线程
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        end = new Date();
        long time2 = end.getTime() - start.getTime();
        System.out.println(
            totalThreads + "线程并行计算" + size + "x" + size + "矩阵乘法耗时：" + time2 + "ms");

        double rate = 1.0*(time1-time2)/time1;
        System.out.printf(
            totalThreads + "线程并行计算" + size + "x" + size + "矩阵乘法的节约时间比例为%.2f\n", rate);
        // 对多线程计算结果进行检验
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (ans[i][j] != matrixC[i][j]) {
                    System.out.println("第" + i + "行" + "第" + j + "列不相等");
                }
            }
        }
        System.out.println();
    }
}

运行结果

多次运行以避免偶然性和减少误差

当前耗时只考虑多线程计算的时间，没有把创建线程和初始化线程的时间算进去

可以看到四线程运行并不能跑满CPU利用率

结果分析

可以看到由于CPU最大支持8线程，所以在4线程的情况下是能做到并行的
- 4线程并行情况下运算耗时大约为单线程情况下的四分之一
- 矩阵规模越大，节约比例越接近0.75
这里我只用了四个线程进行计算，但是却可以发现这边显示的CPU0-7的利用率都同时提升了
- 按理来说，4个线程应该最多只能在4个核上运行
- 原因是，事实上这个CPU在物理上就是4个内核，只是在逻辑上抽象成了8个逻辑处理器
- 可以理解为我把现在雇佣了四个厨师，每个厨师可以同时两只手做两个菜，即左手做一份菜，右手做一份菜
- 现在我派这四个厨师每人做一份菜
- 他们现在很省力，因为可以左手做半份菜，右手做半份菜
- 这对于他们来说只需要花费50%的力气就足够了

十六线程计算矩阵相乘

定义线程类和计算代码类似，在此不再赘述
只需要改线程数即可 public static int totalThreads = 16;

运行结果

多次运行以避免偶然性和减少误差

可以在任务管理器中明显看到，在进行多线程计算时，CPU利用率显著提高，甚至直接跑满了
利用win10自带的资源监视器也可以很明显地看到了是8个核的利用率都满了

结果分析

16线程的理论节约时间比例应该是$15/16 = 0.9375$
- 但是实际上由于CPU只支持最大8线程并行，所以即使创建了16线程，也没有能做到16线程并行
- 所以理论节约时间比例的上限只有$7/8 = 0.875$
可以看到这次运行时间节约比例和理论值差的很多
- 16线程（实际是8线程）计算的所花的时间甚至比4线程计算的时间还要长
- 个人理解是JVM在线程调度的时候开销增加，导致16进程计算矩阵相乘的时候浪费了大量时间进行线程方面的操作
- 当然由于本身系统环境本身也不是不变的，所以也有可能是其他进程对该程序的影响。
在这个情况下，这四个厨子（四个物理核心）
- 我让他们每人做两份菜
- 他们每人左手做一份，右手做一份（每个核心抽象成两个逻辑处理器）
- 因此他们已经达到了自己的极限

线程学习总结

合理利用多线程可以有效的增加计算速度
相对与单线程来说，多线程的编程会更加复杂
过多的线程数并不一定能节省时间，可能会导致计算时间的增加