Algorithmic Techniques for Solving Graph Problems on the Automata Processor
Indranil Roy, Nagakishore Jammula, Srinivas Aluru · 2016
The Automata Processor is a new accelerator technology that supports direct hardware implementation of a set of non-deterministic finite automata over a streaming input, and is designed for complex string pattern matching applications. In this paper, we broaden the scope of this architecture beyond its primary design goal, by developing algorithmic techniques to solve problems on unweighted graphs. We present a strategy to represent nodes and edges in a graph using strings, and use this transformation to develop algorithms for several classic graph problems including finding Hamiltonian paths and cycles, connected components, and breadth-first search. Our algorithms rely on a core set of automata building blocks which we designed for this purpose, and illustrate various design considerations that developers must bear in mind when harnessing this new technology. We expect that this work provides the foundations for solving graph problems using the Automata Processor.