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

　　關鍵詞: CAM? 數據檢索? 嵌入式實時控制系統(tǒng)

?

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

1 MCM69C233功能簡述

　　CAM是一種基于RAM技術的存儲器,數據項存儲在CAM內部的陣列中。每個數據項的位數叫字寬,陣列內所有數據項的條數叫做CAM的深度,CAM的容量通過字寬和深度來表征。MCM69C233可存儲4096條寬度為64 位的數據項。圖1所示為MCM69C233的結構框圖。

?

?

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

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

MCM69C233有兩種工作模式:ATM模式和基本模式。ATM模式主要用于ATM交換機中對ATM信元" title="信元">信元的處理?；灸Ｊ降膽檬朱`活,由于匹配規(guī)則可編程,用戶可根據不同的應用場合實現(xiàn)檢索功能。

2 應用實例

2.1 設計要求

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

?

?

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

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

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

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

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

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

2.2 檢索算法設計

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

?

?

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

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

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

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

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

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

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

?

?

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

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

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

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

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

當進行MAC地址檢索時,CPU先向匹配口寫入如圖4所示的低32位數據,其中高16位有效,低16位可以為任意值;緊接著CPU向匹配口寫入如圖5所示的高32位數據;隨后CPU讀匹配口,就可得到如圖6所示的結果。如果被查詢的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 運行結果

　　某交換機的運行結果表明， 采用CAM， 交換機的以太網端口能工作在100Mbps,基本滿足設計要求;如采用軟件搜索方法， 則只能達到30Mbps。

?

參考文獻

1 嚴蔚敏,吳偉民. 數據結構(第二版). 北京:清華大學出版社,1996

2 張海藩. 軟件工程導論(第三版). 北京:清華大學出版社,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