论文摘要
随着网络与信息技术的高速发展,网络检索、路由查找、信息安全等许多应用领域对字符串模式匹配有着越来越高的速度需求。因此,近年来,人们集中研究如何以快速、高效的方式进行字符串模式匹配。随着硬件工艺水平的提高和FPGA技术的发展,用硬件的并行结构来实现字符串模式匹配处理的研究大量涌现。当然,不同的研究和设计方案,在速度、面积、成本、灵活性等方面都有很大的差别,在实际应用中,这些方案扬长避短,在某些应用领域中能发挥关键的作用。本文提出设计专用处理器的方案,来达到字符串模式匹配加速的目的。专用处理器是一种新型的具有处理器结构和可编程能力的芯片,它为某个或某一类的应用而专门定制。通过权衡速度、面积、成本和灵活性的设计约束,专用处理器往往能够达到更好的平衡点,从而适应嵌入式系统的需要。因而专用处理器在嵌入式领域中具有良好的应用背景。专用处理器的设计需要面对具体的应用定制最优的体系结构,其设计过程往往是从局部展开,基于应用分析和需求分析,提取其中的处理规律和特点,并针对这些规律和特点展开设计。另外,专用处理器的设计要具有一定的完整性,包括配套的编译器（综合器）,便于工程师在嵌入式领域中的开发和接受。本文具体研究内容如下:1)分析正则式和巴克斯范式的语法特点。正则式和巴克斯范式都是用来描述字符串模式规则的文法。正则式是用途最广泛的一种字符串模式描述工具,语法简单高效。增强型巴克斯范式（AugmentedBackus-Naur Form,ABNF）是RFC2234里面定义的一个字符串模式匹配的文法定义,语法更丰富,擅长描述网络协议的结构和规则。本文首先分析正则式和巴克斯范式的语法特点以及它们描述网络协议结构和规则的规律,以便定义指令系统和硬件加速模块的功能。2)定义字符串模式匹配专用处理器的指令集。根据正则式和巴克斯范式的特点,定义并设计了一套指令集,包括基本指令集和专用指令集。基本指令集保证专用处理器具有基本的通用处理能力;专用指令集是针对模式规则的文法特点而设计的一套高级语言指令集,擅长描述字符串模式规则,能够更加简洁地表达模式规则的关系操作,使得字符串模式匹配算法仅需少量的代码即可描述,并且方便使用。3)研究字符串模式匹配处理器的体系结构设计和存储器管理方案。通用处理器上的字符串模式匹配代码中,比较、判断、循环和分支指令占有非常大的比重,指令相关性较强。这种算法的特点要求处理器频繁地访问不连续的存储空间,导致流水线中断、Cache命中率底下等问题,致使基于多级流水线的处理器性能难以发挥。在专用处理器的体系结构的定制上,要想取得较大的加速比,就需要针对这类问题和这些特点进行解决。为了进一步提高指令级的并行能力,面向字符串模式匹配的多核处理器的体系结构设计也是本文的研究内容。无论是单核处理器还是多核处理器,算法的特点都会导致处理器频繁访问存储器,因此,合适的存储器管理方案也是关键的研究内容之一。本文设计的单核专用处理器和双核专用处理器在FPGA上得到验证,并进行了功能测试和性能测试,测试结果表明该专用处理器在功能上满足实际应用的需要,在性能上可以有效地提高字符串模式匹配的处理速度和效率。本文的主要创新点在于:1)提出设计专用处理器的方案,通过针对模式规则的语法特点设计专用指令,得以提高字符串模式匹配的速度,同时又可以兼顾通用性和灵活性。2)通过专用处理器的设计流程,本文讲述了如何从应用需求出发,通过对功能的描述和对传统方案的分析,定制一种面向应用的专用处理器,并进一步挖掘指令级的并行能力的设计方法。3)字符串模式匹配算法加速的最大难点是克服处理器在处理数据过程中频繁访问不连续的存储空间,本文在研究专用处理器的体系结构设计过程中,设计了一些特殊的功能单元来提高处理器的访存效率,这些模块的功能和结构会为从事该领域研究工作的人员带来一定的帮助和启发。