java - java中的并行矩阵乘法

Question

我正在尝试使用多个线程实现矩阵乘法。一切似乎都工作正常，但是，它的工作速度比通常的算法慢得多。这是我的代码

public class Main {
    private static int nRows = 500; //number of rows and columns in matrices
    private static int[][] matrix1 = new int[nRows][nRows]; //first matrix for multiplication
    private static int[][] matrix2 = new int[nRows][nRows]; //second matrix for multiplication
    private static int[][] result1 = new int[nRows][nRows]; //result from linear matrix multiplication
    private static int[][] result2 = new int[nRows][nRows]; //result from parallel matrix multiplication

    private static Thread[][] pool = new Thread[nRows][nRows]; //array of threads

    //method used for transposing a matrix to get its column easily
    public static int[][] transpose(int[][] matrix) {
        int[][] newMatrix = new int[matrix[0].length][matrix.length];
        for (int i = 0; i < matrix[0].length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                newMatrix[i][j] = matrix[j][i];
            }
        }
        return newMatrix;
    }

    public static void main(String[] args) {
        //initializing input matrices (setting all elements = 1)
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nRows; j++) {
                matrix1[i][j] = 1;
                matrix2[i][j] = 1;
            }
        }

        long start;
        long end;

        System.out.println("Linear algorithm");
        start = System.currentTimeMillis();

        //linear multiplication algorithm
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nRows; j++) {
                int temp = 0;
                for (int k = 0; k < nRows; k++) {
                    temp += matrix1[i][k] * matrix2[k][j];
                }
                result1[i][j] = temp;
            }
        }

        //show result
//        for(int i=0;i<nRows;i++){
//            for(int j=0;j<nRows;j++){
//                System.out.print(result1[i][j] + " ");
//            }
//            System.out.println();
//        }

        end = System.currentTimeMillis();
        System.out.println("Time with linear algorithm: " + (end - start));

        //--------------------

        System.out.println("Parallel algorithm");
        start = System.currentTimeMillis();

        int[][] matrix3 = transpose(matrix2); //get a transpose copy of second matrix

        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nRows; j++) {
                pool[i][j] = new myThread(matrix1[i], matrix3[j], i, j); //creating a thread for each element
                pool[i][j].start(); //starting a thread
            }
        }

        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nRows; j++) {
                try {
                    pool[i][j].join(); //waiting for the thread to finish its job
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }

        //show the result
//        for(int i=0;i<nRows;i++){
//            for(int j=0;j<nRows;j++){
//                System.out.print(result2[i][j] + " ");
//            }
//            System.out.println();
//        }

        end = System.currentTimeMillis();
        System.out.println("Time with parallel algorithm: " + (end - start));
    }

    //class, where parallel multiplication is implemented
    private static class myThread extends Thread {
        private int[] row = new int[nRows]; //row for multiplication
        private int[] col = new int[nRows]; //column for multiplication
        private int i;  //row index of the element in resulting matrix
        private int j; //column index of the element in resulting matrix

        //constructor
        public myThread(int[] r, int[] c, int i, int j) {
            row = r;
            col = c;
            this.i = i;
            this.j = j;
        }

        public void run() {
            int temp = 0;
            for (int k = 0; k < nRows; k++) {
                temp += row[k] * col[k]; //getting the element by multiplying row and column of two matrices
            }
            result2[i][j] = temp; //writing the resulting element to the resulting matrix
        }
    }
}

在这里，我为结果矩阵中的每个元素创建一个新线程。然后，我将这些线程写入数组，启动它们，最后等待它们完成工作。我已经看到了一些实现，其中整个输入矩阵(两者)将作为线程的参数给出。然而，我的任务是提出一种算法，其中仅给出一行和一列(对于该特定元素是必需的)。

测量耗时后，我得到以下结果

Linear algorithm
Time with linear algorithm: 557
Parallel algorithm
Time with parallel algorithm: 38262

我做错了什么？提前致谢!

Answer 1

您编写的代码可以在 GPU 上正常工作，其中线程的概念非常不同，并且开销基本上为零。在基于 CPU 的系统上，生成线程是一项极其缓慢的操作，只有当您可以通过大量计算工作分摊此开销时，它才有意义。

以下是一些一般建议，可帮助您为 CPU 编写更好的并行算法:

• 对于计算量大的任务，请使用与物理执行单元(核心)一样多的线程。除非存在大量内存延迟，否则超线程等 SMT 技术并没有多大帮助。对于适合 L1 和 L2 CPU 缓存的小矩阵，延迟非常低，并且 SMT 没有任何好处。当多个线程共享同一核心时，操作系统必须在两个线程之间进行上下文切换，这会增加开销并可能会破坏缓存。
• 保持并行化粒度尽可能粗，以便最大限度地提高每个线程的工作量。让每个线程对连续的行/列 block 进行操作，而不是每个线程进行一行 x 列操作。您可以尝试仅并行化外部循环，即仅并行化第一个矩阵的行。
• 使线程数量取决于硬件属性(核心数量)并且独立于问题大小。为每一行和每一列生成一个单独的线程会随着问题的大小线性扩展开销，从性能的角度来看，这确实很糟糕。
• 避免虚假分享。当在不同内核上运行的两个或多个线程写入属于同一高速缓存行的内存位置时，就会发生这种情况。当一个线程更新其核心的缓存时，更改会传播并使具有相同缓存行的其他核心的缓存失效，迫使它们重新获取数据。在您的情况下，result2 的 16 个连续值落在同一缓存行中(x86 和 ARM 上的缓存行为 64 字节长，int 为 4 字节)，并由16 个不同的线程。临时求和变量的使用以某种方式缓解了这个问题——当错误共享在内部(最)循环中重复发生时，问题会更加严重。
• 当工作项数量超过线程数量且每个线程将多次获取工作时，请使用线程池执行重复任务。在您的情况下，您为每个线程提供一个工作项，因此这并不是真正的池化。

总之，启动与物理核心一样多的线程，并让它们处理输入矩阵的大连续 block 。