并行矩阵乘法线程数增加耗时反而上升的问题咨询

问题描述 #

编写了如下Java代码实现并行矩阵乘法，但在矩阵规模N固定为200时，线程数从1增加到10，计算耗时反而从16ms上升到41ms，而计算机具备12线程处理能力。

原代码 #

public class Main {
    public static int P = 10;
    public static void main(String[] args) {
        for (int i = 0; i < P; i++) {
            Thread Ti = new MyThread(i);
            Ti.start();
        }
    }
}

class MyThread extends Thread {
    int N = 200;
    int P = 10;
    int H = N/P;
    private long time;
    private int threadId;
    public MyThread(int id) {
        this.threadId = id;
    }
    int [][] MX = new int[N][N];
    int [][] MR = new int[N][N];
    int [][] MXMR = new int[N][N];

    public void run() {
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                MX[i][j] = 1;
                MR[i][j] = 1;
            }
        }
        if (threadId == 0){
            time = System.currentTimeMillis();
        }
        for (int i = H*threadId; i < H*(threadId + 1); i++) {
            for (int j = 0; j < N; j++) {
                MXMR[i][j] = 0;
                for (int k = 0; k < N; k++) {
                    MXMR[i][j] += MX[i][k] * MR[k][j];
                }
            }
        }
        if(threadId == 0){
            System.out.println(System.currentTimeMillis() - time);
        }
    }
}

问题原因及优化方案 #

1. 线程内重复初始化矩阵 #

每个线程都独立创建并初始化MX、MR矩阵，这是完全冗余的操作——所有线程使用的都是全1矩阵，没必要重复初始化，既浪费内存，又增加了额外计算开销。

2. 计时逻辑不准确 #

仅线程0记录开始时间，但其他线程的初始化和计算是并行进行的，线程0的计时没有覆盖整体任务的全部耗时，最终输出的时间无法反映真实的总计算时间。正确做法是主线程等待所有子线程完成后，再统计总耗时。

3. 线程开销大于并行收益 #

当N=200时，每个线程仅处理20行数据，计算任务量过小，而创建10个线程的开销（包括线程创建、上下文切换）超过了并行计算带来的性能提升，导致总耗时上升。

4. 数据局部性差 #

矩阵乘法内层循环访问MR[k][j]时，Java二维数组是行优先存储，按列访问MR会导致缓存命中率极低，多线程并行时缓存竞争会进一步加剧这个问题，拖慢计算速度。

优化后的代码示例 #

public class Main {
    public static int P = 10;
    public static int N = 200;
    // 全局共享矩阵，避免线程重复初始化
    public static int[][] MX = new int[N][N];
    public static int[][] MR = new int[N][N];
    public static int[][] MXMR = new int[N][N];

    public static void main(String[] args) throws InterruptedException {
        // 主线程统一初始化共享矩阵
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                MX[i][j] = 1;
                MR[i][j] = 1;
            }
        }

        long startTime = System.currentTimeMillis();
        Thread[] threads = new Thread[P];
        int H = N / P;

        for (int i = 0; i < P; i++) {
            final int threadId = i;
            threads[i] = new Thread(() -> {
                int startRow = H * threadId;
                // 处理最后一个线程的边界情况，确保所有行都被覆盖
                int endRow = threadId == P-1 ? N : H * (threadId + 1);
                // 转置MR矩阵，将列访问转为行访问，提升缓存命中率
                int[][] transposedMR = transpose(MR);
                for (int iRow = startRow; iRow < endRow; iRow++) {
                    for (int j = 0; j < N; j++) {
                        int sum = 0;
                        int[] mxRow = MX[iRow];
                        int[] mrRow = transposedMR[j];
                        for (int k = 0; k < N; k++) {
                            sum += mxRow[k] * mrRow[k];
                        }
                        MXMR[iRow][j] = sum;
                    }
                }
            });
            threads[i].start();
        }

        // 等待所有线程执行完成
        for (Thread thread : threads) {
            thread.join();
        }

        long endTime = System.currentTimeMillis();
        System.out.println("总耗时：" + (endTime - startTime) + "ms");
    }

    // 矩阵转置工具方法
    private static int[][] transpose(int[][] matrix) {
        int n = matrix.length;
        int[][] transposed = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                transposed[j][i] = matrix[i][j];
            }
        }
        return transposed;
    }
}

优化说明 #

• 共享矩阵初始化：主线程一次性完成MX和MR的初始化，避免线程重复操作，节省内存与计算时间。
• 准确计时：主线程在所有线程启动前记录开始时间，等待全部线程结束后统计总耗时，真实反映整体任务耗时。
• 数据局部性优化：转置MR矩阵，将列访问转为行访问，大幅提升缓存命中率，减少内存访问开销。
• 任务边界处理：针对最后一个线程，处理N无法被P整除的情况，确保所有矩阵行都被计算。

内容的提问来源于stack exchange，提问作者Dima