CAM implementation using Dual port ram

Hi,

I am going through a xilinx app note. The basic CAM that is shown is a

32X9 capacity. The total memory capacity used up to implement this is 16kb. I am wondering if the idea is to generate just a match or no_match then just a 512 bit single bit memory array would do the job. Where the array is accessed (both for configure and search) using the 9-bit data instead of address and if the resultant data is 1 then there is a match. Am I missing something? Maybe the application note is more suitable when the size of match data increases to 20 bits or more. Probably it is useful when just more than match or no_match is required (probably a vector output instead of just match or no_match) I am just curious.

Regards

OK, that makes sense. 9-bit data means 512 different data values. For each of those data values you store a 32-bit word, with each bit of the word specifying whether that data word is to be found in one of the 32 locations. Expensive, but *very* fast.

OK. Let's suppose you do that, and (say) write the value 0 to some location in the CAM. At the same time you write 1 to "match" entry 0, to say that a 0 value is present somewhere.

Now let's write 0 to a *second* location. What do we do now? Oh yes, write '1' to match entry 0.

Now let's change the second location's data from 0 to something else. We read the location first, discover its old contents were 0, so we go to match location 0 and .... oops, we clear it to show that there's no longer a match.... but we're wrong, because there *is* still a match, at the first location that had 0 written to it.

I don't think there is any way to fix this if you have only one match bit per data value - unless you somehow have a guarantee that data values in the CAM are unique.

You could get away with each match location containing a COUNT of the number of entries holding that data value; in that case you would need only 6 bits per location, not 32. But that would still leave you with a different problem: if you discover that there is a match, you still don't know *where* that match is. In all applications of CAM that I've come across, that where-is-it information is an essential part of what you're trying to do.

-- Jonathan Bromley, Consultant DOULOS - Developing Design Know-how VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK jonathan.bromley@MYCOMPANY.com http://www.MYCOMPANY.com The contents of this message may contain personal views which are not the views of Doulos Ltd., unless specifically stated.