Automatic Generation of Circuits for Approximate String Matching

Automatic Generation of Circuits for Approximate String Matching

Paper in proceedings (conference paper)

Hardware accelerators for approximate string matching  play animportant role in an increasing number of modern bioinformaticapplications. They are able to reduce the task complexity fromquadratic to linear and show a speed up in orders of hundreds whencompared with the respective software implementation. However, theirwider use is limited by the lack of flexibility and modularity requiredby often variable tasks. In this respect, it is desirable to develop aprocedure for automatic design and implementation of such accelerators,to reach high performance and efficiency typical for strongly optimizedarchitectures, with as little human effort on the side of the designeras possible. This paper proposes the essential element of such aprocedure, a method for the calculation of generic hardwarearchitecture parameters. The proposed method is evaluated on a range oftypical approximate string matching tasks. It demonstrates thedifferences in the designed architecture, when performance ofindividual tasks is maximized.

Hardware accelerators for approximate string matching  play animportant role in an increasing number of modern bioinformaticapplications. They are able to reduce the task complexity fromquadratic to linear and show a speed up in orders of hundreds whencompared with the respective software implementation. However, theirwider use is limited by the lack of flexibility and modularity requiredby often variable tasks. In this respect, it is desirable to develop aprocedure for automatic design and implementation of such accelerators,to reach high performance and efficiency typical for strongly optimizedarchitectures, with as little human effort on the side of the designeras possible. This paper proposes the essential element of such aprocedure, a method for the calculation of generic hardwarearchitecture parameters. The proposed method is evaluated on a range oftypical approximate string matching tasks. It demonstrates thedifferences in the designed architecture, when performance ofindividual tasks is maximized.

automated design, approximate string matching, generic systolic array architecture, FPGA

automated design, approximate string matching, generic systolic array architecture, FPGA

MARTÍNEK, T.; LEXA, M.; BECK, P.; FUČÍK, O.

16.04.2007

IEEE Computer Society

Krakow

1-4244-1161-0

2007 IEEE Design and Diagnostics of Electronic Circuits and Systems

203

208

6