Параллелизм вложенных циклов OpenMP

Я использую OpenMP, и у меня проблема с неправильными результатами.

Вот код:

    #pragma omp parallel shared(L,nthreads,chunk) private(tid,i,j){
        tid = omp_get_thread_num();
        if (tid == 0)
        {
            nthreads = omp_get_num_threads();
            printf("Starting matrix multiple example with %d threads\n",nthreads);
            printf("Initializing matrices...\n");
        }

        #pragma omp for schedule (static, chunk) 
        for( i=0; i<SIZE_A;i++){
            for( j=0; j<SIZE_B;j++){
                if(A[i]==B[j]){
                    if(i==0 || j==0)
                        L[i][j]=1;
                    else
                        L[i][j] = L[i-1][j-1] + 1;
                }
                // or reset the matching score to 0
                else
                    L[i][j]=0;
            }
        }
    }

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

Большое спасибо!


person vanste25    schedule 06.05.2012    source источник


Ответы (1)


У вас есть зависимость данных цикла:

L[i][j] = L[i-1][j-1] + 1;

Здесь, если взаимодействия i и i-1 были назначены разным потокам, то нет гарантии, что первый поток завершится до того, как запустится второй, и, следовательно, второй поток прочитает неверное (все еще не обновленное) значение L[i-1][j-1]. Вы можете сделать выполнение упорядоченным, указав предложение ordered в директиве совместного использования omp for, но это убьет распараллеливание.

Поскольку зависимость является диагональной, вы можете переосмыслить свой алгоритм, чтобы каким-то образом пройти L по диагонали, а не по строкам.

person Hristo Iliev    schedule 06.05.2012
comment
Хм... Это самая длинная общая проблема с подстроками, решенная некоторыми парнями из Intel, и я пытался ее изменить, но рекурсивное решение очень медленное, а оптимизация не очень хорошо объяснена... Спасибо за помощь, Христо :) - person vanste25; 07.05.2012