Acceleration of Multi-agent Simulation on FPGAs

  • Author / Creator
    Cui, Lintao
  • Multi-Agent Simulation (MAS) is a widely used paradigm for modeling and simulating real world complex system, ranging from ant colony foraging to online trading. MAS describes a complex system by representing it as a collection of interactive and concurrent objects following a set of predefined rules. To run MAS, several software frameworks have been developed to enable easy MAS experimentation and implementation. The performance of those MAS software, however, suffers when simulating massive-scale multi-agent systems on traditional serial processing processors. To overcome the limitation of serial computing, a parallel platform is required. In this thesis, we propose a FPGA-based parallel framework to support massivescale MAS modeling and simulation. Memory interleaving, parallel tasks partition, and computing pipeline, i.e. a three-step methodology, are adopted to improve the system throughput and performance for massive-scale MAS applications. A classical MAS benchmark, Conway‘s Game of Life, is used as a case study to illustrate how to map a grid-based model to our MAS framework using the proposed methodology. We implemented it on a Xilinx Virtex-5 FPGA board and achieved a speedup of 290x with two million agents, compared to the C implementation.

  • Subjects / Keywords
  • Graduation date
    Fall 2012
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.