Supporting agent-based simulations on GPU

Using ABS to analyze complex systems gains growing popularity over the past decades. It allows to take into account different levels of interactions as well as the heterogeneity of agents in the system. Through ABS, it is possible to forecast and explore future scenarios, experiment possible alternative decisions, and set different values for the decision variables to analyze the effects of these changes. At an aggregated level, the use of ABS can help in understanding general properties and patterns concerning the whole scenario that could not be deduced nor forecasted by the observation of each individual agent, due to the complexity of the interactions occurring among the agents. One of the fundamental issues in ABS is the speed of execution. As ABS is gaining a more widespread adoption, the need to model agents with more complex and advanced behavior is on the rise. Besides, certain phenomena can only be observed in scenarios with large number of agents, and the number of simulation instances can also be large when various possibilities of the scenario are explored. The complexity and large-scale of ABS pose challenges to the execution efficiency of ABS. In this research, effective and generic strategies are proposed to speed up the ABS execution with GPU platform. The strategies are proposed for the execution of a single ABS execution as well as a parameter space exploration task consisting of multiple ABS instances. The GPU is leveraged in the proposed strategies to exploit the parallelism of ABS. First, two common modules that widely exist in ABS applications are identified, namely the agent management module and the agent interaction module. Improving the efficiency of these two common modules can speed up the ABS execution in general. To support the two modules on GPU, strategies that use an AgentPool data structure to handle agent creation and deletion and GPU memory hierarchy to support efficient agent interaction are proposed. Experiment results show the performance advantage of the proposed strategies over FLAME, a well established GPU based ABS framework. Second, a GPU based ABS library consisting of a set of easy-to-use APIs is provided to facilitate the implementation of ABS using the proposed modules. To demonstrate the effectiveness and generality, the library is applied to implement a range of applications, including game-of-life, flocking boids, prey-and-predator, and the social-force based crowd simulation. The simulation results demonstrate that the proposed modules can be applied to various scenarios and achieve better performance than the commonly used CPU and GPU ABS frameworks, namely MASON and FLAME, for ABS applications using continuous space. Third, a simulation cloning technique for ABS, namely the top-down cloning strategy, is proposed to accelerate a parameter space exploration task consisting of multiple simulation instances. The top-down cloning strategy reuses common computations among simulation instances while maintaining the correctness of execution. Its GPU implementation supports the concurrent execution of agents within each simulation instance as well as the concurrent execution of multiple simulation instances. The performance of the proposed approach is evaluated using a case study of an evacuation scenario. The experiment results demonstrate that the top-down cloning strategy can shorten the overall execution time of the parameter space exploration task. Fourth, the idea of the ABS cloning is further developed by removing the limitations of the top-down cloning strategy. To overcome the limitations, an improved strategy named the bottom-up cloning strategy is proposed. In the experiments, a parameter exploration task consisting of a large number of simulation runs is executed with the bottom-up cloning strategy. It shows that the bottom-up cloning strategy can effectively shorten the execution time of the parameter space exploration and support more scenarios than the top-down cloning strategy. In summary, the contributions of this research are listed as follows: (1) The proposed GPU based agent management module and agent interaction module achieve better execution efficiency than the commonly used GPU based ABS framework for the execution of a single ABS instance; (2) The proposed GPU based ABS library can be generically applied to various ABS applications and accelerate their executions; and (3) The top-down and the bottom-up cloning strategies can speed up a parameter space exploration task that consists of multiple ABS instances. The bottom-up cloning strategy can support broader range of applications than the top-down cloning strategy.DOCTOR OF PHILOSOPHY (SCE