Computing Shortest Path In-memory with Cellular Automata

Abstract

This work explores finite cellular automata (CAs) defined over a Cayley tree. Each cell of the CA is equipped with a memory unit and a tiny processing element. The computation paradigm of the proposed model leverages data-intensive computation within memory, thereby effectively realizing an in-memory computing (IMC) platform. The effectiveness of the proposed model is demonstrated while finding the shortest paths from a given source to all destinations in an arbitrary graph. The computation of the shortest path is completed in $h$ steps, where $h$ is the height of the Cayley tree.