Parallel k-mismatching of strings using daughter-board structure

Toomas P. Plaks

doi:10.1117/12.402514

6 October 2000 Parallel k-mismatching of strings using daughter-board structure

Toomas P. Plaks

Proceedings Volume 4212, Reconfigurable Technology: FPGAs for Computing and Applications II; (2000) https://doi.org/10.1117/12.402514
Event: Information Technologies 2000, 2000, Boston, MA, United States

Abstract

This paper presents a family of scalable regular array structures for k-mismatches problem of a reference string of length n and a pattern of length m. The conventional regular array of size O(m) computes in O(n + m). The drawback of his solution is, first, that the performance is bounded by the length of pattern, and second, the long latency. In this paper we present regular array solutions where the array size is parameterized by the number, s, 1<=s<=n, of parallel input/output channels. The array of size O(sm) computes in O(n/s + m) time. In order to reduce the latency time, tree-like structures for computing reduction are used, reducing the time complexity to O(n/s + m^{1/r}), r is the dimensionality of array. The number of patterns can be l, while the time complexity increases to O(n/s + m^{1/r}+l) using O(sml) processors. Proposed regular arrays are suitable for teal-time applications and are efficiently mapped onto FPGAs using daughter-board structure.

Citation Download Citation

Toomas P. Plaks "Parallel k-mismatching of strings using daughter-board structure", Proc. SPIE 4212, Reconfigurable Technology: FPGAs for Computing and Applications II, (6 October 2000); https://doi.org/10.1117/12.402514

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available