Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Row-Accessed Content Addressable Memory

IP.com Disclosure Number: IPCOM000115305D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 146K

Publishing Venue

IBM

Related People

Rice, DG: AUTHOR

Abstract

There is a need for high-performance, low-cost Content Addressable Memory (CAM) for use in applications such as pattern matching, database search, and dataflow token matching. Current CAM implementations are costly due to the additional circuitry required to implement an associative comparator function for the data in each cell of the CAM array. The proposed approach reduces the amount of this circuitry by providing the comparator function on a per row basis rather than a per cell basis. The approach allows parallel search of the desired data, and reports matches as they occur. However, the search is conducted on each row of the CAM array in a sequential fashion, although all cells in each row are tested in parallel.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Row-Accessed Content Addressable Memory

      There is a need for high-performance, low-cost Content
Addressable Memory (CAM) for use in applications such as pattern
matching, database search, and dataflow token matching.  Current CAM
implementations are costly due to the additional circuitry required
to implement an associative comparator function for the data in each
cell of the CAM array.  The proposed approach reduces the amount of
this circuitry by providing the comparator function on a per row
basis rather than a per cell basis.  The approach allows parallel
search of the desired data, and reports matches as they occur.
However, the search is conducted on each row of the CAM array in a
sequential fashion, although all cells in each row are tested in
parallel.  This compromise between performance and area may be
advantageous for certain applications where the performance of a CAM
is required, yet a full CAM implementation is impractical due to size
or cost constraints.

      Content Addressable Memory (CAM) allows parallel searching of
the data contained within a bank of memory cells to determine matches
against a provided search string, or "tag".  CAMs are useful in
designing high-performance associative memories for pattern matching,
database searching, and dataflow token matching functions.  CAMs are
also very expensive.  This expense is due to the added circuitry
required to perform comparison of each memory bit with the
corresponding search tag bit.  This comparator function (XNOR) adds
several transistors to each memory cell, which can increase the size
of the memory array by 50% or more.  In addition, CAMs which are
implemented as chips are I/O limited, since the "match" signal for
each set of cells (word) which is compared against the search tag
should be readable.  It is difficult to encode these match signals
because there may be multiple matches per search attempt which must
be identified.

      With the advent of chip technology which include logic gate
array cells and standard Random Access Memory (RAM) macros within the
same chip, the problems of added transistors per CAM cell and large
number of required I/O pins can be avoided.

      This CAM implementation is based on a standard RAM macro and
additional logic within the logic gate array portion of the chip.
The outputs of this CAM are then available to additional logic
functions which are created within the chip as well.  These
additional functions may include a microprocessor, for example.

      The RAM macro is used to contain the data to be searched.  In
normal operation the RAM macro will output a data word of length "k"
based on a memory address.  The RAM consist of an "m"x"n" array of
memory cells.  The "m" cells, or bits, in each row are broken into a
set of "m/k" columns of length "k".  These "k" bits form the word
which will be read when for a given address.

      The address to the RAM is broken into a row address an...