Moving average implementation

[Muneer]

Hi guys,

I've been struggling for the past couple of days trying to implement a moving average in ArrayFire. I've simplified the code as much as I could to explain it:

#include <arrayfire.h>


using namespace af;


array ma(array data, array window)
{
    const int w = window.scalar<int>();
    return (data.rows(w, end) - data.rows(0, end-w))/w;
}


int main()
{
    array data = randu(10, 3);
    array data_accum = accum(data);

    af_print(data);
    af_print(data_accum);


    // Generate 4 random window sizes from 1-10
    array windows = randu(4, 1, s32) % 10;
    af_print(windows);


    array avg = ma(data_accum, windows);
    af_print(avg);


    return 0;
}

Essentially I'm trying to get an array of moving averages using different window sizes. At the moment the answer I'm getting is wrong. I tried using gfor, but I struggled a lot trying to get the seq indexing to work with my example. I can do it with a for loop but I need this to run really really really fast. Ideally I'm also looking to get rid of the .scalar() call in the ma() function too.. Intuitively I believe it should be possible.

How do I get this working and running really fast?

Kind regards,

Muneer

[Pavan Yalamanchili]

Hi Muneer,

I am not entirely sure if I understand the problem correctly, but I think this is what you need.

array rng = range(10) + 1;

array avg_accum = data_accum / rng;

af_print(avg_accum);

af_print(avg_accum(windows));

--
You received this message because you are subscribed to the Google Groups "ArrayFire Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to arrayfire-use...@googlegroups.com.
To post to this group, send email to arrayfi...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/arrayfire-users/5827398a-37c9-45cf-a3a8-67f94a527497%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Pavan Yalamanchili]

Oops, you may need to do another step:

array avg_moving = diff1(join(constant(0, 1, 1, avg_accum.type()), avg_accum)));

[Pavan Yalamanchili]

ACtually its buggy. Give me some time to figure this out.

[Pavan Yalamanchili]

Having different window sizes is going to be hard to do in parallel. For a single window size, it is a simple convolution.

What are the typical number of winodws you are looking at ?

[Muneer]

Hi, thanks very much for having a look at this :-)

For moving averages in particular I'd be using windows in the range of 1-200. I'll likely be needing about 90%+ of those to be calculated. The data always stays the same throughout the program run (~90k rows 1D).

I agree I can do it in O(n) by a GPU call per window size in for loop over the unique window sizes. Was really hoping I could do this in constant time though..

The reason this design is so important to me is because I'll be using lots of different formulas, ie. not just moving averages. However they are all based on the concept of calculation over different moving window periods. So there will be many for loops in my code (one for each formula) if I go down the for loop route, which I'm trying to avoid..

Does ArrayFire support asynchronous evaluation? eg. If perhaps I gave ArrayFire a semaphore in the .eval(), it could increment it and return immediately (executing in the background).. then I can keep piling more work onto it and then wait for the results at the end with a .sync(semaphore) or something?

I guess I could write a caching class that lazy evaluates the formula / window combination I'm requesting in the code and keeps the result in host memory. Could also pre-calculate the entire formula / window combinations space and read those numbers from disk when I load the data. It will be a big cache, but I can do it on EC2.

What would be the best way to do this different windows implementation?

[Pavan Yalamanchili]

Hi,

ArrayFire is non blocking but it is not asynchronous currently. We are thinking of ways to make this happen. Please follow this issue for more details:

https://github.com/arrayfire/arrayfire/issues/113

> For moving averages in particular I'd be using windows in the range of 1-200. I'll likely be needing about 90%+ of those to be calculated. The data always stays the same throughout the program run (~90k rows 1D).

Does that mean the data is 90K rows x 1 column? If that is the case then we can pad the convolution windows with zeros to generate windows of the same size. All of the operations can then be done in parallel.

--

Pavan

To view this discussion on the web visit https://groups.google.com/d/msgid/arrayfire-users/89c0dd09-b0df-49bb-bd33-c61bb9629ebf%40googlegroups.com.

[Muneer]

Yes it's 90k rows x 1 column

I'm not sure how to pad the window sizes and convolve them to produce the result.. Please could you demonstrate how it looks in code?

[Pavan Yalamanchili]

Hi Muneer,

You can look at the code here for an example: https://gist.github.com/pavanky/167a4f60089d0dcd6d3d

At the boundaries, I assumed "0" for the missing pieces. We can probably change that to match what you want.

To view this discussion on the web visit https://groups.google.com/d/msgid/arrayfire-users/b4232845-9b04-4b53-8059-3012b809a893%40googlegroups.com.

[Muneer]

ahh I see what you've done here! That's a very clever solution. Thank you so much for your help :-)

[Pavan Yalamanchili]

Hi Muneer,

The windows need to be centered properly to get the right results. I am working on updating the gist. I will let you know when it is fixed.

To view this discussion on the web visit https://groups.google.com/d/msgid/arrayfire-users/2228b0b0-9870-4ac2-ac09-cd761f62f7d3%40googlegroups.com.