home : publications : Abstract, Citations & References

Paper

K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (CAM) circuits and architectures: A tutorial and survey,” IEEE Journal of Solid-State Circuits, vol. 41, no. 3, pp. 712–727, March 2006.
This paper made the Journal of Solid-State Circuits List of Most-Read Articles for the first half of 2006.

Abstract

We survey recent developments in the design of large-capacity content-addressable memory (CAM). A CAM is a memory that implements the lookup-table function in a single clock cycle using dedicated comparison circuitry. CAMs are especially popular in network routers for packet forwarding and packet classification, but they are also beneficial in a variety of applications that require high-speed table lookup. The main CAM-design challenge is to reduce power consumption associated with the large amount of parallel active circuitry, without sacrificing speed or memory density. In this paper, we review CAM- design techniques at the circuit level and at the architectural level. At the circuit level, we review low-power matchline sensing techniques and searchline driving approaches. At the architectural level we review three methods for reducing power consumption.

List of Citations of This Paper

  1. H. Jang and H.S. Kim, “Hierarchical broadcast ring architecture for high-speed ethernet networks” in IEEE International Conference on Computer Communications (INFOCOMM), April 2006, pp. 1–5.

  2. N. Azizi and F.N. Najm, “A family of cells to reduce the soft-error-rate in ternary-CAM,” in Design Automation Conference (DAC), July 2006, pp. 779–784.

  3. K. Pagiamtzis, N. Azizi and F.N. Najm, “A soft-error tolerant content-addressable memory (CAM) using an error-correcting-match scheme,” in IEEE Custom Integrated Circuits Conference (CICC), September 2006, pp. 301–372.

  4. A. Agarwal, S.K. Hsu, H. Kaul, M.A. Anders, and R. Krishnamurthy, “A dual-suppy 4GHz 13fJ/bit/search 64x128b CAM in 65nm CMOS,” European Solid-State Circuits Conference, September 2006, pp. 303–306.

  5. H. Lu, K. Zheng, B. Liu, X. Zhang, and Y. Liu, “A memory-efficient parallel string matching architecture for high-speed intrusion detection,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 10, pp 1793–1804, October 2006.

  6. A. Mupid, M. Mutyam, N. Vijaykrishnan, Y. Xie, and M.J. Irwin, “Variation analysis of CAM cells,” in International Symposium on Quality Electronic Design, March 2007, pp. 333–338.

  7. S. Cho, J.R. Martin, R. Xu, M.H. Hammoud, and R. Melhem, “CA-RAM: A high-performance memory substrate for search-intensive applications,” in International Symposium on Performance Analysis of Systems and Software, April 2007, pp. 333–338.

  8. T. Ramdas, G.K. Egan, D. Abramson, and K. Baldridge, “Converting massive TLP to DLP: a special-purpose processor for molecular orbital computations,” in International Conference on Computing Frontiers, May 2007, pp. 267–276.

List of References

  1. T. Kohonen, Content-Addressable Memories, 2nd ed. New Jersey: Springer-Verlag, 1987.

  2. L. Chisvin and R. J. Duckworth, “Content-addressable and associative memory: Alternatives to the ubiquitous RAM,” IEEE Computer, vol. 22, no. 7, pp. 51–64, July 1989.

  3. K. E. Grosspietsch, “Associative processors and memories: A survey,” IEEE Micro, vol. 12, no. 3, pp. 12–19, June 1992.

  4. I. N. Robinson, “Pattern-addressable memory,” IEEE Micro, vol. 12, no. 3, pp. 20–30, June 1992.

  5. S. Stas, “Associative processing with CAMs,” in Northcon/93 Conference Record, 1993, pp. 161–167.

  6. M. Meribout, T. Ogura, and M. Nakanishi, “On using the CAM concept for parametric curve extraction,” IEEE Transactions on Image Processing, vol. 9, no. 12, pp. 2126–2130, December 2000.

  7. M. Nakanishi and T. Ogura, “Real-time CAM-based Hough transform and its performance evaluation,” Machine Vision and Applications, vol. 12, no. 2, pp. 59–68, August 2000.

  8. E. Komoto, T. Homma, and T. Nakamura, “A high-speed and compact-size JPEG Huffman decoder using CAM,” in IEEE Symposium on VLSI Circuits, 1993, pp. 37–38.

  9. L.-Y. Liu, J.-F. Wang, R.-J. Wang, and J.-Y. Lee, “CAM-based VLSI architectures for dynamic Huffman coding,” IEEE Transactions on Consumer Electronics, vol. 40, no. 3, pp. 282–289, August 1994.

  10. B. W. Wei, R. Tarver, J.-S. Kim, and K. Ng, “A single chip Lempel-Ziv data compressor,” in IEEE International Symposium on Circuits and Systems, vol. 3, 1993, pp. 1953–1955.

  11. R.-Y. Yang and C.-Y. Lee, “High-throughput data compressor designs using content addressable memory,” in IEEE International Symposium on Circuits and Systems, vol. 4, 1994, pp. 147–150.

  12. C.-Y. Lee and R.-Y. Yang, “High-throughput data compressor designs using content addressable memory,” IEE Proceedings—Circuits, Devices and Systems, vol. 142, no. 1, pp. 69–73, February 1995.

  13. D. J. Craft, “A fast hardware data compression algorithm and some algorithmic extansions,” IBM Journal of Research and Development, vol. 42, no. 6, pp. 733–745, November 1998.

  14. S. Panchanathan and M. Goldberg, “A content-addressable memory architecture for image coding using vector quantization,” IEEE Transactions on Signal Processing, vol. 39, no. 9, pp. 2066–2078, September 1991.

  15. T.-B. Pei and C. Zukowski, “VLSI implementation of routing tables: tries and CAMs,” in Joint Conference of the IEEE Computer and Communications Societies, INFOCOM, vol. 2, 1991, pp. 515–524.

  16. T.-B. Pei and C. Zukowski, “Putting routing tables in silicon,” IEEE Network Magazine, vol. 6, no. 1, pp 42–50, January 1992.

  17. A. J. McAuley and P. Francis, “Fast routing table lookup using CAMs,” in Proceedings of IEEE Infocom, vol. 3, 1993, pp 1282–1391.

  18. N.-F. Huang, W.-E. Chen, J.-Y. Luo, and J.-M. Chen, “Design of multi-field IPv6 packet classifiers using ternary CAMs,” in IEEE Global Telecommunications Conference, vol. 3, 2001, pp 1877–1881.

  19. G. Qin, S. Ata, I. Oka, and C. Fujiwara, “Effective bit selection methods for improving performance of packet classifications on IP routers,” in IEEE Global Telecommunications Conference, GLOBECOM, vol. 2, 2002, pp. 2350–2354.

  20. H. J. Chao, “Next generation routers,” Proceedings of the IEEE, vol. 90, no. 9, pp 1518–1558, September 2002.

  21. G. Kasai, Y. Takarabe, K. Furumi, and M. Yoneda, “200MHz/200MSPS 3.2W at 1.5V Vdd, 9.4Mbits ternary CAM with new charge injection match detect circuits and bank selection scheme,” in IEEE Custom Integrated Circuits Conference, 2003, pp 387–390.

  22. A. Roth, D. Foss, R. McKenzie, and D. Perry, “Advanced ternary CAM circuits on 0.13 μm logic process technology,” in IEEE Custom Integrated Circuits Conference, 2004, pp 465–468.

  23. T. Yamagato, M. Mihara, T. Hamamoto, Y. Murai, T. Kobayashi, M. Yamada, and H. Ozaki, “A 288-kbit fully parallel content addressable memory using a stacked-capacitor cell structure,” IEEE Journal Solid-State Circuits, vol. 27, no. 12, pp 1927–1933, December 1992.

  24. T. Ogura, M. Nakanishi, T. Baba, Y. Nakabayashi, and R. Kasai, “A 336-kbit content addressable memory for highly parallel image processing,” in IEEE Custom Integrated Circuits Conference, 1996, pp. 273–276.

  25. H. Kadota, J. Miyake, Y. Nishimichi, H. Kudoh, and K. Kagawa, “An 8-kbit content-addressable and reentrant memory,” IEEE Journal Solid-State Circuits, vol. SC-20, no. 5, pp 951–957, October 1985.

  26. K. J. Schultz, F. Shafai, G. F. R. Gibson, A. G. Bluschke, and D. E. Somppi, “Fully parallel 25 MHz, 2.5-Mb CAM,” in IEEE International Solid-State Circuits Conference, 1998, pp 332–333, 458.

  27. V. Lines, A. Ahmed, P. Ma, and S. Ma, “66MHz 2.3M ternary dynamic content addressable memory,” in Records of the 2000 IEEE International Workshop on Memory Technology, Design and Testing, 2000, pp 101–105.

  28. R. Panigrahy and S. Sharma, “Sorting and searching using ternary CAMs,” in Symposium on High Performance Interconnects, 2002, pp. 101–106.

  29. R. Panigrahy and S. Sharma, “Sorting and searching using ternary CAMs,” IEEE Micro, vol. 23, no. 1, pp 44–53, January-February 2003.

  30. H. Noda, K. Inoue, M. Kuroiwa, F. Igaue, K. Yamamoto, H. J. Mattausch, T. Koide, A. Amo, A. Hachisuka, S. Soeda, I. Hayashi, F. Morishita, K. Dosaka, K. Arimoto, K. Fujishima, K. Anami, and T. Yoshihara, “A cost-efficient high-performance dynamic TCAM with pipelined hierarchical search and shift redudancy architecture,” IEEE Journal Solid-State Circuits, vol. 40, no. 1, pp 245–253, January 2005.

  31. S. R. Ramírez-Chávez, “Encoding don't cares in static and dynamic content-addressable memories,” IEEE Transactions on Circuits Systems II, vol. 39, no. 8, pp 575–578, August 1992.

  32. S. Choi, K. Sohn, M.-W. Lee, S. Kim, H.-M. choi, D. Kim, U.-R. Cho, H.-G. Byun, Y.-S. Shin, and H.-J. Yoo, “A 0.7fJ/bit/search, 2.2ns search time hybrid type TCAM architecture,” in IEEE International Solid-State Circuits Conference, 2004, pp 498–499, 542.

  33. S. Choi, K. Sohn, and H.-J. Yoo, “A 0.7fJ/bit/search, 2.2-ns search time hybrid-type TCAM architecture,” IEEE Journal Solid-State Circuits, vol. 40, no. 1, pp 254–260, January 2005.

  34. H. Miyatake, M. Tanaka, and Y. Mori, “A design for high-speed low-power CMOS fully parallel content-addressable memory macros,” IEEE Journal Solid-State Circuits, vol. 36, no. 6, pp 956–968, June 2001.

  35. 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 Journal Solid-State Circuits, vol. 36, no. 4, pp 712–716, April 2001.

  36. G. Thirugnanam, N. Vijaykrishnan, and M. J. Irwin, “A novel low power CAM design,” in 14th Annual IEEE ASIC/SOC Conference, 2001, pp. 198–202.

  37. K. J. Schultz, “Content-addressable memory core cells: A survey,” Integration, the VLSI Journal, vol. 23, no. 2, pp 171–188, November 1997.

  38. 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 International Solid-State Circuits Conference, 2005, pp 464–465, 610.

  39. 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 Journal Solid-State Circuits, vol. 33, no. 11, pp 1690–1696, November 1998.

  40. B. S. Amrutur and M. A. Horowitz, “A replica technique for wordline and sense control in low-power SRAM's,” IEEE Journal Solid-State Circuits, vol. 33, no. 8, pp 1208–1219, August 1998.

  41. M. M. Khellah and M. Elmasry, “Use of charge sharing to reduce energy consumption in wide fan-in gates,” in IEEE International Symposium on Circuits and Systems, vol. 2, 1998, pp 9–12.

  42. 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 Journal Solid-State Circuits, vol. 38, no. 1, pp 155–158, January 2003.

  43. C. A. Zukowski and S.-Y. Wang, “Use of selective precharge for low-power content-addressable memories,” in IEEE International Symposium on Circuits and Systems, vol. 3, 1997, pp 1788–1791.

  44. I. Y.-L. Hsiao, D.-H. Wang, and C.-W. Jen, “Power modeling and low-power design of content addressable memories,” in IEEE International Symposium on Circuits and Systems, vol. 4, 2001, pp 926–929.

  45. A. Efthymiou and J. D. Garside, “An adaptive serial-parallel CAM architecture for low-power cache blocks,” in International Symposium on Low Power Electronics and Design, 2002, pp 136–141.

  46. A. Efthymiou and J. D. Garside, “A CAM with mixed serial-parallel comparison for use in low energy caches,” IEEE Transactions on VLSI Systems, vol. 12, no. 3, pp 325–329, March 2004.

  47. N. Mohan and M. Sachdev, “Low power dual matchline content addressable memory,” in IEEE International Symposium on Circuits and Systems, vol. 2, 2004, pp 633–636.

  48. K.-H. Cheng, C.-H. Wei, and S.-Y. Jiang, “Static divided word matchline line for low-power content addressable memory design,” in IEEE International Symposium on Circuits and Systems, vol. 2, 2004, pp 629–632.

  49. K. Pagiamtzis and A. Sheikholeslami, “Pipelined match-lines and hierarchical search-lines for low-power content-addressable memories,” in IEEE Custom Integrated Circuits Conference, 2003, pp. 383–386.

  50. K. Pagiamtzis and A. Sheikholeslami, “A low-power content-addressable memory (CAM) using pipelined hierarchical search scheme,” IEEE Journal Solid-State Circuits, vol. 39, no. 9, pp 1512–1519, September 2004.

  51. J. M. Hyjazie and C. Wang, “An approach for improving the speed of content addressable memories,” in IEEE International Symposium on Circuits and Systems, vol. 5, 2003, pp 177–180.

  52. I. Arsovski and A. Sheikholeslami, “A current-saving match-line sensing scheme for content-addressable memories,” in IEEE International Solid-State Circuits Conference, 2003, pp 304–305, 494.

  53. I. Arsovski and A. Sheikholeslami, “A mismatch-dependent power allocation technique for match-line sensing in content-addressable memories,” IEEE Journal Solid-State Circuits, vol. 38, no. 11, pp 1958–1966, November 2003.

  54. P.-F. Lin and J. B. Kuo, “A 0.8-V 128-kb four-way set-associative two-level CMOS cache memory using two-stage wordline/bitline-oriented tag-compare (WLOTC/BLOTC) scheme,” IEEE Journal Solid-State Circuits, vol. 37, no. 10, pp 1307–1317, October 2002.

  55. J. M. Rabaey, A. Chandrakasan, and B. Nikolic, Digital Integrated Circuits: A Design Perspective, 2nd ed. New Jersey: Prentice Hall, 2003.

  56. H. Noda, K. Inoue, M. Kuroiwa, A. Amo, A. Hachisuka, H. J. Mattausch, T. Koide, S. Soeda, K. Dosaka, and K. Arimoto, “A 143MHz 1.1W 4.5Mb dynamic TCAM with hierarchical searching and shift redundancy architecture,” in IEEE International Solid-State Circuits Conference, 2004, pp 208–209, 523.

  57. K. J. Schultz and P. G. Gulak, “Architectures for large-capacity CAMs,” Integration, the VLSI Journal, vol. 18, no. 2-3, pp 151–171, June 1995.

  58. M. Motomura, J. Toyoura, K. Hirata, H. Ooka, H. Yamada, and T. Enomoto, “A 1.2-million transistor, 33-MHz, 20-bit dictionary search processor with a 160 kb CAM,” in IEEE International Solid-State Circuits Conference, 1990, pp. 90–91, 271.

  59. M. Motomura, J. Toyoura, K. Hirata, H. Ooka, H. Yamada, and T. Enomoto, “A 1.2-million transistor, 33-MHz, 20-b dictionary search processor (DISP) with a 160-kb CAM,” IEEE Journal Solid-State Circuits, vol. 25, no. 5, pp 1158–1165, October 1990.

  60. K. J. Schultz and P. G. Gulak, “Fully-parallel multi-megabit integrated CAM/RAM design,” in Records of the IEEE International Workshop on Memory Technology, Design and Testing, 1994, pp 46–51.

  61. K. J. Schultz and P. G. Gulak, “Fully parallel integrated CAM/RAM using preclassification to enable large capacities,” IEEE Journal Solid-State Circuits, vol. 31, no. 5, pp 689–699, May 1996.

  62. R. Panigrahy and S. Sharma, “Reducing TCAM power consumption and increasing throughput,” in Symposium on High Performance Interconnects, 2002, pp 107–112.

  63. F. Zane, G. Narlikar, and A. Basu, “CoolCAMs: Power-efficient TCAMs for forwarding engines,” in IEEE INFOCOM, vol. 1, 2003, pp 42–52.

  64. C.-S. Lin, J.-C. Chang, and B.-D. Liu, “Design for low-power, low-cost, and high-reliability precomputation-based content-addressable memory,” in

  65. C.-S. Lin, J.-C. Chang, and B.-D. Liu, “A low-power precomputation-based fully parallel content-addressable memory,” IEEE Journal Solid-State Circuits, vol. 38, no. 4, pp. 654–662, April 2003.

  66. 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 IEEE Symposium on VLSI Circuits, 2004, pp 382–385.

  67. S. Hanzawa, T. Sakata, K. Kajigaya, R. Takemura, and T. Kawahara, “A large-scale and low-power CAM architecture featuring a one-hot-spot block code for IP-address lookup in a network router,” IEEE Journal Solid-State Circuits, vol. 40, no. 4, pp 853–861, April 2005.

  68. H. Liu, “Efficient mapping of range classifier into ternary-CAM,” in Symposium on High Performance Interconnects, 2002, pp. 95–100.

  69. H. Liu, “Routing table compaction in ternary cam,” IEEE Micro, vol. 22, no. 1, pp 58–64, January-February 2002.

  70. V. Ravikumar and R. N. Mahapatra, “TCAM architecture for IP lookup using prefix properties,” IEEE Micro, vol. 24, no. 2, pp 60–69, Mar-Apr 2004.

  71. A. Sheikholeslami and P. G. Gulak, “A survey of circuit innovations in ferroelectric random-access memories,” Proceedings of the IEEE, vol. 88, no. 5, pp 677–689, May 2000.

  72. S. Tehrani, J. M. Slaughter, M. DeHerrera, B. N. Engel, N. D. Rizzo, J. Salter, M. Durlam, R. W. Dave, J. Janesky, B. Butcher, K. Smith, and G. Grynkewich, “Magnetoresistive random access memory using magnetic tunnel junctions,” Proceedings of the IEEE, vol. 91, no. 5, pp 703–714, May 2003.

  73. K. Kim and G. Jeong, “Memory technologies in the nano-era: challenges and opportunities,” in IEEE International Solid-State Circuits Conference, 2005, pp. 576–577, 618.