Share Email Print

Proceedings Paper

Parallel k-mismatching of strings using daughter-board structure
Author(s): Toomas P. Plaks
Format Member Price Non-Member Price
PDF $17.00 $21.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 6 October 2000
PDF: 12 pages
Proc. SPIE 4212, Reconfigurable Technology: FPGAs for Computing and Applications II, (6 October 2000); doi: 10.1117/12.402514
Show Author Affiliations
Toomas P. Plaks, South Bank Univ. (United Kingdom)

Published in SPIE Proceedings Vol. 4212:
Reconfigurable Technology: FPGAs for Computing and Applications II
John Schewel; Peter M. Athanas; Chris H. Dick; John T. McHenry, Editor(s)

© SPIE. Terms of Use
Back to Top