O objetivo desse projeto é paralelizar o Jogo da Vida de John Conway utilizando memória compatilhada (pThread, openMP) e memória distribuída (MPI).

Autômatos celulares são modelos evolucionais baseados em tempo. Onde cada célula assume um valor que representa seu estado no mundo. Conforme a passagem do tempo o valor de cada célula muda baseado no seu próprio estado e no das células vizinhas.

O jogo da vida é um autômato celular bidimensional com valores possíveis por célula desenvolvido pelo matemático britânico John Horton Conway em 1970. Os valores possíveis são 0 que representa o estado “morto” e o valor 1 que representa o estado “vivo”. Cada célula segue o seguinte conjunto de regras:

1. Qualquer célula viva com menos de dois vizinhos vivos morre de solidão.
2. Qualquer célula viva com mais de três vizinhos vivos morre de superpopulação.
3. Qualquer célula morta com exatamente três vizinhos vivos se torna uma célula viva.
4. Qualquer célula viva com dois ou três vizinhos vivos continua no mesmo estado para a próxima geração.

Anterior à programação paralela, foi criado o código com o núcleo do jogo (e seus conjuntos de regras) para ser utilizado como base nas implementações com pThread, OpenMP e MPI. Desta forma, pode-se comparar os resultados não apenas com o modelo sequencial, como também entre as diferentes estratégias paralelas adotadas.

Os algoritmos paralelos foram projetados para dividir o domínio de dados em áreas menores, conforme a figura abaixo. Essa estratégia de decomposição divide o número de linhas do tabuleiro entre as threads ou processos criados, onde cada um desses processos ou threads executa o núcleo do jogo sobre seu sub-domínio.

A distribuição das linhas é feita de forma balanceada entre as threads ou processos, a menos do última região que recebe o resto da divisão entre o número de linhas do tabuleiro e a quantidade de sub-domínios.

A flag -DPOS_CALC_MACRO compila a macro que é usada para calcular a posição no vetor, caso contrário será compilado a função.

gcc -o sequencial sequencial.c game.c -DPOS_CALC_MACRO

gcc -o pthread pthread.c game.c -DPOS_CALC_MACRO -lpthread

gcc -o openMP openMP.c game.c -DPOS_CALC_MACRO -fopenmp

mpicc -o MPI mpi.c game.c -DPOS_CALC_MACRO 

.\sequencial.exe numeroDeIteracoes inputs\filename.txt

.\pthread.exe numeroDeIteracoes inputs\filename.txt numeroDeThreads

.\openMP.exe numeroDeIteracoes inputs\filename.txt numeroDeThreads

mpirun -np numeroDeProcessos ./MPI numeroDeIteracoes inputs\filename.txt

Deived William

Márcio Medeiros