TR-2015-05
EffCLiP: Efficient Coupled-Linear Packing for Finite Automata
Yuanwei (Kevin) Fang; Andrew Lehane; Andrew A Chien. 30 May, 2015.
Communicated by Andrew Chien.
Abstract
Finite-automata are widely-recognized as a funda- mental computing model with a broad range of applications, notably network monitoring. We propose a new approach, “efficient coupled-linear packing” (EffCLiP), that optimizes both finite-automata size and performance. EffCLiP employs a novel transition representation that enables a simple addressing op- erator (integer addition) while providing flexibility to support transition packing. EffCLiP is a general approach, and we show how it can be used for not only DFA but also a wide range of models such as NFA, A-DFA, and Aho-Corasick multi-string matching. We observe a new structure in finite automata, called “majority tail” and document its frequency.Based on these, we present a novel algorithm for efficient transition packing (efficient coupled-linear packing). We also present a new finite-automata optimization algorithms “majority compression” that exploits the majority tail phenomena. Evalu- ation across a variety of widely-used finite automata workloads and models show that EffCLiP achieves compression rates as high as 8.4x and packing densities of 77% for DFA, 2.24x and >99% for A-DFA, 3.9x and >99% for NFA while supporting high speed and simple implementation.
Original Document
The original document is available in PDF (uploaded 30 May, 2015 by Andrew Chien).