Çetin, N. (2005) Large-scale parallel graph-based simulations. Dissertation, ETH Zurich, Switzerland.

Abstract

When systems are modeled, different techniques are used. Computer simulation is one of these techniques. It draws attention since it makes it possible to model a system that might be real or theoretical, to execute the model on a computer, and to analyze the output of the execution of the model. Execution of a model on a computer develops through time, i.e. the states of the different parts of a system, such as variables and environment, are updated through time according to the rules defined in the model.
Computer simulations come into prominence since they allow models to have complex objects/variables, allow objects to have complex relationships, allow users to model artificial worlds, etc. This thesis focuses on different parts of a transportation planning system, MATSIM (Multi-Agent Transportation SIMulation), which is a computer simulation.
In MATSIM, similar to other multi-agent simulations, all entities are treated at the individual level. Their behavior and interactions, both with each other and with the environment, are defined by their internal rules.
There are two layers in a transportation planning system: the physical layer that includes a traffic flow simulator, and the strategic layer. In the traffic flow simulator, the agents are interacts with each other and with the environment based on the rules defined in the model. In the strategic layer, the agents make their strategies. The relationship between these two layers is best understood in an implementation called a framework.
A framework couples the modules such as traffic flow simulator, router, agent database, activity generator, etc. A traffic flow simulator defines the rules of interactions of the entities in the system. The traffic flow simulator used in MATSIM is based on a queue model developed by Gawron. It reads the street network of the area to be simulated and the plans of the agents, then it executes these plans according to the rules of the queue model. The output of the traffic flow simulation, the events, are used to evaluate the performance of the plans. The evaluation is achieved by the modules of the strategic layer. The evaluated plans are fed to traffic flow simulator simulator by starting a new iteration.
Parallel computing issues are applied to the traffic simulator to handle the large-scale scenarios detailed at microscopic level. Different communication media and different communication libraries are used during this process.
The coupling of modules by framework is via files. From the viewpoint of a traffic flow simulator, this means two files: plans as input and events as output. To avoid the inefficiencies of file I/O, a message passing approach is developed for plans and events. Different methods for creating and transferring different types of messages are investigated.
The traffic flow simulator based on the queue model can be used for simulating other types of entities such as Internet data packet traffic. As Internet grows more, analyzing the data flowing through Internet becomes more interesting between researchers.

thesis_cetin.pdf 1.13 MB