Skip navigation.

James Balasalle successfully defended his MS Thesis: Memory Access Patterns for Cellular Automata Using GPGPUs

The abstract of his thesis:

Today's graphical processing units have hundreds of individual processing cores that
can be used for general purpose computation of mathematical and scientific c problems.
Due to their hardware architecture, these devices are especially e ffective when solving
problems that exhibit a high degree of spatial locality. Cellular automata use small,
local neighborhoods to determine successive states of individual elements and therefore,
provide an excellent opportunity for the application of general purpose GPU
computing. However, the GPU presents a challenging environment because it lacks
many of the features of traditional CPUs, such as automatic, on-chip caching of data.
To fully realize the potential of a GPU, specialized memory techniques and patterns
must be employed to account for their unique architecture. Several techniques are
presented which not only dramatically improve performance, but, in many cases, also
simplify implementation. Many of the approaches discussed relate to the organization
of data in memory or patterns for accessing that data, while others detail methods of
increasing the computation to memory access ratio. The ideas presented are generic,
and applicable to cellular automata models as a whole. Example implementations
are given for several problems, including the Game of Life and Gaussian blurring,
while performance characteristics, such as instruction and memory accesses counts,
are analyzed and compared. A case study is detailed, showing the e effectiveness of
the various techniques when applied to a larger, real-world problem. Lastly, the reasoning
behind each of the improvements is explained, providing general guidelines for
determining when a given technique will be most and least e effective.