摘? 要: 介紹了內(nèi)容可尋址存儲(chǔ)器CAM MCM69C233的特點(diǎn)及使用。通過某交換機(jī)應(yīng)用表明,可大幅度提高數(shù)據(jù)檢索" title="數(shù)據(jù)檢索">數(shù)據(jù)檢索速度,增強(qiáng)系統(tǒng)可靠性。

　　關(guān)鍵詞: CAM? 數(shù)據(jù)檢索? 嵌入式實(shí)時(shí)控制系統(tǒng)

?

　　內(nèi)容可尋址存儲(chǔ)器CAM(Content Addressable Memory)是一種特殊的存儲(chǔ)陣列。它具有將輸入數(shù)據(jù)與CAM中存儲(chǔ)的所有數(shù)據(jù)項(xiàng)同時(shí)進(jìn)行比較,迅速判斷輸入數(shù)據(jù)是否與CAM中存儲(chǔ)的數(shù)據(jù)項(xiàng)相匹配,并給出數(shù)據(jù)項(xiàng)對應(yīng)地址和匹配信息的特點(diǎn),因而被廣泛地應(yīng)用于通信、模式識別等領(lǐng)域。在某型號交換機(jī)的設(shè)計(jì)中,筆者應(yīng)用MOTOROLA公司的CAM芯片——MCM69C233實(shí)現(xiàn)數(shù)據(jù)檢索功能,既提高了系統(tǒng)資源的利用率,又保障了系統(tǒng)性能,大大縮短開發(fā)周期。

1 MCM69C233功能簡述

　　CAM是一種基于RAM技術(shù)的存儲(chǔ)器,數(shù)據(jù)項(xiàng)存儲(chǔ)在CAM內(nèi)部的陣列中。每個(gè)數(shù)據(jù)項(xiàng)的位數(shù)叫字寬,陣列內(nèi)所有數(shù)據(jù)項(xiàng)的條數(shù)叫做CAM的深度,CAM的容量通過字寬和深度來表征。MCM69C233可存儲(chǔ)4096條寬度為64 位的數(shù)據(jù)項(xiàng)。圖1所示為MCM69C233的結(jié)構(gòu)框圖。

?

?

　　MCM69C233有兩個(gè)數(shù)據(jù)端口:控制端口(Control Port)和匹配端口(Match Port)。控制端口用于CAM表(CAM Table)的操作,除用于數(shù)據(jù)項(xiàng)的增加/刪除、校驗(yàn)、統(tǒng)計(jì)外,還可以讀取芯片內(nèi)部狀態(tài)寄存器的信息。數(shù)據(jù)的檢索通過匹配端口完成。盡管基于RAM技術(shù),CAM的存儲(chǔ)機(jī)制卻與RAM大相徑庭。如圖1所示,MCM69C233沒有用于確定內(nèi)容存儲(chǔ)地址的地址總線,地址線A0～A2用于對片內(nèi)控制寄存器的尋址。在寫CAM模式下,MCM69C233從控制端口數(shù)據(jù)線DQ0~DQ15讀取需要寫入的數(shù)據(jù)項(xiàng),數(shù)據(jù)項(xiàng)的存儲(chǔ)地址由芯片內(nèi)部邏輯控制。

　　用戶可對MCM69C233的匹配規(guī)則進(jìn)行編程,在讀CAM模式(查找匹配)時(shí),MCM69C233直接從匹配口數(shù)據(jù)線MQ0~MQ31讀入數(shù)據(jù),并按照預(yù)先定義的匹配規(guī)則將輸入數(shù)據(jù)項(xiàng)與陣列中的所有數(shù)據(jù)項(xiàng)進(jìn)行并行比較。如果數(shù)據(jù)項(xiàng)存在,匹配口輸出該數(shù)據(jù)項(xiàng)的索引值,且MS為0;如果數(shù)據(jù)項(xiàng)不存在,/MS為1。由于比較過程只需一個(gè)時(shí)鐘周期,所以速度極快。MCM69C233的最長匹配時(shí)間為210ns。

MCM69C233有兩種工作模式:ATM模式和基本模式。ATM模式主要用于ATM交換機(jī)中對ATM信元" title="信元">信元的處理。基本模式的應(yīng)用十分靈活,由于匹配規(guī)則可編程,用戶可根據(jù)不同的應(yīng)用場合實(shí)現(xiàn)檢索功能。

2 應(yīng)用實(shí)例

2.1 設(shè)計(jì)要求

　　某型號交換機(jī)根據(jù)產(chǎn)品定義用于ATM網(wǎng)絡(luò)和基于以態(tài)網(wǎng)的城域網(wǎng)E-MAN(Ethernet Metropolitan Area Network)的連接。其ATM端口工作速率為155Mbps,以太網(wǎng)端口工作速率為100Mbps。系統(tǒng)數(shù)據(jù)流如圖2所示。

?

?

　　上行方向,交換機(jī)首先在系統(tǒng)內(nèi)嵌的VP/VC通道表內(nèi)檢查每一個(gè)ATM信元內(nèi)的虛通路值/虛鏈接值VPI/VCI(Virtual Path Index/Virtual Connection Index,標(biāo)識一條虛通道/虛鏈接VP/VC)是否存在。如果存在,CPU獲得該VP/VC的配置信息,準(zhǔn)備下一步的協(xié)議處理。如果輸入信元的VPI/VCI不存在,則丟棄該信元。

　　輸入的ATM信元經(jīng)協(xié)議處理后,包含在ATM信元中的以太網(wǎng)幀被提取出來。交換機(jī)接著對以太網(wǎng)幀的源MAC地址進(jìn)行檢索,判斷該以太網(wǎng)幀是否來自已知的用戶。如果在系統(tǒng)內(nèi)嵌的MAC-VP/VC表中檢索到該MAC地址,則表明該以太網(wǎng)幀來自已知的用戶,系統(tǒng)隨即刷新老化標(biāo)記,將其轉(zhuǎn)發(fā)至以太網(wǎng)接口;如果不存在,則系統(tǒng)將在MAC-VP/VC表中添加該MAC地址并設(shè)置老化標(biāo)記,而后交換機(jī)將該以太網(wǎng)幀轉(zhuǎn)發(fā)至以太網(wǎng)接口。

　　下行方向,系統(tǒng)首先以輸入以太網(wǎng)幀的目的MAC地址為關(guān)鍵字在MAC-VP/VC表中進(jìn)行檢索,該地址就是上文提到的源MAC地址。如果目的MAC地址不存在,則將輸入的以太網(wǎng)幀轉(zhuǎn)換為ATM信元,向所有用戶端口廣播;如果匹配成功,交換機(jī)獲得與該MAC地址對應(yīng)的VPI/VCI,將以太網(wǎng)幀轉(zhuǎn)換為ATM信元,并根據(jù)VPI/VCI通道表,從指定的用戶端口轉(zhuǎn)發(fā)至ADSL終端,最后送達(dá)用戶主機(jī)。

嵌入式實(shí)時(shí)控制系統(tǒng)的性能主要取決于兩方面:硬件平臺的運(yùn)算性能和算法的優(yōu)越性。其中硬件平臺的運(yùn)算性能最為關(guān)鍵,這一點(diǎn)在交換機(jī)中表現(xiàn)得由為突出。按照設(shè)計(jì)要求" title="設(shè)計(jì)要求">設(shè)計(jì)要求,ATM信元的VPI/VCI檢索必須在1/4～1/2的信元接收時(shí)間內(nèi)完成,即684ns～1.37μs,以太網(wǎng)幀的MAC地址的檢索時(shí)間不能超過5.12μs。因此首先要保證數(shù)據(jù)檢索任務(wù)的響應(yīng)速度" title="響應(yīng)速度">響應(yīng)速度;其次,由于交換機(jī)數(shù)據(jù)流量大,對于本系統(tǒng)的ATM端口,系統(tǒng)每秒必須處理約365,566幀ATM信元,數(shù)據(jù)檢索任務(wù)十分繁重;另外,除了業(yè)務(wù)數(shù)據(jù)的ATM-Ethernet雙向協(xié)議處理外,交換機(jī)還必須完成SNMP(Simple Network Management Protocol)協(xié)議處理、命令行處理等任務(wù),所以還必須解決數(shù)據(jù)檢索對系統(tǒng)資源的占用問題。

　　提高性能的方法一般有兩種,最直接的方法就是采用高性能的硬件平臺,如采用分布式控制系統(tǒng),一個(gè)CPU用于協(xié)議處理,另一個(gè)CPU用于網(wǎng)管等事務(wù)處理;或者協(xié)議處理部分由ASIC完成,事務(wù)處理部分由CPU實(shí)現(xiàn)。但這些方案會(huì)帶來硬件成本的大幅提高。另外一種方案就是采用更優(yōu)化的算法。通過分析發(fā)現(xiàn),盡管利用軟件實(shí)現(xiàn)對ATM信元的VPI/VCI和以太網(wǎng)幀的MAC地址檢索并不復(fù)雜,但由于檢索次數(shù)頻繁,大量的系統(tǒng)資源被占用,系統(tǒng)的響應(yīng)速度大大降低,滿足不了大流量數(shù)據(jù)通信的要求。因此純軟件算法解決不了數(shù)據(jù)檢索部分對資源占用的問題。為提高系統(tǒng)的響應(yīng)速度,必須將這兩部分?jǐn)?shù)據(jù)檢索的任務(wù)分離出來由硬件實(shí)現(xiàn),協(xié)議處理部分還由CPU完成。數(shù)據(jù)檢索模塊和協(xié)議處理模塊并行工作,兩部分通過數(shù)據(jù)耦合,既可以提高模塊的內(nèi)聚度,又增強(qiáng)了算法的健壯性;并且利用硬件實(shí)現(xiàn)數(shù)據(jù)檢索還可以提高檢索速度,降低系統(tǒng)資源的占用率。

　　利用硬件進(jìn)行數(shù)據(jù)檢索,通常采用兩種策略:一種是利用FPGA或CPLD等可編程邏輯器件定制數(shù)據(jù)檢索單元。本系統(tǒng)兩種地址的數(shù)據(jù)結(jié)構(gòu)" title="數(shù)據(jù)結(jié)構(gòu)">數(shù)據(jù)結(jié)構(gòu)并不復(fù)雜,定制簡單數(shù)據(jù)結(jié)構(gòu)的檢索單元體現(xiàn)不了可編程邏輯器件功能強(qiáng)大、靈活性強(qiáng)等優(yōu)越性,并且這類器件的開發(fā)難度相對較大,完成后還需要相當(dāng)長一段時(shí)間進(jìn)行測試。另一種策略是選擇CAM實(shí)現(xiàn)數(shù)據(jù)檢索。兩者比較,本系統(tǒng)采用CAM。根據(jù)系統(tǒng)設(shè)計(jì),本交換機(jī)采用兩塊CAM實(shí)現(xiàn)數(shù)據(jù)檢索功能,MAC-CAM用于以太網(wǎng)幀的MAC地址檢索,ATM-CAM用于ATM信元的VPI/VCI檢索,如圖2所示。

2.2 檢索算法設(shè)計(jì)

　　下面根據(jù)系統(tǒng)設(shè)計(jì)方案,以MAC-VP/VC表為例說明以太網(wǎng)側(cè)數(shù)據(jù)檢索功能的實(shí)現(xiàn)。如圖3所示,MAC-VP/VC表由硬件、軟件兩個(gè)子模塊構(gòu)成。MAC-CAM表實(shí)現(xiàn)MAC地址到偏移地址的查詢,這部分由硬件實(shí)現(xiàn);RAM表實(shí)現(xiàn)偏移地址到配置信息的查詢,這部分由軟件實(shí)現(xiàn);兩者通過偏移地址耦合。本系統(tǒng)將每一個(gè)VP/VC認(rèn)為是一個(gè)用戶端口,VP/VC的值保存在用戶端口域。

?

?

　　當(dāng)進(jìn)行MAC地址檢索時(shí),CPU首先以MAC地址為關(guān)鍵字通過MAC-CAM表的檢索得到對應(yīng)的偏移地址a,然后再根據(jù)公式(1)得到RAM表中該MAC地址的存儲(chǔ)位置,并由此地址獲得相關(guān)配置信息。RAM表中標(biāo)志域1、標(biāo)志域2分別表示用戶MAC地址的狀態(tài)信息,限于篇幅這里不詳述了。

　　RAM地址=基地址 + a×b?? (1)

　　公式(1)中,基地址是RAM表的起始地址;a是通過MAC-CAM表查詢得到的偏移量,即MAC地址的索引值;b表示RAM表中的一個(gè)表項(xiàng)的寬度為多少字節(jié)。

　　與MAC-VP/VC表的實(shí)現(xiàn)基本相同,VPI/VCI通道表的實(shí)現(xiàn)也分為兩部分,一部分由硬件CAM實(shí)現(xiàn),另一部分由軟件實(shí)現(xiàn)。執(zhí)行VPI/VCI檢索時(shí),CPU先通過CAM得到某VPI/VCI的偏移地址,然后再根據(jù)該偏移地址得到RAM表中保存的具體配置。

正是通過MAC-VP/VC表和VPI/VCI通道表,本系統(tǒng)實(shí)現(xiàn)了ATM網(wǎng)絡(luò)與E-MAN的交換。

2.3 檢索算法的實(shí)現(xiàn)

　　按協(xié)議規(guī)定MAC地址占48位,表示為6字節(jié)的數(shù)組。圖4和圖5分別表示了MAC-CAM表中MAC地址的高32位數(shù)據(jù)和低16位數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

?

?

　　圖6所示為MAC地址索引項(xiàng)的數(shù)據(jù)結(jié)構(gòu),它分為兩部分:最高位為匹配標(biāo)志(MS),0表示匹配成功,1表示匹配失敗;匹配輸出的低16位為MAC地址的索引(macIndex),用戶可按需要對其進(jìn)行定義,如MAC地址00-3C-CD-17-65-AB的索引值為0x03EF。

不同的協(xié)議要求,VPI/VCI表的數(shù)據(jù)結(jié)構(gòu)與MAC表的數(shù)據(jù)結(jié)構(gòu)并不相同。但由于處理方式相近,這里就不贅述了。

　　MCM69C233的匹配規(guī)則由通用屏蔽字(Global Mask)制定。進(jìn)行檢索時(shí),MCM69C233將檢索內(nèi)容與通用屏蔽字進(jìn)行按位或運(yùn)算,1表示屏蔽該位的值,0表示對該位敏感。從上文可看到,兩種數(shù)據(jù)檢索的數(shù)據(jù)結(jié)構(gòu)大不相同,因此需要不同的匹配規(guī)則。根據(jù)本系統(tǒng)設(shè)計(jì)要求,ATM信元的檢索只對VPI/VCI敏感,因此通用屏蔽字為0xFF00_0000_FFFF_FFFF,即忽略GFC字段和PHY地址標(biāo)識段。對于MAC地址的匹配操作,通用屏蔽字為0x0000_0000_0000_FFFF,即48位匹配。通用屏蔽字的設(shè)定必須在CAM初始化時(shí)完成。

　　在執(zhí)行匹配操作前,CAM須進(jìn)行初始化。由于ATM-CAM和MAC-CAM的工作模式不同,因此兩者的初始化過程亦不盡相同。下面以ATM-CAM為例,用偽碼形式說明初始化過程。

　　atmCamInit()

　　{　

????????????? Set ATM_CAM working on ATM mode;

????????????? Set the Global mask register for VPI/VCI translation;

????????????? Set the ATM_CAM to fast entry mode;

????????????? Input VPC table;

????????????? Initialize VPC table;

　　}

　　對于ATM-CAM,首先必須設(shè)定工作模式,ATM-CAM工作于ATM模式;然后對通用屏蔽字進(jìn)行設(shè)置,以保證正確的匹配規(guī)則;緊接著,將ATM-CAM設(shè)為快速輸入模式(Fast entry mode,當(dāng)需要將大量數(shù)據(jù)寫入CAM時(shí),該模式能加快輸入速度),將預(yù)先定義好的VPI/VCI-Channel Code表寫入CAM;最后執(zhí)行表初始化指令。至此,ATM-CAM能夠正常工作了。前面已提到,MAC表的形成是通過自學(xué)習(xí)得到的,因此MAC-CAM的初始化并不需要該過程。另外,MAC-CAM工作在基本模式,MCM69C233上電后,默認(rèn)工作模式為基本模式。因此MAC-CAM的初始化只需要兩步,通用屏蔽字的設(shè)置和表初始化。

　　匹配操作通過對匹配口讀/寫完成。匹配口數(shù)據(jù)線只有32位。由于MAC地址占48位,因此需要兩次寫操作才能完整地將一個(gè)MAC地址表達(dá)出來;而VPI/VCI只占24位,因此只需一次寫操作就可以了。下面以MAC地址的檢索為例說明CAM的匹配操作過程。

當(dāng)進(jìn)行MAC地址檢索時(shí),CPU先向匹配口寫入如圖4所示的低32位數(shù)據(jù),其中高16位有效,低16位可以為任意值;緊接著CPU向匹配口寫入如圖5所示的高32位數(shù)據(jù);隨后CPU讀匹配口,就可得到如圖6所示的結(jié)果。如果被查詢的MAC地址存在,則MS位為0,macIndex為有效輸出;如果被查詢的MAC地址不存在,則MS位為1,macIndex為輸出無效。上述過程可通過偽碼表示如下:

　　STATUS macCamCheckEntry( )

　　{

? 　　Write low 32-bit word to match port in first cycle；

?　　 Write high 32-bit word to match port in second cycle；

? 　　Read 32-bit result from match port；

?　 　If MS flag is “1”

??　??There is no such Entry；

? 　　Else return macIndex；

　　{

3 運(yùn)行結(jié)果

　　某交換機(jī)的運(yùn)行結(jié)果表明， 采用CAM， 交換機(jī)的以太網(wǎng)端口能工作在100Mbps,基本滿足設(shè)計(jì)要求;如采用軟件搜索方法， 則只能達(dá)到30Mbps。

?

參考文獻(xiàn)

1 嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(第二版). 北京:清華大學(xué)出版社,1996

2 張海藩. 軟件工程導(dǎo)論(第三版). 北京:清華大學(xué)出版社,1998

3 Robert L. Kruse， Clovis L. Tondo， Bruce P. Leung.Data?Structures & Program Design In C. 2nd， Edition. Prentice-Hall International， Inc. 1997

4 Motorola，Inc.MCM69C233 Data Sheet. 2001