Java Multithreading Matrix Multiply

Question

This is my code for multiplying matricies in parallel:

public void multiplyParallel() {
    int numProcessors = Runtime.getRuntime().availableProcessors();
    int step = (int)MATRIX_SIZE/numProcessors;
    for (int i=0; i<numProcessors; i++)  {
        Runnable r = new MatrixMultiply(this.start, this.end);
        new Thread(r).start();
        this.start += step;
        this.end += step;
    }
    this.start = 0;
    this.end = 0;
}

@Override
public void run() { 
    for (int i=this.start; i<this.end; i++) 
        for (int j=this.start; j<this.end; j++)
            for (int k=this.start; k<this.end; k++)
                this.matrix3[i][j] = this.matrix1[i][k] * this.matrix2[k][j];
}

But when I run this code on a 1024x1024 matrix, it only runs for 2-3 ms, whereas a serial version runs for around 1 second. I should be expecting 1/(numProcessors) time for the parallel version at the best.

Is there anything I'm doing wrong? The run() method is being called the same number of times as there are processors on my machine.

Are you comparing it to similarly blocked single processor code, with the same step size? There is a big gain in cache efficiency for working on smaller blocks. — Patricia Shanahan, Aug 11 '13 at 23:40
Yes, I am comparing it to single-processor version (which has the same loop body as the run method here does). — user473973, Aug 11 '13 at 23:42

score 3 · Accepted Answer · edited May 23 '17 at 12:28

3

Is there anything I'm doing wrong?

Yea. You are not multiplying the matrices. What you are actually doing is (in effect) slicing the matrices into submatrices, and then multiply the subset of those matrices that sit on the diagonal of the original matrix.

I suggest you compare the results of the two versions of the computation ... and draw your own conclusions from that.

Effective parallelization of matrix multiplication is not a simple issue.

Here are a couple of relevant links, albeit at a general level:

http://www.cs.berkeley.edu/~yelick/cs267-sp04/lectures/13/lect13-pmatmul-6x.pdf - starting at about slide 17.
http://www.slideshare.net/pkpramit/matrix-multiplicationan-example-of-concurrent-programming
Parallel Matrix Multiplication in Java 6 ... includes some Java code (YMMV).

Also note that according to Wikipedia, there are more efficient non-parallel algorithms than "naive" (O(N^3)) multiplication.

edited May 23 '17 at 12:28

Community

1
1

answered Aug 11 '13 at 23:42

Stephen C

698,415
94
811
1,216

2

Not even that because OP is missing a sum. – jason Aug 11 '13 at 23:45
Oh wow, I didn't even notice that. How would I make it so each thread only works on 1/(numProcessors) of the original matrix? – user473973 Aug 11 '13 at 23:45
The third link was exactly what I was looking for. Thanks! – user473973 Aug 12 '13 at 00:29

Java Multithreading Matrix Multiply

1 Answers1