Implementar PDES em arquiteturas PADS requer que todos os eventos gerados sejam marcados com tempo (timestamped) e entregues seguindo uma abordagem baseada em mensagens. Dois eventos são ditos que estão em ordem casual se um deles pode ter consequências no outro [53]. Essa característica é bem fácil de ser satisfeita em simulações sequenciais, nas quais todos os eventos têm de ser considerados em ordem não decrescente respeitando o seu timestamp. Em arquiteturas de simulação paralela ou distribuída, os componentes podem ser processados em velocidades diferentes, a rede pode introduzir um delay imprevisível e ainda poderá haver perdas nas mensagens entregues. Para garantir que as PADS não violem o princípio da causalidade, todas as PLs envolvidas na execução da simulação têm de ser coordenadas utilizando algum tipo de algoritmo de sincronização.
O planejamento dos eventos da simulação entre diferentes Pls acontecem na troca de mensagens de notificações de eventos, nas quais carregam o conteúdo e o momento em que aconteceu o evento (timestamp). No intuito de assegurar resultados de simulação corretos, mecanismos de sincronização são usados para manter a execução do
Nas últimas décadas, diferentes abordagens e variações foram investigadas, mas tratando de forma simplificada, podem-se citar três métodos principais: time-stepped, conservativo, otimista. Tais abordagens, nos últimos anos, estão sendo bastante investigadas e estudadas, e por isso diversas variações também estão sendo propostas. Pode-se analisar que o desempenho de algoritmos de simulação depende fortemente de vários fatores como: o modelo de simulação, o ambiente de execução e o cenário específico. Predizer o desempenho das PADS é bastante difícil, pois esta depende de vários fatores, alguns sendo estáticos e conhecidos no decorrer do tempo, enquanto outros são desconhecidos ou dependem de condições em tempo de execução [56]. 4.2.1. Time-stepped
O tempo de simulação é dividido em timesteps (passos de tempo) de tamanhos fixos e cada PL só pode proceder a execução do próximo timestep somente quando todas as outras PLs tiverem completadas a elaboração do seu timestep corrente [59]. Sobre o ponto de vista de implementação, essa abordagem é simples, mas a divisão em timesteps pode ser de certa forma desafiadora para alguns modelos de simulação.
Nesse modelo, todas as entidades participantes na simulação estão no mesmo
timestep em qualquer posição no decorrer da execução. Normalmente, a simulação é
dividida em timesteps de tamanhos iguais e a simulação avança de um timestep para o próximo. No i-ésimo step, o algoritmo simula todos os eventos que estão dentro do mesmo intervalo [(i-1)Δ,iΔ], sabendo que o Δ é um parâmetro de projeto [60]. Se o Δ é muito pequeno, a eficiência do método pode degenerar, pois a barreira de sincronização é desperdiçada em intervalos que podem conter nenhum evento. Por isso, o Δ deve ser grande o suficiente para que o processamento de um elemento típico tenha diversos eventos sendo processados em qualquer intervalo dado [(i-1) Δ,iΔ]. Por outro lado, caso o Δ seja grande demais, a simulação se torna com alto acoplamento, pois todos os eventos dentro do intervalo são simulados como se ocorressem de forma simultânea. A Figura 12 seguinte ilustra o avanço de uma simulação timestep convencional.
Figura 12. Progresso da simulação em simulações time-stepped tradicional [60]
4.2.2. Conservativo
O objetivo dessa abordagem é prevenir erros casuais, ou seja, antes de processar um evento com o timestamp “t”, o PL tem que decidir se esse evento é “seguro” ou não. Ele é considerado “seguro” se, no futuro não existir eventos com timestamp menor do que “t”. Se essa regra for seguida por todas as PLs, então a PADS irá obter resultados que são corretos sobre o ponto de vista de sincronização.
Para explicar de forma mais detalhada o mecanismo conservativo, assume-se que um simulador A muda o sinal no nó a no tempo t_stamp. Essa mudança irá levar a um novo valor de sinal conectado no nó b no simulador B. Nesse caso, o simulador A envia uma “mensagem de evento” para o simulador B. Ele informa ao simulador B que o sinal no nó b precisa ser atualizado no tempo t_stamp. Tal mensagem leva a adição de um evento (t_stamp, nó b, sinal a) na fila de eventos de B. t_stamp é chamado de
timestamp do evento.
O tempo local virtual de um simulador é igual ao timestamp de um evento que acabou de ser executado. Se o simulador não processa eventos, o tempo virtual local pode ser atualizado para o tempo em que a próxima execução do evento é esperada. O mecanismo conservativo de simulação garante que o simulador pode somente receber eventos com timestamps maiores ou iguais que o seu próprio tempo virtual [52][61]. Tal mecanismo é utilizado para a sincronização dos simuladores [62].
4.2.3. Otimista
Nesta abordagem, os PLs são livres para violar as restrições de causalidade (correção) e, por exemplo, podem processar os eventos na ordem em que recebem e estão disponíveis. Não existem tentativas a priori para predizer a chegada de novos
eventos com timestamp menores que podem causar violação de causalidade. Se, por um acaso, isto acontecer, o PL terá que fazer um processo de rollback (voltar atrás) para um estado interno anterior que é considerado correto e depois propagar o rollback para as outras LPs afetadas [63], [64]. Isso é feito através da exploração de mecanismos de gravação de informação de estados, chamados checkpoints (state-saving), obtidos durante a execução paralela ou distribuída.
Os checkpoints gravam os valores dos estados das variáveis anterior aos eventos de uma computação e faz o restore através da referência de tais valores salvos durante o mecanismo de rollback.
A abordagem otimista apresenta algumas características, como:
A cópia dos estados salvos cria uma cópia inteira dos estados dos processos
Incrementar os estados salvos a outros mantém um log de mudanças para cada variável de estado individual
Estados salvos não frequentes salva periodicamente a cópia do estado inteiro;
Computação reversa é uma nova técnica que realiza rollbacks através da execução de operações individuais inversas executadas em um evento de computação. Esta técnica está sendo explorada em simulação paralela de pequenas e grandes escalas.