The history of the Time Warp protocol, one of the most commonly used synchronization protocols in parallel and distributed simulation, has been a history of optimizations. Usually the optimization problems are solved by creating an analytical model for the simulation system through careful analysis of the behavior of Time Warp. The model is expressed as a closed-form function that maps system state variables to a control parameter. At run-time, the system state variables are measured and then utilized to derive the value for the control parameter. This approach makes the quality of the optimization heavily dependent on how closely the model actually reflects the simulation reality. Because of the simplifications that are necessary to make in the course of creating such models, it is not certain the control strategies are optimal. Furthermore, models based on a specific application cannot be readily adopted for other applications. / In this thesis, as an alternative approach, we present a number of model-free direct-search algorithms based on techniques from system control, machine learning, and evolutionary computing, namely, learning automata, reinforcement learning, and genetic algorithms. What these methods have in common is the notion of learning. Unlike the traditional methods used in Time Warp optimization, these learning methods treat the Time Warp simulator as a black box. They start with a set of candidate solutions for the optimization parameter and try to find the best solution through a trial-and-error process: learning automata give a better solution a higher probability to be tried; reinforcement learning keeps a value for each candidate that reflects the candidate's quality; genetic algorithms have a dynamic set of candidates and improves the quality of the set by mimicking the evolutionary process. We describe how some optimization problems in Time Warp can be transformed into a search problem, and how the learning methods can be utilized to directly search for the optimal value for the system control parameter. Compared with the analytical model-based approach, these methods are more generic in nature. Since the search is based on actual run-time performance of different values for the control parameter, the learning methods also better reflect the simulation reality. / L'histoire du protocole Time Warp, l'un des protocoles de synchronisation le plus couramment utilise en matiere de simulation parallele et distribue, a ete une histoire de optimisations. Habituellement, la problemes d'optimisation sont resolus par creer un modele analytique pour le systeme de simulation par une analyse minutieuse de la comportement de Time Warp. Le modele est exprime comme une fonction de la forme ferme entre les variables d'etat du systeme et un parametre de controle. Au moment de l'execution, les variables d'etat du systeme sont mesures et servent ensuite à calculer la valeur du parametre de controle. Cette approche rend la qualite de l'optimisation dépend fortement sur la maniere de pres le modele reflete reellement la realite de simulation. En raison de la simplications qui sont necessaires de faire dans le courant de creer de tels modeles, il n'est pas certain que les strategies de controle sont optimale. En outre, les modeles bases sur une application specifique ne peut etre facilement adopte pour d'autres applications. / Dans cette these, comme une approche alternative, nous presentons un certain nombre de algorithmes de direct recherche sans modeles base sur des techniques de controle du systeme, l'apprentissage automatique et evolutive l'informatique, a savoir, l'apprentissage des automates, apprentissage par renforcement, et genetique algorithmes. Ce que ces methodes ont en commun est la notion d'apprentissage. Contrairement aux methodes traditionnelles utilisees dans d'optimisation de Time Warp, ces apprentissages méthodes traitent le simulateur Time Warp comme une boite noire. Ils commencent par une ensemble de solutions candidates pour le parametre d'optimisation et essayer de trouver la meilleure solution grace a un essai-erreur de processus: l'apprentissage d'automates donner un meilleur solution d'une plus grande probabilite d'etre juge; apprentissage par renforcement garde un valeur pour chaque candidat qui reflete la qualite du candidat; genetiques algorithmes ont un ensemble dynamique de candidats et ameliore la qualite de la mis en imitant le processus evolutif. Nous decrivons comment certains probl`emes d'optimisation dans Time Warp peut etre transforme en un probleme de recherche, et comment les methodes d'apprentissage peut etre utilise pour directement recherche de la valeur optimale pour le parametre de controle du systeme. En comparaison avec le modele analytique approche, ces methodes sont plus generiques dans la nature. Comme la recherche est basee sur l'ecoulement des performances en temps reel des differents valeurs pour le parametre de controle, les methodes d'apprentissage aussi de mieux refleter la realite de la simulation.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.92203 |
| Date | January 2010 |
| Creators | Wang, Jun |
| Contributors | Carl Tropper (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0021 seconds