內容可定址記憶體(Content Addressable Memory, CAM)是一種特殊架構的記憶體，它主要是藉由平行比對的方式去降低資料搜尋時所需的時間。因此，它經常被使用在一些需要快速搜尋的應用當中，像是lookup tables，databases，associative computing，and networking等。雖然採用平行比對的方式可降低搜尋的時間，但同時也增加了功率的消耗。
本論文提出一個名為“區塊邏輯選擇 (Gate-Block Selection)”的演算法。此演算法的最大目的在於可針對特定的資料型態去合成預先計算內容可定址記憶體(Pre-computation-Based CAM, PB-CAM) 內的特徵值擷取器，使其能夠減少在進行資料比對時所需要的次數，進而達到節省功率的目的。此外，本論文亦提出一個新穎的內容可定址記憶體單元 (CAM cell) 的電路設計。此設計的最大特性在於僅有一條輸入位元線，且只需要八顆電晶體即可完成。
我們在台積電0.35μm的製程下，利用Spice去實現整個預先計算內容可定址記憶體設計，並且使用Nanosim去模擬整個系統的功率消耗。實驗結果顯示，在一個容量大小為128×32之內容可定址記憶體下，我們所提出之預先計算內容可定址記憶體和採用“數一 (1's Count)”方式之預先計算內容可定址記憶體相比，可以降低8.99∼27.42％的資料比對次數和節省8.65∼27.84％的功率消耗。藉由實驗結果證明我們所提出之預先計算內容可定址記憶體是較適用於特定方面的應用，例如嵌入式系統等。
本論文的最大貢獻在於提出一“區塊邏輯選擇”演算法去針對特定的資料型態合成一較佳的特徵值擷取器，進而提升預先計算內容可定址記憶體的功率效能。另外，在本論文中，也提出一個新穎的內容可定址記憶體單元的電路設計去改善在“數一”預先計算內容可定址記憶體中所提出之特殊內容可定址記憶體單元的設計缺陷。

Content addressable memory (CAM) is frequently used in many applications, such as lookup tables, databases, associative computing, and networking, that require high-speed searches due to its ability to improve application performance by using parallel comparison to reduce search time. Although the use of parallel comparison results in fast search time, it also significantly increases power consumption.
In this master thesis, a gate-block selection algorithm is presented. The proposed algorithm can synthesize a proper parameter extractor of the pre-computation-based content-addressable memory (PB-CAM) to enhance power efficiency for specific applications. Furthermore, a novel CAM cell design with single bit-line is proposed. The proposed CAM cell design requires only one heavy loading bit-line and merely is constructed with eight transistors.
The whole PB-CAM design was described in Spice in TSMC 0.35μm double-poly quadruple-metal CMOS process. We used Synopsys Nanosim to estimate power consumption. With a 128 words by 32 bits CAM size, the experimental results showed that our proposed PB-CAM effectively reduces 8.99% to 27.42% of comparison operations in the CAM and saves 8.65% to 24.84% in power reduction by synthesizing a proper parameter extractor of the PB-CAM compared with the 1’s count PB-CAM. As a result, it implies that our proposed PB-CAM is more flexible and adaptive for specific applications such as embedded systems.
The major contribution of this master thesis is that it presents a gate-block selection algorithm to synthesize a proper parameter extractor of the PB-CAM for a specific data type and proposes a novel CAM cell design to improve the deficiency of the specific CAM cell design proposed in the 1’s count PB-CAM.

[1] S. Swaminathan, S. B. Patel, J. Dieffenderfer, and J. Silberman, “Reducing power consumption during tlb lookups in a powerpc/spl trade/ embedded processor,” in Proc. Int. Symp. Quality of Electronic Design (ISQED), Mar. 2005, pp. 54–58.
[2] Y. Tang, Y. Jiang, and Y. Wang, “Cam-based label search engine for mpls over atm networks,” in Proc. IEEE Global Telecommunications Conf. (GLOBECOM),
vol. 1, Nov. 2001, pp. 45–49.
[3] R. Sangireddy and A. K. Somani, “High-speed ip routing with binary decision diagrams based hardware address lookup engine,” IEEE J. Selected Areas in Communications, vol. 21, pp. 513–521, May 2003.
[4] K.-J. Lin and C.-W. Wu, “A low-power cam design for lz data compression,”
IEEE Trans. Computers, vol. 49, pp. 1139–1145, Oct. 2000.
[5] 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.
[6] 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, Jun. 2001.
[7] I. Arsovski, T. Chandler, and A. Sheikholeslami, “A ternary content-addressable memory (tcam) based on 4t static storage and including a current-race sensing scheme,” IEEE J. Solid-State Circuits, vol. 38, pp. 155–158, Jan. 2003.
[8] I. Arsovski and A. Sheikholeslami, “A mismatch-dependent power allocation
technique for match-line sensing in content-addressable memories,” IEEE J.
Solid-State Circuits, vol. 38, pp. 1958–1966, Nov. 2003.
[9] F. Shafai, K. J. Schultz, G. F. R. Gibson, A. G. Bluschke, and D. E. Somppi, “Fully parallel 30-mhz, 2.5-mb cam,” IEEE J. Solid-State Circuits, vol. 33, pp. 1690–1696, Nov. 1998.
[10] 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 and
Systems (ISCAS), vol. 4, May 2001, pp. 926–929.
[11] A. Efthymiou and J. D. Garside, “A cam with mixed serial-parallel comparison for use in low energy caches,” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 12, pp. 325–329, Mar. 2004.
[12] A. Efthymiou and J. D. Garside, “An adaptive serial-parallel cam architecture for low-power cache blocks,” in Proc. IEEE Int. Symp. Low Power Electronics and Design (ISLPED), 2002, pp. 136–141.
[13] N. Mohan and M. Sachdev, “Low power dual matchline ternary content addressable memory,” in Proc. IEEE Int. Symp. Circuits and Systems (ISCAS), vol. 2, May 2004, pp. 633–636.
[14] K.-H. Cheng, C.-H. Wei, and S.-Y. Jiang, “Static divided word matching line for low-power content addressable memory design,” in Proc. IEEE Int. Symp. Circuits and Systems (ISCAS), vol. 2, May 2004, pp. 629–632.
[15] A. Roth, D. Foss, R. McKenzie, and D. Perry, “Advanced ternary cam circuits on 0.13 um logic process technology,” in Proc. IEEE Custom Integrated Circuits Conf., Oct. 2004, pp. 465–468.
[16] S. Hanzawa, T. Sakata, K. Kajigaya, R. Takemura, and T. Kawahara, “A largescale and low-power cam architecture featuring a one-hot-spot block code for ip-address lookup in a network router,” IEEE J. Solid-State Circuits, vol. 40, pp. 853–861, Apr. 2005.
[17] S. Hanzawa, T. Sakata, K. Kajigaya, R. Takemura, and T. Kawahara, “A dynamic cam - based on a one-hot-spot block code - for millions-entry lookup,” in Symp. VLSI Circuits Dig. Technical Papers, Jun. 2004, pp. 382–385.
[18] 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.
[19] J.-Y. Hsieh and S.-J. Ruan, “Synthesis and design of parameter extractors for low-power pre-computation-based content-addressable memory using gate-block selection algorithm,” in Proc. ACM/IEEE Asia and South Pacific Design Automation Conf. (ASP-DAC), Jan. 2008, pp. 316–321.
[19] J.-Y. Hsieh and S.-J. Ruan, “Synthesis and design of parameter extractors for low-power pre-computation-based content-addressable memory using gate-block selection algorithm,” in Proc. ACM/IEEE Asia and South Pacific Design Automation Conf. (ASP-DAC), Jan. 2008, pp. 316–321.
[20] S.-J. Ruan, C.-Y. Wu, and J.-Y. Hsieh, “Low power design of precomputationbased content addressable memory,” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 16, no. 3, pp. 331–335, Mar. 2008.
[21] G. Thirugnanam, N. Vijaykrishnan, and M. J. Irwin, “A novel low power cam
design,” in Proc. IEEE Int. ASIC/SOC Conf., Sep. 2001, pp. 198–202.
[22] P.-F. Lin and J. B. Kuo, “A 1-v 128-kb four-way set-associative cmos cache memory using wordline-oriented tag-compare (wlotc) structure with the contentaddressable-memory (cam) 10-transistor tag cell,” IEEE J. Solid-State Circuits, vol. 36, pp. 666–675, Apr. 2001.
[23] S. C. Liu, F. A. Wu, and J. B. Kuo, “A novel low-voltage content-addressablememory (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.
[24] C.-S. Lin, K.-H. Chen, and B.-D. Liu, “Low-power and low-voltage fully parallel content-addressable memory,” in Proc. Int. Symp. Circuits and Systems
(ISCAS), vol. 5, May 2003, pp. 373–376.
[25] K.-H. Cheng, C.-H. Wei, and Y.-W. Chen, “Design of low-power contentaddressable memory cell,” in Proc. IEEE Int. Midwest Symp. Circuits and Systems (MWSCAS), vol. 3, Dec. 2003, pp. 1447–1450.
[26] M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown, “Mibench: A free, commercially representative embedded benchmark
suite,” in Proc. IEEE Int. Workshop on Workload Characterization (WWC), Dec. 2001, pp. 3–14.
[27] P. Echeverria, J. L. Ayala, and M. L.-Vallejo, “A banked precomputation-based cam architecture for low-power storage-demanding applications,” in Proc. IEEE Mediterranean Electrotechnical Conf. (MELECON), May 2006, pp. 57–60.
[28] P. Echeverria, J. L. Ayala, and M. L.-Vallejo, “Leakage energy reduction in banked content addressable memories,” in Proc. IEEE Int.l Conf. Electronics, Circuits and Systems (ICECS), Dec. 2006, pp. 1196–1199.