C, OpenMP: Как я могу улучшить параллелизацию тройного цикла?

Я пытаюсь распараллелить алгоритм Floyd-Warshall, используя OpenMP (в основном редактирование 2D-массива на месте), но я сомневаюсь, что делаю это наилучшим образом, вот что у меня есть до сих пор:

    #pragma omp parallel for private(i, j, k) shared(g)
    for ( i = 0; i < n; i++ ) {
        for ( j = 0; j < n; j++ ) {
            for ( k = 0; k < n; k++ ) {
                g->A[j][k] = imin( g->A[j][k], g->A[j][i] + g->A[i][k] );
            }
        }
    }

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

Также, если у кого-нибудь есть какие-либо предложения по другим технологиям, которые будут использоваться для распараллеливания, я внимательно слушаю. Я думал о MPI, но мне нужно было бы сделать всю мою функцию main параллельной, верно?

Спасибо.

ИЗМЕНИТЬ

Приведенный выше код не работает, ответы ниже показывают, почему.


c openmp parallel-processing nested-loops
person Griffin    schedule 22.07.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Распараллелить алгоритм не так просто. См. примечания здесь http://www.mcs.anl.gov/~itf/dbpp/text/node35.html для получения информации о параллельном запуске. Если у вас небольшое количество процессоров (двух-, четырех-, восьмиядерные машины), то Parallel Floyd 1, вероятно, подойдет вам. Если у вас огромное количество процессоров (действительно потрясающий графический процессор, сетчатый компьютер), тогда Parallel Floyd 2 может быть лучше.

person Charles    schedule 22.07.2011
comment
Спасибо за информацию, Чарльз, не могли бы вы помочь мне немного лучше разобрать это в моей голове? Насколько я понимаю, вы разбиваете строки на куски R/N, где R — число или строки, а N — количество потоков/процессоров, затем вы транслируете «граничные» строки другим процессам. Правильно ли я это понимаю, и возможно ли это вообще с OpenMP? Благодарю. - person Griffin; 22.07.2011
comment
Это должно быть возможно, да. См. stackoverflow.com/q/6030658/341362 для кода OpenMP (решение другой проблемы), который, похоже, использует методы, которые вы понадобится. - person Charles; 22.07.2011