Item Details

Subset Encoding: Increasing Pattern Density for Finite Automata

Guo, Deyuan; Brunelle, Nathan; Bo, Chunkun; Wang, Ke; Skadron, Kevin
Format
Report
Author
Guo, Deyuan
Brunelle, Nathan
Bo, Chunkun
Wang, Ke
Skadron, Kevin
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.
Language
English
Date Received
20160404
Published
University of Virginia, Department of Computer Science, 2015
Published Date
2015
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online