Distributed process cooperation in time warp

by Choe, Myongsu

OptMistic simulation (or The Warp) is one of the two major techniques employed in parallel (distributed) discrete event-driven simulation. As op posed to a conservative approach, Time Warp offers great potential to speed up a simulation because it does not rely on the blocking in order to to satisfy the causality constraint. By using rollback to correct causality errors and to avoid deadlock, it provides a great deal of parallelism and modeling power. However, it has adverse affects such as memory over-consumption and futile event processing resulting from uncontroiled rollbacks. In this thesis, we propose approaches to solve the inherent problem of load imbalance in optimistic simulations, especially, on a distributed memory MIMD system, thus seeking stability and simulation efficiency at the same time. As promising candidates to achieve these goals, we focus on an efficient GVT computation and the balancing of loads between processors by regulating bursting outgoing message flows or rnigrating unbalanced loads between processors. First, we suggest a va.riant of Mattern's GVT algorithm which uses a scalar counter and a partly distributed control to reduce the number of control messages required for GVT computation. We compare it with Bellenot, Samadi, and Mattern's algonthms on simulations of large switching networks - the shuffle ring network, Manhattan street network, and a PCS network. We then propose three different load balancing schemes: a flow control algorithm based on the use of stochastic learning automata, a dynamic load balancing scheme, and an integration of both of these controls. The purpose is to balance loads (measured by a space-tirne product) between processors. Three control algorithms and a simulation without using any control are compared on the simulations of shde ring networks and a PCS network in terms of several measures: simulation elapsed the, number of roilbacks and antimessages, roilback distances, goodput, and standard deviation of space-the products. Résumé Contrairement à une approche conventionnelle, qui dépend du groupage pour contourner les limites fixées par la perte, l'approche de simulation optimiste ou distorsion spatiotemporelie (The Warp) ouvre la possibilité d'améliorer l'accélération en exploitant une plus grande utilisation du parallélisme. Cependant, le programme de simulation risque d'être instable car il exige d'une part une utilisation de la mémoire au-delà de sa capacité et d'autre part, le traitement d'événements insignifiants causé par des reprises incontrôlées. Cette thèse propose quelques idées innovatrices s'appliquant tout part iculièrement à une mémoire automatisée répartie pour résoudre le problème inhérent du déséquilibre de la charge lors d'une simulation optimiste; le but est d'obtenir à la fois la stabiiité et une simulation performante. Pour atteindre notre but, nous examinons des candidats prometteurs, soit un calcul efficace du temps virtuel global et des stratégies pour équilibrer la charge entre les processeurs, par exemple en réglant le flux en rafale des données d'entrée ou en déplaçant les charges en déséquilibre d'un processeur à l'autre. Nous proposons un algorithme du temps virtuel global basé sur l'idée d'un instantané, et qui utilise un compteur scalaire et une commande partiellement répartie pour réduire le nombre de messages de commnade nécessaires à chaque calcul du temps virtuel global; nous les comparons aux algorithmes du temps virtuel global typiques. Nous examinons aussi trois stratégies différentes de commande pour équilibre la charge: un algorithme de commande de flux basé sur l'utilisation d'automates stochastiques d'apprentissage, un équilibre dynamique de la charge et l'intégration des deux commandes. De plus, nous iii étudions ces stratégies de commande et une version non contrôlée de la distorsion spatiotemporelle à partir de simulations faites sur de grands réseaux de commutation et sur des réseaux de systèmes de communication personnels.