內(nèi)容可導(dǎo)址存儲(chǔ)器的FPGA設(shè)計(jì)與應(yīng)用

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

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

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

1 CAM的基本原理

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

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

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

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

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

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

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

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

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

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

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

3.1 用SRL 16E實(shí)現(xiàn)CAM

在這種模式下，設(shè)計(jì)的基本模塊為SRL16E移位寄存器。SRL16E為VIRTEX庫(kù)的基本模塊，用戶可以使用SRL16E和其它基本模塊設(shè)計(jì)出不同字寬和字深的CAM來。

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

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

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

如圖4所示，Block SelectRAM的A口和B口其有共同的存儲(chǔ)單元（4096bit），但可以具有各自的地址映射表，A口配置成4096Word×1bit模式，B口配置成256Word×16bit模式。在這種配置形式下，A口可以以地址線寬為12bit、存儲(chǔ)單元容量為1bit的方式寫入數(shù)據(jù)，而B口則可以以地址線寬為8bit、存儲(chǔ)單元容量為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ù)讀取只需一個(gè)時(shí)鐘周期，輸出字寬16bit的匹配結(jié)果。

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

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

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

4 基本CAM的關(guān)聯(lián)比較器的實(shí)現(xiàn)及應(yīng)用

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

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

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

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

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

我們利用Xilinx公司的Foundation系列軟件和XCV100PQ240（10萬(wàn)門）FPGA芯片設(shè)計(jì)了一種基于CAM的脈沖去交錯(cuò)專用器件，考慮到軍用信號(hào)處理領(lǐng)域?qū)μ幚硭俣鹊膰?yán)格要求，設(shè)計(jì)采用了VIRTEX的第二種實(shí)現(xiàn)方法：用Block SelectRAM資源實(shí)現(xiàn)CAM。通過功能仿真和時(shí)序仿真驗(yàn)證了處理器的功能，并基于我們?cè)O(shè)計(jì)高性能可編程信號(hào)處理背板[4]進(jìn)行了半實(shí)物仿真分析，初步驗(yàn)證了處理復(fù)雜信號(hào)處理能力。

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