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

　　關鍵詞: FPGA? 內容可尋址存儲器(CAM)? APEX系列? VIRTEX系列? 關聯比較器

?

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

1 CAM的基本原理

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

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

?

?

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

2 用APEX系列FPGA實現CAM

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

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

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

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

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

?

?

3 用VIRTEX系列FPGA實現CAM

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

3.1 用SRL16E實現CAM

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

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

?

?

3.2 用Block SelectRAM實現CAM

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

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

?

?

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

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

3.3 用Distributed SelectRAM實現CAM

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

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

4 基于CAM的關聯比較器的實現及應用

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

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

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

?

?

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

?

?

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

　　我們利用Xilinx公司的Foundation系列軟件和XCV100PQ240(10萬門)FPGA芯片設計了一種基于CAM的脈沖去交錯專用器件,考慮到軍用信號處理領域對處理速度的嚴格要求,設計采用了VIRTEX的第二種實現方法:用Block SelectRAM資源實現CAM。通過功能仿真和時序仿真驗證了處理器的功能,并基于我們設計的高性能可編程信號處理背板^[4]進行了半實物仿真分析,初步驗證了處理器的復雜信號處理能力。

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

?

參考文獻

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的可編程嵌入式信號處理背板的開發設計.電子技術應用，2000；(26)11

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