• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Why is this parallel matrix addition so inefficient?

 
Greenhorn
Posts: 10
TypeScript Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
     
    Bartender
    Posts: 4633
    182
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • 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?
     
    Marshal
    Posts: 74054
    332
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Welcome to the Ranch

    Stop using System.currentTimeMillis; use System nanoTime instead. Much more precise.
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic