Thread Subject: HOWTO: Accelerate processing algorithm

Hi to everyone


I am new to this forum, but I thought it would be a good idea to try to get this problem solved by many minds rather than continue getting stucked once and again myself :)


My problem is that I am trying to implement an algorithm to iteratively find the solution for an optimization problem. And the data that I have to handle is quite large, since I have to simultaneously work with 10 to 20 images of say 700x600 pixels.

I have found the main blottle-neck in the program, which is the following:

for (m = 1:256)
  [indR, indC] = find(y+1 == m); %Em rows pixels, cols ims
  I(m, iteration+1) = 1/length(indR) * ...
               sum(exposures(indC).' .* x(indR, chan));
end

Basically, y is the [(700x600) 16] matrix, iteration is the current step, and I need to index the variable exposures with the # of the image (1 to 16, returned in indC), and x with both the # of the pixel (indR) and the color channel (chan).


I have tried to speed things up using sparse matrices:

exposuresMat = repmat(exposures, size(y)./size(exposures));

xMat = repmat(x, size(y)./size(x));

[ySort, indices] = sort(y(:), 'ascend');
exposuresMat = exposuresMat(indices);
xMat = xMat(indices);
S = sparse(1:size(ySort), double((ySort+1).'), xMat.*exposuresMat);
S = sum(S);
I(1:length(S), iteration+1) = S;

This last code works (for what I have checked!) but, since I do not have enough memory, I think it needs to access the HD to allocate virtual memory, and everyting slows down again.


I am thinking of trying to implement the for loop in C, and then use a MEX implementation. But I really have no idea how to do this.

More than an explanation of MEX, that I think I can learn from the documentation, I would like to know if anybody has a different suggestion, or even if somebody knows wether the MEX solution would accelerate things.


Thanks in advance
Jose

Jose Antonio <juriguen@gmail.com> wrote in message
>
> S = sparse(1:size(ySort), double((ySort+1).'), xMat.*exposuresMat);
> S = sum(S);

The two lines above can be replaced by :

v = xMat.*exposuresMat;
S = accumarray(ySort(:)+1,v(:));

It also avoid to create S and the required memory

Bruno

On 5 Jul, 13:18, Jose Antonio <jurig...@gmail.com> wrote:

> I am thinking of trying to implement the for loop in C, and then use a MEX implementation. But I really have no idea how to do this.
>
> More than an explanation of MEX, that I think I can learn from the documentation, I would like to know if anybody has a different suggestion, or even if somebody knows wether the MEX solution would accelerate things.

Memory managent is the first thing to check.
If you have many images in memory at the same time,
and do a global search over all frames for all pixels
with some value, cache misses etc might cause your
algorithm to take a lot longer than you think it
would.

So the first work-around would be to accumulate
whatever information you are looking for, from
single frame to single frame.

This approach has the added benefit that you don't
push memory requirements as much as you do now,
since only one frame is passed between functions,
and less space is needed for temporary internal
variables. Which in turn means less probability
of needing disk swap spaces etc, which would
significantly slow you down.

This goes for both matlab and a C(++) MEX implementation.

As for MEX - do you know how to program C or C++?

If 'yes', then check out the 'External Interfaces'
parts of the matlab documentation. There are a few
example files there, on how to achieve what you want.

If you don't already know C or C++ - be aware that
these languages are demanding to learn. You need to
know and understand the inner workings of the computer
in some detail before you can start programming C
with any benefit, compared to matlab. Similarly,
you will not be able to exploit the power of C++
until you learn how to select and use algorithms
and data structures in some detail.

So depending on previous programming experience and
available time, your best choise might be to stick
with matlab but leave the computer to do its job
in your time off; over night, over weekends, etc.

Rune

Thanks a lot!

Apparently it works fine :) I had another error in the code, so I haven't been able to check all the results yet.

I have seen the improvement is from around 35s to 6s, to it's great. However, do you know if it could be even faster implementing the operation in C?

Thanks!

Jose Antonio <juriguen@gmail.com> wrote in message <9281730.75571.1246796996212.JavaMail.jakarta@nitrogen.mathforum.org>...
> Thanks a lot!
>
> Apparently it works fine :) I had another error in the code, so I haven't been able to check all the results yet.
>
> I have seen the improvement is from around 35s to 6s, to it's great. However, do you know if it could be even faster implementing the operation in C?
>

To whom you ask this question? Me or Rune?

If it's to me, my opinion is not bother with MEX. Using ACCUMARRAY, you can remove even the SORT command, and the code pretty much comes down to few basic commands that would be hard for MEX to beat it by much.

Bruno

On 5 Jul, 14:29, Jose Antonio <jurig...@gmail.com> wrote:

> I have seen the improvement is from around 35s to 6s, to it's great. However, do you know if it could be even faster implementing the operation in C?

Somebody who really understand *both* C *and* the
problem you are trying to solve, might be able to
squeeze the performance a bit yet. But then, don't
expect a C newbie to be able to obtain significant
improvment.

The question is, however, *why* one would want to
boost performance. You mentioned optimization, so
I assume this is a function that will be called
over and over.

Again: Leave the computer to work over night, and
the performance boost you already got might be
enough.

Rune

Hi Bruno

The 1st question was for you, so thanks for answering. I guess I will fix to Matlab now, which is performing fast enough!

Thanks

Hi Rune

Thanks for the advice. I will fix to Matlab now, since I am pretty much a newbie to C now :)

I want the code to run as fast as possible because I am using it to perform a series of operations on a set of images and I want to check the results until I code everything properly.

Furthermore, the algorithm should be efficient, since it is not meant to be a long postprocessing stage in the project that I am trying to develop.

Thanks again!
Jose

On 5 Jul, 15:23, Jose Antonio <jurig...@gmail.com> wrote:
> Hi Rune

> I want the code to run as fast as possible because I am using it to perform a series of operations on a set of images and I want to check the results until I code everything properly.

Use smaller data sets (smaller images, fewer images)
for implementation checks.

> Furthermore, the algorithm should be efficient, since it is not meant to be a long postprocessing stage in the project that I am trying to develop.

This boils down to a cost/benefit analysis: How much
effort does it take on your part to achieve the fast
algorithm, and what pay-offs does this provide.

If you spend 6-9 months learning C just to cut a
processing routine from 5 min to 3 min - is it
worth it in the end?

Rune

Thanks a lot again

Just used Bruno's last suggestion, and my running times are now around 2s, rather than 30s tht took with the loop.

Absolutely great!

Rune Allnor <allnor@tele.ntnu.no> wrote in message <efb4c71f-e507-4294-a5b6-1d212c68bc4f@j32g2000yqh.googlegroups.com>...

>
> If you spend 6-9 months learning C just to cut a
> processing routine from 5 min to 3 min - is it
> worth it in the end?

Learning is priceless.

Bruno

Rune

I agree with both Bruno and you. On one hand I want to finish this coding asap but, on the other hand, I am doing it for my MSc project.

Thus, the most I can learn, in general, including remembering C stuff and even how to embed it into Matlab, the best.

Thanks for your comments
Jose