Computational Science Technical Note CSTN-027


Grid-Boxing for Spatial Simulation Performance Optimisation

K. A. Hawick, H. A. James and C. J. Scogings

Archived September 2005


Computer simulations of complex systems such as physical aggregation processes or swarming and collective behaviour of life-forms, often require order N-squared computational complexity for N microscopic components. This is a significant handicap to simulating systems large enough to compare with real-world experimental data. We discuss space partitioning methods for two such simulation codes and demonstrate complexity improvements by taking advantage of information about locations and interaction distances of the microscopic model components. The space of our models are partitioned into grid-boxes. We present results for a diffusion-limited cluster-cluster aggregation code and for an artrificial life simulation code. We discuss the data structures necessary to support such algorithms and show how they can be implemented to obtain high performance and maximal simulation productivity for a given computational resource. There are some subtlties in whether such spatial partitioning algorithms should produce a computational complexity of N to some power between 1 and 2 or whether they should be order N log N. We discuss these effects in the context of our data.

Keywords: complexity; particle-in-grid; performance optimisation.

Full Document Text: PDF version.

Citation Information: BiBTeX database for CSTN Notes.

BiBTeX reference:

  author = {K. A. Hawick and H. A. James and C. J. Scogings},
  title = {Grid-Boxing for Spatial Simulation Performance Optimisation},
  booktitle = {Proc. 39th Annual Simulation Symposium},
  year = {2006},
  editor = {T. Znati},
  pages = {98-106},
  address = {Huntsville, Alabama, USA},
  month = {2-6 April},
  organization = {The Society for Modeling and Simulation International},
  publisher = {IEEE Computer Society}

[ CSTN Index | CSTN BiBTeX ]