Simulação Distribuída em um Hipercubo de Transputers com o Mecanismo Time Warp
Autores
|
3323 |
Luiz Felipe de Lima Perrone
|
163,1505
|
|
3324 |
163,1505
|
Informações:
Publicações do PESC
A simulação de eventos discretos provou estar entre os mais difíceis casos de particionamento de problemas para execução paralela. A distribuição de um problema desta natureza para execução paralela envolve bem mais que a decomposição de estruturas de dados e sincronização de iterações.
Neste tipo de simulações existe uma restrição básica quanto ao escalonamento distribuído de eventos representada pelo conceito de causalidade. O conceito causalidade determina uma ordem parcial entre os eventos da simulação a ser necessariamente respeitada para que a simulação produza resultados corretos.
No desenvolvimento de métodos para simulação paralela de eventos discretos, definiram-se duas abordagens distintas para tratar o escalonamento distribuído de eventos. Os algoritmos da escola conservadora procuram escalonar eventos somente ao encontrarem uma situação em que pode-se garantir a não ocorrência de erros de causalidade. Este tipo de técnica tem mostrado ao longo do tempo ser incapaz de explorar bem o paralelismo das aplicações e portanto, proporcionalmente, maiores atenções tem sido dispensadas no aprimoramento dos algoritmos da escola otimista. Os algoritmos otimistas baseiam-se em uma forma mais flexível de escalonamento que, ao mesmo tempo que permite ocorrência de erros de causalidade para corrigi-los em seguida, permite bom aproveitamento da concorrência natural da aplicação.
O trabalho de David Jefferson no paradigma de Tempo Virtual criou novas perspectivas para a simulação de eventos discretos em máquinas multiprocessadas, dentro da escola otimista. O mecanismo otimista Time Warp, que implementa este paradigma, tem sido cada vez mais estudado e fundamenta-se hoje como o método mais promissor no desenvolvimento de simuladores paralelos de uso genérico.
Este trabalho apresenta o projeto e análise de desempenho de um mecanismo Time Warp para um multiprocessador hipercúbico baseado em transputers. Neste projeto, procurou-se empregar técnicas eficientes de controle de fluxo e gerenciamento de memória, desenvolvidas a partir do protocolo Cancelback, de Jefferson, adaptado para execução em um sistema de memória distribuída. Apresenta-se também um novo algoritmo de cálculo de Tempo Virtual Global, baseado no algoritmo de registro de estados globais de Chandy e Lamport, que opera em conjunto com o protocolo Cancelback. O projeto incorpora, além destas modificações, uma nova proposta no mecanismo de cancelamento de mensagens procurando aproveitar a idéia do Direct Cancellation de Richard Fujimoto, para máquinas de memória compartilhada, também em máquinas de memória distribuída.
O sistema foi escrito na linguagem de programação occam 2 com alguns poucos trechos em assembly language. Devido à necessidade de utilizar um método de escalonamento de processos cuja características divergem dos algoritmos implementados em microcódigo no transputer, desenvolveu-se uma técnica para sobrepujar a ação normal do processador. Desta forma, apresenta-se aqui um algoritmo de escalonamento preemptivo capaz de tomar decisões próprias de escalonamento sem interferência do processador.
Discrete-event simulation has proved to be among the hardest problems to be partitioned for parallel execution. Differently from other applications, its distribution involves much more than simple decomposition of data structures and synchronization of loop cycles.
In this kind of simulations, there is always a partial order of events that must be preserved to ensure the correctness of the computation. This partial order is defined by a causality relation between events that define how they must be scheduled in a way as to produce valid results.
In the development of methods for parallel execution of discrete events, two different paradigms have been created to handle the distributed scheduling of events. The conservative algorithms try to schedule events in such a way as to avoid the ocurrence of causality errors. This kind of technique has proved not to be able to exploit the parallelism inherent to applications in its full and, therefore, much effort has been put forth in the development of algorithms belonging to the optimistic school. The optimistic algorithms embody a more flexible event scheduling technique that as well as allowing causality errors to occur, correcting them afterwards, leads to a good exploitation of the application's parallelism.
David Jefferson's work on the Virtual Time paradigm has opened new perpectives in optimistic distributed simulation on multiprocessed machines. The Time Warp mechanism, that implements this paradigm, has been the object of extensive research and also has been said to offer a great potential as a general purpose strategy for parallel simulation. This work presents the project and performance analysis of a modified version of the Time Warp mechanism for a transputer hypercubical multiprocessor. This project includes nove1 efficient techniques for f l o c~o ntrol and memory management based on David Jefferson's Cancelback protocol and for message cancellation based on Richard Fujimoto's Direct Cancellation. Originally, these were developed for shared memory machines, but here equivalent techniques for distributed memory architectures are presented. A new algorithm for Global Virtual Time (GVT) computation, that works together with the Cancelbacb protocol, is also presented. This algorithm is based on Chandy and Lamport's global snapshot algorithm.
The system discussed here is written mostly in the occam 2 programming language
with very few parts in assembly. The Time Warp mechanism has scheduling requirements that are essentially different from the transputer microcoded scheduler, and thus a strategy to override processor control had to be devised. This strategy, used to implement a preemptive scheduling algorithm, is also presented here and can be used as a model for other works when the ultimate scheduling decision must be made without processor interference.