Pipelined Parallel Finite Automata Evaluation
Vipula Sateesh, Connor Mkckeon, Jared Winograd, and André DeHon
Proceedings of the IEEE International Conference on Field-Programmable Technology,
(FPT, December 11--13, 2019)
Finite automata are key compute models in modern computational theory and
important building blocks for digital logic used for regular expression and protocol
parsing, filtering, and control. Finite automata evaluation would seem to
be a sequential operation, since we need to complete the evaluation of one
state to know the next state in which to evaluate the logic. Nonetheless,
parallel theory provides strategies for parallel finite automata
evaluation. We show how to exploit this parallel evaluation strategy in
practice on today's high capacity FPGAs, including a novel formulation
for spatially pipelined evaluation. For non-deterministic finite
automata (NFA) with S states, we can evaluate N inputs in a single cycle with
O(N*S2) BRAMs
and O(N*S3) LUTs.
This allows us, for
example, to consume 64 inputs on a 16 state NFA in a single cycle on the
Xilinx XZCU9EG-ffvb1156-2-i SoC FPGA, achieving
47 GB/s (377 Gb/s) single stream throughput for 8b inputs.
For a 40 Gb/s network link, we can support 28 state NFAs.
© 2019 IEEE. Personal use of this material is
permitted. However, permission to reprint/republish this material
for advertising or promotional purposes or for creating new
collective works for resale or redistribution to servers or lists,
or to reuse any copyrighted component of this work in other works
must be obtained from the IEEE.
This material is presented to ensure timely
dissemination of scholarly and technical work. Copyright and all
rights therein are retained by authors or by other copyright
holders. All persons copying this information are expected to
adhere to the terms and constraints invoked by each author's
copyright. In most cases, these works may not be reposted without
the explicit permission of the copyright holder.
(
IEEE Copyright)
|
