Hash Table

[prasunp]

Hello:

My question is regarding Hash tables. How would one model a hash table
in verilog? Use memory and what about the hashing function? Any
Ideas... I'm just curious to what people think.

Thank You,
Prasun

 

[Jeremy Ralph]

What kind of values would be the input to your hashing function? For
synthesizable code you would have to constrain the maximum size of the
memory/hash. The hash function would just convert a string (or
whatever you are hashing) into a memory address (i.e. your unique key)
where your value is stored.

For synthesisable RTL code it's likely best to keep things simple and
just stick with memories (or arrays of registers) and addresses. For
verification I could see a behavioural hashtable being useful, this
should be easy enough to implement in SystemVerilog using object
orientation features.

Jeremy
---
PDTi [ http://www.productive-eda.com ]
SpectaReg -- Spec-down code and doc generation for register maps

 

[prasunp]

Thank You Jeremy,
The inputs are two 8bit numbers. Since SystemVerilog has been brought
up, any recommendations for decent references, websites or books for
SystemVerilog. Originally,
I was going to code my hash table in C and use it as a PLI function.
But I started wondering...Why not make it actual hardware.

Once again, Thank you for your input. anyone else?

-Prasun

 

[Ron]

prasunp wrote:

The inputs are two 8bit numbers. ... Originally,
I was going to code my hash table in C and use it as a PLI function.
But I started wondering...Why not make it actual hardware.

Once again, Thank you for your input. anyone else?

Sure Prasun, I don't see any problems with that. Just code it up in
Verilog instead of C. Probably the RAM interface will be the most
difficult part. You mentioned that the inputs are two 8 bit numbers.
That puzzles me because I've typically used hash tables to contain
strings or a non-trivial amount of data. If your data is only eight bits
wide why not just use a directly addressable array rather than a hash table.

As for hash functions, I've found that simple ones such as the hash
function shown in the K&R C Whitebook work almost as well as anything
else, but it depends somewhat upon your data.

Ron

 

[prasunp]

Thanks Ron,

Well, I guess I should expand on my problem description. I am working
on a TCP packet parser and associating the Source Port and Destination
port to a ID number. Hence my two options: Code a Hash Table in C and
use PLI or try to actually use specialized hardware (memory). The
ports could be numbers or strings, I guess.

Thanks
Prasun

 

[Jeremy Ralph]

So would there be 2^16 possible ID numbers? If so why not just
concatenate the source and destination port to get at 16 bit ID number.
Then interface to some ram(s) and devise an addressing scheme that
uses the 16 bit ID.

For example, say you wanted to store 1K addresses of data (tailor data
width to your application) for each source/dest association, then your
addressing scheme could be:

parameter SOURCE_DEST_BLOCK_ADDR_BITS = 10;
parameter SOURCE_ADDR_BITS = 8;
parameter DEST_ADDR_BITS = 8;
....
input [SOURCE_ADDR_BITS-1:0] source;
input [DEST_ADDR_BITS-1:0] dest;
input [SOURCE_DEST_BLOCK_ADDR_BITS-1:0] data_index;
....
assign source_dest_id = {source,dest}; //concatenate
assign method1_table_addr = {data_index, source_dest_id};
assign method2_table_addr = {source_dest_id, data_index};

If you want to access more than one source_dest_id concurrently you'll
need more than one mem or multi-port memories. The choice between
addressing method1 and method2 might affect power consumption.