So just to continue a back-of-the-envelope sketch here using just one example, to try and give an idea of the capabilities of FPGAs (and leaving the Perl world entirely now)... the Xilinx Virtex-7 FPGA VC707 Evaluation Kit (http://www.xilinx.com/products/boards-and-kits/ek-v7-vc707-g.html) features the XC7VX485T device, which contains, among other things, about 300,000 6-input LUTs (http://www.xilinx.com/support/documentation/data_sheets/ds180_7Series_Overview.pdf), meaning you could build logic to run comparisons of thousands of bits in parallel. One limiting factor would probably be that the more bits you compare at once, the logic cascades would probably limit the clock speed; the design tools would tell you that (and I suspect an experienced FPGA designer would know some tricks to improve the speed).

Anyway, implementing access to external RAM is something you can get off-the-shelf (http://www.xilinx.com/products/technology/memory-interfacing.html); this board includes 1GB DDR3 RAM. It also includes a pretty fast PCI Express interface, again there should be reference designs available. That would hopefully give one fast enough access to the external data.

Once one has access to the data, perhaps loaded into the onboard RAM, one would read the blocks of data into the FPGA's registers. From there, my initial thought would be two design possibilities: either one massive shift register through which the data is shifted and compared on each shift, or running the comparisons in parallel through multiples of the comparison logic. Which is best will depend on a timing comparison and of course on how long the bit strings are that you are seeking.

As you can tell I think FPGAs are really cool and I wish I got to work with them more often... well, at least I get to work with Perl ;-)

In reply to Re^2: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by Anonymous Monk
in thread Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.