成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	蔡睿哲 Tsai, Ruei-Jhe
論文名稱：	低功率內容可定址記憶體設計及其在網路路由器之應用 Design of Low-Power Content-Addressable Memory and Its Application in Network Routers
指導教授：	劉濱達 Liu, Bin-Da
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2007
畢業學年度：	95
語文別：	英文
論文頁數：	82
中文關鍵詞：	內容可定址記憶體、最長字首比對、路由器
外文關鍵詞：	Router, Longest Prefix Matching (LPM), Content-Addressable Memory (CAM)
相關次數：	點閱：99 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本論文提出兩種新穎的電路架構以實現高速度及低功率之內容可定址記憶體設計，這兩種電路架構分別為：1. 分離搜尋線架構之三元內容可定址記憶體單元電路及 2.利用遮罩訊號特性之局部搜尋線分離技術。此外，本論文並提出另一種新的高速度及低成本之最長字首比對機制。
為了改善字組線的效能，我們採用一種靜態虛擬-互補式金氧半邏輯字組電路，與所提出的兩種電路架構結合。由模擬結果可得知，採用所提出的三元內容可定址記憶體單元，以一個64 × 64之三元內容可定址記憶體在TSMC 0.13 um和1.2 V的條件下，與單一位元線架構之電路相較，可分別改善66 %及45 %之功率消耗及搜尋速度。而在內容大小為256 × 128之內容可定址記憶體中，若進一步利用遮罩訊號特性之局部搜尋線分離技術，更可在拿掉112條資料搜尋線的情況下，改善22.19 %的功耗速度乘積值。此外，本論文亦提出一個額外的自我測試機制，以更客觀的量得待測電路的搜尋速度。
所提出以內容可定址記憶體及贏者通吃電路為基礎之最長字首比對電路，由晶片量測結果得知，在128 × 32之容量，0.18 um製程及1.8 V的情況下，可達到160 MSearch/s之路由速度及10.8 mW之功率消耗。符合高速的OC-3072 (160 Gb/s) 百億位元乙太網路傳輸需求。此外，也可將所提出之最長字首比對電路調整成其他尺寸，以符合如IPv6不同規格的需求。

This thesis presents two novel VLSI architectures for high-speed and low-power fully parallel CAM design. These two proposed architectures are 1) eleven transistors – ternary CAM (11T-TCAM) cell with separated searchline and 2) mask-based local searchline (MBLS) approach. Moreover, a novel high-speed, and low-cost longest prefix matching (LPM) search engine which combined with the concepts of CAM and winner-take-all mechanism (WTA), was also developed in this thesis.
In order to improve the word matchline performance, a static pseudo-CMOS logic TCAM (PC-TCAM) word matchline scheme is adopted to combine with two proposed architectures. The simulation results show that a 64 × 64 PC-TCAM with proposed 11T-TCAM cell reduces 66% power dissipation and improves 45% searching speed compared with the single bitline TCAM cell. And the power-delay-product (PDP) value is further improved 22.19 % in 256 × 128 PC-TCAM, when 112 number of global searchline were taken off by MBLS approach, with TSMC 0.13 um process at 1.2 V. Moreover, an extra BIST mechanism is also presented to measure the searching speed more objectively.
The chip measurement results of the proposed 128 × 32CAM/WTA-based LPM (CW-LPM) search engine achieves 160 MSearch/s routing speed with 10.8 mW power dissipation, based on a 0.18 um 1.8 V process. It meets the requirement of high-speed OC-3072 multi-gigabit/s Ethernet network. In addition, the chip configuration of the proposed CW-LPM can be adjusted to meets other requirements, such as IPv6 protocol.

Table of Contents	i
List of Figures	iv 
List of Tables	vii

Chapter 1 Introduction　　　　　　　　　　1
1 Comparison between RAM and CAM　　　　1 
2 Applications of CAM　　　　　　　　　　3
3 Research Motivation　　　　　　　　　　3
4 Organization of The Thesis　　　　　　5
Chapter 2 CAM Circuits and Architectures　6 
1 CAM Architecture　　　　　　　　　　　6 
2 CAM Cells　　　　　　　　　　　　　　　8
2.1 Cell Basics　　　　　　　　　　　　　9
2.2 Cell Variants　　　　　　　　　　　　11
2.3 Ternary-CAM Cell　　　　　　　　　　14
3 Matchline Schemes　　　　　　　　　　　16
3.1 Conventional Matchline Schemes　　　16
3.2 Precomputation-Based CAM Approach　　19
3.3 AND-Type Matchline Scheme　　　　　　21
4 Low Power Design Consideration　　　　23
4.1 Power Modeling of CAM	　　　　　　　　23
4.2 Static Circuit Design Approach	　　　24
4.3 Searchline Driving Approach　　　　　25
5 Summary　　　　　　　　　　　　　　　　26
Chapter 3 Proposed Low Power CAM Circuit with Mask-Based Local Searchline Scheme　　　　　　　　　　　　　　　　　　　　　　27
1 Introduction of Pseudo-CMOS Logic　　　　　　27
2 Pseudo-CMOS TCAM (PC-TCAM) Circuit Design　　32
2.1 PC-TCAM Architecture　　　　　　　　　　　　32
2.2 PC-TCAM Matchline Scheme　　　　　　　　　　33
2.3 PC-TCAM Cell Circuit　　　　　　　　　　　　35
3 Mask-Based Local Searchline (MBLS) Approach　39
3.1 The Concepts of Searchline Reduction　　　　39
3.2 Proposed MBLS Approach　　　　　　　　　　　42
4 Circuit Implementation and Simulation Results　44
4.1 The Hierarchical Structure of Proposed CAM　44
4.2 Simulation Results　　　　　　　　　　　　　46
5 Summary　　　　　　　　　　　　　　　　　　　　52
Chapter 4 Applacation on Longest Prefix Matching (LPM)　53
1 Introduction of LPM　　　　　　　　　　　　　　　　53
2 Proposed CAM / WTA-Based LPM (CW-LPM) Architecture	57
2.1 Winner-Take-All / Maximun (WTA / MAX) Mechanism	57
2.2 System Flows of Proposed CW-LPM Search Engine	60
3 Simulation and Measurement Results　　　　　　　　62
3.1 Simulation Results　　　　　　　　　　　　　　　　62
3.2 Chip Implementation and Layout Considerations	65
3.3 Measurement Results　　　　　　　　　　　　　　　69
4 Summary　　　　　　　　　　　　　　　　　　　　　　73
Chapter 5 Conclusions and Future Work　　　　　　　　　74
1 Conclusions　　　　　　　　　　　　　　　　　　　　74
2 Future Work　　　　　　　　　　　　　　　　　　　　76
References 　　　　　　　　　　　　　　　　　　　　　　77
Publications　　　　　　　　　　　　　　　　　　　　　82

                                    

[1] T. Jamil, “RAM versus CAM,” IEEE Potentials, vol. 16, pp. 26-29, Apr.-May, 1997.
[2] S. V. Kartalopoulos, “An associative RAM-based CAM and its application to broad-band communications systems,” IEEE Trans. Neural Networks, vol. 9, pp. 1036-1041, Sep. 1998.
[3] K. J. Lin, C. W. Wu, and S. Member, “A low-power CAM design for LZ data compression,” IEEE Trans. Comput., vol. 49, pp. 1139-1145, Oct. 2000.
[4] T. Ikenaga and T. Ogura, “A fully-parallel 1 Mb CAM LSI for real-time pixel-parallel image processing,” IEEE J. Solid-State Circuits, vol. 35, pp. 536-544, Apr. 2000.
[5] A. Efthymiou and J. D. Garside, “A CAM with mixed serial-parallel comparison for use in low energy caches,” IEEE Trans. VLSI Syst., vol. 12, pp. 325-329, Mar. 2004.
[6] M. Meribout, T. Ogura, and M. Nakanishi, “On using the CAM concept for parametric curve extraction,” IEEE Trans. Image Processing, vol. 9, pp.2126-2130, Dec. 2000.
[7] M. Sumita, “A 800 MHz single cycle access 32 entry fully associative TLB with a 240 ps access match circuit,” in Proc. Symp. VLSI Circuits Dig. Tech. Papers, June 2001, pp. 231-232.
[8] J. H. Lee, G. H. Park, S. B. Park, and S. D. Kim, “A selective filter-bank TLB system [embedded processor MMU for low power],” in Proc. Int. Symp. Low Power Electron. Design, Aug. 2003, pp. 312-317.
[9] Z. Liang, J. Wu, and K. Xu, “A TCAM-based IP lookup scheme for multi-nexthop routing,” in Proc. Int. Comput. Networks Mobile Comput., Oct. 2003, pp. 128-135.
[10] F. Zane, N. Girija, and A. Basu, “Coolcams: power-efficient TCAMs for forwarding engines,” in Proc. IEEE INFOCOM’03, Mar. 2003, vol. 1, pp. 42-52.
[11] T. Matsuda and K. Matsuda, “A new protocol processing architecture for high-speed networks,” in Proc. IEEE Global Telecommun. Conf., Nov. 1996, pp. 798-803.
[12] S. V. Kartalopoulos, “Associative RAM-based CAM applicable to packet-based broadband systems,” in Proc. IEEE Global Telecommun. Conf., Nov. 1998, pp. 2888-2891.
[13] K. J. Schultz and P. G. Gulak, “CAM-based single-chip shared buffer ATM switch,” in Proc. IEEE Int. Conf. Commun., May 1994, pp. 1190-1195.
[14] C. S. Lin and B. D. Liu, “Design of a shared buffer management scheme for ATM switches,” in Proc. 15th Annual IEEE Int. ASIC/SOC, Sept. 2002, pp. 261-264.
[15] R. J. Tsai, H. W. Ting, C. S. Lin, and B. D. Liu, “A CAM/WTA-based high speed and low power longest prefix matching circuit design,” in Proc. IEEE Asia-Pacific Conf. Circuits and Syst., Dec. 2006, pp. 427-430.
[16] H. Miyatake, M. Tanaka, and Y. Mori, “A design for high-speed low-power CMOS fully parallel content-addressable memory macros,” IEEE J. Solid-State Circuits, vol. 36, pp. 956-968, June 2001.
[17] K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (CAM) circuits and architectures: a tutorial and survey,” IEEE J. Solid-State Circuits, vol. 41, pp.712-727, Mar. 2006.
[18] C. A. Zukowski and S. Y. Wang, “Use of selective precharge for low-power content-addressable memories,” in Proc. IEEE Int. Symp. Circuits Syst., June 1997, vol. 3, pp. 1788-1791.
[19] G. Thirugnanam, N. Vijaykrishnan, and M. J. Irwin, “A novel low power CAM designs,” in Proc. IEEE Int. ASIC/SOC Conf., Sep. 2001, pp. 198-202.
[20] S. Liu, F. Wu, and J. B. Kuo, “A novel low-voltage content-addressable memory (CAM) cell with a fast tag-compare capability using partially depleted (PD) SOI CMOS dynamic-threshold (DTMOS) techniques,” IEEE J. Solid-State Circuits, vol. 36, pp. 712-716, Apr. 2001.
[21] K. J. Schultz, “Content-addressable memory core cells: A survey,” Integration, the VLSI Journal, vol. 23, pp. 171-188, 1997.
[22] T. Yamagata, M. Mihara, T. Hamamoto, T. Kobayashi, and M. Yamada, “A 288-kbit fully parallel content addressable memory using stacked capacitor cell structure,” in Proc. IEEE Cust. Int. Circuits Conf., May 1991, pp. 10.3.1-10.3.4.
[23] N. H. E. Weste and K. Eshraghian, Principles of CMOS VLSI Design: A Systems Perspective. Reading, MA: Addison-Wesley, 2nd edition, 1993.
[24] J. Rabaey, A. Chandrakasan, and B. Nikolic, Digital Integrated Circuits: A Design Perspective, 2nd Edition, Eaglewood Cliffs, NJ: Prentice Hall, 2003.
[25] C. S. Lin, “Design of low-power fully parallel content-adressable memories,” Ph.D. dissertation, National Cheng Kung University, Tainan, Taiwan, June 2004.
[26] K. H. Cheng, C. H. Wei, and S. Y. Jiang, “Static divided word matchline line for low-power content addressable memory design,” in Proc. IEEE Int. Symp. Circuits Syst., vol. 2, May 2004, pp. 629-632.
[27] C. S. Lin, J. C. Chang, and B. D. Liu, “A low-power precomputation-based fully parallel content-addressable memory,” IEEE J. Solid-State Circuits, vol. 38, pp. 654-662, Apr. 2003.
[28] J. S. Wang, H. Y. Li, C. C. Chen, and C. Yeh, “An AND type match-line scheme for energy efficient content addressable memories,” in IEEE Int. Solid-State Circuits Conf. Dig. Tech. Papers, 2005, pp. 464-465.
[29] I. Y. L. Hsiao, D. H. Wang, and C. W. Jen, “Power modeling and low-power design of content addressable memories,” in Proc. IEEE Int. Symp. Circuits Syst., vol. 4, 2001, pp. 926-929.
[30] C. S. Lin, K. H. Chen, and B. D. Liu, “Low-power and low-voltage fully parallel content-addressable memory,” in Proc. IEEE Int. Symp. Circuits Syst., May 2003, vol. 5, pp. 373-376.
[31] J. M. Wang, S. C. Fang, and W. S. Feng, “New efficient designs for XOR and XNOR functions on the transistor level,” IEEE J. Solid-State Circuits, vol. 29, pp. 780-786, July 1994.
[32] K. Pagiamtzis and A. Sheikholeslami, “A low-power content-addressable memory (CAM) using pipelined hierarchical search scheme,” IEEE J. Solid-State Circuits, vol. 39, pp. 1512-1519, Sep. 2004.
[33] J. S. Wang, C. C. Wang, and C. Yeh, “TCAM for IP-address lookup using tree-style AND-type match lines and segmented search lines,” in IEEE Int. Solid-State Circuits Conf. Dig. Tech. Papers, 2006, pp. 577-586.
[34] S. Choi, K. Sohn, and H. J. Yoo, “A 0.7 fJ/bit/search, 2.2-ns search time hybrid-type TCAM architecture,” IEEE J. Solid-State Circuits, vol. 40, pp. 254-260, Jan. 2005.
[35] M. A. Ruiz-Sanchez, E. Biersack, and W. Dabbous, “Survey and taxonomy of IP address lookup algorithms,” IEEE Network, vol. 15, pp. 8-23, Mar./Apr. 2001.
[36] P. C. Wang, C. T. Chan, S. C. Hu, Y. C. Shin, and Y. C. Chen, “Hardware-based IP routing lookup with incremental update,” in Proc. Int. Conf. Parallel Distributed Syst., Dec. 2003, pp. 183-188.
[37] M. Kobayashi, T. Murase, and A. Kuriyama, “A longest prefix match search engine for multi-gigabit IP processing,” in Proc. IEEE Int. Conf. Commu., June 2000, vol. 3, pp. 1360-1364.
[38] A. J. McAuley and P. Francis, “Fast routing table lookup using CAMs,” in Proc. IEEE INFOCOM, Mar. 1993, vol. 3, pp. 1382-1391.
[39] S. Kasnavi, V. C. Gaudet, P. Berube, and J. N. Amaral, “A hardware-based longest prefix matching scheme for TCAMs,” in Proc. IEEE Int. Symp. Circuits Syst., vol. 4, May 2005, pp. 3339-3342.
[40] S. H. Ou, C. S. Lin, and B. D. Liu, “A scalable sorting architecture based on maskable WTA/MAX circuit,” in Proc. IEEE Int. Symp. Circuits Syst., May 2002, pp. 209-212.
[41] R. Sangireddy, and A. K. Somani, “High-speed IP routing with binary decision diagrams based hardware address lookup engine,” IEEE J. Select. Areas Commun., vol. 21, pp. 513-521, May 2003.

校內：2008-01-29公開
校外：2009-01-29公開

簡易檢索 / 詳目顯示

相關論文