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

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

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

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

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

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

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

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