Subset Encoding: Increasing Pattern Density for Finite Automata

Report
Authors:Guo, Deyuan, Department of Computer ScienceUniversity of Virginia Brunelle, Nathan, Department of Computer ScienceUniversity of Virginia Bo, Chunkun, Department of Computer ScienceUniversity of Virginia Wang, Ke, Department of Computer ScienceUniversity of Virginia Skadron, Kevin, Department of Computer ScienceUniversity of Virginia
Abstract:

Micron's Automata Processor is an innovative reconfigurable hardware accelerator for parallel finite-automata-based regular-expression matching. While the Automata Processor has demonstrated potential for many pattern matching applications, other applications receive reduced benefit from the architecture due to capacity limitations or routing limitations. In this paper, we present an efficient input encoding method that often results in simplified automata designs and simplified routing by better exploiting the powerful character matching abilities of the Automata Processor. This enables the Automata Processor to more efficiently solve problems for a broad range of new applications. We present Hamming distance, edit distance, and Damerau-Levenshtein distance automata as motivating examples, observing space efficiency improvements up to 192x.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Guo, Deyuan, Nathan Brunelle, Chunkun Bo, Ke Wang, and Kevin Skadron. "Subset Encoding: Increasing Pattern Density for Finite Automata." University of Virginia Dept. of Computer Science Tech Report (2015).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2015