包分類(lèi)算法研究與實(shí)現(xiàn).pdf

1、該論文主要論述利用可重構(gòu)FPGA技術(shù)實(shí)現(xiàn)硬件平臺(tái),通過(guò)系統(tǒng)對(duì)FPGA的重配置,對(duì)兩種分類(lèi)算法進(jìn)行硬件設(shè)計(jì)和實(shí)現(xiàn).第一章簡(jiǎn)述前人在分類(lèi)算法方面的工作.第二章介紹了基于TCAM的完全硬件分類(lèi)方法的設(shè)計(jì),包括硬件分類(lèi)算法實(shí)現(xiàn)的平臺(tái)的簡(jiǎn)介.在設(shè)計(jì)中采用延遲數(shù)據(jù)緩沖降低預(yù)處理緩存的復(fù)雜性,并通過(guò)優(yōu)化提高了系統(tǒng)的主時(shí)鐘頻率.使用源同步時(shí)鐘技術(shù)確保了時(shí)序的完整性.最后測(cè)試結(jié)果表明,根據(jù)所選網(wǎng)絡(luò)信息包的域的不同,TCAM的搜索延時(shí)在8~10周期間.對(duì)于

2、平均長(zhǎng)度小于70字節(jié)的網(wǎng)絡(luò)信息包,TCAM硬件分類(lèi)設(shè)計(jì)對(duì)輸入的網(wǎng)絡(luò)信息包處理速率可達(dá)到2.5Gb/s,此時(shí)FPGA和TCAM部分工作的主頻為40 MHz.時(shí)序后仿真表明,FPGA實(shí)際的分類(lèi)部分的時(shí)鐘頻率可以超過(guò)60MHz,相應(yīng)的分類(lèi)線(xiàn)速可達(dá)3.7Gbit/s.第三章介紹區(qū)域分割算法的硬件實(shí)現(xiàn).區(qū)域分割法是一種基本的空間點(diǎn)定位方法,Pankai Gupta等首先提出將區(qū)域分割法應(yīng)用于包分類(lèi).區(qū)域分割法實(shí)現(xiàn)包分類(lèi)是目前較為有效的分類(lèi)算法.在

3、區(qū)域分割基本思想的基礎(chǔ)上算法有很多種實(shí)現(xiàn)可能,且不同實(shí)現(xiàn)可能有較大的性能差別,所以?xún)?yōu)化實(shí)現(xiàn)是區(qū)域分割包分類(lèi)算法的核心研究?jī)?nèi)容.從區(qū)域分割算法原理知道,如果規(guī)則分布不均勻,通過(guò)簡(jiǎn)單的隨機(jī)等分某個(gè)域很難將規(guī)則分開(kāi)到不同的節(jié)點(diǎn)去,則樹(shù)的深度會(huì)急劇增加,從而使算法的時(shí)間、空間特性變壞.這一章在深入研究了區(qū)域分割方法特點(diǎn)的基礎(chǔ)上,提出了有效的分割準(zhǔn)則,再根據(jù)算法所涉及的小范圍(規(guī)則數(shù)小于20)內(nèi)線(xiàn)性查找過(guò)程的特點(diǎn),在算法預(yù)處理時(shí)對(duì)每個(gè)葉子結(jié)點(diǎn)的規(guī)

4、則進(jìn)行單域化處理;使得算法在較大規(guī)則數(shù)范圍內(nèi)時(shí)間復(fù)雜度僅為O(d),空間復(fù)雜度為O(dN).并行區(qū)域分割包分類(lèi)算法是在區(qū)域分割思想基礎(chǔ)上,利用區(qū)域分割總體結(jié)構(gòu)的存儲(chǔ)器映射方法和兩級(jí)、多通道并行處理技術(shù)實(shí)現(xiàn)的高速包分類(lèi)算法.并行區(qū)域分割包分類(lèi)算法具有區(qū)域分割方法的空間特性,快速更新(小于0.1S)特點(diǎn)和完整規(guī)則類(lèi)型適應(yīng)性等優(yōu)點(diǎn),同時(shí)具有更高的包分類(lèi)速度.第四章介紹一個(gè)使用Verilog HDL代碼的可綜合的RISC可編程整數(shù)微處理器軟核的

5、設(shè)計(jì)和實(shí)現(xiàn)以及其在FPGA內(nèi)部設(shè)計(jì)和調(diào)試的方法.該軟核用來(lái)解決區(qū)域分割算法實(shí)現(xiàn)中規(guī)則數(shù)據(jù)更新緩慢的問(wèn)題.在20世紀(jì)90年代中期,ASIC技術(shù)從芯片集成的理念發(fā)展成為基于嵌入式核的片上系統(tǒng)(SoC)概念.SoC是一種將多個(gè)獨(dú)立的VLSI設(shè)計(jì)拼合在一起,來(lái)完成某一應(yīng)用所需的全部功能的集成電路.在SoC的定義中,明確地強(qiáng)調(diào)了服務(wù)于多種應(yīng)用的稱(chēng)為"核"的預(yù)先設(shè)計(jì)的復(fù)雜功能模型.該處理器軟核可以根據(jù)實(shí)際應(yīng)用需要進(jìn)行靈活的剪裁.通過(guò)針對(duì)FPGA內(nèi)部