|Manufacturing Computations Lab
Mega-Scale Interactive Agent-Based Model Simulations on the GPU
Keywords: ABM Simulation, Graphics Processing Units (GPU), GPGPU, Complex Systems, Data-Parallel Algorithms
size is extremely important in
Some researchers have attempted to speed up ABM simulations by using cluster based parallel computing. However, even these methods are severely limited due to the restricted bandwidth of the interconnects between computers. Load-balancing issues can severely degrade performance. Moreover, visualization is extremely difficult/impossible because of the amount of data that must be piped through the interconnects to the computer that handles the display.Method:
In this project, we utilize the computational capabilities of the Graphics Processing Unit (GPU) to speed up ABM simulations. There are two factors that enable the scale and speed of ABMs that we want to achieve. This first is the computing power, the second is memory bandwidth. The latest generation NVIDIA GeForce 8800 GTX (costing about $500) is rated at 576 GFlops. The top of the line Intel quad core Xenon(costing about $3,300) has a peak performance of 63 GFlops . The GPU bandwidth (between GPU and video memory) is about 830 Gbps while as the quad core Xenon with a FSB of 1066 MHz is only rated at 68Gbps. The fastest Infiniband interconnects between computers (used in cluster computing) is about 12Gbps.
Programming the GPU for ABM simulation is a non-trivial task. To make full use of the computing power and bandwidth, all computation have to be restricted to the GPU with minimal/no communication with the CPU. This is because the connection between the CPU and GPU (PCI Express) is much slower. As part of this effort, we have developed innovative methods for representing and manipulating agent and environment data. This involves creative use of GPU texture memory and constructs such as framebuffer objects for off-line rendering. We have developed innovative algorithms for handling agent movement, interaction, birth and environment evolution.
We have implemented two prototypical ABM models which are frequently used to benchmark ABM frameworks. The first is SugarScape, a simple ABM that captures all fundamental concepts of social sciences modeling. The second is StupidBugs v16, an ABM model which utilizes time consuming environment update calculations, specially designed as a stress test for ABM frameworks.
Figure 1 shows the screen shot of the SugarScape simulation. In this simulation there are over 2 million agents on an environment of 2560x1024 running at about 50 frames a second. Figure 2 demonstrates the scalability of our SugarScape implementation. Figure 3 shows the bench mark results for StupidBugs v16 for about 2000 bugs on an environment of 256x128. Note that for small problem sizes, the overhead of invoking procedures on the GPU forms a significant part of the time for execution. This overhead is constant and is well amortized for large problem sizes.
 Lysenko, M., D'Souza, R. M., 2007, A framework for megascale agent-based model simulations on the GPU, Accept at the Journal of Artificial Societies and Social Simulation. (JASSS)