Mac-499 Trabalho de Formatura Supervisionado
Tipo de Trabalho : Iniciação Científica
Implementação Paralela de Autômatos Celulares
Para
Tecidos Orgânicos
Aluno : Adroaldo Lazouriano Moreira Borges
Supervisor : Prof. Dr. Marco Dimas Gubitoso
[email protected]
[email protected]
Resumo
Vários fenômenos naturais requerem simulações com
desempenho computacional de alto nível. Por exemplo, na
previsão de tempo. Para isso usamos o processamento
paralelo nas simulações e modelamos vários desse
fenômenos por intermédio de autômatos celulares.
Computação Paralela
Arquiteturas Paralelas e Programações Paralelas
■ Arquiteturas Paralelas :
■ Arquiteturas de Memória compartilhada : cada
processador tem a sua memória local, mas comunica com
os outros por intermédio de algumas memórias
compartilhadas.
■ Arquiteturas de Memória distribuida : cada
processador tem a sua própria memória, mas comunica com
demais através de alguma estratégia implementável.
Computação Paralela (cont.)
■ Programações Paralelas :
■ Programas de Memórias Compartilhadas são aqueles
que implementam a política de variáveis compartilhadas.
■ Programas de Memórias Distribuidas são aqueles em
que a comunicação entre os processadores acontece através de
passagens de mensagens.
A programação paralela envolve a decomposição de dados ou
de tarefas entre os processadores, coordenação das tarefas e
comunicação entre os processadores.
Autômatos Celulares
De uma forma sucinta, podemos dizer que autômato celular
são modelos matématicos para modelagem de sistemas
complexos.
Definição matématico :
Um Autômato Celular α é um quadruplo (G, S, N, R) onde,
■ G = {cell(i,j): 1 ≤ i ≤ m-1 e 1 ≤ j ≤ n-1} onde, cell(i,j) é a
célula na posição (i,j) da grade G.
■ S é o conjunto do estados possíveis para a célula cell(i,j) .
Representaremos o estado da célula cell(i,j) no instante t por
st(i,j).
Autômatos Celulares (cont.)
■ N(i,j) é o conjunto das células vizinhas da célula cell(i,j).
■ R é o universo de todas as regras aplicáveis ao autômato
celular. Assim R(N(i,j)) é o conjunto de regras aplicáveis à
célula cell(i,j).
Alguns Autômatos Celulares
■ Game of Life
■ Greenburg - Hasting
■ Hodgepodge Machine
■Wireworld
Game of Life
Autômato Celular com as seguintes características :
■ G é uma grade ou matriz de células. Estas células são
representados por 0's e 1's.
■ S = {0, 1}
■ N(i,j) = {cell(k,l) : |k-i| = 1 e |l-j| = 1}
■ As regras são iguais para todas as células da G.
■ Uma célula morta (re)nasce se tiver exatamente 3 vizinhas
vivas. Caso contrário continua morta.
■ Uma célula viva continua viva se tiver 2 ou 3 vizinhas
vivas. Caso contrário morre.
Von Neumann
Moore
Moore Extendido
Matérias Relevantes
■ MAC0110 : noção de programação
■ MAC0122 : Escolha de melhores algoritmos e estruturas de
dados.
■ MAC0239 : Lógica e demonstração de corretude de
programas
■ MAC0412 : Noção de processamento de alto desempenho,
aliás foi a matéria que me motivou a computação paralela.
■ MAC0414 : Noção de autômatos e consequentemente
autômatos celulares.
Referências Bibliográficas
[1] Peter Pacheco, Parallel Programming with MPI, San
Francisco California. Kaufmann
[2] T. Toffoli e N. Margolus, Cellular Automata Machines,
MIT Press Series in Scientific Computation.
[3] R. Saldaña, W. Tabares e W. Yu, Parallel Implementations
of Cellular Automata Algorithms on the AGILA, High
Performance Computing System. Ateneo de Manila
University
[4] S. Song, E. Cáceres e H. Mongelli, Algoritmos Paralelos
usando CGM/PVM/MPI. Slides aulas.