CISG Extended Abstract

A Parallel Computing Framework for Spatially-Explicit Agent-Based Models

Introduction

Agent Based Models (ABM) are an increasingly popular computational approach to study dynamic geospatial phenomena, because these phenomena are too complex to fully understand. Historically popular ABM packages, such as Netlogo and RePast /cite{railsback 2006}, have been limited to executing on a single computer. However, the need to study complex phenomena at finer resolutions (e.g. spatial & temporal) requires enormous computational power. High performance computing environments, such as those provided by NSF TeraGrid (www.teragrid.org), provide sufficient computation resources to facilitate these highly complex and detailed studies if ABM simulations can be efficiently parallelized. However, there are a series of issues when parallelizing spatially-explicit ABM (e.g. managing agent migration and distributing environment information across neighboring processors, limiting computation and communication load imbalance and in some circumstances handling agent movement ordering and conflicts) that must be addressed before ABMs fully leverage high performance computing environments. Fundamentally these issues are caused by the spatiotemporal characteristics of ABM, which make their parallelization challenging.

We propose a parallel framework for spatially-explicit ABM. The goal of the framework is to support millions of agents and scale to hundreds of processors with excellent performance using the TeraGrid, which is the worlds largest distributed cyberinfrastructure for scientific research. It is used by GISolve (www.gisolve.org) and other GIScience research \cite{shaowen}.

Approach

/* and limit the spatiotemporal problems associated with ABMs */ We present an effective parallel framework to simulate large-scale ABM which is designed to fully exploit high performance computing environments with hundreds of teraflops peak performance. The underpinnings of the framework are the parallel workflow algorithm and communication strategies which enable the framework to offer:

  • efficient parallel processor scaling;
  • effective agent migration across processors;
  • environment boundary sharing;
  • independent communication strategies; and
  • life cycle operations completed in constant time [ e.g. O(1) ].

The parallel ABM workflow \alg{1} is similar to serial ABM workflows with two additional parallel communication steps. Serial ABMs could be parallelized using this approach by adding the two parallel communication steps and handling environment decomposition. This is possible, because the parallel communication and non-parallel computation are partitioned in such a way that the computation is independent of the communication.

Initialization
  Environment decomposition
  Setup parallel communication
  Initialize agents, environment, and buffers
Simulation
  In each iteration
    Environment Update
      Environment boundary sharing * Parallel communication
      Environment update
    Agent Update
      Agent population look and move
      Agent migration * Parallel communication
    Agent/Environment interactions
Finalize
  Collect and output results

Figures 1 and 2 illustrate the data structures that support the workflow by separating the computation data (e.g. agents and the environment) from the communication data (e.g. buffers). Decoupling these data structures enables the platform to accommodate various communication, decomposition, and load-balancing strategies \cite{HPABM,load-balancing paper} and to support synchronous and asynchronous communication. The drawbacks of this approach include potentially unnecessary communication by sending semi-empty groups and performing unnecessary computation by iterating over dead agents and empty buffer groups. However, the flexibility gained by decoupling the data structures considerably outweighs the minor performance losses.

 Figure 1 Figure 1 Agent structures

 Figure 2 Figure 2 Environment with Ghost regions and 2 agents with vision distance = 2

/* Move into figures (shrinking of course)

The population is a set of groups which hold a an array of agents, in Figure 1.  Both agents and groups can be linked lists.  Free agents is a linked-list of the agents in the population that are not alive.  A similar list is available for migrating agents.  Agent buffers are single instance groups to buffer migrating agents.  The grid, in Figure 2, consists of subsection of the array of cells in the simulation surrounded by a set of "ghost zones" which contain neighboring grid information.  Grid buffers are arrays to buffer the "ghost zones".

*/

Communication often determines the potential scalability in parallel systems. If the communication paradigm generates excessive overhead the simulation will not scale to hundreds of parallel processors. It is crucial to identify a fitting communication strategy that introduces minimal overhead and scales efficiently. Our framework uses a distributed communication strategy where each processor is organized into a cartesian grid and sends its respective data to the neighboring processor to the north, south, east, then west in parallel. This strategy scales to any number of processors and results in the processor organization directly mapping to block-based environment decomposition. Environment boundary sharing is straightforward, because the data is always regular (e.g. same number of data elements shared every iteration). Figure 3 depicts the stages in the environment communication step. Agent migration, unlike the environment sharing, is irregular and requires additional work. The agent communication strategy must handle any number of agents migrating to and from the processor. This is accomplished by sending a populated group in each direction, similar to the environment communication stages. The key difference between these two steps is if the sending or receiving group is full, then the processor will continue sending and/or receiving groups of agents until all agents have been migrated to and from the processor; thus handling any number of agents. The two presented strategies are shown to be scalable, but could easily be replaced with different communication strategies particularly if dynamic domain decomposition is used.

/* The environment communication step is regular and straightforward. MAKE COMMUNICATION MORE GENERIC AND PUT SPECIFICS INTO FIGURE CAPTION For example if sending in the north direction: 1) copy the northern edge into the buffer and send to north processor, 2) receive the south processor's grid edge in the buffer, and 3) copy the data in the receive buffer into the south ghost zone. Agent migration, however, is irregular and requires additional work. If sending in the north direction, for example, all processors execute the following steps: 1) populate the send group buffer with agents migrating north, 2) receive the south processor's group in the receive buffer, and 3) move agents from the buffer to the population. If the send or receive group buffer is full, then continue sending and/or receiving groups of agents until all agents have been migrated to and from the processor. */ /* add 2 diagrams for communication (combined pics into 1 diagram)*/

Figure 3 (series of 4 diagrams copying env data NSEW)

This paper offers a framework to effectively parallelize spatially-explicit ABM simulations by separating communication and computation. Our approach is able to leverage current work in load-balancing techniques and spatial environment decomposition methods to address current parallelization issues in ABM simulations. It is shown to be scalable and offers excellent performance.

Case Study

/*Introduce case study */ We use empirical analysis to study the effect that agent and environment spatial characteristics have on parallel performance of ABMs. As a case study we implemented a parallel version of the Sugarscape model \cite{sugarscape} written in C and the Message Passing Interface (MPI). The implementation includes the environment growback rule G, agent movement rule M, and agent replacement rule R.

/* summarize exp */

  1. Look at efficiency (compare to linear speedup in graph).
  2. Look at changing communication/computation ratio.
  3. Present scaling numbers (maximum resolution and agent count)
  4. Look at the effect of load imbalance

/* results */ /* Load-imbalance can have X% impact on performance refer to Load Balancing.pdf from Kale for specific examples to use .... */ === Conclusion === Using an innovative approach, we have made significant progress toward enabling scalable parallel ABMs to facilitate the study of more complex geographic phenomena at finer spatial resolutions. We examined the effect that spatially-explicit characteristics of ABMs have on parallel performance. The technical strategies proposed have been shown to efficiently scale to X processors supporting A agents with RxC cells. Our approach can leverage and can be leveraged by other work in parallel ABM literature and provides a solid platform to build an effective parallel ABM simulation framework. /* These factors heavily influence the ability for ABMs to scale in order to study more complex phenomena. */ /* Unintuitively allocating space for a single agent costs more than allocating space for an array of agents based on simple timing tests. Therefore when the population reaches the current storage capacity a new groupstruct is allocated to store more agents. The initial allocation costs less in addition we gain groupsize-1 allocations for free, because the remaining agents are added to the free agents list. */ /* Isoefficiency? Empirical methods are used (code timing) Statistical analysis may also be used to produce general findings. */ FIXME need to add some background work at the end of approach === References === @article{railsback2006abs, title=review_and_development_recommendations, author={Railsback, S.F. and Lytinen, S.L. and Jackson, S.K.}, journal={SIMULATION}, volume={82}, number={9}, pages={609}, year={2006}, publisher={SCS} } ====== Guidelines ====== - Abstract + References < 1000 words - 1500 word length MAXIMUM for entire document - In .doc standard template (attached on CISG email) - Must submit signed document and extended abstract by November 12 ==== Extended Abstract Guidelines ===== - Pulled from http://www.sigplan.org/conferences/author-info/pughadvice.html - An extended abstract is not simply a long abstract. An extended abstract should contain references, comparisons to related work, proofs of key theorems and other details expected in a research paper but not in an abstract. - An extended abstract is a research paper whose ideas and significance can be understood in less than an hour. Writing an extended abstract can be more demanding than writing a research paper. - Some things that can be omitted from an extended abstract: future work, details of proofs or implementation that should seem plausible to reviewers, ramifications not relevant to the key ideas of the abstract. - An ideal submission should have a reviewer intrigued within the first 5 minutes of reading, excited within 15 minutes and satisfied within 45 minutes. If your abstract fails any of these tests, it might be rejected no matter how good the research is. - Don't overlook the importance of the introduction, figures, examples, and conclusions (and measurements if applicable) in an extended abstract. - Remember that some program committee members, of necessity, are not experts in your area of research and that when they pick up your abstract they may have already reviewed 8 abstracts that day. Material that may take an expert in your area 5 minutes to go through might take some committee members 20 minutes or more. Back to index