摘? 要： 內(nèi)容可尋址存儲器(CAM)是一種快速匹配存儲器件,在通信、雷達等許多領(lǐng)域有著廣泛的應用。在介紹CAM基本原理的基礎上,提出了以兩類新型FPGA實現(xiàn)CAM的設計方法" title="設計方法">設計方法。例舉了一種基于CAM實現(xiàn)的關(guān)聯(lián)比較器" title="比較器">比較器及其在雷達截獲系統(tǒng)信號處理" title="信號處理">信號處理領(lǐng)域的重要作用。

　　關(guān)鍵詞: FPGA? 內(nèi)容可尋址存儲器(CAM)? APEX系列? VIRTEX系列? 關(guān)聯(lián)比較器

?

　　內(nèi)容可尋址存儲器(CAM)是一種新型的存儲器,它的高速、并行、易擴展和實現(xiàn)的靈活性使它一出現(xiàn)就得到人們的重視。CAM基于內(nèi)容尋址,通過硬件電路實現(xiàn)快速匹配。CAM的并行處理特性使得它在數(shù)據(jù)分選領(lǐng)域倍受青睞,被廣泛應用于以太網(wǎng)網(wǎng)址搜尋、數(shù)據(jù)壓縮、模式識別、高速緩存、高速數(shù)據(jù)處理、數(shù)據(jù)安全和數(shù)據(jù)加密等。另外,CAM的出現(xiàn)也為軍用信號處理(尤其是雷達截獲系統(tǒng)信號處理)提供了新的思路。但是,由于CAM的實現(xiàn)是以犧牲硬件資源為代價的,常規(guī)的FPGA器件只能實現(xiàn)很小規(guī)模的CAM。因此,以前的CAM都是專用器件且規(guī)模較小,使用靈活性較低。隨著FPGA器件門數(shù)的增加和結(jié)構(gòu)的改進以及IP庫的不斷豐富,基于FPGA的CAM實現(xiàn)已成為可能。尤其是1999年底和2000年初,Altera公司和Xilinx公司相繼推出了APEX和VIRTEX系列超大規(guī)模FPGA,使得利用FPGA實現(xiàn)大規(guī)模CAM的時機趨于成熟。

1 CAM的基本原理

　　CAM是一種專門為快速查找數(shù)據(jù)地址而設計的存儲器。CAM通過把輸入數(shù)據(jù)與其內(nèi)所存數(shù)據(jù)相比較,能快速確定輸入數(shù)據(jù)是否與其內(nèi)部某個數(shù)據(jù)或某幾個數(shù)據(jù)相匹配。CAM的數(shù)據(jù)尋址方式因應用要求不同而不同,最快方式下僅需要一個時鐘周期便可完成對所有數(shù)據(jù)的尋址。

　　與RAM一樣,CAM也是采取陣列式數(shù)據(jù)存儲。其數(shù)據(jù)的寫入方式與RAM差不多,但CAM的數(shù)據(jù)讀取方式卻與RAM不同。在RAM中,輸入的是數(shù)據(jù)地址,輸出的是數(shù)據(jù);而在CAM中,輸入的是所要查詢的數(shù)據(jù),輸出的是數(shù)據(jù)地址和匹配標志(Match)。若匹配(即數(shù)據(jù)搜尋到),則輸出數(shù)據(jù)地址。在RAM中,RAM的存儲容量由地址線寬度確定。例如,10bit寬地址總線的RAM存儲容量為210=1024個字節(jié),CAM卻沒有這個限制,因為它不是采用傳統(tǒng)的通過地址讀取數(shù)據(jù)的方式。如若從1024個字節(jié)中查詢某一數(shù)據(jù),輸入數(shù)據(jù)寬度為8bit,數(shù)據(jù)存在則輸出匹配標志和10bit寬的數(shù)據(jù)地址。因為CAM不是采用傳統(tǒng)的地址線模式讀取數(shù)據(jù),存儲空間可以很容易地擴展,輸入數(shù)據(jù)線寬度只由需查詢的數(shù)據(jù)位數(shù)決定。圖1為數(shù)據(jù)讀取模式下的RAM和CAM的比較。

?

?

　　顯然,CAM 的數(shù)據(jù)查詢速度遠遠高于RAM。因此,CAM大量應用于需要高速數(shù)據(jù)處理的系統(tǒng)之中。CAM的出現(xiàn)加快了一些系統(tǒng)和技術(shù)的應用,如大型數(shù)據(jù)庫管理、數(shù)據(jù)鏈接、模式識別等在圖像識別、語音識別中的應用。CAM的核心為存儲單元" title="存儲單元">存儲單元陣列和存儲單元與輸入數(shù)據(jù)之間的比較器。不同的應用對CAM的速度、密度有不同的要求,而且CAM實現(xiàn)途徑也是多樣的。

2 用APEX系列FPGA實現(xiàn)CAM

　　APEX系列FPGA是Altera公司最新推出的高檔FPGA芯片,APEX系列真正實現(xiàn)了單芯片的系統(tǒng)級綜合。在多心線結(jié)構(gòu)的支持下,APEX芯片既具有以往PLD的優(yōu)點,又對這些優(yōu)點有所擴展,并且在復雜系統(tǒng)的設計和應用中表現(xiàn)出極大的靈活性和高效性。

APEX芯片內(nèi)含多達250萬個邏輯門,能夠單芯片實現(xiàn)諸如鎖相倍頻環(huán)之類的復雜系統(tǒng)。它擁有64bit的數(shù)據(jù)線寬度和66MHz的總線頻率,數(shù)據(jù)處理速度達620Mbit/s。2.5V供電的APEX采用0.22微米工藝,1.8V供電的APEX芯片則采用更先進的0.18微米工藝。

　　APEX芯片主要由三大部分組成:LUT、Product Term和Memory。這三大部分綜合到一個芯片中,不但節(jié)省了應用系統(tǒng)所占空間,而且使復雜系統(tǒng)的設計和實現(xiàn)變得簡單可靠,系統(tǒng)執(zhí)行效能也大大提高。ESB(Embedded System Block)是APEX芯片的核心,它可以用來構(gòu)成APEX芯片的各種控制部件。

　　通常,許多需要快速數(shù)據(jù)尋址的系統(tǒng)使用分立的CAM,這不僅會延長開發(fā)周期、占用印制板空間,而且也會因片內(nèi)、外的時延而降低系統(tǒng)效能。APEX芯片則較好地解決了這個問題,它內(nèi)含嵌入式CAM,把分立式CAM 20ns的時延降低至4ns以下。與采用分立式CAM的系統(tǒng)相比較,采用APEX芯片的系統(tǒng),則效率成倍提高。對中小型系統(tǒng)來說,APEX芯片無疑是系統(tǒng)優(yōu)化的最佳選擇。

APEX芯片可用ESB直接構(gòu)成CAM,實現(xiàn)高速數(shù)據(jù)尋址。還可用多個ESB擴展CAM的容量和數(shù)據(jù)寬度。在APEX20KE芯片中,每一ESB可配置成大小為32word×32bit的CAM,如圖2所示。

?

?

3 用VIRTEX系列FPGA實現(xiàn)CAM

　　APEX提供了一個規(guī)范的CAM基本器件,可通過級聯(lián)和位擴展來實現(xiàn)更大規(guī)模的CAM,但實現(xiàn)方式還是不夠靈活。而Xilinx公司開發(fā)的Foundation系列軟件和VIRTEX系列FPGA為CAM的應用提供了優(yōu)越的軟硬件條件,且VIRTEX最大的優(yōu)點是沒有為CAM提供固定的模式。它設計的靈活性,使CAM能在不同條件下、不同領(lǐng)域內(nèi),以不同方式實現(xiàn),達到最優(yōu)化。基于VIRTEX的CAM的實現(xiàn)主要有三種途徑:用SRL16E的實現(xiàn);用Block SelectRAM實現(xiàn);用Distributed SelectRAM的實現(xiàn)。

3.1 用SRL16E實現(xiàn)CAM

　　在這種模式下,設計的基本模塊為SRL16E移位寄存器。SRL16E為VIRTEX庫的基本模塊,用戶可以使用SRL16E和其它基本模塊設計出不同字寬和字深的CAM來。

　　用SRL16E實現(xiàn)的8-bit的CAM如圖3所示。初始化時,已知參數(shù)與4位遞減計數(shù)器內(nèi)容依次相比較,得到16bit" title="16bit">16bit比較值(含1個“1”,15個“0”),經(jīng)過16個時鐘周期,依次存入SRL16E移位寄存器。寄存器帶有4位地址端,可對移位寄存器的16bit數(shù)據(jù)位實現(xiàn)尋址。CAM工作時,數(shù)據(jù)直接輸入寄存器的地址端,若此數(shù)據(jù)與初始化時參數(shù)相一致,則輸出“1”,否則輸出“0”。

?

?

3.2 用Block SelectRAM實現(xiàn)CAM

　　除了用SRL16E實現(xiàn)CAM外,利用VIRTEX芯片內(nèi)可編程資源Block SelectRAM也是實現(xiàn)CAM的途徑之一。一個Block SelectRAM可配置成一個CAM16Word×8bit的CAM基本模塊,且有獨立的讀寫雙通道,這得益于Block SelectRAM的雙口特性。Block SelectRAM是真正具有獨立雙通道的存儲器,它的每個通道擁有各自的時鐘和控制信號,A口和B口可獨立配置成4096Word×1bit或256Word×16bit RAM模式?；贐lock SelectRAM 的CAM的設計正是利用了Block SelectRAM內(nèi)部地址映射的靈活性。

　　如圖4所示,Block SelectRAM 的A口和B口具有共同的存儲單元(4096bit),但可以具有各自的地址映射表,A口配置成4096Word×1bit模式,B口配置成256Word×16bit模式。在這種配置形式下,A口可以以地址線寬為12bit、存儲單元容量為1bit的方式寫入數(shù)據(jù),而B口則可以以地址線寬為8bit、存儲單元容量為16bit的方式讀取數(shù)據(jù)。

?

?

　　CAM16×8的A口為數(shù)據(jù)寫入口,數(shù)據(jù)輸入帶寬為8bit,地址線寬為4bit。Data_write[7：0]也可由它的譯碼值形式唯一地表示,Data_write[7：0]經(jīng)譯碼成256bit,存入Addr[3：0]所指的地址單元。

　　CAM16×8的B口為數(shù)據(jù)讀出口,匹配數(shù)據(jù)直接輸入B口的地址端,數(shù)據(jù)讀取只需一個時鐘周期,輸出字寬16bit的匹配結(jié)果。

3.3 用Distributed SelectRAM實現(xiàn)CAM

　　Distributed SelectRAM也是實現(xiàn)CAM的途徑之一。與Block SelectRAM類似,VIRTEX芯片內(nèi)部還有一種由LUT配置而成的Distributed SelectRAM,這兩種存儲器都可用來形成CAM。

??? 每個LUT(Look-Up Table)可配置成一片16Word×1bit RAM,每片RAM可以位尋址。16bit寬數(shù)據(jù)寫入時,分散寫入16片RAM。數(shù)據(jù)讀取時,地址端由一遞增計數(shù)器產(chǎn)生4位地址,從RAM讀出數(shù)據(jù)與查詢數(shù)據(jù)逐個比特相比較。最多經(jīng)過16個時鐘周期,便可完成與整個存儲數(shù)據(jù)相比較,得到匹配結(jié)果。

4 基于CAM的關(guān)聯(lián)比較器的實現(xiàn)及應用

??? 國外研究表明,關(guān)聯(lián)比較器(Coherent Processor，簡稱CP)技術(shù)對高密度信號環(huán)境下的脈沖列去交錯有著積極和重要的意義。由于器件方面的限制,國內(nèi)相關(guān)領(lǐng)域的研究一直停留于理論分析層面,僅有極少數(shù)系統(tǒng)采用了一些小規(guī)模的并行比較器件。

??? CP與CAM的主要區(qū)別是:CP是實現(xiàn)范圍比較,而CAM是精確單值匹配。在基于CAM的CP設計實踐中,我們結(jié)合復雜信號環(huán)境的具體應用背景和上述CAM設計方法,探索了兩種可能的途徑:(1)CAM和RAM結(jié)合實現(xiàn)結(jié)構(gòu)靈活的CP;(2)從CAM內(nèi)部結(jié)構(gòu)和原理出發(fā),對CAM進行適當改造,使得CAM具備范圍匹配功能。

??? 第一種途徑是通過研究許多CAM的應用實例而受到啟發(fā)的。例如,IP地址到以太網(wǎng)地址的映射是由CAM和RAM相結(jié)合完成的,首先將IP輸入CAM,得到匹配標志和匹配地址,然后將匹配地址作為RAM的輸入,從RAM中讀取相應的以太網(wǎng)地址,完成地址映射過程。還有IP路由表、高速緩存等應用的基本原理也是如此。相應地,在脈沖去交錯應用中,若將脈沖參數(shù)范圍內(nèi)的每一個值都作為CAM中的一項,將得到的匹配輸出地址作為預先存儲的RAM表項的輸入,即可實現(xiàn)CP的功能。如圖5所示,設輻射源M的頻率參數(shù)范圍是011111100b≤RF≤011111111b,則輻射源M在CAM中占用4個存儲單元n～n+3,在RAM內(nèi)n～n+3地址的存儲內(nèi)容均初始化為M。當輸入頻率值落入輻射源參數(shù)范圍時,便可由關(guān)聯(lián)比較器直接得到所屬的輻射源類型M。這種設計方法利用外部RAM實現(xiàn)了組合邏輯功能。

?

?

　　第二種途徑是利用可編程邏輯器件靈活的設計方法,對CAM內(nèi)部結(jié)構(gòu)進行改造,使其具備范圍參數(shù)匹配的功能。圖6示出了利用這種途徑實現(xiàn)CP的基本原理,圖示結(jié)構(gòu)為用一個256×1bit的RAM來實現(xiàn)一個8bitCAM單元。在CAM單元初始化時,以輸入數(shù)據(jù)作為RAM的地址,根據(jù)參數(shù)范圍對相應地址的RAM內(nèi)容進行初始化,落入?yún)?shù)范圍的尋址內(nèi)容為1,否則為0。完成初始化后,CAM即可實現(xiàn)范圍參數(shù)的匹配。

?

?

　　上述兩種實現(xiàn)途徑實際上都是通過耗費更多的硬件資源來達到范圍匹配的目的。當參數(shù)范圍較大時,硬件資源的需求會急劇增加,導致CAM深度的下降。若我們將上述兩種途徑與中值比較的原理結(jié)合起來,即用合理截取有效位數(shù)的方法來充分表示參數(shù)范圍特點,則可以獲得預期的效果。

　　我們利用Xilinx公司的Foundation系列軟件和XCV100PQ240(10萬門)FPGA芯片設計了一種基于CAM的脈沖去交錯專用器件,考慮到軍用信號處理領(lǐng)域?qū)μ幚硭俣鹊膰栏褚?設計采用了VIRTEX的第二種實現(xiàn)方法:用Block SelectRAM資源實現(xiàn)CAM。通過功能仿真和時序仿真驗證了處理器的功能,并基于我們設計的高性能可編程信號處理背板^[4]進行了半實物仿真分析,初步驗證了處理器的復雜信號處理能力。

　　高度并行性是CAM的基本特征。隨著FPGA技術(shù)的不斷進步,CAM實現(xiàn)的規(guī)模和速度將會有更大的進步,基于FPGA的CAM實現(xiàn)將在數(shù)據(jù)壓縮、模式識別、高速緩存、高速數(shù)據(jù)處理、數(shù)據(jù)安全和數(shù)據(jù)加密以及軍用信號處理等各種不同的應用領(lǐng)域中迸發(fā)出勃勃生機。

?

參考文獻

1 Stromon，C.D.，et al.An Architecture Based on Content? Addressable Memory for the Rapid Execution of Prolog.?Proceedings of 5th International Conference and Symposium on Logic Programming， Seattle， WA，1998

2 High-Density Embedded Programmable Logic Devicesfor?System-level Integration. Altera Corporation, July 1999

3 Virtex FPGA application Notes. Xilinx Corporation, 2000

4 徐 欣，盧啟中.基于Virtex系列FPGA的可編程嵌入式信號處理背板的開發(fā)設計.電子技術(shù)應用，2000；(26)11

5 徐 欣,周一宇,盧啟中.雷達截獲系統(tǒng)實時信號分選處理技術(shù)研究.系統(tǒng)工程與電子技術(shù),2001(3)