Counting bits

Hello,

I am a Python programmer writing neural network code with binary firing
and binary weight values.  My code will take many days to parse my
large data sets.  I have no idea how much fpga could help, what the
cost would be, and how easy it would be to access it from Python.  The
problem is similar to competitive networks, where I must dot product
many million-length bit vectors (which only change occasionally) with 1
input vector.  Anybody want to estimate the cost, speedup, and value an
fpga could offer me?

Seems like this problem shouldn't be so hard, but from the little
research I've done I haven't found a good value product that is
ready-made, so I'm looking at (multiple?) fpga as a coprocessor.

Dini has a new PCIe x8 board. It should work really well for your needs
but nobody has built the DMA engine and drivers for it yet so that adds
to its $10k cost. FPGAs are great for accelerating neural network
projects. There are lots of papers with algorithms for it in ACM and
IEEE journals. The Python interface is not a problem. It will come to
IOCTLs at some point. You may have to make a C API and DLL wrapper if
your Python cannot make IOCTL calls directly.

Here's my usual plug: I just wish there were a hardware vendor who
would put some cheap FPGAs (Spartan 3e 1600s) on a cheap board with
some standard DRAM and SRAM slots (unpopulated) and a PCIe x8 (or x4)
slot and then sell the board for < $300. Design the darn thing for
acceleration, not prototyping. They could make a killing on a well-made
board with 8 or 16 fast DMA channels and a driver that worked for that
really well.

On a sunny day (14 Apr 2006 14:28:38 -0700) it happened andrewfelch@gmail.com
wrote in <1145050118.699722.123650@e56g2000cwe.googlegroups.com>:

>Hello,
>
>I am a Python programmer writing neural network code with binary firing
>and binary weight values.  My code will take many days to parse my
>large data sets.  I have no idea how much fpga could help, what the
>cost would be, and how easy it would be to access it from Python.  The
>problem is similar to competitive networks, where I must dot product
>many million-length bit vectors (which only change occasionally) with 1
>input vector.  Anybody want to estimate the cost, speedup, and value an
>fpga could offer me?
>
>Seems like this problem shouldn't be so hard, but from the little
>research I've done I haven't found a good value product that is
>ready-made, so I'm looking at (multiple?) fpga as a coprocessor.
>
>
Sounds to me like vector processing.
Cray (supercomputers) know all about it.
Can be done in FPGA.
For neural nets many hardware units have been designed.
Is not python horribly slow for this? C would be better? ASM?
Anyways, perhaps (this has been done), you can implement your neuron in
hardware.
There also exist vector plugin cards for the PC (designed one once).

So how many million-length bit-vector dot products might I be able to
do per second?  My 3.8ghz P4 can do 125/sec.  I would prefer building a
beowulf cluster if the price:performance was similar (because fpga is
so foreign to me).  Of course if you tell me 10,000/sec I will become
an instant fpga evangelist, hehe.

Jan: I use a matrix library written in C.

Thanks for your help guys,
AndrewF

I have not found a decent bit-vector dot product plugin card.  I think
they usually do integers or floating points, but not bits in an
efficient manner.

On a sunny day (14 Apr 2006 21:56:19 -0700) it happened andrewfelch@gmail.com
wrote in <1145076979.683557.142540@g10g2000cwb.googlegroups.com>:

>So how many million-length bit-vector dot products might I be able to
>do per second?  My 3.8ghz P4 can do 125/sec.  I would prefer building a
>beowulf cluster if the price:performance was similar (because fpga is
>so foreign to me).  Of course if you tell me 10,000/sec I will become
>an instant fpga evangelist, hehe.
>
>Jan: I use a matrix library written in C.
Ah, Ok.
You know, this is not a 'saturday afternoon after shopping' thing
(it is that now here), I can asnwer just like that.
My old boss used to DEMAND to see the whole project else he did
not even want to venture.
Because often these things can be broken down, done in different ways.
If it was a simple multiply you could see how many nnbit ,multipliers there are
in the largest FPGA, but millions.... And you would soemhopw have to get the
data in and out.
Some project.
in Virtex (Xilinx knows more) at 500MHz you can have 512 xtreme DSP blocks
with 18x18 multiplyer. 512 x 18 = 9216 bits at the time in 2 nS.
To make a million (in a loop) x 109 = 218 nS per multiply...
Sort of a wild number, you really need to talk to these guys, I have no experience with
the virtex 4.
Over to X (or Altera).
Budget? Time? All counts.

andrewfelch@gmail.com schrieb:
> where I must dot product
> many million-length bit vectors (which only change occasionally) with 1
> input vector.  Anybody want to estimate the cost, speedup, and value an
> fpga could offer me?

If I understand you correctly, for each vector you want to know at how
many places both the vector and the input vector are 1?
Your vectors change rarely, the single input vector changes rapidly?

I would say that in an FPGA you would not do it one vector at a time but
N bits at a time for many vectors in parallel.

If your vectors are stored of chip you can process them as fast as you
can read them. With the right board at a rate of a few hundred gigabits
per second.


>So how many million-length bit-vector dot products might I be able to
> do per second?  My 3.8ghz P4 can do 125/sec.
Thats 125MBits/s. That is very easy to beat.
You probably can get some affordable board with 64-bit 200MHz SRAM and a
small FPGA. This will get you about a factor of ten over the P4.

On the other hand the P4 value seems to low. According to "Hacker's
Delight" pages 65ff counting the number of bits in a 32-bit word takes
less than 20 instruction. Adding one instruction for the initial AND,
the loads, index updates and some loop control instructions results in
about one instruction per bit. This means that a P4 should be able to do
a few gigabits per second.
And thats wihtout using MMX instructions which can do the dot product
after the first three reductions.

Kolja

andrewfelch@gmail.com wrote:
> So how many million-length bit-vector dot products might I be able to
> do per second?  My 3.8ghz P4 can do 125/sec.  I would prefer building a
> beowulf cluster if the price:performance was similar (because fpga is
> so foreign to me).  Of course if you tell me 10,000/sec I will become
> an instant fpga evangelist, hehe.

If I understood correctly :

  - You have many (what is many for you ? 100, 1000, 1000000 ?) million
bits vectors that are quite 'static' (or at least don't change much
compared to your 'input' vector). Let says you have N of them and that
you million bit vector is in fact 1024*1024 bits long.
  - You also have 1 input vector that change quite often.
  - You want the N cross products which is basically the number of 1 in 
the bit wise AND of the fixed vectors and the input vector.

To get an estimation on how fast it could be done, N should be known ...
or at least a range because I think the main limitation is gonna be
the bandwith between the host and the card and not the FPGA itself.

An FPGA can do the cross product pretty easily, imagine you get the
vectors 32 bits by 32 bits. First the 32 first bits of 'input' then the 
32 first bits of the 'references' one by one. Then the 32 bits after
that, and so on. So to enter all the vectors info for 1 given
input vector, you need (N+1)*2^15 cycles. The logic doing the cross
product is just a AND bit by bit, a stage that perform the counting of 
the 32 bits, then a 21 bits adder that stores the result in block rams
(given that N is sufficiently small to fits the 21 bits results in
block ram. Let says < 16384 for a small FPGA). The logic doing that 
could easily be pipelined to go at > 100 MHz even in a small cheap
spartan 3 and since you need 2^15 cycles to do a complete vector (if 
N>>1) that would be 3000/s and that's in a small FPGA.

Now, use a 128 bits wide DDR2 memory that's 256 bits in parallel, use
a high speed grade to run the whole things at > 250 MHz and you get
60.000 of them in parallel ...

But as I said, you need to get the data into the DDR2 memory and
organized so that the read is efficient. pretty easy. A million bit
vector is 128kb, getting 60 thousands of them per seconds is 7.5 GBytes
of traffic per second ...

Of course, you need to define N better and theses numbers are just for
the first design I can think of with the info you provided. You mileage 
may vary. I think it could be done pretty quickly if you hire someone 
that already has and has used, a memory controller and whatever 
controller is needed to input/output the data. And getting data in/out 
is the real challenge here ...


	Sylvain	

In article <1145050118.699722.123650@e56g2000cwe.googlegroups.com>,
<andrewfelch@gmail.com> wrote:

> Hello,
> 
> I am a Python programmer writing neural network code with binary firing
> and binary weight values.  My code will take many days to parse my
> large data sets.  I have no idea how much fpga could help, what the
> cost would be, and how easy it would be to access it from Python.  The
> problem is similar to competitive networks, where I must dot product
> many million-length bit vectors (which only change occasionally) with 1
> input vector.  Anybody want to estimate the cost, speedup, and value an
> fpga could offer me?

I assume you have looked for algorithmic speed-ups?  (Also FPGAs have
different algorithmic speed-ups available than conventional computers.)

Algorithmic speed-ups might be available if:
a) the bit vectors are sparse (i.e. only a small fraction are ones, or
a small fraction are zeros)
b) the bit vectors are non-random (e.g. you are matching to shift
register sequences, or to highly-compressible sequences that can be
described in considerably less data than the raw bit stream)
c) the bit vectors are related (e.g. you are using the neural net to
listen to a data stream for a pattern: you don't find it, so you shift
by one bit and try again).
d) You can do pruning (e.g. if you don't find any evidence of a match
after doing 10% of the sequence, you can abandon that vector and try
the next)
e) You can match multiple input vectors instead of just 1.  (Since most
of your conventional processor time is going to be spent waiting around
for slow DRAM to get the next memory fetch of megabit matching vectors,
you may as well compare it to a few dozen inputs, rather than just
one).

As a Python programmer, you will probably find it easier to use C than
to learn VHDL/Verilog to the extent you need to implement this.  If a
single order-of-magnitude speed-up will solve your problems, then
changing to a language closer to the metal may be enough and is easy
enough to try.

-- 
David M. Palmer  dmpalmer@email.com (formerly @clark.net, @ematic.com)

Wow, you guys have all been really helpful.

The conclusion seems to be that it would depend on system bandwidth,
but if there are 20 (possibly 1,000 as I scale to larger problems and
need greater capacity)  "reference" million-bit-vectors, then I only
need to read the input vector from memory 1/20th as often as your
figure, right?

Jan wrote:
>> Budget? Time? All counts.
I'd prefer a scalable solution so I can pay more later for more speed.
I parse pieces of a sentence independently, so the problem breaks up
easily across several fpga cards, if that is cheaper.  I perform Monte
Carlo sampling, which means that I run 30 indpendent experiments.  So
if I'm bandwidth limited I should breakup the problem to 30 fpga
equipped computers.

Kolja wrote:
>> On the other hand the P4 value seems to low. According to "Hacker's
>> Delight" pages 65ff counting the number of bits in a 32-bit word takes
>> less than 20 instruction.

I agree that I should write it in C/C++ to see what my max P4 speed is,
but http://www-db.stanford.edu/~manku/bitcount/bitcount.html indicates
that 16-bit lookup tables are most efficient (fits in L1 cache on a
AMD64, which I don't have, using only 3 clock cycles), which is what I
already use.  The next step is definately to implement in C/C++ by
hand.

The consensus seems to be that it could be done well in fpga, and that
price scales with the problem much better than clusters of CPU's acting
on their own.  It also seems that I would have to hire someone to build
it because it is not simple enough for a newbie to try.  I hack xboxes,
i-opener (net appliance), and other hardware so I am a DIY learning
kind of guy, and it seems to me that at 27 years of age, being able to
implement pieces of my algorithms in hardware would be a great
advantage to decades of my future work.

I could get $200 to $500 from my advisor for a developer's kit for
sure.  Any additional suggestions on specific hardware, estimated time
to develop for a newbie, etc. are greatly appreciated.

Thanks!
AndrewF