LINUX.ORG.RU

Низкая производительность вычислений в openMP

 , , ,


0

2

Доброго времени суток.

Решил я на досуге к своей программе добавить параллельность на базе openMP. В результате никакого ускорения я не получил (а даже наоборот). Сделал я для проверки тестовый пример (подобный тем, которыми в изобилии интернет):

#include <iostream>
#include <boost/timer.hpp>

#include <omp.h>

using namespace std;

long single_thread(long a[], const long &niter)
{
    long sum = 0;
    for (long i = 0; i < niter; i++)
    {
        for (long j = 0; j < niter; j++)
        {
            for (long k = 0; k < niter; k++)
            {
                sum += (a[i] + a[j] + a[k]);
            }
        }
    }
    return sum;
}

long omp_atomic(long a[], const long &niter, const int &num_treads)
{
    long sum = 0;
    omp_set_num_threads(num_treads);

#pragma omp parallel for
    for (long i = 0; i < niter; i++)
    {
        for (long j = 0; j < niter; j++)
        {
            for (long k = 0; k < niter; k++)
            {
#pragma omp atomic
                sum += (a[i] + a[j] + a[k]);
            }
        }
    }
    return sum;
}

long omp_reduction(long a[], const long &niter, const int &num_treads)
{
    long sum = 0;
    omp_set_num_threads(num_treads);

#pragma omp parallel for reduction(+: sum)
    for (long i = 0; i < niter; i++)
    {
        for (long j = 0; j < niter; j++)
        {
            for (long k = 0; k < niter; k++)
            {
                sum = sum + (a[i] + a[j] + a[k]);
            }
        }
    }
    return sum;
}

int main()
{
    boost::timer t;
    const long niter = 1000;
    long a [niter];
    long sum = 0;



    for (long i = 0; i < niter; i++)
    {
        a[i] = i;
    }

    t.restart();
    sum = single_thread(a, niter);
    cout << "Iterative. Sum: " << sum << " time: " << t.elapsed() << endl;

    t.restart();
    sum = omp_atomic(a, niter, 2);
    cout << "Atomic, 2 threads. Sum: " << sum << " time: " << t.elapsed() << endl;

    t.restart();
    sum = omp_atomic(a, niter, 4);
    cout << "Atomic, 4 threads. Sum: " << sum << " time: " << t.elapsed() << endl;

    t.restart();
    sum = omp_reduction(a, niter, 2);
    cout << "Reduction, 2 threads. Sum: " << sum << " time: " << t.elapsed() << endl;

    t.restart();
    sum = omp_reduction(a, niter, 4);
    cout << "Reduction, 4 threads. Sum: " << sum << " time: " << t.elapsed() << endl;

    return 0;
}

В итоге получил следующие результаты:

./openmp_test 
Iterative. Sum: 1498500000000 time: 0.98
Atomic, 2 threads. Sum: 1498500000000 time: 60.85
Atomic, 4 threads. Sum: 1498500000000 time: 117.51
Reduction, 2 threads. Sum: 1498500000000 time: 11.04
Reduction, 4 threads. Sum: 1498500000000 time: 24.45

В качестве тестовой выступает машина под управлением openSuse:

cat /proc/cpuinfo
processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 42
model name	: Intel(R) Core(TM) i3-2310M CPU @ 2.10GHz
...

Может кто-нибудь сталкивался с подобной проблемой, как лечили?

★★★

Блокировки всё съели. Лечить переписыванием алгоритма. Каждый поток должен быть без блокировок и при этом делать какую-о ощутимую работу, используя данные из кеша _неоднократно_.

Reset ★★★★★ ()

на моем проце вообще вот так получилось

$ ./a.out
Iterative. Sum: 1498500000000 time: 0.57
Atomic, 2 threads. Sum: 1498500000000 time: 143.11
Atomic, 4 threads. Sum: 1498500000000 time: 325.13
Reduction, 2 threads. Sum: 1498500000000 time: 0.58
Reduction, 4 threads. Sum: 1498500000000 time: 0.57

Reset ★★★★★ ()

1) постоянные блокировки через atomic - конец производительности :)

2) цикл у тебя слишком короткий и легкий, одно ядро успевает прогнать его так же быстро, как и несколько тредов (+ оверхед на их создание, запуск-остановку, синхронизацию). Делай в теле цикла какие-нибудь тяжелые вычисления - получишь ускорение. А так - стрельба из пушки по воробъям. Ты бы еще через MPI на кластере считал :)))

htower_ ★★ ()
Ответ на: комментарий от htower_

Утяжелил вычисления и вместо atomic добавил две параллельные секции без блокировок:

#include <iostream>
#include <boost/timer.hpp>

#include <math.h>

#include <omp.h>

using namespace std;

double single_thread(double a[], const int &niter)
{
    double sum = 0.0;
    double x;
    for (int i = 0; i < niter; i++)
    {
        for (int j = 0; j < niter; j++)
        {
            for (int k = 0; k < niter; k++)
            {
                x = sin(a[i]) * cos(a[j]) * sin(a[k]);
                sum += x;
            }
        }
    }
    return sum;
}

double omp_reduction(double a[], const int &niter, const int &num_treads)
{
    double sum = 0;
    double x;
    omp_set_num_threads(num_treads);

#pragma omp parallel for reduction(+:sum) shared(a) private(x)
    for (int i = 0; i < niter; i++)
    {
        for (int j = 0; j < niter; j++)
        {
            for (int k = 0; k < niter; k++)
            {
                x = sin(a[i]) * cos(a[j]) * sin(a[k]);
                sum = sum + x;
            }
        }
    }
    return sum;
}

double omp_sections(double a[], const int &niter)
{
    double sum1 = 0;
    double sum2 = 0;

#pragma omp parallel sections num_threads(2)
    {
#pragma omp section
        {
            for (int i = 0; i < niter / 2; i++)
            {
                for (int j = 0; j < niter; j++)
                {
                    for (int k = 0; k < niter; k++)
                    {
                        double x = sin(a[i]) * cos(a[j]) * sin(a[k]);
                        sum1 += x;
                    }
                }
            }
        }
#pragma omp section
        {
            for (int i = niter / 2; i < niter ; i++)
            {
                for (int j = 0; j < niter; j++)
                {
                    for (int k = 0; k < niter; k++)
                    {
                        double x = sin(a[i]) * cos(a[j]) * sin(a[k]);
                        sum2 += x;
                    }
                }
            }
        }
    }
    return sum1 + sum2;
}

int main()
{
    boost::timer t;
    const int niter = 2000;
    double a [niter];
    double sum = 0;



    for (long i = 0; i < niter; i++)
    {
        a[i] = (double)i / (double)niter;
    }

    t.restart();
    sum = single_thread(a, niter);
    cout << "Iterative. Sum: " << sum << " time: " << t.elapsed() << endl;

    t.restart();
    sum = omp_reduction(a, niter, 2);
    cout << "Reduction, 2 threads. Sum: " << sum << " time: " << t.elapsed() << endl;

    t.restart();
    sum = omp_reduction(a, niter, 4);
    cout << "Reduction, 4 threads. Sum: " << sum << " time: " << t.elapsed() << endl;

    t.restart();
    sum = omp_sections(a, niter);
    cout << "Two sections. Sum: " << sum << " time: " << t.elapsed() << endl;

    return 0;
}

Получил следующие результаты.

./openmp_test 
Iterative. Sum: 1.42146e+09 time: 180.21
Reduction, 2 threads. Sum: 1.42146e+09 time: 185.55
Reduction, 4 threads. Sum: 1.42146e+09 time: 302.89
Two sections. Sum: 1.42146e+09 time: 507.55

Взял пример из статьи http://www.viva64.com/en/a/0056/ , в которой получили двукратный прирост используя reduction на двух потоках (правда они эксперимент, судя по заголовочному файлу, проводили под оффтопиком). Те же функции у меня дали результаты, в которых нет увеличения производительности.

Function. Result = 2.87305e+08 time = 11.9
FunctionOpenMP. Result = 2.873e+08 time = 11.93
FixedFunctionOpenMP. Result = 2.87305e+08 time = 28.57
OptimizedFunction. Result = 2.87305e+08 time = 11.93

Genuine ★★★ ()

boost::thread

Сделал аналогичный тест на базе boost::thread.

#include <iostream>
#include <boost/timer.hpp>
#include <boost/thread.hpp>

using namespace std;

class Calc
{
private:
    double *a;
    int niter;
    int start;
    int end;
    double sum;
public:
    Calc(double *a_ptr, const int &niter_ref, const int &start_ref, const int &end_ref)
    {
        a = a_ptr;
        niter = niter_ref;
        start = start_ref;
        end = end_ref;
        sum = 0.0;
    }
    void run()
    {
        double x;
        for (int i = start; i < end; i++)
        {
            for (int j = 0; j < niter; j++)
            {
                for (int k = 0; k < niter; k++)
                {
                    x = sin(a[i]) * cos(a[j]) * sin(a[k]);
                    sum += x;
                }
            }
        }
    }
    double Sum()
    {
        return sum;
    }
};

double single_thread(double a[], const int &niter)
{
    double sum = 0.0;
    double x;
    for (int i = 0; i < niter; i++)
    {
        for (int j = 0; j < niter; j++)
        {
            for (int k = 0; k < niter; k++)
            {
                x = sin(a[i]) * cos(a[j]) * sin(a[k]);
                sum += x;
            }
        }
    }
    return sum;
}

int main()
{
    boost::timer t;
    const int niter = 2000;
    double a [niter];
    double sum = 0;
    for (long i = 0; i < niter; i++)
    {
        a[i] = (double)i / (double)niter;
    }

    t.restart();
    sum = single_thread(a, niter);
    cout << "Serial. Sum: " << sum << " time: " << t.elapsed() << endl;

    Calc c1(a, niter, 0, niter / 2);
    Calc c2(a, niter, niter / 2, niter);
    t.restart();
    boost::thread calculationThread1(boost::bind( &Calc::run, &c1 ));
    boost::thread calculationThread2(boost::bind( &Calc::run, &c2 ));
    calculationThread1.join();
    calculationThread2.join();
    cout << "Two boost threads. Sum: " << c1.Sum() + c2.Sum() << " time: " << t.elapsed() << endl;
    return 0;
}
Результат не порадовал:
./boost_thread_test 
Serial. Sum: 1.42146e+09 time: 180.1
Two boost threads. Sum: 1.42146e+09 time: 494.82

Genuine ★★★ ()
Ответ на: boost::thread от Genuine
#include <stdio.h>
#include <math.h>
#include <omp.h>
#include <sys/time.h>

#define N 10000

long long gettimeus()
{
    struct timeval tv;

    gettimeofday( &tv, NULL );
    return (long long) tv.tv_sec * 1000000LL + (long long) tv.tv_usec;
}

double test()
{
    double sum = 0;
    for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	    sum += sin(i) + cos(j);

    return sum;
}

double test_omp()
{
    double sum = 0;
    #pragma omp parallel for reduction(+: sum)
    for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	    sum += sin(i) + cos(j);

    return sum;
}


int main()
{
    double res1, res2;
    long long t0, t1, t2;
    res1 = res2 = 0.0;

    t0 = gettimeus();
    res1 = test();
    t1 = gettimeus();
    res2 = test_omp();
    t2 = gettimeus();

    printf("single thread; sum = %20.15e; exec time = %10.2f ms\n", res1, (t1 - t0) / 1000.0);
    printf("       openMP; sum = %20.15e; exec time = %10.2f ms\n", res2, (t2 - t1) / 1000.0);
    return 0;
}

Компилируем:

gcc -std=c99 -lm -fopenmp omp_test.c -o omp_test

И запускаем:

OMP_NUM_THREADS=1 ./omp_test
single thread; sum = 2.635871401590270e+04; exec time =    7046.94 ms
       openMP; sum = 2.635871401590270e+04; exec time =    7005.45 ms

OMP_NUM_THREADS=2 ./omp_test
single thread; sum = 2.635871401590270e+04; exec time =    7072.08 ms
       openMP; sum = 2.635871401590936e+04; exec time =    3697.22 ms

OMP_NUM_THREADS=3 ./omp_test
single thread; sum = 2.635871401590270e+04; exec time =    7048.74 ms
       openMP; sum = 2.635871401590335e+04; exec time =    2879.15 ms

OMP_NUM_THREADS=4 ./omp_test
single thread; sum = 2.635871401590270e+04; exec time =    7038.30 ms
       openMP; sum = 2.635871401591186e+04; exec time =    2350.24 ms

Железка, на которой пускалось:

cat /proc/cpuinfo | grep "model name"
model name      : Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz
model name      : Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz
model name      : Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz
model name      : Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz

htower_ ★★ ()
Ответ на: комментарий от htower_

Добавление ключика -O3 дает такую картину:

OMP_NUM_THREADS=4 ./omp_test
single thread; sum = 2.635871401590270e+04; exec time =    3883.94 ms
       openMP; sum = 2.635871401591186e+04; exec time =    1247.25 ms

htower_ ★★ ()
Ответ на: комментарий от htower_

При использовании #pragma omp parallel for reduction(+: sum) у меня аналогичная картина.

Как выяснилось, основная проблема была в использовании boost::timer для замера потраченного времени (замена последнего на omp_get_wtime() существенно увеличила производительность).

Итоговый код получился следующий.

#include <iostream>
#include <math.h>
#include <omp.h>

using namespace std;

double single_thread(double a[], const int &niter)
{
    double sum = 0.0;
    double x;
    for (int i = 0; i < niter; i++)
    {
        for (int j = 0; j < niter; j++)
        {
            for (int k = 0; k < niter; k++)
            {
                x = sin(a[i]) * cos(a[j]) * sin(a[k]);
                sum += x;
            }
        }
    }
    return sum;
}

double omp_reduction(double a[], const int &niter, const int &num_treads)
{
    double sum = 0;
    omp_set_num_threads(num_treads);

#pragma omp parallel for reduction(+:sum)
    for (int i = 0; i < niter; i++)
    {
        double sai = sin(a[i]);
        for (int j = 0; j < niter; j++)
        {
            double cai = cos(a[i]);
            for (int k = 0; k < niter; k++)
            {
                double x = sai * cai * sin(a[k]);
                sum = sum + x;
            }
        }
    }
    return sum;
}

double omp_sections(double a[], const int &niter)
{
    double sum1 = 0;
    double sum2 = 0;

#pragma omp parallel sections num_threads(2)
    {
#pragma omp section
        {
            for (int i = 0; i < niter / 2; i++)
            {
                double sai = sin(a[i]);
                for (int j = 0; j < niter; j++)
                {
                    double cai = cos(a[i]);
                    for (int k = 0; k < niter; k++)
                    {
                        double x = sai * cai * sin(a[k]);
                        sum1 += x;
                    }
                }
            }
        }
#pragma omp section
        {
            for (int i = niter / 2; i < niter ; i++)
            {
                double sai = sin(a[i]);
                for (int j = 0; j < niter; j++)
                {
                    double cai = cos(a[i]);
                    for (int k = 0; k < niter; k++)
                    {
                        double x = sai * cai * sin(a[k]);
                        sum1 += x;
                    }
                }
            }
        }
    }
    return sum1 + sum2;
}

double omp_sections_reduction(double a[], const int &niter)
{
    double sum = 0;
    //    double x;

#pragma omp parallel sections reduction(+:sum) num_threads(2)
    {
#pragma omp section
        {
            for (int i = 0; i < niter / 2; i++)
            {
                double sai = sin(a[i]);
                for (int j = 0; j < niter; j++)
                {
                    double cai = cos(a[i]);
                    for (int k = 0; k < niter; k++)
                    {
                        double x = sai * cai * sin(a[k]);
                        sum += x;
                    }
                }
            }
        }
#pragma omp section
        {
            for (int i = niter / 2; i < niter ; i++)
            {
                double sai = sin(a[i]);
                for (int j = 0; j < niter; j++)
                {
                    double cai = cos(a[i]);
                    for (int k = 0; k < niter; k++)
                    {
                        double x = sai * cai * sin(a[k]);
                        sum += x;
                    }
                }
            }
        }
    }
    return sum;
}

int main()
{
    const int niter = 1000;
    double a [niter];
    double sum = 0;
    // time
    double t1, t2;

    for (long i = 0; i < niter; i++)
    {
        a[i] = (double)i / (double)niter;
    }

    t1 = omp_get_wtime();
    sum = single_thread(a, niter);
    t2 = omp_get_wtime();
    cout << "Serial. Sum: " << sum << " time: " << t2 - t1 << endl;

    t1 = omp_get_wtime();
    sum = omp_reduction(a, niter, 2);
    t2 = omp_get_wtime();
    cout << "Reduction, 2 threads. Sum: " << sum << " time: " << t2 - t1 << endl;

    t1 = omp_get_wtime();
    sum = omp_reduction(a, niter, 4);
    t2 = omp_get_wtime();
    cout << "Reduction, 4 threads. Sum: " << sum << " time: " << t2 - t1 << endl;

    t1 = omp_get_wtime();
    sum = omp_sections(a, niter);
    t2 = omp_get_wtime();
    cout << "Two sections. Sum: " << sum << " time: " << t2 - t1 << endl;

    t1 = omp_get_wtime();
    sum = omp_sections_reduction(a, niter);
    t2 = omp_get_wtime();
    cout << "Two sections (reduction). Sum: " << sum << " time: " << t2 - t1 << endl;

    return 0;
}
Результаты:
./openmp_test 
Serial. Sum: 1.77544e+08 time: 21.8642
Reduction, 2 threads. Sum: 1.62496e+08 time: 10.8724
Reduction, 4 threads. Sum: 1.62496e+08 time: 9.34711
Two sections. Sum: 9.87314e+07 time: 11.6266
Two sections (reduction). Sum: 1.62496e+08 time: 10.8513

Genuine ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.