Accelerated Pattern Recognition Processing Using Hybrid Spatial/Von Neumann Architectures

Newly available spatial architectures to accelerate finite automata-based pattern recognition processing have spurred a large amount of research and development of finite automata-based applications and accelerators. However, a lack of standard, open-source tools for automata processing application and architecture research has slowed the pace of innovation.

This dissertation first presents a new non-obvious application use-case for automata processing: efficient and high-quality pseudo-random number generation, further motivating research into automata processing acceleration. This dissertation then presents three new tools to enable and accelerate high-quality automata processing research. The first tool is a novel automata processing simulation, profiling, and optimization framework to accelerate automata application and architecture research. The second tool is a diverse benchmark suite of standardized automata graphs and inputs from published work to provide easy and fair comparisons among automata processing engines and architectures. The third tool is design-space exploration tool to help design and build spatial/reconfigurable automata processing architectures.

This dissertation then presents two novel architecture studies, enabled by the above toolchain. The first study characterizes spatial automata processor output processing and recognizes it as an important bottleneck to performance in real systems. We relax this bottleneck by designing a parameterizable reporting architecture to efficiently accommodate common-case behavior. The final study recognizes that automata states can have highly contrasting behavior. We dynamically profile automata graphs and find that some states perform orders of magnitude less computation than others. We propose a hybrid automata processing approach where highly active states are computed using spatial architectures, while rarely active states are offloaded to a von Neumann processor. This offloading can greatly reduce the resource pressure on the spatial automata processor, while maintaining a large proportion of acceleration potential.