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.