Experiences in data-parallel simulation and analysis of complex systems with irregular graph structures : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Albany, New Zealand
The interactions between the components of many natural and artificial systems can be described using
a graph. These graphs often have an irregular structure with non-trivial topological features. Complex
system behaviour emerges on the macroscopic scale from a large number of relatively simple interactions
on the microscopic scale. To better understand the observed behaviour of a complex system, the interactions
among its basic elements are commonly described in a computational model. As long as the interactions are
defined accurately and the number of elements is large enough for complex patterns to emerge, a simulation
based on such a model is expected to produce the same behaviour as the system under investigation.
The difficulty is often to simulate the model on a large enough scale to obtain scientifically meaningful
results. Powerful computer systems are required to calculate the effects caused by the interactions of large
numbers of elements. Supercomputers that are constructed from hundreds of thousands of processing units
can be used to update many components of the system in parallel and thus reduce the overall simulation
time, but these systems are expensive to buy and maintain. As the processor architectures used in workstations
and regular desktop computers are becoming more powerful, a small cluster constructed from these
systems can be a more viable option. In recent years, the highly data parallel architecture of commodity
graphics processing units (GPUs) has received a growing amount of attention due to their high peak compute
throughput compared to central processing units (CPUs). New software development tools that turn
the GPU hardware into a general purpose compute accelerator have become available.
This thesis describes how GPUs can be used to accelerate scientific simulations of complex systems that
are based on irregular graph structures. New software development approaches and algorithms are needed
to fully utilise the data parallel many-core architecture of today’s GPUs. Irregular graph structures are particularly
challenging, as the hardware is based on the single instruction, multiple data (SIMD) processor
design, where a group of processing elements receives the same instructions. The architecture also imposes
strict requirements on memory access patterns, making the optimisation of the memory layout for the irregular
data structures and associated information particularly important. Performance suffers dramatically
when the algorithm does not comply with these design restrictions.
The author proposes different software design strategies for a number of common graph problems and
discusses the advantages and disadvantages of each approach. Two complex system models are used to
demonstrate how the GPU can help to accelerate scientific simulations. The first model investigates how
the phase transition from ordered to disordered system states in a computational ferromagnet is affected
by distortions to the lattice substrate. The second model implements a large scale spiking neural network.
The findings show that it is beneficial to utilise the GPU as accelerator to the CPU in almost all scenarios,
as long as the project has a long enough run time to justify the more complex software development of
the data parallel algorithms. When the model has some regularities in its structure or when some of the
design decisions that influence the way memory is accessed can be made with the data parallel architecture
in mind, then it is possible to achieve such high performance on the graphics device that it is best to leave
the entire computational work to the GPU and use the CPU only to manage the execution of the program.