Parallel Automata Processor
Parallel Automata Processor
复制标题
并行自动机处理器
DOI：
10.1145/3140659.3080207
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Das, Reetuparna
中科院分区：
文献类型：
--
作者：
Subramaniyan, Arun;Das, Reetuparna
有限状态机（FSM）是广泛应用于许多应用领域的计算模型。这些具有不规则存储器访问模式的顺序应用程序在传统的冯-诺依曼架构上表现不佳。Micron Automata Processor（AP）是一种基于内存的计算架构，可加速硬件中的非确定性有限自动机（NFA）处理。然而，AP上的每个FSM都是顺序处理的，限制了潜在的加速比。由于高状态转换跟踪开销和指数计算复杂度，将经典并行化技术扩展到在AP上执行的NFA是不平凡的。我们提出了相关的挑战，并提出了解决方案，利用这两个独特的性质的NFA（连接组件、输入符号范围、收敛、公共父状态）和AP中的独特功能（支持同时转换，低开销流交换，状态向量高速缓冲存储器）为了在AP上实现并行NFA执行，我们针对几个重要的基准测试（包括用于网络入侵的NFA）来评估我们的技术检测、恶意软件检测、文本处理、蛋白质基序搜索、DNA测序和数据分析。我们提出的并行化方案表现出显着的加速（平均25.5倍）相比，顺序执行AP。之前的工作已经表明，AP上的顺序执行至少比GPU，多核处理器和Xeon Phi加速器好一个数量级。
Finite State Machines (FSM) are widely used computation models for many application domains. These embarrassingly sequential applications with irregular memory access patterns perform poorly on conventional von-Neumann architectures. The Micron Automata Processor (AP) is an in-situ memory-based computational architecture that accelerates non-deterministic finite automata (NFA) processing in hardware. However, each FSM on the AP is processed sequentially, limiting potential speedups.In this paper, we explore the FSM parallelization problem in the context of the AP. Extending classical parallelization techniques to NFAs executing on AP is non-trivial because of high state-transition tracking overheads and exponential computation complexity. We present the associated challenges and propose solutions that leverage both the unique properties of the NFAs (connected components, input symbol ranges, convergence, common parent states) and unique features in the AP (support for simultaneous transitions, low-overhead flow switching, state vector cache) to realize parallel NFA execution on the AP.We evaluate our techniques against several important benchmarks including NFAs used for network intrusion detection, malware detection, text processing, protein motif searching, DNA sequencing, and data analytics. Our proposed parallelization scheme demonstrates significant speedup (25.5x on average) compared to sequential execution on AP. Prior work has already shown that sequential execution on AP is at least an order of magnitude better than GPUs, multi-core processors and Xeon Phi accelerator.