Why is OpenMP slow in this case?

Question

I am trying to understand why OpenMP works the way it does in the following example.

#include <omp.h>
#include <iostream>
#include <vector>
#include <stdlib.h>

void AddVectors (std::vector< double >& v1,
                 std::vector< double >& v2) {

    size_t i;

#pragma omp parallel for private(i)
    for (i = 0; i < v1.size(); i++) v1[i] += v2[i];

}


int main (int argc, char** argv) {

    size_t N1 = atoi(argv[1]);

    std::vector< double > v1(N1,1);
    std::vector< double > v2(N1,2);

    for (size_t i = 0; i < N1; i++) AddVectors(v1,v2);

    return 0;

}

I first compiled the code above without enabling OpenMP (by omitting -fopenmp on the compiling flags). The execution time for N1 = 10000 was 0.1s. Enabling OpenMP makes the execution time go beyond 1 minute. I stopped it before it was done (got tired of waiting...).

I am compiling the code as below:

g++ -std=c++0x -O3 -funroll-loops -march=core2 -fomit-frame-pointer -Wall -fno-strict-aliasing -o main.o -c main.cpp

g++ main.o -o main

Not all these flags are necessary here but I'm using them on the project I'm trying to parallelize and I use those flags there. That's why I decided to leave them here. Also, I add -fopenmp to enable OpenMP on the compilation.

Does anybody know what's going wrong? Thank you!

Answer 1

I have tried the same example on Visual Studio 2008. I did two modification to your code example, and it runs roughly 3 times faster with OpenMP, than without OpenMP.

Without being able to confirm it on GCC, the problem might be in main loop the function AddVectors is called, and each time it has to perform a "fork" operation, and this will take some measurable time. So if you have N1 = 10000, it has to spawn 10000 "fork" operations.

I have attached your own code snippet modified only to make it work under Visual Studio, and I added a print statement in the end to avoid the compiler removing all the code.

#include <omp.h>
#include <iostream>
#include <vector>
#include <stdlib.h>

void AddVectors (std::vector< double >& v1,
                 std::vector< double >& v2) {

    #pragma omp parallel for
    for (int i = 0; i < static_cast<int>(v1.size()); i++) v1[i] += v2[i];

}


int main (int argc, char** argv) {

    size_t N1 = atoi(argv[1]);

    std::vector< double > v1(N1,1);
    std::vector< double > v2(N1,2);

    for (size_t i = 0; i < N1; i++) AddVectors(v1,v2);


    printf("%g\n",v1[0]);
    return 0;

}

Answer 2

The problem is with array type you are using.

A vector is a container. It is a structure which stores several information like size, begin, end etc; and has several in-build function, where operator [] is one of them used to access the data. As a result the cache lines which tend to load say for index "i" of the vector V, loads the element V[i] and some information which is not being used in the code.

On the contrary, if you use classical arrays (dynamic/static), the operator [] results in loading only the data elements. As a result a cache line (usually 64 bytes long) will load 8 elements of this double array (size of double = 8 bytes).

See difference between _mm_malloc and malloc for enhancing data alignment.

@Mr Fooz I am not sure about that. Lets compare the performance results for both the cases:

4 Threads on i7 processor

Array Time Taken.: 0.122007 | Repeat: 4 | MFlops: 327.85

Vector Time Taken: 0.101006 | Repeat: 2 | MFlops: 188.669

I force the runtime to be more than 0.1sec, so the code repeats itself. The main loop:

const int N = 10000000;
timing(&wcs);
for(; runtime < 0.1; repeat*=2)
{
    for(int r = 0; r < repeat; r++)
    {
        #pragma omp parallel for
        for(int i = 0; i < N; i++)
        {
            A[i] += B[i];
        }
        if(A[0]==0) dummy(A[0]);
    }
    timing(&wce);
    runtime = wce-wcs;
}

MFLops: ((N*repeat)/runtime)/1000000

Answer 3

May be g++ optimized out whole AddVectors calls? Try to return last v1 element and store it in volatile variable.