Рекурсивные задачи OpenMP с общими данными приводят к огромному замедлению - PullRequest
Новая
       65

Рекурсивные задачи OpenMP с общими данными приводят к огромному замедлению

1 голос
/ 06 марта 2020

Я пытаюсь реализовать решатель n-queens с задачами OpenMP. Тем не менее, игровая доска настроена на основную функцию, и я даю ей функцию.

Пока у меня есть: 

bool solve_NQueens(int board[N][N], int col) 
{ 

    if (col == N) 
    { 
        // #pragma omp critical
        //     print_solution(board);
        #pragma omp critical
            SOLUTION_EXISTS = true;
        return true; 
    } 

    for (int i = 0; i < N; i++) 
    { 
        if (can_be_placed(board, i, col)) 
        {  
            int new_board[N][N];
            board[i][col] = 1; 
            copy(board, new_board);
            #pragma omp task firstprivate(col)
                solve_NQueens(new_board, col + 1); 
            board[i][col] = 0;

        }
    }

    return SOLUTION_EXISTS; 
}

Первоначальный вызов этой функции в main: 

    #pragma omp parallel if(omp_get_num_threads() > 1)
    {
        #pragma omp single
        {
            #pragma omp taskgroup
            {
                solve_NQueens(board, 0);
            }
        }
    }

Параметры: 

// these are global
#define N 14
bool SOLUTION_EXISTS = false;
// these are in main
int board[N][N]; 
memset(board, 0, sizeof(board));

Компилятор: 

gcc

Количество потоков: 4

Я использовал taskgroup, чтобы дождаться выполнения всех заданий, прежде чем получить результат, и мне пришлось скопировать игровое поле. для каждой задачи (это тяжелая работа, когда N установлен на 14, поскольку существует 356k решений).

Я пытался сделать доску firstprivate или private, использовать taskwait внутри и снаружи из l oop, используйте taskgroup внутри для l oop и так далее. Мне нужен совет, чтобы оптимизировать этот лог c.

Примечание. Помещение taskgroup в for l oop в предложении if также помогает, но это намного медленнее, чем ожидалось.

1 Ответ

1 голос
/ 06 марта 2020

Прежде всего, существует огромная проблема в вашем коде: solve_NQueens может отправлять задачи рекурсивно и возвращать до того, как все задачи будут фактически завершены . Вам нужно поставить синхронизацию перед return, чтобы действительное значение SOLUTION_EXISTS (с использованием #pragma omp taskwait или #pragma omp taskgroup).

С точки зрения производительности, существует множество проблем. .

Основная проблема заключается в том, что для многих задач создано: вы создаете задачу в каждом рекурсивном вызове. Хотя создание нескольких задач приносит необходимый параллелизм, создание многих из них также приводит к значительным накладным расходам. Эти издержки могут быть намного выше, чем выполнение хвостовых вызовов. Стратегия отсечка , которую можно реализовать для сокращения накладных расходов: общая идея заключается в создании задач только для первых рекурсивных вызовов. В вашем случае вы можете сделать это с помощью пункта if(col < 3) в конце #pragma omp task. Обратите внимание, что 3 является произвольным значением, вам может потребоваться настроить этот порог.

Кроме того, board копируется (дважды) при создании задачи (так как это массив stati c и переменные по умолчанию, необходимые для задачи OpenMP, неявно копируются). Ваша дополнительная копия не нужна, и строка board[i][col] = 0; бесполезна *, если код скомпилирован с поддержкой OpenMP (в противном случае прагма игнорируется, а это , а не true *). Однако вводимые дополнительные издержки не должны быть критическими, если вы решите проблему, описанную выше.

...