正則表達式是一種熱門的字符匹配技術,在BGP路由協議中得到了重要的應用,本文的研究內容的是如何提高正則表達式的匹配速度。在BGP路由協議中,正則表達式通過軟件實現的方式用于路由信息過濾,但大量的過濾事務和自身效率問題在一定程度上影響了BGP的性能,如何提高正則表達式的匹配速度是解決問題的關鍵。在這樣的項目需求下,本研究課題應運而生。 經過對國內外關于正則表達式的實現技術進行了調研,本文提出了一種新的正則表達式實現技術,它以BGP網絡路由協議的應用為背景,以嵌入式平臺為運行環(huán)境,采用了POSIX正則表達式庫的軟件算法,結合軟件平臺的靈活和硬件平臺的高效,使得嵌入式Linux軟件系統(tǒng)和FPGA硬件協同工作,通過硬件加速的方式完成了對正則表達式的匹配。 具體實施中,系統(tǒng)被劃分成了軟件系統(tǒng)模塊、硬件系統(tǒng)模塊和負責軟硬件通信的接口等三個組成部分。輸入的正則表達式和字符串首先進入軟件系統(tǒng)模塊,它基于嵌入式Linux軟件系統(tǒng)實現,結合堆棧技術,把正則表達式編譯成為機器能識別并執(zhí)行的執(zhí)行碼指令,并生成fastmap數據。因為軟件系統(tǒng)模塊和硬件系統(tǒng)模塊的實現平臺不同,運行速度級別也有差異,故通信接口負責它們之間的數據傳輸。硬件系統(tǒng)模塊基于FPGA實現,結合堆棧技術,根據得到的執(zhí)行碼、字符串和fastmap數據來完成正則表達式的匹配計算,得到最終是否匹配的結果。 在整體設計中,系統(tǒng)具有“硬件加速”、“默認使用最短匹配原則”和“放棄計算匹配細節(jié)”等獨到的設計特點,系統(tǒng)內部高效運作,很好地完成了設計任務。文章在最后給出的邏輯測試和性能測試證明,系統(tǒng)不僅很好地完成了設計邏輯,并且擁有良好的加速效果,表明了本次科研設計是成功的。 本文的創(chuàng)新和貢獻在于:(1)總結了當前各種正則表達式的實現技術,結合了軟件解決方案和硬件解決方案的優(yōu)點,創(chuàng)新出軟硬件協同工作的解決方案。(2)在嵌入式領域上提高了正則表達式的匹配速度,有力地支持了路由器等設備,拓展了正則表達式在嵌入式平臺上的應用領域。
【學位單位】：上海交通大學
【學位級別】：碩士
【學位年份】：2010
【中圖分類】：TP368.1
【部分圖文】：

圖 2-1 構造自動機原理圖Fig. 2-1 principle graph of making automaton由正則表達式構造出自動機的過程，如圖 2-1 所示。首先，正則表達式被解樹，然后再轉換成非確定有限自動機。目前，從解析樹構造非確定有限自用方法有湯姆遜（Thompson）構造法[9]和格拉施科夫（Glushkov）構造法[9非確定有限自動機后，可以直接用它進行文本匹配，也可以將它確定化和構造出相應的確定有限自動機，然后用確定有限自動機進行文本匹配。3 正則表達式軟件實現的相關研究目前的軟件平臺上，C、C++、Java 等編程語言都有支持正則表達式的語法，各有優(yōu)缺點，在這些實現方法中，不少方法用到了自動機理論的知識，實現正則表達式的算法，都是可以值得借鑒的。以下是支持正則表達式的和軟件庫：

通大學工程碩士學位論文 第三章程中，只要發(fā)現有部分字符串符合正則表達式的規(guī)則，即宣告匹配成功，而不尋找符合要求的、長度更長的字符串；“放棄計算匹配細節(jié)”指的是放棄匹配細計算，諸如不計算出“字符串中共有多少部分的字符信息符合要求”等。以上設計特點，都是結合課題應用背景需求，減少計算，為了更好地實現加速匹配。 系統(tǒng)設計與實現構架在本次設計中，采用軟件和硬件相結合的方式來實現系統(tǒng)功能，軟件平臺采用嵌 Linux 系統(tǒng)，它能提供很好的軟件開發(fā)平臺，而硬件平臺采用 FPGA 芯片，它程的特點，提供了硬件開發(fā)過程中能不斷調試的機會，并且自身優(yōu)良的性能可速實現正則表達式的匹配計算。

工程碩士學位論文 第四章 軟件系統(tǒng)模塊設計系統(tǒng)模塊概述上一章節(jié)介紹，我們得知整體系統(tǒng)設計劃分為三個組成部分，本章節(jié)件系統(tǒng)模塊進行介紹。系統(tǒng)模塊是基于 Linux 操作系統(tǒng)實現的，屬于 Linux 操作系統(tǒng)的應用程其被封裝成 regcomp 函數模塊，所實現的功能是提供調用接口給用戶的編譯和 fastmap 數據生成、同硬件系統(tǒng)模塊通信。

【參考文獻】

相關期刊論文 前5條

1 葉梅;趙京偉;初元萍;;嵌入式Linux系統(tǒng)在PowerPC上的實現[J];核電子學與探測技術;2006年05期

2 買培培;邵東暉;蘇濤;;Linux在Xilinx FPGA上的移植[J];火控雷達技術;2009年04期

3 潘建,董金祥;基于GNU工具鏈的嵌入式操作系統(tǒng)開發(fā)[J];計算機工程與應用;2004年26期

4 張宇;馮丹;;基于Xilinx SoPC的可重構嵌入式計算系統(tǒng)的研究與設計[J];計算機科學;2010年05期

5 夏軍波;車建國;楊建文;石磊;;基于硬件的快速正則表達式匹配方法[J];通信技術;2010年01期

本文編號：2820003