Efficient parallel implementation of cellular automata and stencil computations in current processors

Abstract

A Cellular Automaton is a bio-inspired discrete model of computation with multiple applications, consisting of a regular grid of cells that have different states a long time. Our research group at the University of Seville(Spain)collaborated in the past with Prof. Mohammad S. Obaidat in the fusion of Cellular Automata(CA) with another bio-inspired approach, the Address-Event-Representation (AER) neuromorphic communication protocol, for implementing a vision filter based on 3×3 convolutions[22].In the last years, our group has continued working on the optimization of CA implementations in current high-performance computational systems. In this chapter, several of these optimizations will be described, focusing on those especially a mediated current processor, including hardware alternatives (e.g. GPUs, BTBs, etc.), different forms of parallelism such as instruction-level parallelism, thread-level parallelism, data-level parallelism, as well as software approaches (such as ‘if-else’ statement elimination, loop unrolling, data pipelining and blocking, etc.). The effect of these optimizations will be qualitatively illustrated by means of the Roof line model, considering simple CAs such as the well-known Game-of-Life (GOL), which has been extensively used to explore CA characteristics. This CA was invented by John Horton Conway, an English mathematician that recently died of complications from COVID-19, so we want this case-study to serve also as a tribute to him.