Как добиться линейной скорости с более чем 3-мя потоками в моем коде?

Question

Я работаю над кодом в openMP.Код должен печатать в файле все простые числа от 2 до 1000000. Последовательный алгоритм занимает 150 секунд, чтобы выполнить все вычисления, с двумя потоками export OMP_NUM_THREADS=2 код выполняется за 81 секунду (что означает ускорение, равное 1,85),Но до 2 export OMP_THREADS=3,4 потоков скорость не меняется.оно все равно равно ~ 1,8.

Я также изменил расписание без изменений.

Где мой код primes.cpp .Вы можете скопировать и вставить его в свой редактор и скомпилировать его с помощью следующих команд строк:

~$ g++ primes.cpp -o primes -fopenmp

изменить номер процесса на 2 (или как вам больше нравится)

~$ export OMP_NUM_THREADS=2

изменить расписание задач (статическое, динамическое, управляемое)

~$ export OMP_SCHEDULE=dynamic,100000

и запустить его с помощью

~$ ./primes

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <time.h>
#include <omp.h>

#define SIZE 1000000

using namespace std;



int main(){
    // code permettant derecuperer dans un fichier la liste des
    // nombres premiers entre O et SIZE

    // variables
    int cprime;
    int chunk;
    int lap, loop, i;
    int isprime;
    int count;

    FILE * file;
    char * filename;

    time_t t1;
    vector<int>primelist;

    int thread_num;
    //omp_sched_t schedule;

    // initialisation
    t1 = time(NULL);
    chunk = 100000;
    count = 0;

    filename = (char *) malloc(sizeof(char)*100);
    strcpy(filename, "primes.txt");

    file = fopen(filename, "w");

    // ------------- ALGORITHME ---------------
    #pragma omp parallel private(thread_num)
    {
      thread_num = omp_get_thread_num();

      if(thread_num == 0) 
          printf("%d processor are available for work\n", omp_get_num_threads());      

      #pragma omp barrier
      #pragma omp critical
      {
     printf("I'm processor %d ready for work\n", thread_num);
      }

    }

    #pragma omp parallel for private(cprime, loop, isprime) schedule(runtime)     shared(primelist) reduction(+:count)
    for(cprime = 2; cprime < SIZE; cprime++){

        loop = 1;
        isprime = 1;

        // looking if it's a prime number
        while((++loop<cprime) && isprime){
            if(cprime % loop == 0) isprime = 0;
        }

        if(isprime) {    
             #pragma omp critical
          {
            primelist.push_back(loop);
          }   

          count++;
        }

        #pragma omp critical 
        {
          if(cprime % chunk == 0) 
            printf("Indicator from thread %d current(size N) : %d\n",omp_get_thread_num(),     cprime);
        }

    }

    sort(primelist.begin(), primelist.end());
    lap = primelist.size();

    for(i = 0; i < lap; i++)
      fprintf(file, "%d\n", primelist[i]);

    fclose(file);

    printf("%d primes where discover between 0 and %d, duration of the operation         %d\n", count, SIZE, (int) difftime(time(NULL), t1));

    return 0;

}

Информация о среде выполнения

На моем компьютере 4 процессора

Я проверил это в файле /proc/cpuinfo, откуда идет описаниеprocessor : 0 до processor 3.все Intel® Core ™ TM CPU M 600 @ 2,53 ГГц

Спасибо за любой ответ

Answer 1

Проверьте процессор на компьютере, на котором вы его запускаете. Если в нем не более двух ядер, вы вряд ли увидите значительное улучшение за пределами двух потоков.

Будьте внимательны при учете гиперпоточных процессоров, которые имеют вдвое больше ядер, чем в действительности.

Answer 2

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

Но есть также несколько проблем с вашим кодом и тем, как вы измеряете время выполнения. Оба могут создать впечатление плохого ускорения.

О вашем коде Я должен сказать, что синхронизация (в вашем случае наличие критического раздела) всегда значительно замедляет ваше программное обеспечение. У меня уже была эта проблема несколько раз. Но в отличие от вашей проблемы я заранее знал, сколько элементов у меня будет в моем векторе. Таким образом, я мог сначала изменить размер вектора и поместить элементы в правильное положение, не добавляя их в вектор. Это значительно ускоряет код для многих процессоров. Однако у меня нет аналогичного решения вашей проблемы.

В вашем коде также есть небольшая ошибка: ваша переменная count не будет иметь предсказуемого значения после нескольких присваиваний. Он также должен быть в критическом разделе (или здесь вы можете использовать операцию atomic). Гораздо лучшим подходом было бы сделать эту переменную OpenMP private в цикле for и использовать сокращение с +, например:

#pragma omp parallel for private(cprime, loop, isprime, count) reduction (+: count) schedule(runtime)

Это даст правильный результат для count после завершения цикла for.

Я не очень понимаю, почему вы используете schedule(runtime) в своем for заявлении или что на самом деле происходит здесь. Но вы должны знать, что вы перезаписали расписание, которое вы ранее установили, с помощью оператора export.

А теперь возникает проблема с синхронизацией вашего приложения: вы синхронизируете все приложение, а не только параллель для цикла. В этом случае вы должны учитывать, что вы также включаете последовательную сортировку. Это ограничивает скорость, которую вы можете ожидать от своего приложения. Кроме того, для начального теста последовательного приложения вы должны включить OpenMP только с одним потоком; это будет медленнее, чем приложение без OpenMP, потому что OpenMP - даже с одним потоком - будет иметь небольшие накладные расходы. Это может дать вам ожидаемое 2-кратное ускорение для двух потоков.

Answer 3

Первая слепая вещь, которую я бы сделал, - это использование профилировщика OpenMP, как в

http://www.vi -hps.org / пул данных / страница / 18 / fuerlinger.pdf

, чтобы выяснить, если что-то не так с параллелизмом. Возможно, вы серьезно боретесь с откатом в середине всего этого, и это требует времени. Или, может быть, цикл for не распараллелен должным образом, хотя быстрый взгляд не говорит мне, что с ним что-то не так.

Далее, не забудьте сравнить ваш код с самой быстрой последовательной реализацией. Есть один в Кнуте, TaOCP, основанный на сите, которое трудно , чтобы победить с помощью параллельного алгоритма.