字符串模式匹配的硬件加速研究.pdf

1、隨著網(wǎng)絡(luò)與信息技術(shù)的高速發(fā)展，網(wǎng)絡(luò)檢索、路由查找、信息安全等許多應(yīng)用領(lǐng)域?qū)ψ址Ｊ狡ヅ溆兄絹碓礁叩乃俣刃枨蟆Ｒ虼?，近年來，人們集中研究如何以快速、高效的方式進(jìn)行字符串模式匹配。隨著硬件工藝水平的提高和FPGA技術(shù)的發(fā)展，用硬件的并行結(jié)構(gòu)來實(shí)現(xiàn)字符串模式匹配處理的研究大量涌現(xiàn)。當(dāng)然，不同的研究和設(shè)計(jì)方案，在速度、面積、成本、靈活性等方面都有很大的差別，在實(shí)際應(yīng)用中，這些方案揚(yáng)長避短，在某些應(yīng)用領(lǐng)域中能發(fā)揮關(guān)鍵的作用。 本文提出

2、設(shè)計(jì)專用處理器的方案，來達(dá)到字符串模式匹配加速的目的。專用處理器是一種新型的具有處理器結(jié)構(gòu)和可編程能力的芯片，它為某個(gè)或某一類的應(yīng)用而專門定制。通過權(quán)衡速度、面積、成本和靈活性的設(shè)計(jì)約束，專用處理器往往能夠達(dá)到更好的平衡點(diǎn)，從而適應(yīng)嵌入式系統(tǒng)的需要。因而專用處理器在嵌入式領(lǐng)域中具有良好的應(yīng)用背景。 專用處理器的設(shè)計(jì)需要面對具體的應(yīng)用定制最優(yōu)的體系結(jié)構(gòu)，其設(shè)計(jì)過程往往是從局部展開，基于應(yīng)用分析和需求分析，提取其中的處理規(guī)律和特點(diǎn)，

3、并針對這些規(guī)律和特點(diǎn)展開設(shè)計(jì)。另外，專用處理器的設(shè)計(jì)要具有一定的完整性，包括配套的編譯器(綜合器)，便于工程師在嵌入式領(lǐng)域中的開發(fā)和接受。 本文具體研究內(nèi)容如下： 1)分析正則式和巴克斯范式的語法特點(diǎn)。 正則式和巴克斯范式都是用來描述字符串模式規(guī)則的文法。正則式是用途最廣泛的一種字符串模式描述工具，語法簡單高效。增強(qiáng)型巴克斯范式(Augmented Backus-Naur Form，ABNF)是RFC2234里面

4、定義的一個(gè)字符串模式匹配的文法定義，語法更豐富，擅長描述網(wǎng)絡(luò)協(xié)議的結(jié)構(gòu)和規(guī)則。本文首先分析正則式和巴克斯范式的語法特點(diǎn)以及它們描述網(wǎng)絡(luò)協(xié)議結(jié)構(gòu)和規(guī)則的規(guī)律，以便定義指令系統(tǒng)和硬件加速模塊的功能。 2)定義字符串模式匹配專用處理器的指令集。 根據(jù)正則式和巴克斯范式的特點(diǎn)，定義并設(shè)計(jì)了一套指令集，包括基本指令集和專用指令集?；局噶罴ＷC專用處理器具有基本的通用處理能力；專用指令集是針對模式規(guī)則的文法特點(diǎn)而設(shè)計(jì)的一套高級語言

5、指令集，擅長描述字符串模式規(guī)則，能夠更加簡潔地表達(dá)模式規(guī)則的關(guān)系操作，使得字符串模式匹配算法僅需少量的代碼即可描述，并且方便使用。 3)研究字符串模式匹配處理器的體系結(jié)構(gòu)設(shè)計(jì)和存儲器管理方案。 通用處理器上的字符串模式匹配代碼中，比較、判斷、循環(huán)和分支指令占有非常大的比重，指令相關(guān)性較強(qiáng)。這種算法的特點(diǎn)要求處理器頻繁地訪問不連續(xù)的存儲空間，導(dǎo)致流水線中斷、Cache命中率底下等問題，致使基于多級流水線的處理器性能難以發(fā)揮。在專用

6、處理器的體系結(jié)構(gòu)的定制上，要想取得較大的加速比，就需要針對這類問題和這些特點(diǎn)進(jìn)行解決。為了進(jìn)一步提高指令級的并行能力，面向字符串模式匹配的多核處理器的體系結(jié)構(gòu)設(shè)計(jì)也是本文的研究內(nèi)容。無論是單核處理器還是多核處理器，算法的特點(diǎn)都會導(dǎo)致處理器頻繁訪問存儲器，因此，合適的存儲器管理方案也是關(guān)鍵的研究內(nèi)容之一。 本文設(shè)計(jì)的單核專用處理器和雙核專用處理器在FPGA上褥到驗(yàn)證，并進(jìn)行了功能測試和性能測試，測試結(jié)果表明該專用處理器在功能上滿足

7、實(shí)際應(yīng)用的需要，在性能上可以有效地提高字符串模式匹配的處理速度和效率。 本文的主要創(chuàng)新點(diǎn)在于： 1)提出設(shè)計(jì)專用處理器的方案，通過針對模式規(guī)則的語法特點(diǎn)設(shè)計(jì)專用指令，得以提高字符串模式匹配的速度，同時(shí)又可以兼顧通用性和靈活性。 2)通過專用處理器的設(shè)計(jì)流程，本文講述了如何從應(yīng)用需求出發(fā)，通過對功能的描述和對傳統(tǒng)方案的分析，定制一種面向應(yīng)用的專用處理器，并進(jìn)一步挖掘指令級的并行能力的設(shè)計(jì)方法。 3)字符串模