In this new world of heterogeneous computing, automata processing has seen renewed interest with the advent of new workloads like machine learning, gene sequence matching, and other established disciplines like compiler design. This paper makes a good case for state-of-the-art field-programmable gate arrays (FPGAs) to powerfully assist automata processing.

Traditional sequential processors like central processing units (CPUs) and graphics processing units (GPUs) need to store states and transition rules in the memory. This can suffer from look-up latencies due to random-access memory. For large dataset input streams, this can be inefficient.

Traditionally, processing/matching an input sequence can be done using finite automatons or non-finite automatons. Non-finite automatons are spatially optimized, as only the active states need to be stored and parsed, but loading new activation states can cause latencies in memory lookup. Finite automatons for small datasets are runtime optimized and look-up optimized, as no new states need to be loaded in the memory. However, a large memory footprint is required for large active states. A middle path approach of converting non-finite automaton graphs to a defined finite automaton graph at each activation state can reduce memory lookups.

FPGAs and domain-specific hardware like Micron’s Automata Processor store states and transition graphs in hardware logic circuitry, and this forms the basis for the authors’ interest in implementing an FPGA-based reconfigurable automaton processor. The authors present an implementation using Xilinx Vivado HLS and SDAccel, and test it on two public cloud infrastructures, NImbix and Amazon EC2 F1. They show favorable results for their implementation using the ANMLZoo benchmark.

It should come as no surprise that most of the power and resources consumed by the circuitry is due to the input/output (I/O) infrastructure required to move data from the host memory to the FPGA attached memory, and vice versa. The memory wall is a hotly debated discussion point in a post Moore’s era world, and many architects and researchers have advocate for the reduction of memory lookups using in-memory computing techniques. This end-to-end design implementation makes a case for reconfigurable architectures.