A PARALLEL SLIDING REGION ALGORITHM TO MAKE AGENT-BASED MODELING POSSIBLE FOR LARGE-SCALE SIMULATION

Purpose:   Agent-based models (ABMs) are computer simulation models, which are possible to define interactions among agents, and then simulate emergent behavior that arises from the ensemble of local decisions.  ABMs have been increasingly used to examine trends in infectious disease epidemiology.  However, the main limitation of ABMs is computational intensiveness, especially for large-scale simulation.  To determine the magnitude of efficiency for large-scale ABM simulation, we built a parallelizable sliding region algorithm (SRA) for ABM and compared it against with a non-parallelizable ABM.

Method: The SRA defines three simulation regions: 1) Entire simulation region (ESR): the universe of the ABM (e.g., a province in Canada); 2) Postal-code simulation region (PSR): a smaller region associated with a postal-code that the ABM is currently working on; 3) Interaction region (IR) – region that is bigger than the PSR, which contains extra postal-codes to provide further inter-postal-code interactions for the agents.  The SRA starts the simulation with an arbitrary PSR and IR within the ESR.  Once the algorithm finishes simulating the initial PSR, it then moves to the next PSR and redefines the IR for the next simulation. It continues to move the PSR and the IR until the algorithm covers the whole ESR. Figure 1 illustrates this concept.  

Result: To demonstrate the SRA, we used our recently developed complex agent network model to perform two simulations on Saskatchewan, a Canadian province, with 985,386 population in 45 postal-codes.  One simulation used the SRA and worked on the postal-code one by one, while another simulation simulated the entire population all-at-once. Simulations were performed in two 2 quad core Xeon 2.4 Ghz servers with 96Gb of memory. SRA required 345 minutes to simulate one postal-code on average.  With 16 parallel processes, the SRA completed the entire province in 980 minutes.  On the other hand, the all-at-once simulation required 1,132 minutes to simulate the entire province.  In terms of results, both simulations provided very similar results.  However, the memory requirements for the SRA were much lower.

Conclusion:   Our parallelizable SRA showed good computational time and reasonable simulation results in a province-wide simulation.  Using the same method, SRA can be generalized for performing a countrywide simulation.  Thus, this parallel algorithm enables the possibility of using ABM for large-scale simulation with limited computational resources.