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: Proc 39th Annual Simulation Symposium - 2-6 April 2006, Huntsville Alabama, USA, Pub. IEEE Computer Society.
BiBTeX reference:
@inproceedings{CSTN-027,
address="Huntsville, Alabama, USA",
title="Grid-Boxing for Spatial Simulation Performance Optimisation",
author="K.A.Hawick, H.A.James and C.J.Scogings",
booktitle="Proc. 39th Annual Simulation Symposium",
editor="T.Znati",
year="2006",
pages="CD",
month="April",
note="The Society for Modeling and Simulation International, Pub. IEEE Computer Society",
series="CSTN-027"
}
\bibitem{CSTN-027}
Grid-Boxing for Spatial Simulation Performance Optimisation,
K.A.Hawick, H.A.James and C.J.Scogings,
Proc. 39th Annual Simulation Symposium, Huntsville, Alabama, USA, edited by T.Znati,
2-6 2006 April, The Society for Modeling and Simulation International, Pub. IEEE Computer Society,
and Technical Note CSTN-027.