Acceleration of Multi-agent Simulation on FPGAs

Abstract

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.