Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-11-09
2003-02-25
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S158000
Reexamination Certificate
active
06526474
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a CAM with dynamic sequential multiple access sizes.
2. Related Art
A CAM (content addressable memory) is sometimes used in a computer system or device for storing and retrieving information. CAMs have the advantage that they can rapidly link associated data values with known tags; it is thus possible to perform rapid lookup of the associated data values once the tag is known. Known CAMs include comparison circuits for matching an input tag with each tag recorded in the CAM, so as to determine which if any of the elements in the CAM matches the tag.
One problem in the known art is that the comparison circuits in known CAMs operate so as to match the input tag with a fixed array of value bits. Thus, the input tag and the value array are both a fixed width that cannot be changed once the CAM is manufactured. (In some known CAMs, there is more than one different width, but that width is only selectable at a configuration time, or using a configuration pin.) This problem significantly reduces the flexibility and utility of CAMs, particularly when the input tags are contemplated as being of variable size. This problem also reduces the utility of CAMs in many systems, in that when CAM is manufactured to accommodate for the largest possible input tag, the CAM might either (a) have less capacity than required by the particular application, or (b) have significant unused capacity.
Accordingly, it would be desirable to provide a method and system for operating a CAM with a variable size input tag. This advantage is achieved in an embodiment of the invention in which a CAM has multiple access sizes, each of which can be accessed dynamically, even for sequential accesses to the CAM.
SUMMARY OF THE INVENTION
The invention provides a method and system for operating a CAM with a dynamically variable size input tag. The improved CAM has multiple access sizes, dynamically selectable by sequences of successive accesses to the CAM. A size selection circuit accumulates the independent match results. The size selection circuit logic determines which CAM entries are matched for each possible width of request value the CAM was designed for. For example, the size selection circuit can determine whether a selected 72-bit request matches a single CAM entry in one of the two CAM arrays. A priority encoder coupled to the size selection circuit collects the accumulated matches and presents a match as an output from the CAM.
In a preferred embodiment, each CAM entry can be selected from a set of preselected sizes, each corresponding to a contemplated input tag size, such as 72 bits, 144 bits, or 288 bits.
REFERENCES:
patent: 3648254 (1972-03-01), Beausoleil
patent: 4296475 (1981-10-01), Nederlof et al.
patent: 4791606 (1988-12-01), Threewitt et al.
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5088032 (1992-02-01), Bosack
patent: 5319763 (1994-06-01), Ho et al.
patent: 5383146 (1995-01-01), Threewitt
patent: 5440715 (1995-08-01), Wyland
patent: 5450351 (1995-09-01), Heddes
patent: 5481540 (1996-01-01), Huang
patent: 5515370 (1996-05-01), Rau
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5841874 (1998-11-01), Kempke et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5898689 (1999-04-01), Kumar et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5956336 (1999-09-01), Loschke et al.
patent: 5978885 (1999-11-01), Clark, II
patent: 6000008 (1999-12-01), Simcoe
patent: 6041389 (2000-03-01), Rao
patent: 6047369 (2000-04-01), Colwell et al.
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6069573 (2000-05-01), Clark, II et al.
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6097724 (2000-08-01), Kartalopoulos
patent: 6134135 (2000-10-01), Andersson
patent: 6137707 (2000-10-01), Srinivasan et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6154384 (2000-11-01), Nataraj et al.
patent: 6175513 (2001-01-01), Khanna
patent: 6181698 (2001-01-01), Hariguchi
patent: 6199140 (2001-03-01), Srinivasan et al.
patent: 6236658 (2001-05-01), Essbaum et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6240003 (2001-05-01), McElroy
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6246601 (2001-06-01), Pereira
patent: 6295576 (2001-09-01), Ogura et al.
patent: 6307855 (2001-10-01), Hariguchi
patent: 6374326 (2002-04-01), Kansal et al.
patent: 6389506 (2002-05-01), Ross et al.
Jon P. Wade and Charles G. Sodini; “A Ternary Content Addressable Search Engine,” Aug. 1989; pp. 1003-1013; IEEE Journal of Solid-State Circuits, vol. 24, No. 4.
Teuvo Kohonen, Content-Addressable Memories, 1987, pp. 128-129 and 142-144, Springer-Verlang, New York.
Brian Dipert, ed., “Special-purpose SRAMs Smooth the Ride,” EDN, Jun. 24, 1999, pp. 93-104.
“Extending the LANCAM Comparand,” Application Brief AB-N3, Rev. 1.0a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Advantages of CAM in ASIC-Based Network Address Processing,” Application Brief AB-N11, Rev. 1.2a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Virtual Memory Applications of the MU9C1480A LANCAM,” Application Note AN-N3, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 12 pages.
“Using the MU9C1965A LANCAM MP for Data Wider than 128 Bits,” Application Note AN-N19, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 16 pages.
“Fast IPv4 and IPv4 CIDR Address Translation and Filtering Using the MUAC Routing CoProcessor (RCP),” Application Note AN-N25, Rev. 0a, Music Semiconductors, Milpitas, CA, Oct. 1, 1998, 16 pages.
“Using MUSIC Devices and RCPs for IP Flow Recognition,” Application Note AN-N27, Rev. 0, Music Semiconductors, Milpitas, CA, Oct. 21, 1998, 20 pages.
“Wide Ternary Searches Using Music CAMs and RCPs,” Application Note AN-N31, Rev. 0, Music Semiconductors, Milpitas, CA, Apr. 13, 1999, 8 pages.
Bragdon Reginald G.
Cisco Technology Inc.
The Law Office of Kirk D. Williams
LandOfFree
Content addressable memory (CAM) with accesses to multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content addressable memory (CAM) with accesses to multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory (CAM) with accesses to multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121315