1

Estou tendo problemas para paralelizar meu código em C com OpenMP e obter um bom desempenho no problema das n rainhas.

Os resultados são sempre consideravelmente mais lentos com paralelização ativada e não sei o motivo.

O código é este abaixo:

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

int checkQueen(int **queens, int linha, int col, int n);
void printTabuleiro(int **queens, int n);
void play(int **queens, int col, int n, int *sol, int *maxQueens, int *count);


//MAIN
int main(){
    int n = 10, sol = 0, maxQueens = 0, count = 0;

    //alocando rainhas
    int **queens = (int**) malloc(n  * sizeof(int *));
    for(int i = 0; i < n; ++i)
        queens[i] = (int*) malloc(n  * sizeof(int));

    #pragma omp parallel for
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            queens[i][j] = 0;
        }
    }

    play(queens, 0, n, &sol, &maxQueens, &count);

    //imprime resultados
        printf("Maximo de rainhas: %d \n", maxQueens);
        printf("Numero de solucoes: %d \n", sol);


    return 0;
}

//testando se é possivel colocar rainha em determinada posição

int checkQueen(int **queens, int linha, int col, int n){

    int a = 0;

    if(queens[linha][col] == 1)
        return 1;
    #pragma omp parallel num_threads(n)
    {
        for(int i = linha, j = col; j >= 0 && i >= 0; --i, --j){
            if(queens[i][j] == 1){
                #pragma atomic
                a = 1;
            }
        }


        if(!a){
            for(int i = linha, j = col; j >= 0 && i < n ; ++i, --j){
                if(queens[i][j] == 1){
                    #pragma atomic
                    a = 1;
                }
            }
        }


        if(!a){
            for(int i = linha, j = col; j < n && i >= 0 ; --i, ++j){
                if(queens[i][j] == 1){
                    #pragma atomic
                    a = 1;
                }
            }
        }


        if(!a){
            for(int i = linha, j = col; j < n && i < n ; ++i, ++j){
                if(queens[i][j] == 1){
                    #pragma atomic
                    a = 1;
                }
            }
        }


        if(!a){
            for(int i = linha; i < n ; ++i){
                if(queens[linha][i] == 1){
                    #pragma atomic
                    a = 1;
                }
            }
        }


        if(!a){
            for(int i = linha; i >= 0 ; --i){
                if(queens[linha][i] == 1){
                    #pragma atomic
                    a = 1;
                }
            }
        }


        if(!a){
            for(int i = col; i < n ; ++i){
                if(queens[i][col] == 1){
                    #pragma atomic
                    a = 1;
                }
            }
        }


        if(!a){
            for(int i = col; i >= 0 ; --i){
                if(queens[i][col] == 1){
                    #pragma atomic
                    a = 1;
                }
            }
        }

    }

    return a;
}

//Imprime tabuleiro
void printTabuleiro(int **queens, int n){
    printf("//////////////////////////////////////////////");
    printf("\n//// 1 - rainhas / 0 - posicoes vazias ////\n");
    printf("//////////////////////////////////////////////");
    for(int i = 0; i < n; ++i){
        printf("\n");
        for(int j = 0; j < n; ++j){
            printf("%d - ", queens[i][j]);
        }
    }
    printf("\n");
}

//executa testes
void play(int **queens, int col, int n, int *sol, int *maxQueens, int *count){
    if (col == n){
        printf("\nSolucao #%d\n", ++*sol);
        printTabuleiro(queens, n);
        return;
    }

    for(int i = 0; i < n; ++i){
        if(!checkQueen(queens, i, col, n)){
            queens[i][col] = 1;
            ++*count;
            play(queens, col+1, n, sol, maxQueens, count);

            if(*count > *maxQueens){
                *maxQueens = *count;
            }

            --*count;
            queens[i][col] = 0;
        }
    }


}

1 Resposta 1

4

Sua estratégia de paralelização está errada. O problema é o bloco delimitado com isso dentro da função checkQueen

    #pragma omp parallel num_threads(n)

Ocorre que o código do conteúdo desse bloco verifica o tabuleiro inteiro. Como você está lançando n threads aí, cada uma dessas n threads vai verificar todo o tabuleiro, o que significa bastante trabalho redundante. Esse bloco só vai terminar quando a última dessas threads terminar. Some isso com a complexidade e o impacto no desempenho para manter as atribuições atômicas e com isso o resultado será bem mais lento do que seria uma versão com uma única thread.

Ou seja, o problema é que ao invés de você dividir o trabalho em n threads, você o multiplicou por n threads.

Para piorar, a função checkQueen é chamada múltiplas vezes dentro da função recursiva play. Isso significa que esse overhead de criar e sincronizar threads vai ser multiplicado pelo número de vezes que checkQueen for chamado, deixando tudo ainda mais lento.

Sugiro fortemente a você, paralelizar a função play, e não a função checkQueen. Para se beneficiar do paralelismo, é importante que você dependa o mínimo possível de partes que sejam sequenciais single-thread, e é exatamente assim que a função play está.

Além disso, para ter um bom ganho de performance ao se paralelizar, é importante você evitar que as threads tenham que interagir umas com as outras. É perfeitamente possível deixar com que elas interajam e muitas vezes é inevitável, mas ao fazer isso, provavelmente você terá algum custo de desempenho, e portanto isso é algo a ser evitado/minimizado. A forma com a qual você implementou o checkQueen tem um monte de interações entre threads por meio da variável a.

O for dentro do main para inicializar tudo com zero também não tem ganho apreciativo de performance ao ser paralelizado. Pelo contrário, o overhead que o gerenciamento de threads deve impôr provavelmente será maior que o ganho. Aliás, para que haja ganho de performance, a quantidade de carga de trabalho que cada thread tem que ganhar tem que ser grande o suficiente para que ela ultrapasse esse overhead, e nenhuma das partes que você paralelizou têm essa característica.

Tenho também duas obervações:

  • Fazer o checkQueen retornar 1 quando não é possível colocar uma rainha e 0 quando é soa um pouco estranho, pois implica que 1=não e 0=sim, o oposto da convenção. Ao mudar-se isso, pode-se retirar o operador ! que está no if da função play. Melhor ainda, você pode mudar o nome dessa função para queen_ok para ficar mais claro.

  • Você pode alocar uma única área de memória com n * n células e usar queen[linha * n + coluna] para acessar os elementos. Dessa forma, você só tem que alocar memória uma vez para montar o tabuleiro e garante também que ela é contígua, o que oferece um melhor desempenho.

  • Para evitar com que uma thread interfira na outra ao alterar o tabuleiro, crie um tabuleiro por thread e use uma função para copiar os tabuleiros.

  • Para evitar ter que trabalhar com int *queen e int n em todos os locais, sugiro você criar um struct para isso.

  • Para evitar fazer com que as threads venham a competir pelo printf ao exibir soluções, utilize locking. A solução abaixo utiliza o conceito dessa resposta no SOen.

  • Talvez ao utilizar-se schedule(dynamic,1), você acabe tendo um bom ganho de desempenho ao considerar-se que nem todos os tabuleiros parcialmente preenchidos têm o mesmo peso para serem analisados.

  • Essas variáveis sol, count e maxQueens vão te atrapalhar na paralelização. Mas não é muito difícil eliminá-las. O count pode ser colocado no struct que mencionei. O sol só é usado em um contexto onde você tem o lock devido a necessidade de usar o printf. O maxQueens pode ser atualizado de forma preguiçosa apenas nesse ponto.

  • Não se esqueça de dar free em tudo que você der malloc.

  • No C, a maior parte das funções usa a notação separada_por_underscores, e não a notação camelCase.

Sugiro que seu código fique assim, paralelizando o play:

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

typedef struct Tabuleiro {
    int n;
    int *casas;
    int queens_count;
} Tabuleiro;

// Funções básicas sobre tabuleiro.
Tabuleiro *criar_tabuleiro(int n);
Tabuleiro *copiar_tabuleiro(Tabuleiro *original);
void destruir_tabuleiro(Tabuleiro *tabuleiro);
void print_tabuleiro(Tabuleiro *tabuleiro);

// Implementação do n queens.
int queen_ok(Tabuleiro *tabuleiro, int linha, int coluna);
void play(Tabuleiro *tabuleiro, int *solucoes, int *max_queens, omp_lock_t *lock);
void play_in(Tabuleiro *tabuleiro, int coluna, int *solucoes, int *max_queens, omp_lock_t *lock);

// Função main.
int main() {
    int n = 10, solucoes = 0, max_queens = 0;

    omp_lock_t lock;
    omp_init_lock(&lock);

    Tabuleiro *tabuleiro = criar_tabuleiro(n);

    play(tabuleiro, &solucoes, &max_queens, lock);

    printf("Maximo de rainhas: %d \n", max_queens);
    printf("Numero de solucoes: %d \n", solucoes);

    omp_destroy_lock(&lock);
    destruir_tabuleiro(tabuleiro);
    return 0;
}

Tabuleiro *criar_tabuleiro(int n) {
    Tabuleiro *tabuleiro = malloc(sizeof(Tabuleiro));
    tabuleiro->n = n;
    tabuleiro->queens_count = 0;
    tabuleiro->casas = malloc(n * n * sizeof(int));

    for (int i = 0; i < n * n; n++) {
        tabuleiro->casas[i] = 0;
    }
    return tabuleiro;
}

Tabuleiro *copiar_tabuleiro(Tabuleiro *original) {
    int n = original->n;
    Tabuleiro *tabuleiro = malloc(sizeof(Tabuleiro));
    tabuleiro->n = n;
    tabuleiro->queens_count = original->queens_count;
    tabuleiro->casas = malloc(n * n * sizeof(int));

    for (int i = 0; i < n * n; n++) {
        tabuleiro->casas[i] = original->casas[i];
    }
    return tabuleiro;
}

void destruir_tabuleiro(Tabuleiro *tabuleiro) {
    free(tabuleiro->casas);
    free(tabuleiro);
}

void print_tabuleiro(Tabuleiro *tabuleiro) {
    int n = tabuleiro->n;
    for (int i = 0; i < n; ++i) {
        printf("\n");
        for (int j = 0; j < n; ++j) {
            printf("%c", tabuleiro->casas[i * n + j] ? 'X' : '.');
        }
    }
    printf("\n\n");
}

int queen_ok(Tabuleiro *tabuleiro, int linha, int coluna) {
    int n = tabuleiro->n;
    int *queens = tabuleiro->casas;

    if (queens[linha * n + coluna] == 1) return 0;

    // Diagonal para cima e para a esquerda.
    for (int i = linha, j = coluna; j >= 0 && i >= 0; --i, --j) {
        if (queens[i * n + j]) return 0;
    }

    // Diagonal para baixo e para a esquerda.
    for (int i = linha, j = coluna; j >= 0 && i < n; ++i, --j) {
        if (queens[i * n + j]) return 0;
    }

    // Diagonal para cima e para a direita.
    for (int i = linha, j = coluna; j < n && i >= 0; --i, ++j) {
        if (queens[i * n + j]) return 0;
    }

    // Diagonal para baixo e para a direita.
    for (int i = linha, j = coluna; j < n && i < n; ++i, ++j) {
        if (queens[i * n + j]) return 0;
    }

    // Para baixo.
    for (int i = linha; i < n ; ++i) {
        if (queens[i * n + coluna]) return 0;
    }

    // Para cima.
    for (int i = linha; i >= 0; --i) {
        if (queens[i * n + coluna]) return 0;
    }

    // Para a direita.
    for (int j = coluna; j < n; ++j) {
        if (queens[linha * n + j]) return 0;
    }

    // Para a esquerda.
    for (int j = coluna; j >= 0; --j) {
        if (queens[linha * n + j]) return 0;
    }

    return 1;
}

void play(Tabuleiro *tabuleiro, int *solucoes, int *max_queens, omp_lock_t *lock) {
    int n = tabuleiro->n;

    #pragma omp parallel num_threads(n) schedule(dynamic,1)
    for (int i = 0; i < n; ++i) {
        Tabuleiro *copia = copiar_tabuleiro(tabuleiro);
        copia->casas[i * n] = 1;
        copia->queens_count++;

        play_in(copia, 0, solucoes, max_queens, lock);

        destruir_tabuleiro(copia);
    }
}

void play_in(Tabuleiro *tabuleiro, int coluna, int *solucoes, int *max_queens, omp_lock_t *lock) {
    int n = tabuleiro->n;

    if (coluna == n) {
        omp_set_lock(lock);
        printf("\nSolucao #%d\n", ++*solucoes);
        print_tabuleiro(tabuleiro);
        if (*max_queens < tabuleiro->queens_count) {
            *max_queens = tabuleiro->queens_count;
        }
        omp_unset_lock(lock);
        return;
    }

    for (int i = 0; i < n; ++i) {
        if (queen_ok(tabuleiro, i, coluna)) {
            Tabuleiro *copia = copiar_tabuleiro(tabuleiro);
            copia->casas[i * n + coluna] = 1;
            copia->queens_count++;

            play_in(copia, coluna + 1, solucoes, max_queens, lock);

            destruir_tabuleiro(copia);
        }
    }
}

Observação: Não testei esse código, então não sei se vai dar certo de primeira, talvez haja algum erro bobo em algum lugar. Entretanto, mesmo se houver algo errado, o resultado correto certamente é algo próximo disso.

Ainda daria para dar uma melhorada tentando evitar as repetidas alocações e desalocações ao prealocar-se um pool de tabuleiros e obtê-los/devolvê-los a esse pool quando necessário. Entretanto, não tenho certeza de qual é o tamanho do pool, mas uma estimativa do tamanho do limite superior desse pool seria algo da ordem de n²/4. Nota-se também que esse pool seria uma pilha.

3
  • Fiz alguns testes com teu código e o tempo com OpenMP ativado é maior do que com OpenMP desligado. Quanto maior o N, maior fica a distancia entre os tempos a favor do sem paralelização.
    – DJM_JM
    Commented 3/03/2018 às 1:36
  • @DJM_JM Editei a resposta. Veja se agora dá certo. Commented 3/03/2018 às 3:29
  • Continua com o mesmo problema. Inclusive ele não roda com "#pragma omp parallel num_threads(n) schedule(dynamic,1)", preciso dividir em "#pragma omp parallel num_threads(n){ #pragma omp for schedule(dynamic,1) }" para funcionar. Executando persiste o mesmo erro.
    – DJM_JM
    Commented 3/03/2018 às 18:41

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .