Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Why is this parallel matrix addition so inefficient?  RSS feed

 
Paul Folder
Greenhorn
Posts: 8
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm very new to multithreading and don't have much experience using inner classes.

The task is to add two matrices containing double values in a parallelized way.

My idea was to do this recursively, splitting the big matrixes into smaller ones and performing the addition when the matrices reached a certain size limit, then fusing them.

The parallelized code runs 40-80x slower than the serialized code.

I suspect that I'm doing something wrong here. Perhaps it's because I create so many new matrices, or because I traverse them so many times.

Here is the code:



Thankful for any help.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Folder wrote:My idea was to do this recursively, splitting the big matrixes into smaller ones and performing the addition when the matrices reached a certain size limit, then fusing them.

Sounds reasonable; although you seem to have chosen a very complex way of "splitting" - after all, there's nothing that says a matrix has to be square.

I suspect that I'm doing something wrong here...

I suspect so too, but nothing logically leaps out to me at the moment - although I don't like the fact that you join() before you do the calculation.

Many structural things do though:
1. You don't have a Matrix class.
2. All your methods are static.
3. You appear to assume that matrices are square.
4. (probably because of 3) You've chosen the most compilcated way to "split" a matrix - ie, into smaller "squares".

I think if I was trying to do this, Matrix is where I'd start.

Forget all that "parallel" stuff for the moment and simply design a Matrix class that can at the very least
  • Add itself to another Matrix and return the results in a third one - ie, public Matrix add(Matrix other).
  • Return a portion of itself as a "sub-Matrix" - ie, public Matrix subMatrix(int fromRow, int toRow).
  • Replace a portion of itself with data from another Matrix - ie, public Matrix copyFrom(Matrix other, int toRow).
  • and you may well find you need other stuff as well.

    Once you have that, I suspect you'll find the business of "parallelling" much simpler. Right now, you're trying to solve everything at once with code; and it's holding you back.

    HIH

    Winston
     
    Piet Souris
    Rancher
    Posts: 1979
    67
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi Paul,

    apart from Winstons remarks, I would say: just look
    at the enormous amount of labour that goes into splitting
    the two matrices into 12 other matrices, starting a number
    of threads, joining back the results...

    I bet the serial version is finished before your twelve
    matrices are created. To be sure you would need
    to split your code up into some methods and use
    a profiler.

    As an aside: what if the matrices are n x n, with n odd?
     
    Campbell Ritchie
    Marshal
    Posts: 55680
    161
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Welcome to the Ranch

    Stop using System.currentTimeMillis; use System nanoTime instead. Much more precise.
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!