Data Structures to be used for a TCAM

SystemVerilog
, , , ,
1

Hi

I have a TCAM (ternary Content Adressible memory) and Id like to see what data structures I can use to describe it.

For simplicity lets say I have data[31:0] and addr[31:0] and mask[31:0].

I need to be able to query the address based on the data(so I guess we can use an associative array).

but since we also need to use the mask where if the mask bit is set then the corresponding addr bit is checked else it is a don’t care.

e.g.
data[31:0] = 0x0000_ABCD
addr[31:0] = 0xCAFE_CAFE
mask[31:0] = 0x0000_FFFF

Now a query for data[31:0] = 0x???_ABCD should return 0xCAFE_CAFE where ? represents 0,1,X (since mask is 0 for msb 16 bits)

I thought of using an assoc array like this

I saw an example in this post below where u have used an assoc array as shown below.
(Multi-dimensional arrays | Verification Academy)

but im not sure if that is the right way to go about for this problem.

Thanks for the help

Pranav

2

In reply to pranavsamsung:

I am not sure I understood your question right or not but I assume you have 3 variables of 32 bits each and you want to know which is best way to handle that without taking multiple arrays ?

You can think of single associative array with one of the variable being it’s key(Index) and storage of 64 bit data. You can concatenation remaining 2 variables as single location data.

For example:
bit [63:0] addr_n_mask[int]; // Here Index is address and data_n_mask[63:32] is addr, data_n_mask[31:0] is mask

3 


// I think you want to query address based on {data & mask}. 
// and I assume returning address might be greater than 1
// using associative array : 
// - key_index is "data & mask" 
// - item is "32-bit queue" to represent multiple address items      
// associative array cost is fairly huge ... be careful

    typedef struct packed {
      bit [31:0] data;
      bit [31:0] mask;
    } data_s;

            data_s mem[];
            bit [31:0] lookup_table [bit[31:0]][$]

            xmem = new[10];
            // preparing memory
            for (int i = 0; i < mem.size(); i++) begin
                mem[i].data = $urandom_range(0,5);
                mem[i].mask = '1;
            end
            // preparing lookup table
            for (int j = 0; j < mem.size(); j++) begin
                key = mem[j].data & mem[j].mask;
                if (lookup_tbl.exists(key)) begin
                    lookup_tbl[key].push_back(j); 
                end 
                else begin
                    addr_q = {j};
                    lookup_tbl[key] = addr_q;
                end
            end