Publication Details

Automatic Generation of Circuits for Approximate String Matching

MARTÍNEK Tomáš, LEXA Matej, BECK Patrik and FUČÍK Otto. Automatic Generation of Circuits for Approximate String Matching. In: 2007 IEEE Design and Diagnostics of Electronic Circuits and Systems. Krakow: IEEE Computer Society, 2007, pp. 203-208. ISBN 1-4244-1161-0.
Czech title
Automatické generování obvodů pro hledání podobnosti v řetězcích
Type
conference paper
Language
english
Authors
Martínek Tomáš, doc. Ing., Ph.D. (DCSY FIT BUT)
Lexa Matej, Ing., Ph.D. (FI MUNI)
Beck Patrik, Bc. (FIT BUT)
Fučík Otto, doc. Dr. Ing. (DCSY FIT BUT)
Keywords

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

Abstract

Hardware accelerators for approximate string matching  play an important role in an increasing number of modern bioinformatic applications. They are able to reduce the task complexity from quadratic to linear and show a speed up in orders of hundreds when compared with the respective software implementation. However, their wider use is limited by the lack of flexibility and modularity required by often variable tasks. In this respect, it is desirable to develop a procedure for automatic design and implementation of such accelerators, to reach high performance and efficiency typical for strongly optimized architectures, with as little human effort on the side of the designer as possible. This paper proposes the essential element of such a procedure, a method for the calculation of generic hardware architecture parameters. The proposed method is evaluated on a range of typical approximate string matching tasks. It demonstrates the differences in the designed architecture, when performance of individual tasks is maximized.

Published
2007
Pages
203-208
Proceedings
2007 IEEE Design and Diagnostics of Electronic Circuits and Systems
Conference
The 10th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, Krakow, PL
ISBN
1-4244-1161-0
Publisher
IEEE Computer Society
Place
Krakow, PL
DOI
UT WoS
000250200100033
BibTeX
@INPROCEEDINGS{FITPUB8304,
   author = "Tom\'{a}\v{s} Mart\'{i}nek and Matej Lexa and Patrik Beck and Otto Fu\v{c}\'{i}k",
   title = "Automatic Generation of Circuits for Approximate String Matching",
   pages = "203--208",
   booktitle = "2007 IEEE Design and Diagnostics of Electronic Circuits and Systems",
   year = 2007,
   location = "Krakow, PL",
   publisher = "IEEE Computer Society",
   ISBN = "1-4244-1161-0",
   doi = "10.1109/DDECS.2007.4295281",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8304"
}
Back to top