Demystifying automata processing: GPUs, FPGAs or Micron's AP?
Demystifying automata processing: GPUs, FPGAs or Micron's AP?
复制标题
揭秘自动机处理：GPU、FPGA 还是美光的 AP？
DOI：
10.1145/3079079.3079100
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Becchi
中科院分区：
文献类型：
--
作者：
Marziyeh Nourian;Xiang Wang;Xiaodong Yu;Wu;M. Becchi
许多已建立的和新兴的应用程序在其核心执行某种形式的模式匹配，这是一种自然映射到有限自动机抽象的计算。因此，近年来，人们在高速自动机处理方面开展了大量工作，从而催生了许多针对各种并行平台的实现：CPU、GPU、FPGA、ASIC 和网络处理器。最近，美光宣布推出自动机处理器 (AP)，这是一种基于 DRAM 的非确定性有限自动机 (NFA) 加速器。尽管该领域的工作非常丰富，但不同自动机处理加速器的优缺点以及该领域的创新空间仍不清楚。在这项工作中，我们针对这个问题并提出了一个工具链，可以对 GPU、FPGA 和美光 AP 三个平台上的 NFA 加速引擎进行同类比较。我们讨论适用于这三个平台的自动机优化。我们对大规模数据集进行评估：为此，我们提出了一种 NFA 分区算法，该算法最大限度地减少了与未分区 NFA 保持功能等效性所需的状态复制数量，并且我们评估了每个实现对大型 NFA 和大量输入流的可扩展性。我们的实验评估涵盖了资源利用率、遍历吞吐量和预处理开销，并表明 FPGA 以大量预处理时间（小时级）为代价提供了最佳遍历吞吐量（Gbps 级）； GPU 提供适度的遍历吞吐量（大约为 Mbps），但提供较低的预处理时间（大约为秒或分钟）和良好的模式密度（它们可以在单个设备上容纳大型数据集）；美光的 AP 提供的吞吐量、模式密度和预处理时间介于 FPGA 和 GPU 之间，最适合使用由许多小型 NFA 组成的数据集的应用程序，这些小型 NFA 的拓扑是固定且已知的。
Many established and emerging applications perform at their core some form of pattern matching, a computation that maps naturally onto finite automata abstractions. As a consequence, in recent years there has been a substantial amount of work on high-speed automata processing, which has led to a number of implementations targeting a variety of parallel platforms: CPUs, GPUs, FPGAs, ASICs, and Network Processors. More recently, Micron has announced its Automata Processor (AP), a DRAM-based accelerator of non-deterministic finite automata (NFA). Despite the abundance of work in this domain, the advantages and disadvantages of different automata processing accelerators and the innovation space in this area are still unclear. In this work we target this problem and propose a toolchain to allow an apples-to-apples comparison of NFA acceleration engines on three platforms: GPUs, FPGAs and Micron's AP. We discuss the automata optimizations that are applicable to these three platforms. We perform an evaluation on large-scale datasets: to this end, we propose an NFA partitioning algorithm that minimizes the number of state replications required to maintain functional equivalence with an unpartitioned NFA, and we evaluate the scalability of each implementation to both large NFAs and large numbers of input streams. Our experimental evaluation covers resource utilization, traversal throughput, and preprocessing overhead and shows that the FPGA provides the best traversal throughputs (on the order of Gbps) at the cost of significant preprocessing times (on the order of hours); GPUs deliver modest traversal throughputs (on the order of Mbps), but offer low preprocessing times (on the order of seconds or minutes) and good pattern densities (they can accommodate large datasets on a single device); Micron's AP delivers throughputs, pattern densities, and preprocessing times that are intermediate between those of FPGAs and GPUs, and it is most suited for applications that use datasets consisting of many small NFAs with a topology that is fixed and known a priori.