Java并行矩阵乘法

Question

有人可以帮我解决这个问题吗？我正在尝试使用并行编程-Java 进行矩阵乘法。 这是我到目前为止所尝试过的

public class MatrixParallel22 extends Thread {
    final static int noThreads = 2;

    public static void main(String args[]) throws Exception {
        //get the start time
        long startTime = System.currentTimeMillis();

        MatrixParallel[] threads = new MatrixParallel[noThreads];
        for (int me = 0; me < noThreads; me++) {
            threads[me] = new MatrixParallel(me);
            threads[me].start();
        }

        for (int me = 0; me < noThreads; me++) {
            threads[me].join();
        }

        long endTime = System.currentTimeMillis();

        System.out.println("Calculation completed in " +
                (endTime - startTime) + " milliseconds");
    }

    int me;

    public MatrixParallel(int me) {
        this.me = me;
    }

    public void run() {
        //generate two matrices using random numbers
        int matrix1[][] = matrixGenerator();
        int matrix2[][] = matrixGenerator();

        //get the number of rows from the first matrix
        int m1rows = matrix1.length;
        //get the number of columns from the first matrix
        int m1cols = matrix1[0].length;
        //get the number of columns from the second matrix
        int m2cols = matrix2[0].length;

        //multiply the matrices and put the result in an array
        int[][] result = new int[m1rows][m2cols];
        for (int i = 0; i < m1rows; i++) {
            for (int j = 0; j < m2cols; j++) {
                for (int k = 0; k < m1cols; k++) {
                    result[i][j] += matrix1[i][k] * matrix2[k][j];
                }
            }
        }
    }

    public static int[][] matrixGenerator() {
        //create an array
        int matrix[][] = new int[550][550];
        //create a random generator
        //and fill it with random numbers
        Random r = new Random();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = r.nextInt(10000);
            }
        }
        return matrix;
    }
}

在本例中，我尝试在变量中设置线程数，然后测量并查看增加/减少线程数时程序的执行速度。

//更新-- 当我执行代码时..它工作正常。但问题是，如果我增加线程数量，执行时间就会变慢。 例如，使用 2 个线程，我得到 316 毫秒 对于 8 个线程，我得到 755 毫秒 我不知道哪一部分是错误的。这是我执行线程的方式吗？

Answer 1

当您使用更多线程时，您的程序不会运行得更快，这是完全可以预料的，因为您在每个单独的工作线程中创建了用于乘法的新矩阵。您不会将任务拆分为多个部分，以便由不同的工作线程并行处理。

• 这本身不会导致您所看到的性能进一步下降，因此您很可能遇到了与使用过多线程相关的一些潜在问题，例如严重争用、缓存抖动等。

至于在 Java 中加速简单的矩阵乘法实现，有很多类似的问题都有很好的答案(例如 Peter Lawrey's answer here )。

如果您实际上使用的矩阵那么大 (n > 500)，您也可以尝试 Strassen's algorithm 。当然，任何用于矩阵乘法的专用工具都会使简单的 Java 实现大吃一惊，但我假设您这样做部分是为了好玩，部分是作为练习。

编辑:

您似乎不确定如何拆分和(尝试)并行化任务。最明显的分治策略需要将每个矩阵分成 4 个象限，并将 1 个 n 维矩阵的乘法转换为 8 个 n/2 维矩阵的乘法，大致如下那:

| A11 | A12 |   | B11 | B12 |   | A11*B11 | A11*B12 |   | A12*B21 | A12*B22 |
|-----+-----| x |-----+-----| = |---------+---------| + |---------+---------|
| A21 | A22 |   | B21 | B21 |   | A21*B11 | A21*B21 |   | A22*B21 | A22*B22 |

Strassen 的算法可以通过非常精确地选择 A_ij 和 B_ij 矩阵的操作，将其减少到 7 次乘法。

您还可以将使用多个线程获得的加速与精心选择的数组迭代顺序获得的加速进行比较(请参阅 Wayne and Sedgewick's illustration here )。