一种新型动态可重构的正则表达式匹配引擎设计

高阳阳，徐烈伟，俞 剑，许 薇

(1.复旦大学 专用集成电路与系统国家重点实验室，上海 201203； 2.上海复旦微电子集团股份有限公司，上海 200433)

正则表达式匹配是根据预定义的特定字符及其组合所构成的正则表达式对文本字符串进行逻辑过滤的一种逻辑操作，在网络安全、文本处理、信息检索以及医学等领域都有着广泛的应用[1].正则表达式匹配技术在早期的计算机和信息技术出现时就已经产生[2]，但随着近年来大数据、云计算以及互联网技术和应用的快速发展，海量的数据处理对文本检测和匹配的要求急剧提高，对正则表达式匹配的匹配特性、匹配速度以及匹配规则的动态更新能力等各个方面都提出了更高的要求和挑战.

正则表达式匹配算法通常采用有限自动机(Finite Automata machine, FA)来实现[3]，分为确定性有限自动机(Deterministic Finite Automation, DFA)和非确定性有限自动机(Non-deterministic Finite Automation, NFA).在DFA中[4]，自动机的状态跳转是唯一确定的，因此只需要对字符串进行1次遍历，匹配速度快，但带来的问题是无法匹配具有回溯特征的正则表达式，导致其匹配特性较少.同时，基于DFA的匹配算法在每个状态跳转时消耗1个待匹配的输入字符，其计算处理的空间复杂度随着输入字符的个数呈指数级增长，因此基于DFA的匹配算法普遍存在预处理时间过长的问题，无法满足大规模数据处理和需要动态更新匹配规则的计算场景和计算需求.

基于NFA的匹配算法中，每输入1个字符会同时产生多个后继状态，允许对正则表达式进行回溯操作，具有更为丰富的匹配特性.并且，NFA的空间复杂度随输入字符的个数呈线性增长，可以有效解决基于DFA的匹配算法所存在的预处理时间过长的问题，因此目前主流的正则表达式匹配引擎(如Perl、Python的re模块以及Java的regex库等)均基于NFA进行设计.然而，NFA状态跳转的不确定性也使得计算的时间复杂度较高，导致其匹配速度较慢[5-6].因此，更多围绕NFA的最新研究都着眼于利用硬件的并行化工作特点来提高正则表达式的匹配速度，主要有ASIC和FPGA 2种实现方式.ASIC[7-8]实现方式的计算速度高但灵活性差，其匹配规则无法自动更新，同时，多种不同类型的复杂的正则表达式也无法通过预设计电路的方式来实现快速匹配，导致有限的硬件资源无法覆盖更多的匹配特性和提供更高的匹配能力.相比于ASIC实现方式，FPGA实现方式具有电路可编程的特性，其硬件电路的计算功能可以像软件一样通过编程来修改，可以灵活地分配硬件资源，增大匹配特性，同时可以减少更新匹配规则时的重配置时间，使得基于FPGA实现的正则表达式快速匹配成为目前主流的技术解决方案.

围绕基于FPGA的正则表达式快速匹配和计算加速，贺伟[9]提出了一种基于FPGA的动态元件级可重构的正则表达式匹配算法，通过对FPGA中可编程SRAM的配置来实现匹配电路的动态更新，提高正则表达式匹配的预处理速度.算法将不同元字符所对应的NFA映射成硬件电路，采用多路选择器将这些电路组合成正则表达式匹配中的单元电路，如图1所示.

图1 正则表达式匹配的单元电路Fig.1 Unit circuit of regular expression matching

图1中，虚线框内是单字符匹配的基本电路，通过对多路选择器的选择信号进行配置，可以实现正则表达式中的几类基本元字符(“*”、“+”、“?”、“{}”和“|”)对单字符子表达式的匹配功能.例如，当选择信号1和2均置为“01”时，电路实现的功能为“r*”；当选择信号1和2分别置为“01”和“10”时，电路实现的功能为“r{n}”，其中，r是字符比较器中预存的字符，n是计数器中预存的数值.算法将这种可重构的单元电路级联起来，通过改变配置信息，可以实现多种形式的正则表达式匹配.但在实际工作场景中，正则表达式所包含的元字符种类及组合方式非常多，无法一一枚举，因此这种可重构设计所能覆盖的匹配特性较少，具有很大的局限性.

为此，Zsolt等[10]提出了基于CPU-FPGA架构的正则表达式匹配算法，首先将连续的普通字符以及范围匹配(例如“[a—z]”)的表达式视作1个字符串，采用单个标记(token)来表征字符串(例如，将正则表达式“(abc)|(def)”表征成“x|y”)的方法将正则表达式化简并分割成若干个较短的单个标记，再将化简后的正则表达式构造成NFA，利用FPGA硬件电路对这些单个标记所代表的子表达式进行快速的并行匹配.采用这种方式，可以在扩展匹配特性的同时提高匹配速度.Vaibhav[11]则提出了另一种软硬件协同计算的硬件加速算法，以元字符(例如“*”、“+”、“?”、“{}”、“|”等)为标记将正则表达式分割成多个匹配组件(component)，并用“前导信号(precedence vector，指激活当前状态的状态信号)”和“重复量词(repetition bound，指组件重复的次数)”2个参数表征每个匹配组件.以正则表达式“ab{2,4}c”为例，“a”、“b{2,4}”、“c”为分割得到的匹配组件，匹配组件“b{2,4}”的前导信号为“a”，重复量词为[2,4]；匹配组件“c”的前导信号为“b”，重复量词为[1,1]).算法继而对匹配组件进行参数提取，通过改变这些参数，实现对不同形式正则表达式的匹配.采用这种元字符分割、参数提取以及动态重构匹配规则的方法，可以进一步扩展匹配特性，但仍然无法匹配对多字符子表达式进行“*”、“+”操作的正则表达式，也无法匹配出现无界重复量词(如{n,})的正则表达式.

上述采用FPGA来实现的正则表达式匹配算法[9-11]，通过对FPGA的动态可重构特性的有效利用，提高了正则表达式的匹配特性和匹配速度，同时缩短了构造正则表达式匹配规则的预处理时间，但是其匹配速度受限于FPGA的最高工作频率，仍然无法更好地满足大规模数据处理的加速计算要求.为了进一步提高匹配速度，同时进一步增加可覆盖到的匹配特性，本文提出了一种动态可重构的正则表达式匹配算法，采用参数化一致性表达方法来以丰富算法的匹配特性和提高正则表达式的动态匹配能力.同时，采用专用并行计算电路与FPGA电路的混合计算框架和软硬件协同的工作模式，提出和设计了一种新型动态可重构计算硬件，不仅可以最大化地利用FPGA电路的可重构特性完成正则表达式的动态更新来提高正则表达式匹配的预处理速度，专用并行计算电路的使用更大大提高了并行匹配计算的匹配速度.

1 参数化一致性表达的匹配算法

1.1 正则表达式的NFA构造和一致性表达

基于NFA的正则表达式匹配，首先需要完成的是NFA的构造.经典的NFA构造算法[12]，以递归方式将正则表达式划分为若干子表达式，得到每个子表达式所对应的子NFA，再根据子表达式之间的运算关系构造完整的NFA.图2为4种基本子表达式的NFA构造示例，其中： m1和m2分别表示2个状态机;ε表示空串匹配;s为初始状态;f为接受状态.

图2 正则表达式的NFA构造示例Fig.2 NFA construction example of regular expression

对于长度为n的正则表达式，NFA的空间复杂度为O(n)，正则表达式可以较为快速地转化为NFA，其预处理时间较短.但另一方面，NFA中可能同时存在多个激活状态(例如，图2(c)中，NFA处于初始状态时，状态s1和状态s2均处于激活状态)，每输入1个字符会产生多个可能的后继状态.当NFA中所有状态均处于激活状态时，任意一个状态都有跳转到其他所有状态的可能，在这种最坏情况下，串行匹配的时间复杂度为O(n2)，匹配速度较慢.

有鉴于此，最新研究均采用硬件来并行地加速处理NFA中的多个激活状态，提高正则表达式的匹配速度.图3所示为对应上述4种基本子表达式的逻辑电路[13]，其中： N1和N2分别表示2个单字符匹配模块；i表示模块输入(该模块处于激活状态时，输入高电平)；o表示匹配结果.

图3 4种正则表达式匹配的硬件实现Fig.3 Four types of hardware implementation for regular expression matching

在图3(a)中，当输入字符和预先存储在比较器中的单字符子表达式相同时，比较结果为1，表示匹配成功.对比图2(c)和图3(c)可以看到，当同时存在多个激活状态时，可以通过将单字符匹配电路并联的方式，并行处理正则表达式中的所有激活状态，提高匹配速度.但是不同类型的元字符及其组合所构成的正则表达式对应的是不同的匹配计算模型，受到硬件计算资源的限制，无法将各种类型的匹配计算模型都一一映射成硬件电路，从而限制了算法所能覆盖到的匹配特性.对此，本文提出一种参数化一致性表达方法，通过将各种类型的正则表达式统一成包含有限匹配类型的同一种匹配规则，通过固化匹配计算的架构及可并行化的底层计算模型，来实现对各种不同类型正则表达式的通用的匹配计算.

首先，是将正则表达式的匹配类型合并成尽可能少的种类，并对其实现一致性的表达，以便算法后续工作可以从中提取出能有效表征所有匹配计算类型的表达式参数.在进行匹配计算时，可以将一些较为复杂的元字符，展开成最基本的元字符(例如“*”、“+”、“?”、“|”)，以减少元字符的种类(例如①和②).此外，对于不会对匹配计算结果产生影响的元字符，则进行合并(例如③和④).

① 范围匹配

范围匹配是指对指定范围内的任意字符进行匹配，例如“[a—z]”表示匹配“a”到“z”范围内的任意字符.由于正则表达式中对范围的匹配种类繁多，且对应不同的计算方法，为了使各种类型的范围匹配都可以用统一的计算模型加以实现，本文在算法设计中引入了1种新的元字符“&”和4种比较符号“=”、“≥”、“≤”、“≠”，以使类似于“[a—z]”这样的范围匹配表达式可以被展开成“(≥a)&(≤z)”的形式(其中“&”表示“同时满足左右两边的条件”)，由此将范围匹配转化成由“&”、“|”、比较符号以及普通字符所构成的最小化的正则表达式，在等价的前提下简化了范围匹配中可能存在的元字符种类.表1所示为3种典型的范围匹配的转换方式，其中对于“W”，其转换后的表达式中还存在比较符号“>”和“<”，为了减少比较符号的种类，可以进一步结合被其比较的普通字符，将“>”和“<”分别转换为“≥”和“≤”，例如“>z”可以转换为“≥{”(在ASCII码表中，字符“{”在字符“z”的后1位).

② 重复匹配

重复匹配是指对某个普通字符或子表达式进行多次连续的匹配，例如，表达式“a{3,5}”表示连续匹配“a”3次、4次或者5次，因为元字符“?”表示匹配字符0次或1次，因此可以将上述表达式展开成“aaaa?a?”，这样正则表达式中的每一个普通字符对应1次匹配操作，仅用基本元字符“?”、“+”就可以完全表征任意形式的重复匹配.表2所示为3种典型的重复匹配的转换方式.

表1 范围匹配的转换方式

表2 重复匹配的转换方式

③ 非贪婪匹配

非贪婪匹配(例如“*?”、“+?”、“??”等)指匹配尽可能少的字符，与之相对应的是贪婪匹配(“*”、“+”、“?”等)，指匹配尽可能多的字符.例如分别用表达式“ab+?”和“ab+”匹配字符串“abbb”，均会匹配成功，但“ab+?”匹配到的字符串是“ab”，而“ab+”匹配到的字符串是“abbb”.在并行匹配时，当“a”匹配成功后，每匹配上1个“b”，都会显示匹配成功，即无论使用哪种表达式对该字符串进行匹配，均会连续显示3次匹配成功.因此非贪婪匹配和贪婪匹配在匹配的过程和结果上都是等价的，而贪婪匹配中的元字符是最原始也是最基本的元字符，因此，在不影响匹配结果的前提下，本文在匹配规则中将非贪婪匹配均转化成贪婪匹配，表3(见第710页)所示为2种典型的非贪婪匹配的转换方式.

④ 零宽断言

零宽断言用于匹配在这个位置之前或之后的字符表达式.例如正则表达式“a(?=b)”匹配在字符“b”这个位置之前的字符“a”，用该表达式匹配字符串“abac”时，只有当“a”字符后紧接着“b”字符，才表示匹配成功，即该表达式仅可以匹配成功1次(字符串中的第1个“a”).因此，正则表达式“a(?=b)”和“ab”在匹配的过程和结果上都是等价的，可以将位置匹配简化成普通的字符匹配.表4(见第710页)所示为2种典型的零宽断言的转换方式.

通过上述的范围匹配、重复匹配、非贪婪匹配以及零宽断言4种方式的转换，本文将众多类型的正则表达式元字符最终合并成5类：“*”、“+”、“?”、“|”和“&”.由此，转换后的正则表达式可以表征成由普通字符(用ASCII码表示的字符)、元字符(“*”、“+”、“?”、“|”和“&”)以及比较符号(“=”、“≥”、“≤”、“≠”)所构成的更为统一且简单的表达形式，减少了正则表达式的匹配类型，同时可以方便地采用尽可能少的参数来进一步加以抽象表征.

表3 非贪婪匹配的转换方式

表4 零宽断言的转换方式

1.2 参数的提取和转换

完成了一致性表达之后，需要进一步提取出可以完全表征各类正则表达式的参数，并将其转换成匹配计算时可以识别及更改的配置信息.其中，最主要的工作是构造正则表达式所对应的NFA，并确定NFA中每个状态所对应的转移函数.由图2可知，转移函数分为字符匹配和空串匹配.字符匹配由输入字符和正则表达式中普通字符的比较结果决定，用来匹配正则表达式中的单个普通字符，在此，本文引入参数“比较信号”来表征4种情况的比较关系，分别是“=”、“≥”、“≤”、“≠”；空串匹配由正则表达式中的元字符类型决定，用来将匹配单字符子表达式的子NFA组合成完整的NFA，在此，本文引入参数“使能信号”来表征字符匹配后的状态跳转关系，正则表达式中的每个普通字符都有其对应的使能信号(包含一个或多个字符)，当NFA匹配上某字符所对应的使能信号时，状态就会发生跳转来进行该字符的匹配.例如图2(b)中，当字符“r1”匹配成功后，NFA处于f1状态，并通过空串匹配跳转到f2状态，开始对字符“r2”进行匹配，因此字符“r2”的使能信号是“r1”.

在硬件实现NFA时，由图3可知，每个单字符匹配对应一个比较器，可以将这些比较器的输入和输出根据使能信号连接起来(一个单字符匹配对应的比较器的输入是其使能信号对应的比较器的输出)，来实现完整的正则表达式匹配.同时，针对本文提出的元字符“&”，则通过参数“级联信号”的引入来表征用“&”连接字符时的字符间转移函数.例如正则表达式“(≥x)&(≤z)”(原表达式为“[x—z]”)包含2个普通字符“x”、“z”，作为一个整体，需要将“≥x”的子表达式NFA的匹配结果级联到“≤z”的子表达式NFA，只有待匹配的字符同时匹配上“≥x”和“≤z”时，匹配才被认为是成功的.其中，正则表达式的匹配结果并不是硬件实现时最后一个字符所对应的比较器输出结果，而是NFA中结束状态所对应的使能信号的匹配结果，例如正则表达式“a(b|c)”，只要“b”或者“c”中任意一个字符匹配上，即表示该正则表达式匹配成功(“b”和“c”所对应的NFA状态均可以通过空串匹配跳转到结束状态，即结束状态的使能信号为“b”和“c”).因此，正则表达式可以由： ① 表达式中的普通字符和每个普通字符对应的特性参数(比较信号、使能信号和级联信号)；② 最终状态所对应的使能信号所表征，匹配结果为最终状态对应的使能信号的匹配输出结果.

由于提取特性参数的目的是将正则表达式的特性参数映射成可实现的硬件电路中的配置信息，因此需要结合硬件电路的可实现性来进一步处理这些特性参数.本文提出2个定义，定义①： 对于预处理后的正则表达式，按从左到右的顺序对正则表达式中的普通字符进行排序，称在某字符左边的字符，是该字符的前序字符；定义②： 将来自前序字符的使能信号称为前驱使能信号，来自本身及后序字符的使能信

表5 “a(bc)*[x—z]”中的特性参数

号称为后驱使能信号.由于算法在配置计算电路时，会按照普通字符的前后顺序依次分配单字符匹配电路，前驱使能和后驱使能所分别对应的硬件结构是不同的，因此，本文在算法设计中将字符的匹配使能特性再细分为3类，分别是前驱使能特性、后驱使能特性、使能选择信号，分别进行参数提取.

以正则表达式“a(bc)*[x—z]”为例，表5为从该正则表达式中提取出的特性参数.

表6 前驱使能信号对应的配置信息

表7 “a(bc)*[x—z]”对应的配置信息

提取出这些特性参数后，还需要将其转化为匹配计算时可以识别及更改的配置信息.本文采用二进制的方法来表征这些特性参数，例如用二进制数“00”来表征比较信号中的“=”、“01”表征“≥”、“10”表征“≤”、“11”表征“≠”.由于前驱和后驱使能信号需要在多个单字符匹配模块间通过传递信号来实现，因此提出一种表6所示的参数转换方式.

使能信号可能出现多级传递的情况(例如正则表达式“a(bc)*[x—z]”中的“a”需要通过“b”和“c”传递给“x”)，在传递时配置信息会发生冲突，此时需要配置多条传递线来保证信号的正常传递.以正则表达式“a(bc)*[x—z]”为例，表7给出了表5中的参数对应的配置信息.其中，“c”的前驱使能是“b”，需要将“b”的前驱使能传递线配置成“10”；“x”的前驱使能是“a|c”，需要将“a”的传递线配置成“10”、“b”的传递线配置成“01”、“c”的传递线配置成“11”才能完成信号传递.此时，“b”的传递线配置发生了冲突，需要用2条传递线分别传递“c”和“x”使能信息(对应于表7中的“线1”和“线2”选项)，并判断“c”和“x”的使能信号所分别对应的传递线(对应于表7中的“选择”选项)，由此实现对使能传递线的配置.

由表7的配置信息可以看到，字符“b”的前驱使能在“a”中进行的配置(“a”的前驱使能传递线1被配置成“10”，表示将本级的匹配信号“a”传递给下一级“b”)，即当前字符的前驱使能在上一个字符中完成配置.由于正则表达式的最终匹配结果是最终状态所对应的使能信号的输出值，因此，将最后一个字符“z”的前驱使能传递线配置为“10”，“z”中前驱使能信号的输出值即代表最终的匹配结果.上述配置方法，通过若干条使能传递线将单字符匹配模块级联起来，实现了对完整正则表达式的匹配.

由此，通过这种参数化的提取和转换，任意经过一致性表达处理后的正则表达式，均可以用以上二进制信息完全表征，在进行匹配计算时，可以由若干相同结构的单字符匹配模块级联而成.并且，通过将这些完全表征正则表达式的参数集合转化为可以进行动态重构的配置信息，只需要改变这些配置信息，无需修改硬件电路结构，即可实现不同正则表达式的匹配.上述本文所设计和实现的这种参数化一致性的表达算法，在扩展了匹配特性的同时降低了硬件电路的复杂度，提高了电路的工作效率.表8为文献[9]和[11]中正则表达式匹配特性和本文的比较，可以看到，本文这种参数化一致性表达算法相比文献[9]和[11]具有更宽泛的匹配特性.

表8 正则表达式匹配算法的匹配特性比较

1.3 电路映射

由1.2节可知，任意单字符子表达式的匹配功能均可由比较信号、使能信号和级联信号这3种参数完全表征，其匹配计算模型由相对应的3个部分构成： ① 输入待匹配的字符和表征普通字符的ASCII码，根据比较信号，输出比较结果；② 根据使能信号，输入来自其他单字符子表达式的匹配结果，输出使能结果；③ 输入比较结果和使能结果，根据级联信号，确定本级单字符子表达式的最终匹配结果.通过前驱和后驱使能传递线将单字符子表达式级联起来，在进行正则表达式匹配时，待匹配的输入字符并行地进行上述单字符匹配的计算，最终的匹配结果是最后一级单字符匹配模块的前驱使能传递线的输出结果.以正则表达式“a(bc)*[x—z]”为例，若将NFA直接映射成硬件电路，每一个单字符子表达式对应的电路都是不同的，而通过1.1节和1.2节中对正则表达式的参数化一致性表达，固化了匹配计算的架构及单字符匹配的底层计算模型，并且正则表达式可以由计算模型中的“表征普通字符的ASCII码”、“比较信号”、“使能信号”、“级联信号”等参数完全表征，将这些参数集合转换为配置信息，只需要更改上述配置，即可实现各类正则表达式的匹配.

由此，本文所提出的参数化一致性表达的正则表达式匹配算法的设计框架如图4所示.

图4 正则表达式匹配算法的框架示意图Fig.4 Schematic diagram of the regular expression matching algorithm

图4中，算法通过对正则表达式的一致性表达，把各种类型的正则表达式转换成由普通字符和特定元字符(“*”、“+”、“?”、“|”和“&”)等构成的统一形式的正则表达式，再从这种一致性表达的正则表达式规则中抽象和提取出可以完全表征各类正则表达式的参数集合，并转化为配置信息，然后将这种可以用参数完全表征的正则表达式匹配规则映射成固定计算模型的硬件电路，并行地进行正则表达式匹配.对于不同类型的正则表达式，可以通过改变硬件电路的配置信息来实现正则表达式的快速匹配.

2 动态可重构匹配加速引擎的实现

2.1 软硬件协同工作架构

根据1.3节叙述，本文将正则表达式的匹配任务划分成如下2个部分： ① 软件实现的编译模块；② 硬件实现的配置和计算模块.图5所示为实现该正则表达式匹配算法的架构.

图5 算法实现的架构Fig.5 Algorithm implementation architecture

首先，软件编译模块利用软件灵活易修改的特点来实现对正则表达式的参数化一致性表达，通过软件实现的预处理模块对各种类型的正则表达式进行一致性表达处理，将其转化为统一的形式，再从中提取出可以完全表征这类正则表达式的参数集合，将统一形式的正则表达式匹配规则映射成可并行执行匹配任务的子表达式，并将参数集合转化为配置信息.随后，硬件加速模块完成对正则表达式匹配的快速更新和并行计算.

为进一步达到硬件计算加速的效果，本文提出了一种在FPGA中内嵌ASIC电路的混合计算框架，分别实现匹配规则的可重构配置和匹配计算的并行计算加速.其中： FPGA电路根据软件编译获得的配置信息，负责完成对正则表达式匹配计算模型的动态更新；ASIC电路是以单字符匹配(core)电路为基本单元构成的并行计算阵列，通过配置信息将若干个core电路级联起来构成完整的正则表达式匹配电路，完成正则表达式的高速并行匹配计算.这种硬件架构在最大化利用FPGA电路的可重构特性进行正则表达式更新的同时，采用专用ASIC电路实现的并行匹配计算可以极大地提高匹配计算的速度.

2.2 动态可重构配置电路

图6 动态重配置模块的电路结构Fig.6 Dynamic reconfiguration module circuit

本文采用基于FPGA设计的动态可重构(dynamical reconfigurable programming, drp)电路对正则表达式匹配电路进行配置，这种动态可重构配置电路在更新匹配规则的同时仍然能保证电路的动态接续，当完成重配置操作后即可立刻进行新的匹配计算，可以最大程度地减少更新匹配规则时所需要的重配置时间.drp电路由控制模块和SRAM阵列组成，通过读写端口对SRAM阵列进行配置，如图6所示，读写端口的位宽均为16，可以同时对16个SRAM进行并行配置.

drp电路的设计需要确定其所配置的SRAM数量.首先，需要确定1个单字符匹配(core)电路所需要的SRAM数量.由1.2节可知，正则表达式可能需要多条传递线来进行使能信号的传递，不同的正则表达式所需要的SRAM数量是不同的.本文分别从regexlib库(http：∥regexlib.com/)和snort规则集(http：∥ snort.org/)中，根据正则表达式的几类常用场景(字符串匹配、邮箱/日期/时间等合法性检查、网络入侵检测等)，随机选取了100条正则表达式来完成对drp电路和并行计算电路的设计参数的选择，选取的目标是使其能够尽量覆盖所有类型的元字符种类.根据1.2节中所述的配置方法，分别提取正则表达式中每个普通字符对应的使能信号，并将其转化为二进制的配置信息，选取的实验结果表明： 这100条正则表达式均可以通过最多4条前驱使能传递线和3条后驱使能传递线来完成匹配计算.因此，权衡硬件的资源消耗和表达式的常用匹配场景，本文采用了4条前驱使能传递线和4条后驱使能传递线来进行core电路间的使能信号传递(即本文无法匹配需要超过4条前驱或者后驱使能传递线的正则表达式).综上，1个core电路需要33个SRAM进行配置(包括8位ASCII码、10位前驱使能信号、10位后驱使能信号、2位使能选择信号、2位比较信号和1位级联信号).由此，对于1个长度为n的正则表达式(n为所包含的普通字符的个数)，共需要33×n位二进制数来对其进行完全的表征.

其次，还需要确定1个drp电路对多少个core电路进行配置.统计计算上述随机选取的正则表达式匹配所需要的core电路的个数，统计结果显示，87%的表达式所需个数低于64.因此，综合考虑匹配速度(硬件中包含越多的core电路，匹配速度越快)、预处理速度(每个drp电路控制越少的core电路，预处理速度越快)以及版图的面积限制，本文采用了1个drp电路对64个core电路进行参数配置的设计.根据这种设计，当正则表达式长度小于(或等于)64时，只需要1个drp电路工作即可完成配置更新；当正则表达式长度大于64时，需要将更多的core电路级联，并通过多个drp电路进行配置以实现匹配计算.

综上所述，对于64位长度的正则表达式，需要64×33=2112个SRAM对其进行动态可重构配置，考虑到drp的端口位宽和SRAM阵列在FPGA中的布局布线，最终所设计的drp电路中共包含64×40=2560个SRAM.采用这种设计，在端口位宽为16、且若干个drp电路可以并行工作的情况下，任意长度的正则表达式的配置均可以在2560/16=160个时钟周期内完成，平均每个core电路可以在160/64=2.5个时钟周期内完成计算.

2.3 并行计算电路

相比ASIC电路，FPGA的LUT电路结构在实现相同的正则表达式匹配电路时，会需要消耗更多的逻辑电路资源以及更多的布线资源，时钟频率也会严重受限于其本身的最高工作频率.因此，对于正则表达式的并行匹配计算，本文采用了专用ASIC电路来加以实现.根据1.3节中的计算模型，首先搭建单字符匹配电路，如图7所示.

图7 单字符匹配模块的结构框图Fig.7 Block diagram of the single character matching module

core电路主要由4个部分构成：

1) 比较模块.比较器的2个输入分别是待匹配的字符和表征普通字符的ASCII码，根据比较信号选择需要的比较结果；

2) 使能模块.该模块的功能是根据使能选择信号决定该电路所需的信号类型(前驱使能信号或后驱使能信号)，模块还包含2个子模块： 前驱使能模块和后驱使能模块，分别进行其所对应的前驱和后驱使能信号的传递；

3) 级联模块.该模块的功能是根据级联信号决定当前电路的匹配结果是否和前一级电路的匹配结果有关，当前电路最终的匹配结果由该模块输出；

4) 时序模块.通过D触发器进行电路流水线的设计，每个时钟周期完成对1个输入字符的处理.

针对使能模块中的前驱和后驱使能信号的传递，本文提出和设计了一种由多路选择器(MUX)和或门构成的菊花链(daisy-chaining)结构，采用这种设计，前驱和后驱信号可以在任意数量的core电路之间进行传递.其中，前驱使能菊花链将core电路从前向后进行级联，后驱使能菊花链将core电路从后向前进行级联.以前驱使能菊花链为例，2条菊花链的电路结构如图8所示.

图8 前驱使能菊花链结构图Fig.8 Structure diagram of precursor enable daisy-chaining

图8中，菊花链的输入是级联模块的输出信号(match_next)和使能模块的输入信号(pre)，MUX的选择端由对应的配置位流决定，输出信号(pre_next)同时也是下一级core电路中使能模块的输入信号(pre).其中，最后一级core电路中“pre_next”的信号值是整个正则表达式的匹配结果.通过这样的菊花链设计，计算电路可以分割为若干相同的匹配单字符子表达式的core电路，core电路可以级联以匹配任意长度的正则表达式，也可以独立并行地匹配不同的正则表达式.相比文献[10]和文献[11]中需要若干不同功能的底层模块(两者均需要分别对分割产生的字符串和化简后的正则表达式进行匹配计算)，本文设计的并行计算电路仅通过单一的基本单元即可实现正则表达式匹配功能，降低了硬件复杂度.

图9 正则表达式匹配的硬件加速引擎的设计示意图Fig.9 Schematic diagram of hardware acceleration engine for regular expression matching

由2.2节可知，1个drp电路可以完成对64个core电路的SRAM配置，图9为由64个core电路级联而成的正则表达式匹配加速引擎的设计示意图.其中，每个方框代表1个core电路，core电路间的箭头方向是前驱使能级联线的方向，后驱使能级联线的方向与此相反.这种core电路的布局方式，缩短了版图实现时的布线长度，可以进一步提高匹配速度.

对图9所示的匹配引擎进行仿真验证，采用TSMC 28nm CMOS工艺进行专用ASIC电路设计，当其工作频率在1GHz时，可以在1ns 内完成对单个字符子表达式的匹配.同样的匹配计算模块设计，当其实现在Kintex-7 FPGA上时，实验得到的一个单字符子表达式匹配完成的时间为5ns.因此，采用ASIC设计实现的并行计算模块，可以为单字符子表达式的匹配提供5倍以上的计算加速.

3 测试结果

3.1 正则表达式匹配引擎的物理设计

图10 reb电路的物理版图Fig.10 Physical layout of the reb circuit

本文设计和实现的动态可重构硬件电路采用TSMC 28nm CMOS工艺进行流片，完整的动态可重构的正则表达式匹配引擎(Dynamic Reconfigurable Regular expression matching engine, DRR-engine)电路由70个的图10所示的正则表达式匹配单元(regex expression matching block, reb)电路构成，每个reb电路包含1个基于FPGA实现的drp电路和4个采用ASIC方式设计实现的并行匹配计算(regex)电路，其中，每个regex电路包含16个core电路.reb电路的物理版图的面积是0.07mm×0.25mm=0.0175mm2(regex和drp电路的面积相等).DRR-engine中所有的core电路(共计64×70=4480个)均通过菊花链级联，单独的core电路可以根据SRAM配置级联起来以匹配较长的正则表达式，也可以独立工作.综上，本文设计实现的DRR-engine中包含70个drp模块和280个regex模块，最多可以同时进行280个正则表达式(假设每个表达式所需要的core电路数量≤16个)的并行匹配.

3.2 实验条件和硬件测试

本文所设计实现的DRR-engine模块是整个AI-FPGA芯片的一个组成部分，图11(见第716页)是DRR-engine模块在AI-FPGA芯片中所在的物理位置示意，测试用到的3个模块分别是： 数据传输(PCIE)模块、数据存储(BRAM)模块、DRR-engine模块.测试平台以及测试流程如图12(见第716页)所示，软件编译模块接收和处理正则表达式，生成对应的硬件配置信息，通过PCIE模块(图11中黑色框②所示)将配置信息传递给DRR-engine模块(图11中红色框①所示)中的配置模块进行动态可重构配置；BRAM模块(图11中黄色框③所示)中存储待匹配的字符串，DRR-engine模块从BRAM模块接收字符串数据，完成正则表达式的并行匹配计算，输出匹配结果.

本文实验所采用的regexlib库是互联网中第一个正则表达式库，包含各种类型的正则表达式，也是最为常用的正则表达式库.本文基于regexlib库完成正则表达式匹配的测试和验证.

3.2.1 匹配特性

从regexlib库中随机选取1000个正则表达式进行匹配计算.匹配实验的测试结果显示，本文算法可以很好地支持包括贪婪匹配、零宽断言、范围匹配、重复匹配以及由元字符“*”、“+”、“?”、“|”和普通字符组成的各种类型的正则表达式的匹配，覆盖87%的匹配类型.未覆盖到的正则表达式类型主要是反向引用和一部分转义字符等.

图11 AI-FPGA芯片的物理版图Fig.11 Physical layout of the AI-FPGA chip

图12 测试平台及测试流程Fig.12 Test platform and test process

3.2.2 预处理速度

从regexlib库中随机选取300个算法可实现匹配的正则表达式，对drp模块的重构时间进行测试，drp模块的最高工作频率设置为500MHz.测试结果显示： 通过并行地对SRAM进行配置，可以在0.32μs内完成对所有正则表达式匹配电路的配置，平均每个正则表达式的配置时间为32ns.

3.2.3 匹配计算速度

从regexlib库中随机选取300个包含所有硬件可实现的元字符种类的正则表达式，分别对一段50MB 的文本进行匹配.测试结果显示，当执行快速匹配任务的regex并行计算电路的工作主频设置为1GHz 时，在对单个正则表达式进行匹配的情况下，每一个正则表达式均可以在20ms内完成对全部文本的匹配，吞吐率为1Gb/s；在对多个正则表达式进行匹配的情况下，280个regex电路可以相互独立地同时工作，可以支持最多280个正则表达式的并行匹配，此时，吞吐率达到280Gb/s.

3.3 实验结果分析

表9给出了本文算法与其他同类算法的比较.文献[9-11]均采用基于FPGA的正则表达式匹配算法，其中文献[11]同时完成了基于FPGA和基于ASIC的匹配电路设计.从表9的实验结果可见，对比文献[11]基于ASIC实现的快速匹配电路，本文所设计实现的动态可重构的正则表达式匹配引擎在吞吐率上大致相当，但具有更为丰富的匹配特性和动态可重构的匹配能力.

对比文献[9-11]基于FPGA实现的可重构加速匹配算法，本文算法通过对正则表达式进行参数化一致性表达、并将参数信息映射到硬件电路上的方法，无须更改并行计算的单元匹配硬件电路即可实现匹配特性的动态更新，具有更完备的动态可重构的匹配能力.在匹配特性上，本文算法相较于文献[9]和文献[11]具有更丰富的匹配特性，与文献[10]大致相当.而在匹配速度上，依据本文算法所实现的加速匹配引擎(DRR-engine)，相较于其他同类型的匹配引擎均具有超过5倍以上的提升.

表9 正则表达式匹配引擎算法比较

4 结 论

本文提出了一种更为宽泛和一致性的参数化设计，通过对正则表达式的一致性表达，简化了表达式匹配的计算复杂度，并进一步抽象和提取出可以完全表征各类正则表达式的参数集合，将其转化为可重构计算硬件的配置信息，在扩展了正则表达式匹配特性的同时降低了配置复杂度，减少了预处理时间.在此基础上，本文采用FPGA+ASIC的混合计算框架，设计了基于FPGA的动态可重构配置(drp)电路，和以单字符匹配(core)电路为基本单元的可扩展的regex并行计算阵列，完成了动态可重构的正则表达式匹配计算加速引擎的设计和实现，并在TSMC 28nm CMOS工艺下完成了芯片的流片.实验结果表明，本文提出的动态可重构的正则表达式匹配算法和基于FPGA+ASIC混合计算框架所实现的并行化计算加速引擎，与目前同类型的正则表达式计算引擎相比，不仅在正则表达式的匹配特性上提供了更为完整的覆盖能力，具有更快速的动态可配置能力，同时在匹配速度上获得了超过5倍以上的提升，最大吞吐率达到280Gb/s.