Trabalho II: Simulação de um Ecossistema de Raposas e Coelhos

Objectivo

Descrição

O problema que se pretende resolver consiste em simular a evolução, ao longo de várias gerações, de um ecossistema em que co-habitam duas espécies diferentes de animais cuja existência é mutuamente dependente: raposas e coelhos.

A simulação deve ser realizada sobre uma matriz com LIN linhas e COL colunas, onde as células da matriz representam o espaço do ecossistema sobre o qual as raposas e os coelhos se movimentam. Em cada geração, cada espaço pode estar livre ou ocupado. Um espaço pode ser ocupado por um coelho, por uma raposa ou por uma rocha. A matriz é inicializada com uma população inicial de coelhos, raposas e rochas colocados aleatoriamente. Ao longo das gerações, cada população evolui de acordo com um determinado conjunto de regras. A simulação consiste em partir das populações iniciais e ir construíndo as sucessivas gerações da populações de coelhos e raposas até um limite previamente estipulado.

Regras para os Coelhos

• Em cada geração, os coelhos tentam mover-se para um dos espaços adjacentes livres. Se existirem vários espaços adjacentes livres, escolhem um deles segundo um determinado critério. Se não existir nenhum espaço adjacente livre, mantêm-se no mesmo lugar.
• Os coelhos podem mover-se na horizontal e na vertical mas não na diagonal.
• Os coelhos podem procriar sempre que passarem GER_PROC_COELHOS gerações desde que nasceram ou desde que procriaram pela última vez. Depois de atingir a idade de procriar, quando posteriormente um coelho se move, este deixa na sua posição anterior um novo coelho de idade 0. A sua idade para procriar volta a 0.

Regras para as Raposas

• A cada geração, as raposas tentam comer coelhos movendo-se para espaços adjacentes que estejam ocupados por coelhos. Se existirem vários espaços adjacentes ocupados por coelhos, escolhem um deles segundo um determinado critério. Se não existir nenhum espaço adjacente ocupado por coelhos, as raposas tentam mover-se para um dos espaços adjacentes livres, utilizando o mesmo critério de escolha no caso de existirem vários espaços livres. Se não existir nenhum espaço adjacente ocupado por coelhos ou livre, mantêm-se no mesmo lugar.
• As raposas podem mover-se na horizontal e na vertical mas não na diagonal.
• As raposas podem procriar sempre que passam GER_PROC_RAPOSAS gerações desde que nasceram ou desde que procriaram pela última vez. Depois de atingirem a idade de procriar, quando posteriormente uma raposa se move, esta deixa na sua posição anterior uma nova raposa de idade 0. A idade da raposa que se move volta a 0.
• As raposas morrem se não se alimentarem durante GER_ALIM_RAPOSAS gerações desde que nasceram ou desde que comeram um coelho pela última vez. As raposas não comem outras raposas, apenas coelhos.

Regras para as Rochas

• As rochas ocupam sempre o mesmo espaço ao longo do tempo e nenhum animal pode ocupar um espaço ocupado por uma rocha.

Critério para Seleccionar Espaços Adjacentes

• Numerar a partir de 0 e seguindo a ordem dos ponteiros do relógio, os possíveis P espaços adjacentes para onde é possível um coelho ou uma raposa se movimentar: espaço adjacente acima, espaço adjacente à direita, espaço adjacente abaixo e espaço adjacente à esquerda.
• Seja G a geração actual e sejam (X,Y) as coordenadas do espaço em que o coelho ou a raposa se encontra, então o novo espaço a seleccionar é determinado por (G+X+Y) mod P. Considere que a geração inicial (antes de qualquer movimentação) é a 0 e que a origem da matriz é (0,0).

Resolução de Conflitos

• Em cada geração, comece por movimentar primeiro o conjunto dos coelhos e só depois movimente o conjunto das raposas. No entanto, a ordem pela qual o conjunto dos coelhos ou o conjunto das raposas é movimentado durante uma geração não deve influenciar o resultado final da mesma, ou seja, considere que todos os coelhos se movimentam ao mesmo tempo e que todas as raposas se movimentam igualmente ao mesmo tempo.
• Durante a movimentação de uma geração, pode acontecer que um espaço seja ocupado por mais do que um coelho e/ou raposa. Quando isso acontece considere as seguintes regras:
  • Quando 2 ou mais coelhos se movimentam para o mesmo espaço livre, o coelho com o maior valor de idade (valor mais perto de GER_PROC_COELHOS) fica, os outros desaparecem.
  • Quando 2 ou mais raposas se movimentam para comer o mesmo coelho, a raposa com o maior valor de idade (valor mais perto de GER_PROC_RAPOSAS) fica, as outras desaparecem.
  • Quando 2 ou mais raposas se movimentam para o mesmo espaço livre, a raposa com mais fome (valor mais próximo de GER_ALIM_RAPOSAS) fica, as outras desaparecem. No caso de existirem 2 ou mais raposas com o mesmo valor de fome, fica aquela com o maior valor de idade (valor mais perto de GER_PROC_RAPOSAS).

Implementação

Comece por implementar uma versão sequencial do problema e apenas depois deve tentar implementar uma primeira versão paralela. Pode desenvolver versões paralelas para memória partilhada e/ou distribuída. Uma primeira estratégia poderá ser ter cada processo responsável por calcular as movimentações (nova geração) de uma parte da matriz. Notar que no final de cada geração pode ser necessário sincronizar informação com os processos adjacentes sobre os coelhos e/ou raposas que se movimentaram do espaço de um processo para o espaço dos processos adjacentes. Note ainda que a divisão da matriz pode ser feita de forma estática dividindo-a na horizontal, na vertical ou em ambas as dimensões. A divisão estática da matriz tem o problema da carga poder ser diferente para cada processo ao longo do tempo. Um melhor balanceamento da carga poderá ser conseguido através da divisão dinâmica do espaço da matriz sempre que se atinge determinado número de gerações.

Input

A aplicação a desenvolver deverá ler do standard-input um conjunto de linhas sucessivas com os valores dos parâmetros de configuração e estado inicial do ecossistema, com a seguinte ordem:

• GER_PROC_COELHOS - número de gerações até que um coelho possa procriar.
• GER_PROC_RAPOSAS - número de gerações até que uma raposa possa procriar.
• GER_ALIM_RAPOSAS - número de gerações até que uma raposa morre à fome.
• N_GER - número de gerações a simular
• LIN COL - número de linhas e colunas da matriz que representa o ecossistema.
• N_OBJS - número de objectos do ecossistema inicial.
• Seguem-se N_OBJS, um por linha com o seguinte formato OBJECTO X Y onde OBJECTO pode ser ROCHA, RAPOSA ou COELHO e X e Y são as coordenadas do posicionamento do OBJECTO na matriz.

3
6
3
100
10 10
ROCHA 0 0 
COELHO 0 2
ROCHA 0 5 
COELHO 2 5
RAPOSA 9 9

Output

Como resultado a aplicação deverá escrever para o standard output a descrição das populações finais, seguindo o mesmo formato de descrição dos objectos que representavam a descrição das populações iniciais. Segue-se um exemplo de output, que não tem relação com a simulação do exemplo de input.

MATRIZ 10 10
ROCHA 0 0 
ROCHA 0 5 
COELHO 1 2
COELHO 2 2
COELHO 2 5
RAPOSA 2 9
RAPOSA 5 2
RAPOSA 5 9
COELHO 7 5

O Que Entregar?

• Os ficheiros com o código da aplicação (pode ser só um);
• A makefile que gera o executável da aplicação (utilizar o nome 'simulador');
• Um ficheiro .pdf com um pequeno relatório do trabalho (estrutura livre) onde se descreve de forma sucinta e clara:
  • A implementação: estruturas de dados utilizadas, ideia base do algoritmo, divisão de trabalho, pontos de sincronização, balanceamento da carga, ...;
  • As dificuldades encontradas na implementação (se alguma);
  • Os tempos de execução (em milisegundos e sem contabilizar as operações de input/output) e speedups (em relação à execução com 1 processo) obtidos para 1, 2, e 4 ou 1, 2, 4 e 8 processos, dependendo da solução ser memória partilhada ou distribuída.

Prazos