"Efficient Implementation of a String Matching Algorithm for SRC and Cray Reconfigurable Computers"

Esam El-Araby1, Mohamed Taher1, Tarek El-Ghazawi1, Mohamed Abouellail1, Nandakishore Sastry2, and Kris Gaj2

1 The George Washington University
2 George Mason University


String matching is a fundamental problem in computer science, which involves the finding of one or all the occurrences of a string (more generally termed as pattern) in a text. String matching has numerous applications in fields like text editing, Network Intrusion Detection Systems and DNA Pattern Matching. Many string matching algorithms specific to these applications have been proposed in the past. There have been many implementations of these algorithms on FPGAs.

In this work, we investigate the use of Reconfigurable computers for implementing the Smith-Waterman algorithm for DNA Pattern Matching. An attempt is made to implement all algorithms in a generalized way, so their codes or at least selected functions are portable between two architecturally different reconfigurable computers from SRC Computers and Cray. We report on the performance of these machines in terms of the maximum data throughputs in processing of patterns of various lengths. We also describe our experiences regarding the development time, ease of programming, and ease of debugging applications using both reconfigurable computers.


2005 MAPLD International Conference Home Page