How to rewrite a nested loop using the C++ STL algorithms?

Question

The loop is simple enough, but I just can't seem to wrap my head around using the STL algorithms to give the same nested loop below.

const int a_size = 5; // input
const int c_size = 2; // output
const int b_size = a_size * c_size; // multipliers

std::vector<float> a(a_size);
std::vector<float> b(b_size);
std::vector<float> c(c_size);

// fill a and b with data

// this nested loop
for(int i = 0; i<c_size; i++) {
    c[i] = 0.0;
    for(int k = 0; k<a_size; k++) {
        c[i] += (a[k] * b[i*a_size+k]);
    }
    c[i] = sigmoid(c[i]);
}

The reason why I would like to do this, is for the Boost.Compute library, which would do the calculations on the GPU using STL-like algorithms (std::transform, std::for_each, etc.).

It seems that one can rewrite your algorithm using matrix operations. — Siyuan Ren
– Siyuan Ren, Commented Oct 30, 2013 at 9:23
I think it is better to allow users to write arbitrary kernels in Boost.Compute - it will be much more useful. For instance via TaskGraph method which I described here. — Evgeny Panasyuk
– Evgeny Panasyuk, Commented Oct 30, 2013 at 9:26

Vlad from Moscow · Accepted Answer · 2013-10-30 09:48:39Z

8

in fact the nested loop is algorithm std::inner_product.

auto first = std::begin( b );
auto increment = std::distance( std::begin( a ), std::end( a ) );
//,,

c[i] = std::inner_product( std::begin( a ), std::end( a ), first, 0 );
std::advance( first, increment );

Instead of the outer loop you could use algorithm std::generate.

answered Oct 30, 2013 at 9:48

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Evgeny Panasyuk · Accepted Answer · 2013-10-30 12:14:32Z

6

I came up with:

auto i = 0;
generate(begin(c), end(c), [&i, &a, &b]
{
    return sigmoid(inner_product
    (
        begin(a), end(a),
        begin(b) + distance(begin(a), end(a)) * i++, 0.f
    ));
});

But it does not look pretty well - probably in such case I would prefer to write my own algorithm.

Or use matrix-form. With Eigen library it will became:

MatrixXd b;
VectorXd a, c;
// ...
c = (b*a).unaryExpr(sigmoid);

edited Oct 30, 2013 at 12:14

answered Oct 30, 2013 at 10:00

Evgeny Panasyuk

9,2191 gold badge37 silver badges57 bronze badges

4 Comments

user1973386 Over a year ago

It will take me a while to digest that. Never heard of Eigen, does it support computations on the GPU?

Evgeny Panasyuk Over a year ago

@user1973386 AFAIK - for the moment it does not support GPU. Though it does vectorization via intrinsics (SSE2, etc). I have just found following thing: gpumatrix - "A matrix and array library on GPU with interface compatible with Eigen" - I think it worth to look too.

user1973386 Over a year ago

Too bad it does not support OpenCL just yet, but it's planned. I'll keep track of that library :).

Evgeny Panasyuk Over a year ago

@nijansen As I understand from code-sample - It just provides types similar to GLSL for C++, but not does computations on GPU.

Collectives™ on Stack Overflow

How to rewrite a nested loop using the C++ STL algorithms?

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related