Как реализовать MPI_MINLO C в OpenMP? - PullRequest
Новая
       66

Как реализовать MPI_MINLO C в OpenMP?

0 голосов
/ 13 марта 2020

Как я могу вычислить глобальный минимум и индекс, привязанный к минимальному значению в OpenMP, используя язык C?

Можно ли получить реальную выгоду с несколькими потоками? 

// thread-private result
double mymin = DBL_MAX;
double myloc = SIZE_MAX;

// bottleneck parallel part
#pragma omp for reduction(min:gmin)
for (size_t i=0; i<n; ++i) {
    if (v[i] < mymin) {
        mymin = v[i];
        gmin = v[i];
        myloc = i;
    }
}

if(gmin == mymin) {
// find global result
  #pragma omp single
  {
     gloc = myloc;
  }
}

1 Ответ

0 голосов
/ 16 марта 2020

Да, вы можете получить выгоду от больших проблем, используя OpenMP здесь. Преимущество будет реализовано, когда входной сигнал достаточно велик, чтобы ограничивать пропускную способность памяти, а несколько потоков обеспечивают более высокую пропускную способность памяти. Это почти наверняка будет ограничено входными данными, которые не помещаются в последний уровень кэша.

Я включил простой пример программы о том, как это сделать. Эта реализация использует старые и широко доступные функции. Может быть возможно использовать определяемые пользователем сокращения OpenMP 5.0, но я сомневаюсь, что это обеспечивает заметное преимущество в производительности, и вы, вероятно, обнаружите, что многие реализации не поддерживают эту функцию.

Обратите внимание, что мой пример программы не поддерживает Время повторных тестов и никакой статистики по таймингу. Таким образом, вы не должны считать это высоко научным c тестом. Тем не менее, он демонстрирует явное преимущество на моем двухъядерном ноутбуке для массива 100M, как и ожидалось. 

$ make minloc && ./minloc 100000000
icc -O3 -qopenmp -std=c11 minloc.c -o minloc
MINLOC of 100000000 elements with 4 threads
OpenMP: dt=0.076681, gmin=0.000000, gloc=4022958
Sequential: dt=0.157333, gmin=0.000000, gloc=4022958
SUCCESS

Соответствующий отрывок 

        // thread-private result
        double mymin = DBL_MAX;
        double myloc = SIZE_MAX;

        // bottleneck parallel part
        #pragma omp for
        for (size_t i=0; i<n; ++i) {
            if (v[i] < mymin) {
                mymin = v[i];
                myloc = i;
            }
        }

        // write thread-private results to shared
        tmin[me] = mymin;
        tloc[me] = myloc;
        #pragma omp barrier

        // find global result
        #pragma omp master
        {
            for (int i=0; i<nt; ++i) {
                if (tmin[i] < gmin) {
                    gmin = tmin[i];
                    gloc = tloc[i];
                }
            }
        }

Полный пример программы 

#include <stdio.h>
#include <stdlib.h>

#include <float.h>

#include <omp.h>

int main(int argc, char* argv[])
{
    size_t n = (argc > 1) ? atol(argv[1]) : 100;

    double * v = malloc(n * sizeof(double));
    if (v==NULL) abort();

    // g = global
    double gmin = DBL_MAX;
    size_t gloc = SIZE_MAX;

    const int mt = omp_get_max_threads();

    printf("MINLOC of %zu elements with %d threads\n", n, mt);

    // t = thread
    double * tmin = malloc(mt * sizeof(double));
    size_t * tloc = malloc(mt * sizeof(size_t));
    if (tmin==NULL || tloc==NULL) abort();

    for (int i=0; i<mt; ++i) {
        tmin[i] = DBL_MAX;
        tloc[i] = SIZE_MAX;
    }

    double dt = 0.0;

    #pragma omp parallel firstprivate(n) shared(v, tmin, tloc, gmin, gloc, dt)
    {
        const int me = omp_get_thread_num();
        const int nt = omp_get_num_threads();

        unsigned int seed = (unsigned int)me;
        srand(seed);
        #pragma omp for
        for (size_t i=0; i<n; ++i) {
            // this is not a _good_ random number generator, but it does not matter for this use case
            double r = (double)rand_r(&seed) / (double)RAND_MAX;
            v[i] = r;
        }

        double t0 = 0.0;

        #pragma omp barrier
        #pragma omp master
        {
            t0 = omp_get_wtime();
        }

        // thread-private result
        double mymin = DBL_MAX;
        double myloc = SIZE_MAX;

        // bottleneck parallel part
        #pragma omp for
        for (size_t i=0; i<n; ++i) {
            if (v[i] < mymin) {
                mymin = v[i];
                myloc = i;
            }
        }

        // write thread-private results to shared
        tmin[me] = mymin;
        tloc[me] = myloc;
        #pragma omp barrier

        // find global result
        #pragma omp master
        {
            for (int i=0; i<nt; ++i) {
                if (tmin[i] < gmin) {
                    gmin = tmin[i];
                    gloc = tloc[i];
                }
            }
        }

        #pragma omp barrier
        #pragma omp master
        {
            double t1 = omp_get_wtime();
            dt = t1 - t0;
        }

#if 0
        #pragma omp critical
        {
            printf("%d: mymin=%f, myloc=%zu\n", me, mymin, myloc);
            fflush(stdout);
        }
#endif
    }

    printf("OpenMP: dt=%f, gmin=%f, gloc=%zu\n", dt, gmin, gloc);
    fflush(stdout);

    // sequential reference timing
    {
        double t0 = omp_get_wtime();

        double mymin = DBL_MAX;
        double myloc = SIZE_MAX;

        for (size_t i=0; i<n; ++i) {
            if (v[i] < mymin) {
                mymin = v[i];
                myloc = i;
            }
        }

        gmin = mymin;
        gloc = myloc;

        double t1 = omp_get_wtime();
        dt = t1 - t0;
    }

    printf("Sequential: dt=%f, gmin=%f, gloc=%zu\n", dt, gmin, gloc);
    fflush(stdout);

    // debug printing for toy inputs
    if (n<100) {
        for (size_t i=0; i<n; ++i) {
            printf("v[%zu]=%f\n", i , v[i]);
        }
        fflush(stdout);
    }

    free(v);

    printf("SUCCESS\n");

    return 0;
}
...