FPGA based database searching

[Norman Bollmann]

Hello,



I've been searching the internet for days now and still I'm not sure about
what I am trying to do. Okay now, I've got a software implementation in
ANSI-C for a complex database searching. The database is a proprietary
format where I am saving data, which has to be given as a result, depending
on the input data. Problem is, the software implementation is far to slow.



Now I am looking for alternative ways for a faster implementation and came
across the idea to implement the whole database searching as electronic
circuit in an FPGA. The database is of course far too big to save it inside
an FPGA, e.g. the BlockRAMs of a Spartan3. Therefore external memory has to
be used, slowing down the throughput. Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.



Does anybody have experience with FPGA based database handling or similar
tasks? Your urgent response will be highly appreciated!



Regards

Norman Bollmann

 

[Jon Beniston]

Hello,

I've been searching the internet for days now and still I'm not sure about
what I am trying to do. Okay now, I've got a software implementation in
ANSI-C for a complex database searching. The database is a proprietary
format where I am saving data, which has to be given as a result, depending
on the input data. Problem is, the software implementation is far to slow.

Now I am looking for alternative ways for a faster implementation and came
across the idea to implement the whole database searching as electronic
circuit in an FPGA. The database is of course far too big to save it inside
an FPGA, e.g. the BlockRAMs of a Spartan3. Therefore external memory has to
be used, slowing down the throughput. Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.

Does anybody have experience with FPGA based database handling or similar
tasks? Your urgent response will be highly appreciated!

How slow is the software solution? Are you sure it can't be done on a
faster PC? Have you tried searching in parallel? i.e. 64-bits at a
time. That would mean you need to search 64k entries in 220ms. That's
3us per entry. You can execute quite a few instructions on a PC in
that amount of time. A dataset of that size will fit in to your cache
too.

Jon

 

[Mike Treseler]

I've got a software implementation in
ANSI-C for a complex database searching. The database is a proprietary
format where I am saving data, which has to be given as a result, depending
on the input data. Problem is, the software implementation is far to slow.

Get a faster server, load linux.
FPGA's are OK for data filtering or statistics.
If you need "complex database searching" you
need a computer.

-- Mike Treseler

 

[Ben Jackson]

Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.

There are only 65536 possible values of your 16 bit value. What is the
output of your algorithm? Found y/n? Then use a lookup table! I doubt
an FPGA is the right answer to your problem. On a modern CPU you've got
thousands of cycles for each element -- assuming you even have to consider
all of them for any given key.

 

[Andy]

Get a faster server, load linux.
FPGA's are OK for data filtering or statistics.
If you need "complex database searching" you
need a computer.

-- Mike Treseler

The bottleneck for most searches has to do with how many compares can
be done per unit time, which usually boils down to how fast data can
be brought into the search. Unless you have a significantly faster
mechanism to access the data than the CPU, you probably won't be able
to search it any faster. That's assuming you have the undivided
attention of the CPU. If the CPU is busy doing other things while your
FPGA could be doing the searching, that might improve overall
performance.

Block ram usually won't help much, since you can only access one or
two addresses at a time. If you had a multi-word key, then pulling the
data into a multi-way structure (flops or replicated block rams) such
that the different parts of the key could be compared to multiple data
words in parallel, then you'd be getting somewhere.

Andy

 

[PFC]

be used, slowing down the throughput. Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.

If you are searching 16 bit datums then your search space is limited to
65536 different datums. Why would you want to store more than this ? A
hashtable comes to mind, for instance.

What is your searching algorithm ? Why is it that complex ? Can you post
a description ?

Taking well-designed software as example, your 220 ms time budget is
enough for Postgresql to perform about 3000-5000 simple SQL queries
returning 1 row with btree index lookup on a table with millions of rows
including network overhead (as long as it doesn't need to hit the disk),
in 220 ms Xapian can make multiple full text phrase searches with ranking
on a multi gigabyte text dataset. These are per core of course.

So, I suggest reviewing your search algorithm

 

[Kolja Sulimma]

Therefore external memory has to
be used, slowing down the throughput. Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.

What type of searches are you performing? What other operations are
required?
There are data structures that do an identity lookup in constant time
and interval
searches in logarithmic time. A CPU should do that in less than a
microsecond.

Kolja Sulimma

 

[Nico Coesel]

Hello,



I've been searching the internet for days now and still I'm not sure about
what I am trying to do. Okay now, I've got a software implementation in
ANSI-C for a complex database searching. The database is a proprietary
format where I am saving data, which has to be given as a result, depending
on the input data. Problem is, the software implementation is far to slow.



Now I am looking for alternative ways for a faster implementation and came
across the idea to implement the whole database searching as electronic
circuit in an FPGA. The database is of course far too big to save it inside
an FPGA, e.g. the BlockRAMs of a Spartan3. Therefore external memory has to
be used, slowing down the throughput. Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.

I suggest you optimize your software algorithm. 262144 elements fits
in the cache of any modern PC CPU. You'll have a hard time creating an
FPGA design that will perform better.

 

[Norman Bollmann]

Thank you very much for your feedback, so far!

Oh my.... I'm sorry. That was definitely a spelling mistake: it's supposed
to be "26290144 elements". Sorry 'bout that!

Regards

Norman Bollmann

 

[Chris Maryan]

Thank you very much for your feedback, so far!

Oh my.... I'm sorry. That was definitely a spelling mistake: it's supposed
to be "26290144 elements". Sorry 'bout that!

Regards

Norman Bollmann

Even with 26M elements to search, as long as they're only 16bits,
that's still only 65k choices. A hash table based thing as someone
else pointed out would be a good option.

Can you give some details about the search you need to perform?

Chris

 

[rponsard]

see AMMASS project
there was a demo

Even with 26M elements to search, as long as they're only 16bits,
that's still only 65k choices. A hash table based thing as someone
else pointed out would be a good option.

Can you give some details about the search you need to perform?

Chris

 

[rponsard]

see AMMASS project
there was a demo
at IP07 grenoble http://www.design-reuse.com/ip07