FPGA based database searching

N

Norman Bollmann

Guest
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
 
On 2008-06-23, Norman Bollmann <wirdnichtgelesen@gmx.net> wrote:
Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.
Click to expand...
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.

--
Ben Jackson AD7GD
<ben@ben.com>
http://www.ben.com/
 
"Norman Bollmann" <wirdnichtgelesen@gmx.net> wrote:

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.
Click to expand...
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.

--
Programmeren in Almere?
E-mail naar nico@nctdevpuntnl (punt=.)
 
In comp.arch.fpga PFC <lists@peufeu.com> wrote:
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.
Click to expand...
And Google can search the entire freaking Internet :)

So, I suggest reviewing your search algorithm ;)
Click to expand...
What he said.

Describe problem more please.

G.
 
On 23 Jun, 14:00, "Norman Bollmann" <wirdnichtgele...@gmx.net> wrote:
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!
Click to expand...
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
 
Norman Bollmann wrote:

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.
Click to expand...
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
 
On Jun 23, 1:04 pm, Mike Treseler <mike_trese...@comcast.net> wrote:
Norman Bollmann wrote:
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
Click to expand...
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
 
be used, slowing down the throughput. Target is a database searching of
262144 elements with 16 bit each in maximum 220 ms.
Click to expand...
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 ;)
 
On 23 Jun., 15:00, "Norman Bollmann" <wirdnichtgele...@gmx.net> wrote:
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.
Click to expand...
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
 
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
 
On Jun 27, 11:05 am, "Norman Bollmann" <wirdnichtgele...@gmx.net>
wrote:
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
Click to expand...
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
 
On Jun 27, 7:52 pm, Chris Maryan <kmar...@gmail.com> wrote:
On Jun 27, 11:05 am, "Norman Bollmann" <wirdnichtgele...@gmx.net
wrote:

Thank you very much for your feedback, so far!

see AMMASS project
Click to expand...
there was a demo

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
Click to expand...
 
see AMMASS project
there was a demo
at IP07 grenoble http://www.design-reuse.com/ip07
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top