Processamento Concorrente e Paralelo Exercício 2 Jogo da Vida
Transcrição
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