Java parallel matrix multiplication

Question

Can someone help me with this, please? I'm trying to do a matrix multiplication using parallel programming - Java. This is what I've tried so far

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;
    }
}

In this case, I'm trying to set up the number of threads in a variable and then to measure and see how fast the program performs if I increase/decrease the number of threads.

//update -- When I execute the code.. it works fine. But the thing is that if I increase the number of threads, the execution time is slower. For instance, with 2 threads, i get 316 milliseconds and with 8 threads I get 755 milliseconds I don't know which part is wrong. Is it the way I execute the threads?

Answer 1

It's entirely expected that your program doesn't run any faster when you use more threads, because you create new matrices for multiplication in each separate worker. You are not splitting your task in multiple pieces that can be processed by different worker threads in parallel.

• This by itself shouldn't result in the further performance degradation that you are seeing, so most probably you are experiencing some of the potential problems related to using too many threads like significant contention, cache thrashing and others.

As for speeding up a simple matrix multiplication implementation in Java, there are many similar questions with very nice answers (like Peter Lawrey's answer here).

If you actually are using matrices that big (n > 500), you may also try Strassen's algorithm. Of course, any of the specialized tools for matrix multiplication will blow a simple Java implementation out of the water, but I'm assuming that you're doing this partly for fun and partly as an exercise.

Edit:

It looks like you are unsure how to split and (try to) parallelize the task. The most obvious divide and conquer strategy requires splitting each matrix into 4 quadrants and translating 1 multiplication of n-dimension matrices into 8 multiplications of n/2-dimension matrices, roughly like that:

| 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's algorithm can reduce this to 7 multiplications, using very precisely chosen manipulation of the A_ij and B_ij matrices.

You can also compare the speedup you get from using multiple threads with the speedup from a carefully chosen array iteration order (see Wayne and Sedgewick's illustration here).