loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
15th IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'04)
Families of FPGA-Based Algorithms for Approximate String Matching
Galveston, Texas
September 27-September 29
ISBN: 0-7695-2226-2
Tom Van Court, Boston University
Martin C. Herbordt, Boston University
Dynamic programming for approximate string matching is a large family of different algorithms, which vary significantly in purpose, complexity, and hardware utilization. Many implementations have reported impressive speed-ups, but have typically been point solutions - highly specialized and addressing only one or a few of the many possible options. The problem to be solved is creating a hardware description that implements a broad range of behavioral options without losing efficiency due to feature bloat. We report a set of three component types that address different parts of the DP string matching problem. Multiple, interchangeable implementations are available for each component type. This allows each application to choose the feature set required, then make maximum use of the FPGA fabric according to that application's specific resource requirements. Synthesis estimates show a 4:1 improvement in time-space performance, depending on the options chosen for a specific matching task.
Citation:
Tom Van Court, Martin C. Herbordt, "Families of FPGA-Based Algorithms for Approximate String Matching," asap, pp.354-364, 15th IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.