Families of FPGA-Based Accelerators for Approximate String Matching
Tom Van Court1, Martin C Herbordt
1Department of Electrical and Computer Engineering Boston University.
Microprocessors and Microsystems
|May 24, 2011
Summary
This study introduces a flexible hardware accelerator for approximate string matching algorithms. It achieves significant speed-ups (150x-400x) by using modular components for dynamic programming, enhancing FPGA utilization.
Area of Science:
- Computer Science
- Bioinformatics
- Computational Biology
Background:
- Approximate string matching algorithms are crucial in various fields.
- Existing hardware solutions are often specialized, lacking flexibility.
- Efficient hardware acceleration for diverse approximate string matching needs is challenging.
Purpose of the Study:
- To develop a hardware description for a broad range of approximate string matching algorithms.
- To avoid performance degradation from feature bloat in hardware implementations.
- To enable efficient and flexible hardware acceleration for approximate string matching.
Main Methods:
- Designed three component types addressing different aspects of approximate string matching.
- Enabled interchangeable implementations for each component type.
- Utilized Field-Programmable Gate Array (FPGA) fabric for efficient resource allocation.
Main Results:
- Achieved efficient generation of a large family of approximate string matching accelerators.
- Demonstrated high performance with speed-ups of 150× to 400× compared to serial reference codes.
- Maintained efficiency by allowing applications to select specific feature sets.
Conclusions:
- The proposed component-based approach enables a flexible and efficient hardware accelerator family for approximate string matching.
- This methodology overcomes the limitations of specialized, single-purpose hardware solutions.
- The system offers significant performance gains for diverse approximate string matching applications.
More Related Videos
Related Concept Videos
01:17Accelerators
Accelerators in concrete serve as admixtures to speed up the hardening process, enabling the concrete to achieve early strength faster. Although accelerators do not necessarily impact the time it takes concrete to set, they reduce this time in practice. A common accelerator is calcium chloride, which is particularly useful for hastening early strength development in cold weather or for rapid repair jobs that require quick heat generation after mixing.
The effectiveness of calcium chloride can...
The effectiveness of calcium chloride can...
01:05Maxam-Gilbert Sequencing
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
01:21Linear Approximation in Time Domain
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length, the...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length, the...
01:57Gene Families
Gene families consist of groups of genes proposed to have originated from a common ancestor. Typically these arise through events in which a gene or genes are mistakenly duplicated during cell division. Unlike their parent genes (which are subject to selection pressure to maintain function), these gene copies do not need to preserve their sequences and may evolve at a relatively faster rate.
Occasionally these regions can be adapted to take on new roles within the organism, becoming novel genes...
Occasionally these regions can be adapted to take on new roles within the organism, becoming novel genes...
01:17Sign Test for Matched Pairs
The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in value between...
To conduct the sign test, we first calculate the differences in value between...
01:26Linear Approximation in Frequency Domain
Linear systems are characterized by two main properties: superposition and homogeneity. Superposition allows the response to multiple inputs to be the sum of the responses to each individual input. Homogeneity ensures that scaling an input by a scalar results in the response being scaled by the same scalar.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear.