Manufacturing Computations Lab


Home

News

Research

People

Classes
Mega-Scale Interactive Agent-Based Model Simulations on the GPU
 
Keywords: ABM Simulation, Graphics Processing Units (GPU), GPGPU,  Complex Systems, Data-Parallel Algorithms

Background:
Agent-Based Models (ABMs) are used to model dynamic systems such as stock markets, societies, and complex biological systems that are difficult to model analytically using partial differential equations. This is particularly the case where the system consists of autonomous individuals who are “intelligent” and evolve over time. By intelligent, we mean that the individuals can independently act based on their goals, the environment and other individuals. The properties of the system as a whole emerge from micro-scale interactions between individuals and the environment. In the recent past, there has been an explosion in
ABM research in disciplines such as economics, sociology, ecology, epidemiology, and computational biology .  

Population size is extremely important in ABM. By nature, system level behaviors change with population size. Relevant simulations should have agent populations matching those of real dynamic systems. For example, New York City has a population of about nine million. A milliliter of blood from an infected human has about 4000 leukocytes and up to 10 million virus particles. As of 2007, there are about 90 million individual stock holders in China. An ABM used to describe any of these systems should have the capacity of handling tens of millions of individuals. Current generation ABM frameworks  designed for desktop computing (NetLogo, Swarm, EcoLab, MASON, Repast)can handle at the most a population size of several thousands. This is because of the serial nature of computing on the Central Processing Unit (CPU). 

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.

Results:
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.

Here is a movie (.ogg format ~200MB) of our 3-D simulation of granuloma formation in TB infection. This model was originally invented by Kirschner et al. at U. of Michigan, Ann Arbor.


Publications:
[1] D'Souza, R. M., Lysenko, M., Rahmani, K., 2007, SugarScape on steroids: simulating over a million agents at interactive rates, Proceedings of Agent2007 conference. Chicago, IL. Slides

[2] 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)

 



Dept. of Mechanical Engineering-Engineering Mechanics
Michigan Tech. University
1400 Townsend Drive
Houghton MI 49931
Ph: 906-487-1001