An Overlay Architecture for Pattern Matching

摘要

Deterministic and Non-deterministic Finite Automata (DFA and NFA) comprise the fundamental unit of work for many emerging big-data applications, motivating recent efforts to develop Domain-Specific architectures (DSAs) to exploit fine-grain parallelism available in automata workloads. In this paper we present NAPOLY (Non-Deterministic Automata Processor OverLaY), an overlay architecture and associated software that attempts to maximally exploit on-chip memory parallelism for NFA evaluation. In order to avoid an upper bound on NFA size that commonly affects prior efforts, NAPOLY is optimized for runtime reconfiguration, allowing for full reconfiguration in 10s of microseconds. NAPOLY is also parameterizable, allowing for offline generation of a repertoire of overlay configurations with various trade-offs between state capacity and transition capacity. In this paper we evaluate NAPOLY using our proposed state mapping heuristic and the ANMLZoo benchmark suite, and we compare NAPOLY's performance against existing CPU and GPU implementations. To the best of the authors' knowledge this is the first example of a runtime-reprogrammable FPGA-based automata processor overlay.