Detail publikace

Automatic Generation of Circuits for Approximate String Matching

Originální název

Automatic Generation of Circuits for Approximate String Matching

Anglický název

Automatic Generation of Circuits for Approximate String Matching

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@inproceedings{BUT26049,
  author="Tomáš {Martínek} and Matej {Lexa} and Patrik {Beck} and Otto {Fučík}",
  title="Automatic Generation of Circuits for Approximate String Matching",
  annote="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.",
  address="IEEE Computer Society",
  booktitle="2007 IEEE Design and Diagnostics of Electronic Circuits and Systems",
  chapter="26049",
  doi="10.1109/DDECS.2007.4295281",
  howpublished="online",
  institution="IEEE Computer Society",
  year="2007",
  month="april",
  pages="203--208",
  publisher="IEEE Computer Society",
  type="conference paper"
}