Processamento Concorrente e Paralelo Exercício 2 Jogo da Vida

Processamento Concorrente e Paralelo
Exercício 2
Considere o Jogo da Vida descrito abaixo e suas implementações discutidas em sala:
FuncionamentoVida e TempoExec.
Implemente o paralelismo OpenMP conforme discutido em sala no módulo ModVida.
Certifique-se da correção de sua implementação executando o programa principal
Funcionamento na versão paralela de ModVida.
Em seguida, meça o tempo de execução em função do tamanho do tabuleiro e do
número de “threads”, usando TempoExec e a versão paralela de ModVida. Calcule o ganho
(“speed-up”) para diversos tamanhos de tabuleiro e número de threads.
Entregue relatório sucinto apresentando os ganhos e analisando os resultados.
Jogo da Vida
O Jogo da Vida1, criado por John H. Conway, utiliza um autômato celular para simular
gerações sucessivas de uma sociedade de organismos vivos.
É composto por um tabuleiro bi-dimensional, infinito em qualquer direção, de células
quadradas idênticas. Cada célula tem exatamente oito células vizinhas (todas as células que
compartilham, com a célula original, uma aresta ou um vértice). Cada célula está em um de dois
estados: viva ou morta. Uma geração da sociedade é representada pelo conjunto dos estados das
células do tabuleiro. Sociedades evoluem de uma geração para a próxima aplicando
simultaneamente, a todas as células do tabuleiro, regras que estabelecem o próximo estado de
cada célula. As regras são:
1. Células vivas com menos de 2 vizinhas vivas morrem por abandono;
2. Células vivas com mais de 3 vizinhas vivas morrem de superpopulação;
3. Células mortas com exatamente 3 vizinhas vivas tornam-se vivas;
4. As demais células mantêm seu estado anterior.
O tarball FuncionamentoVida.tgz contem programa em Fortran90 que reproduz o Jogo
da Vida sobre um tabuleiro finito, NxN, orlado por células eternamente mortas. Admita que
(1,1) identifica a célula no canto superior esquerdo do tabuleiro e que (N,N) identifica a célula
no canto inferior direito. O programa está estruturado da seguinte forma:
1. O módulo ModVida contém três procedimentos: (1) UmaVida computa a próxima geração
de um tabuleiro tabulIn de tamanho tam, colocando o resultado no tabuleiro tabulOut; (2)
DumpTabuleiro imprime a região do tabuleiro entre as células (pri,pri) e (ult,ult); (3)
InitTabuleiro inicializa o tabuleiro com um “veleiro”.
2. A função wall_time retorna o tempo (wall clock) decorrido a partir da primeira invocação.
3. O programa Funcionamento aloca tabuleiros de tamanho N (constante simbólica), inicializaos invocando InitTabuleiro e move o veleiro de um canto a outro do tabuleiro por sucessivas
gerações, repetidamente invocando UmaVida. Cada geração é impressa, a partir da geração
inicial, invocando DumpTabuleiro.
Já o tarball MedeTempoVida.tgz contém outro programa principal, o TempoExec, que
mede o tempo de execução para diversos tamanhos de tabuleiro.
[1] – Martin Gardner, “Mathematical Games – The fantastic combinations of John Conway’s
new solitaire game life”, Scientific American 223, Oct. 1970, pp 120-123, ou
http://ddi.cs.uni-potsdam.de/HyFISCH/Produzieren/lis_projekt/proj_gamelife/ConwayScientificAmerican.htm