FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > Verilog

Verilog comp.lang.verilog newsgroup / usenet

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 05-06-2006, 07:14 AM
prasunp
Guest
 
Posts: n/a
Default Hash Table

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

Reply With Quote
  #2 (permalink)  
Old 05-06-2006, 07:36 PM
Jeremy Ralph
Guest
 
Posts: n/a
Default Re: Hash Table

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

Reply With Quote
  #3 (permalink)  
Old 05-06-2006, 08:13 PM
prasunp
Guest
 
Posts: n/a
Default Re: Hash Table

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

Reply With Quote
  #4 (permalink)  
Old 05-06-2006, 11:04 PM
Ron
Guest
 
Posts: n/a
Default Re: Hash Table

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
Reply With Quote
  #5 (permalink)  
Old 05-07-2006, 08:14 AM
prasunp
Guest
 
Posts: n/a
Default Re: Hash Table

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

Reply With Quote
  #6 (permalink)  
Old 05-07-2006, 09:17 PM
Jeremy Ralph
Guest
 
Posts: n/a
Default Re: Hash Table

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.

Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
implementing a lookup table [email protected] Verilog 4 04-19-2006 04:44 PM
Tool: Verilog testbench to time-voltage table arvan Verilog 2 03-01-2006 08:33 PM
Creating ARCTAN Lookup table for Verilog implementation [email protected] Verilog 2 08-11-2005 04:49 PM
how to implement LUT(look-up table) in Verilog thomasc Verilog 2 05-11-2005 05:51 PM
request for help using look-up table [email protected] Verilog 2 02-22-2005 11:51 PM


All times are GMT +1. The time now is 11:40 AM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved