FPGA开源框架Grapefruit：加速正则表达式设计与探索

需积分: 0 108 浏览量更新于2024-08-04 收藏 680KB PDF 举报

Grapefruit是一个创新的开源项目，旨在为FPGA（Field-Programmable Gate Array）平台提供全面、定制化的有限状态自动机（Finite State Automata, FSA）处理解决方案。这项2020年的IEEE论文由Reza Rahimi、Elaheh Sadredini、Mircea Stan和Kevin Skadron四位来自弗吉尼亚大学的专家共同开发，他们分别来自电气与计算机工程系和计算机科学系。正则表达式在诸如网络安全、机器学习和自然语言处理等领域有着广泛应用，对它们进行加速的需求日益增长。FPGA因其灵活性和性能优势，成为了理想的加速平台。然而，市场上缺乏一个公开、全面且易于使用的框架，能够支持广泛的增长性模式匹配应用的设计空间探索。 Grapefruit填补了这一空白，它是一个全新的、全栈的FPGA自动化处理框架，具备高效的编译器和丰富的参数，能够适应各种规模的自动机处理任务。其特点包括： 1. **开源性**：Grapefruit作为开源项目，意味着开发者可以自由地获取源代码并根据需要进行修改或扩展，促进了社区的合作与创新。 2. **全栈设计**：该框架覆盖了从输入正则表达式到硬件实现再到实际应用的全过程，提供了端到端的解决方案，简化了用户的使用流程。 3. **可定制化**：框架内嵌的编译器允许用户调整多个参数，以优化特定应用的性能，满足不同场景下的需求。 4. **效率和可扩展性**：Grapefruit致力于提供高效的处理能力，随着应用程序的扩大，它也能够轻松扩展，保持性能上的竞争力。 5. **易用性**：论文强调了Grapefruit的易用性，这意味着即使是对FPGA不熟悉的开发者也能相对容易地理解和使用这个工具。通过Grapefruit，研究人员和工程师能够更加便捷地利用FPGA技术来加速正则表达式匹配，从而在需要高速、高效和定制化处理的应用场景中取得显著性能提升。这对于推动FPGA在更广泛的领域中的应用具有重要意义，并有望在未来推动整个行业的技术进步。

Grapefruit: An Open-Source, Full-Stack, and

Customizable Automata Processing on FPGAs

Reza Rahimi

, Elaheh Sadredini

, Mircea Stan

, Kevin Skadron

Department of Electrical & Computer Engineering,

Department of Computer Science

University of Virginia

Charlottesville, Virginia, USA

Email: {rahimi, elaheh, mircea, skadron}@virginia.edu

Abstract—Regular expressions have been widely used in var-

ious application domains such as network security, machine

learning, and natural language processing. Increasing demand for

accelerated regular expressions, or equivalently ﬁnite automata,

has motivated many efforts in designing FPGA accelerators.

However, there is no framework that is publicly available,

comprehensive, parameterizable, general, full-stack, and easy-to-

use, all in one, for design space exploration for a wide range of

growing pattern matching applications on FPGAs. In this paper,

we present Grapefruit, the ﬁrst open-source, full-stack, efﬁcient,

scalable, and extendable automata processing framework on

FPGAs. Grapefruit is equipped with an integrated compiler with

many parameters for automata simulation, veriﬁcation, mini-

mization, transformation, and optimizations. Our modular and

standard design allows researchers to add capabilities and explore

various features for a target application. Our experimental results

show that the hardware generated by Grapefruit performs 9%-

80% better than prior work that is not fully end-to-end and

has 3.4× higher throughput in a multi-stride solution than a

single-stride solution.

I. INTRODUCTION

Finite automata are an efﬁcient computational model for

widely used pattern recognition languages such as regular

expressions, with applications in network security [1], [2], log

analysis [3], and newly-demonstrated other applications in do-

mains such as data-mining [4], [5], [6], [7], bioinformatics [8],

[9], machine learning [10], [11], natural language processing

[12], [13], and big data analytics [14] that have been shown

to greatly beneﬁt from accelerated automata processing.

Researchers are increasingly exploiting hardware accelera-

tors to meet demanding real-time requirements as performance

growth in conventional processors is slowing. In particular,

several FPGA-based regex implementations for single-stride

[15], [16], [17], [18], [19] and multi-stride [20], [21], [22],

[23] automata processing have been proposed to improve the

performance of regex matching. These solutions provide a

reconﬁgurable substrate to lay out the rules in hardware by

placing-and-routing automata states and connections onto a

pool of hardware units in logic- or memory-based fabrics. This

allows a large number of automata to be executed in parallel,

up to the hardware capacity, in contrast to von Neumann

architectures such as CPUs that must handle one rule at a time

in each core. Most of the current FPGA solutions are inspired

by network applications such as Network Intrusion Detection

Systems (NIDS). However, patterns in other applications can

have different structure and behavior, e.g., higher fan-outs, and

this makes it difﬁcult for NIDS-based FPGA solutions to map

other automata to FPGA resources efﬁciently [18], [24], [25].

To enable architectural research, trade-off analysis, and

performance comparison with other architectures on the grow-

ing range of applications, an open-source, full-stack, param-

eterized, optimized, scalable, easy-to-use, and easy-to-verify

framework for automata processing is required. REAPR [15] is

a reconﬁgurable engine for automata processing, and generates

FPGA conﬁgurations that operate very similarly to the Micron

Automata Processor (AP) style [26] processing model. The

RTL generated from the automata graph is a ﬂat design, which

causes a very long compilation time. Due to this ﬂat-design

approach, this solution is not scalable and the synthesizer fails

to generate RTL for larger designs. Moreover, REAPR only

generates the matching kernel and does not provide a full-stack

solution or even the automata reporting architecture.

Bo et al. [27] extend REAPR and provide an end-to-end

solution on FPGAs using SDAccel for the I/O. However,

their I/O design has two issues. First, the input stream should

be segmented into limited-size chunks. Second, the reporting

structure is very simple; whenever a state generates a report,

a long vector (the size of the vector is equal to the number of

total reporting states), mostly ﬁlled with zeroes, is read and

sent to the host. This reporting architecture may become a

bottleneck for applications with frequent but sparse reporting,

which is a common reporting behavior [28]. Casias et al. [29]

also extended REAPR and proposed a tree-shaped hierarchical

pipeline architecture. However, their solution generates the

HDL code for only the kernel and does not provide a full-

stack solution (i.e., broadcasting input symbols to the logic

elements and getting the reporting data out the FPGA chip).

Furthermore, their source code is not publicly available.

Researchers are interested in using a tool that gives them

the ﬂexibility to explore design space parameters compre-

hensively. For example, in automata processing, symbol size

impacts the throughput and hardware cost [30], and none of

the prior tools provide support for that. Similarly, reporting

architecture can be a performance bottleneck that can reduce

the throughput signiﬁcantly [28] (up to 46X stall overhead in

the Micron AP). To improve the performance, Liu et el. [31]

138

2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)

DOI 10.1109/FCCM48280.2020.00027

Authorized licensed use limited to: Univ of Calif Riverside. Downloaded on December 16,2020 at 06:39:35 UTC from IEEE Xplore. Restrictions apply.

下载后可阅读完整内容，剩余9页未读，立即下载

wudinin

粉丝: 11
资源: 9

FPGA开源框架Grapefruit：加速正则表达式设计与探索

FPGA加速正则表达式匹配：一种高效算法

使用Haskell实现FPGA正则表达式编译：案例研究

两级存储优化正则表达式匹配：50倍性能提升与33Gbps吞吐量

【跨平台GBFF文件解析】：兼容性问题的终极解决方案

深度包检测中的正则表达式匹配：应用、算法与硬件平台综述

Spring MVC架构详解与配置指南：实现Web应用的高效开发

基于golang的渗透测试武器，将web打点部分与常规的漏扫部分进行整合与改进.zip

渗透测试与搭建.zip

【java毕业设计】野生动物公益保护系统源码（ssm+mysql+说明文档+LW）.zip

【java毕业设计】易商B2C网上交易系统ssh+mysql源码（完整前后端+说明文档+LW）.zip

最新资源