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

  • FPGA
  • Acceleration
  • Multi-agent Simulation

• Graduation date

  Fall 2012

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3Z419

• 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.