A Compiler Framework for Fixed-Topology Non-Deterministic Finite Automata on SIMD Platforms

Authors: Marziyeh Nourian (North Carolina State University), Hancheng Wu (North Carolina State University), Michela Becchi (North Carolina State University)

Abstract: Automata traversal acceleration has been studied on various parallel platforms. Many existing acceleration methods store finite automata states and transitions in memory. For these designs memory size and bandwidth are the main limiting factors to performance and power efficiency. Many applications, however, require processing several fixed-topology automata that differ only in the symbols associated to the transitions. This property enables the design of alternative, memory-efficient solutions. We target fixed-topology non-deterministic finite automata (NFAs) and propose a memory-efficient design, suitable to SIMD architectures, that embeds the automata topology in code and stores only the transition symbols in memory. We design a compiler that automates deployment of this design on SIMD platforms for a set of fixed-topology NFAs. Our compiler framework performs a combination of platform-agnostic and platform-specific design decisions and optimizations. This poster describes the compiler toolchain and shows the achieved throughput on GPU and Intel SIMD devices.

Best Poster Finalist (BP): no

Poster: pdf
Poster summary: PDF
Reproducibility Description Appendix: PDF


Back to Poster Archive Listing