TW200832408A - Hierarchical search line with internal storage irrelevant entry control - Google Patents

Description

200832408 九、發明說明： 【發明所屬之技術領域】 本發明係有關一種通訊網路上搜循線之設計，特別是指一種應用於Ip 位址搜尋，利用内容可定址記憶體以無關項控制之階層式搜循線。 【先前技術】 内容可定址記憶體（Content-addressable memory^ CAM)係為一種可利 用比較電路在單-週期内執行絲功能之記憶裝置，更是一種高性能的搜 _ 尋引擎，其將單一時脈中輸入之搜尋資料與全部内容做比對；内容可定址 記憶單元提供位元儲存及位元比較兩種功能，就位元儲存來說，内容可定 址記憶體就如同-般的記髓，但鱗態賴存取記㈣（s·福⑽ acxe_em〇ly，SRAM)不同的是，内容可定址記憶體還可進行搜尋動作這 特殊权式，且具有高搜尋速度。隨著内容可^址記憶體之應用層面擴展， 功率問題也更加嚴重，如何在功率、速度及面積三者中取得平衡是一項重 要的課題。 内谷了疋址δ己憶單元可分為一元内容可定址記憶單元cam) 及二朗容可定址記憶單元(temary cAM )，其中二元内容可定址記憶單元 包含〇與1兩種狀態，而三元内容可定址記憶單元則另包含「無關項」這 一狀態，適用於網路應闕面，目此三元内容可定址記憶單元需要格外的 儲存空間來儲存第三種狀態。 傳統之三元内容可定址記憶體架構如第一圖所示，包含資料記憶體、 位址解碼器、位元線預支電路、字續應電路、讀取感應放大器及位址優 先順序編碼器（addresspri〇rity enc〇der)等等，提供寫入、讀取及搜尋等操 5 200832408 作。•之麟字分觸存錢麟上，内料仏峨财字元的位元 數通常很大’其範圍約在36〜144位元，標準型内容可定址記憶體依據其 7〜15位元之位址㈣’可擁有幾百項到处項之間的表格大小， 每-儲存字元包含-對應線（喊hline)，其代表搜尋字元及儲存字元完全 •相同（對應）或不相同（不對應或有誤差），用以使編碼器在對應情況下根 據對應線來產Hit對應位置，但此編碼器僅在單—對應下使用，而 在内容可定址記誠之朗中可能會有—個社之枝產生對應，故利用 _ -健優先祕編碼ϋ來取代單—解，恤優細率編碼驗據較低 位址字元取得較高優先順序之原則產生之對應結果，選取出具有最高優先 順序之對應位置容可紐記㈣巾全部的魏皆在於取得一搜尋字 元並回復對應之記憶體位置。 將1¾層式搜循線電路分割為總體搜循線（glGbalsearchline，GSL)及區 域搜循線（local Searchliiie，LSL)兩層級，如第二圖所示，此階層式搜循線 係建立在管線對應線（pipeline match_lines)之頂端，可解決傳統搜循線中 ® 僅極少數對應線可取得第一區段之問題。如圖所示，每一區域搜循線雖然 僅連接一單一對應線，但每一區域搜循線之對應線數量可達到64〜256條； 總體搜循線每一週期搜尋一次，但區域搜循線僅在需要時動作，當區域搜 循線連接之對應線中至少一條動作，才會激發區域搜循線，可節省消耗。 然而’搜尋之速度亦會被階層式搜循線系統所限制，主要原因在於控 制訊號來自於同一區塊中前一級的比較結果，造成每一級都必須等到前一 級完全運算完畢後，再經過一級階層式搜循線上邏輯閘的延遲才可開始進 6 200832408 行比對運算，造成搜尋時間延遲，此外，階層式搜循線之緩衝器為了得到 下一級的控制訊號’必須有-個非常大的控制邏輯問，其中管線正反号 (Pipdine flip_fl〇ps)會造成面積及功率消耗，增加面積與功率上的消^ 時脈驅動H (doekdriv㈦會降低_式__城。 因此，本發明即針對上述習知技術之數項缺失，提出一種内儲存無關 項控制之階層式麵線，贿效克服上叙轉問題。 【發明内容】 本發明之主要目的在提供一種内儲存無關項控制之階層式搜循線，其 係利_容可定址記憶體中，將f料崎殊方_，以無關項的特性 直接比對嫌嫩崎彻，_編綱㈣是，則較其 為短之資料也皆為無關項。 本心明之另-目的在提供一種内儲存無關項控制之階層式搜循線，其 係依照減帽肋容之長細貞序，將具有最長前置内容之資料儲存於記 憶單元之最底層’在搜尋時由底層向上搜尋。 本毛月之S目的在提供一種内儲存無關項控制之階層式搜循線，其 係以每-區塊最朗之資_容簡_區之控制訊號 ，因此在寫入週期 時即可得知此控舰號之數值，#搜尋日林會造成麟上之時間延遲。 本發明之又-目的在提供一種内儲存無關項控制之階層式搜循線，其 二在位址搜尋的應用备中，直接利用無關項之排列特性來控制階層式搜 循線，無需額外的儲存單元。 本發明之又-目的在提供—種内儲存無襲控制之階層式搜循線，其 7 200832408 係將Ρό層式搜循線切割為總體搜循線與區域搜循線，總艘搜循線在每一次 的搜尋都會被啟動，如果每個賴㈣域觀線之内容可定址記憶體之狀 態均為「無關」，則區域搜循線會被關閉以減少功率消耗。 為達上述之目的，本發明提供一種内儲存無關項控制之階層式搜循 線，其係架構在内容可定址記憶體中，包括：複數區塊，其係該内容可定 址記憶體所劃分出，每一區塊中包含一記憶單元，且於區塊中儲存有已定 義無關項狀態之複數；複數組階層式搜循線，其係設置於區塊中，每一組 階層式搜循線係包括一總體搜循線及一區域搜循線，區域搜循線係連結記 憶單元，在搜尋無關項時，每一區塊係同步搜尋；以及複數緩衝器，其係 刀別《又置於母區塊中，連結總體搜循線及區域搜循線，依據無關項之狀 態判斷總體搜循線之資料是否要傳遞到區域搜循線中。 本發明並提供一種利用階層式搜循線搜尋之方法，其係應用於一内容 可定址記憶體中，將内容可定址記憶體分成複數區塊，每一區塊中具有一 組階層式搜循線，且每一組階層式搜循線係包括一總體搜循線及一區域搜 循線，並將總體搜循線及區域搜循線利用一緩衝器連結，每一區塊中包含 複數已疋義是否為無關項之資料，該方法包括下列步驟：將内容可定址記 隐體之負料依照其前置内容之長度順序儲存於區塊中，並將欲比對之資料 傳送到總體搜循線；每一區塊判斷具有最長前置内容之資料是否為無關 項，以供緩衝器依據無關項之一狀態值判斷總體搜循線之資料是否要傳遞 到區域搜循線中，緩衝器並輸出區域搜循線之一搜尋值；以及區域搜循線 將搜尋值傳送出去。 8 200832408 底下藉由具體實施解加制，當更容鎌解本發明之目的、技術内 容、特點及其所達成之功效。 【實施方式】 本發明係提供-種内儲存無關項控制之階層式搜循線，其係應用於通 訊網路上有關〇>紐搜尋時，内容可定址記㈣與無關補性之搜循 線設計，朗本發明，在麟時控舰號不會職尋延料間造成影響， 亦不需要複雜的控織路與齡單元，可有效降低搜觀上之功率消耗而 保持相同之搜尋延遲時間，並節省面積。 由於當内容可定址記·的狀態為無關時，其所產生之訊號與輸入訊 號是相互獨立的，此時可關閉搜循線不需傳遞資料。因此，本發明將搜循 線分為總體搜循線無域搜麟，如第三·第四騎示，其巾第四圖為 本發明之簡單電路圖，内容可定址記憶體ω被分為複數個區塊12，每一區 。匕3夕條比幸又線、一條區域搜循，線Μ、-條總體搜循線16及一緩衝 器18 ’此緩衝器18係為NOR架構者，其用以連結總體搜循線16及區域搜 循線14，在每—次搜尋時，欲輯之資料先被傳送至總體觀線16 ’再由 緩衝器18根翻容可定址記憶體1G中無_之狀態來判斷總體搜循線16 上之資料是轉要傳遞顺域搜餅14。本發騎制之内料幻止記憶 (ternary Content-addressable memoiy, TCAM) 〇 將本發明應用在IPv6位址搜尋當中，將儲存於内容可定址記憶體中之 資料依照其前置内容（prefix)之長度順序儲存，以第三圖為例在内容可 定址記憶體1〇中存儲有256位元之内容，四個區塊12各儲存⑶位元之 200832408 資料，且每—筆賴皆已定義其是轉無_，财每-行之〇各代表一 記憶位元2G，其中錢色χ者為無關項内容，深色X為有關彻容，如圖 所示’具有最長輸㈣料婦仙容可紐記憶體⑴之底部，亦即 第-區塊之取上層’反之具有最短前置内容的資料被儲存在内容可定址記 憶體㈣最上部，亦即第四區塊之最下層^於每—區塊η皆設有緩衝 器18，故搜尋時，每一區塊12可同步搜尋。 由於貝料依其則置内谷之長短依序儲存於内容可定址記憶體川中之複 數£塊12中，故若判斷出具有最長前置内容之龍為無關項，則可肯定其 上之記憶單元20中之資料亦為無關項，而本發明·儲存在内容可定址記 憶體H)内無關項的狀態做為緩衝器18的控制訊號來源，利用資料以特殊 方式排列之_，Kf轉-嶋綱响械，_容作為控 _即可，_難18依據無_之狀_總體搜循線Μ之資料 疋否要傳遞到區域搜循線14中；緩衝器18接受總體搜循線Μ與無關項之 1並輸出II域搜麟14之—搜尋值，最後區域搜循線Μ再將搜尋值 傳送到區塊12上之記憶單元20中。 内儲存無關項控制之階層式搜循線與傳統接層次搜循線比較的另一個 最大好處’在於其不會增加搜尋時的_延遲，如第五圖所示之内儲存無 關項控制之崎式搜循線之時間分析示意圖，由於咖之控制訊號在寫 入週期後就可以被確定’因此緩衝器對於搜尋時間延遲無任何的影響，由 圖中可明顯看出，總體搜循線到區域搜循線之操作延遲時間少於半個系統 時鐘週期，在運算時’區域搜循線的資料已經準備就緒。由此可見本發明 200832408 所提出之架構對於延遲時間無任何的負擔。 ^上所述’本發明提供之内儲存無襲控制之階層式搜麟將内容可 定址讀、體刀為複數區塊，每—區塊中皆包含—緩衝器，利用在寫入週期 時p可確^得到之無關項狀態做為緩衝器之控制訊號，可使進行搜尋時不 θ猶哥5^遲~間造成影響，且不需如先前技術般需要額外的儲存單元及 複雜的控制電路來取得下_級控制訊號；此外，本發明中之緩衝器為 _ 架構▼減》緩衝器之面積與耗能，使搜循線具有更好的效能。 唯以上所述者，僅為本發明之難實關而已，並非絲限林發明 貫施之_。故即驗本發明中誠_述之舰及精神㈣之均等變化 或修飾，均應包括於本發明之申請專利範圍内。 【圖式簡單說明】 第一圖為先前技術中三元内容可定址記憶體之示意圖。 第二圖為先前技術中階層式搜循線之架構示意圖。 % 第三圖為本發明内儲存無關項控制之階層式搜循線之示意圖。 第四圖為本發明内儲存無關項控制之階層式搜循線之簡單電路圖。 第五圖為本發明内儲存無關項控制之階層式搜循線之時間週期曲線圖。 【主要元件符號說明】 10内容可定址記憶體 12區塊 14區域搜循線 16總體搜循線 200832408 18緩衝器 20記億單元

Claims (1)

1. 200832408 十、申請專利範圍： 1· 一種内儲存無關項控制之階層式搜循線，其係應用於一内容可定址記憶 。 體中，包括： 複數區塊，其係由該内容可定址記憶體所劃分出，每一該區塊中包含 ‘ 一記憶單元，且於該區塊中儲存有已定義無關項狀態之複數； 複數組階層式搜循線，其係設置於該區塊中，每一組該階層式搜循線 係包括一總體搜循線及一區域搜循線，該區域搜循線係連結該記憶單 φ 元’在搜尋該無關項時，每一該區塊係同步搜尋；以及 複數緩衝H，其係分舰置於每—該區塊巾，連結該總體搜循線及該 區域搜循線’依據該無關項之狀態判斷該總體搜循線之資料是否要傳遞 到該區域搜循線中。 2·如申請專利範圍第1項所述之内儲存無關項控制之階層式麵線，其中 該階層式搜循線係對應至相同之該區塊中之同一行。 3·如申請專利範圍第1項所述之内儲存無關項控制之階層式麵線，其中 Φ 該區域搜循線係用以傳送搜尋值到該區塊上之該記憶單元中。 4·如申4專利fc圍第1項所述之内儲存無關項控制之階層式搜循線，其中 每一該區塊中皆設有一組該階層式搜循線。 5·如f 4專她财1項所述之内儲存無襲控制之階層式搜循線，其中 該内容可定址記憶體之資料係依照其前置内容之長度順序儲存於該區塊 中。 6.如申請專利範圍第1項所述之内儲存無關項控制之階層式搜循線，其中 該區域搜麟帽紅同-狀該區顺觀錢接至m總體搜循 13 200832408 線，在進行每一次搜尋時，欲搜尋之資料先傳遞至該總體搜循線上。 7·如申請專利範圍第1項所述之内儲存無關項控制之階層式搜循線，其中 該緩衝器係接受該總體搜循線與該無關項之輸入，並輸出該區域搜循線 之值。 8·如申請專利範圍第1項所述之内儲存無關項控制之階層式搜循線，其中 該無關項之值係為每一該區塊中存放於該記憶單元最上層之内容。 9.如申請專利範圍第1項所述之内儲存無關項控制之階層式搜循線，其中 該緩衝器係為NOR架構。 10·—種利用階層式搜循線搜尋之方法，其係應用於一内容可定址記憶體 中’將该内容可定址記憶體分成複數區塊，每一該區塊中具有一組階層 式搜循線，且每一組該階層式搜循線係包括一總體搜循線及一區域搜循 線，並將該總體搜循線及該區域搜循線利用一緩衝器連結，每一該區塊 中包&複數已疋義疋否為無關項之貨料，該方法包括下列步驟： 在該内容可定址記憶體之資料依照其前置内容之長度順序儲存於該區 塊中，並將欲比對之資料傳送到該總體搜循線； 每一該區塊係同步判斷具有最長前置内容之資料是否為無關項，以供 該緩衝器依據該無關項之一狀態值判斷該總體搜循線之資料是否要傳遞 到該區域搜循線中，該緩衝器並輸出該區域搜循線之一搜尋值；以及 該區域搜循線將該搜尋值傳送出去。 11 ·如申請專利範圍第丨0項所述之利用階層式搜循線搜尋之方法，其中該階 層式搜循線係對應至相同之該區塊中之同一行。 200832408 i2·如申請專利範圍第10項所述之利用階層式搜循線搜尋之方法，其中該區 域搜循線t職簡-行之親域顺_連接朗—該紐搜循線， 在進订每-次搜尋時，欲搜尋之資料先傳遞至該總體搜循線上。 U·如申巧專利範圍第1〇項所述之利用階層賴循線搜尋之方法，其中該緩 衝讀、接魏細麵線無細項之輸人，並輸出麵域搜循線之值。 如申請專利範圍第10項所述之利用階層式搜循線搜尋之方法，其中該無 關項之值係為每-該區塊中存放於該記憶單元最上層之内容。 15·如申,月專利範圍第1〇項所述之利用階層式搜循線搜尋之方法，其中該區 塊中具有最長前置内容之資料係儲存於該記憶單元之底部，而具有最短 前置内容之資料則儲存於該記憶單元之最上層。 16·如申請專利範圍第10項所述之利用階層式搜循線搜尋之方法，其中該無 關項之$亥狀怨值係做為該緩衝器之控制訊號。 17.如申請專利範圍第10項所述之利用階層式麵線搜尋之方法，其中該緩 衝器係為NOR架構。