0

In my function, there is a lot of element wise matrix multiplication which are independent. Is there a way to calculate them in parallel ?

All of them are very simple operations, but 70% of my run time is for these parts of code because this function is invoked millions of times.

function [r1,r2,r3]=backward(A,B,C,D,E,F,r1,r2,r3)
r1=A.*B;
r2=C.*D;
r3=E*F;
end

for i=1:300

[r1,r2,r3]=backward(A,B,C,D,E,F,r1,r2,r3)

end
Novice_Developer
  • 1,432
  • 2
  • 19
  • 33
A.Mani
  • 71
  • 1
  • 9

2 Answers2

0

EDIT: After writing the answer, I observed that you are not multiplying all the input matrices by means of matrix multiplication. Some of them are elementwise multiplications. If this is what you intended, the following answer won't apply.

You are looking for an optimal algorithm for computing product of multiple matrices. People have studied this problem long ago and they have come up with a dynamic programming algorithm to decide the optimal order.

For example, if A is of size 10000 x 1, B is of size 1 x 10000 and C is of size 10000 x 1, it would be a lot more efficient if we computed A*B*C as A*(B*C), instead of (A*B)*C. The proof of correctness of this technique lies in the fact that matrix multiplication is associative. You can read more about this on Wikipedia. If you want a good quality MATLAB implementation of this, you can find it here. It takes the matrices as input and gives out the product. It seems like this implementation does a decent job of finding the optimal way of computing "upto" 10 matrices.

Autonomous
  • 8,935
  • 1
  • 38
  • 77
  • thax for your answer, yes most of them are element wise operation. Is there any way to do all of them in parallel, instead of sequential? – A.Mani Jun 18 '16 at 06:09
  • Ok. Then clarify what's the role of `r1, r2, r3`. You pass them as input but don't use them at all. They are given as output. So you might as well not pass them, am I right? – Autonomous Jun 18 '16 at 06:21
  • @ Parag S. Chandakkar: sorry I don't understand your mean. would you please explain more? I send r1,r2 and r3 in ouptup because in next itterate the current value of them which come from previous itterate is important – A.Mani Jun 18 '16 at 06:54
  • @A.Mani You don't use the inputs `r1, r2, r3`. You might as well not send them. So in short, you will have 6 inputs (now you have 9 inputs) and 3 output arguments. The second answer also mentions the same thing. Read first two lines of the second answer. – Autonomous Jun 18 '16 at 06:58
  • @ Parag S. Chandakkar: but if I don't send them to function so how could I change them? – A.Mani Jun 18 '16 at 07:10
  • @A.Mani You are just assigning multiplication results to `r1,r2,r3`. You are not using them on the right hand side anywhere. Thus you don't need them as input arguments. Anyway, if this is your code, I think only `parfor` may be able to help you as also stated in the other answer. – Autonomous Jun 18 '16 at 07:22
  • @ Parag S. Chandakkar: I update my code, please check it. thank you – A.Mani Jun 18 '16 at 07:36
  • Ok. I will make a last attempt at telling this. Imagine you pass `r1=r2=r3=1`, to your `backward` function from the `for i=1:300` loop. Now, pass `r1=r2=r3=0` (or any other value for that matter, `r1,r2,r3` can be different too), will it change the values of outputs `[r1,r2,r3]`? No. So, if 0 or 1 or any random inputs are going to give the same value, they are redundant. So you have don't have to pass them. There is no harm either in passing them. – Autonomous Jun 18 '16 at 08:02
0

First thing to note: the last 3 variables that you provide as input are not beeing used. I don't think this will matter much, but it would be better to clean it up.

Now the actual answer:

MATLAB is all about matrix operations, and this has been highly optimized. Even using C++ you will not expect a significant speedup (and be wary of a slowdown). As such, with the information that is provided in the question, the conclusion would be that you cannot do anything to speed up independent matrix calculations.

That being said: If you could reduce the number of sequential function calls, there may be something to gain.

It is hard to say how to do this in general, but two ideas:

  1. If you call the fuction in a for loop, use a parfor loop instead (assuming you have the parallel processing toolbox, otherwise manually break up the loop and open 4 matlab instances to paralellize the loop (can be automated if needed).
  2. See whether you really need this many function calls to small matrix operations. If you could improve your algorithm, that could offer a huge improvement, but otherwise you may still be able to combine multiple matrices (multiple versions of A with multiple versions of B for instance) and do 1 big multiplication, rather than a 100 tiny ones).
Community
  • 1
  • 1
Dennis Jaheruddin
  • 21,208
  • 8
  • 66
  • 122
  • thank you, I call this function in a for loop, but I can't use parfor because order of calling is important, but in the fuction order of matrix oprtations is not important – A.Mani Jun 18 '16 at 06:26
  • @A.Mani With the current available information, there really isn't much more that one can recommend. As mentioned in point 2: think hard on what you are trying to do, and whether you really need all calculations that you are doing, and do they all need to be sequential. If the answer is yes, then I think you just have to accept the runtime (for your current hardware). – Dennis Jaheruddin Jun 20 '16 at 07:45