Design of an FPGA-Based Hardware Module for Improving The Performance of String Matching

Abstract

String matching is a widely used operation in many modern day applications and is always a research focus in the area of computer science. Software-based string matching implementations experience poor performance especially when large arrays are considered. In this study, a hardware module for FPGA chips was designed to speed-up the string matching process. The module was tested using test data and the performance of it was measured. Its performance was compared to some general purpose computers. The results showed that the string matching operations performed using the module can be carried out up to twenty-four times faster than the software implementation running on different PCs.

Keywords

• FPGA, String matching, Hardware module.

Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı

Abstract

Dize eşleştirme işlemleri, güncel uygulamalarda oldukça yaygın olarak kullanılmaktadır ve her zaman bilgisayar bilimleri alanında araştırmalara bir odak noktası olmuştur. Yazılım tabanlı olarak gerçeklenen dize eşleştirme işlemi özellikle büyük boyutlu dizelerde eşleme yapıldığında uzun zaman almaktadır. Bu çalışmada, eşleştirme işlemlerini hızlandırarak, dize eşleştirme başarımını iyileştirmek amacıyla FPGA tabanlı bir donanım modülü tasarlanmıştır. Tasarlanan modül, test verileri kullanılarak test edilmiş ve başarım tespiti yapılmıştır. Modülün veri işleme hızı değişik bilgisayarlarla karşılaştırılmıştır. Karşılaştırma sonuçları, tasarlanan modülün, dize eşleştirme işlemlerini bilgisayarlara nispeten yaklaşık 24 kat kadar daha hızlı gerçekleştirilebileceğini göstermiştir.

Keywords

• FPGA, Dize eşleştirme, Donanım Modülü.

References

1. Wang W.; Wu S., (2009). A jumping string mode matching algorithm, 4th International Conference on Computer Science & Education, 1181-1185.
2. Dehon, A., (2000). The Density Advantage of Reconfigurable Computing, IEEE Computer, 33, 41-49.
3. Qasim, S.M., Abbasi S.A., and Almashary, B., (2009). An Overview of Advanced FPGA Architectures for Optimized Hardware Realization of Computation Intensive Algorithms, IMPACT’09, 300-303.
4. Boyer R.S., Moore J.S., (1977). A Fast String Searching Algorithm, Communications of the ACM, 20, 762-772.
5. Knuth D.E., Morris J.H., Pratt V.B., (1977). Fast pattern matching in strings, SIAM Journal of Computing, 6, 323-350.
6. Aho A., Corasick, M., (1975). Efficient string matching: an aid to bibliographic search, Communications of the ACM, 18, 333-340.
7. Sidhu R., Prasanna, V.K., (2001). Fast Regular Expression Matching Using FPGAs, 2272
8. Fide S., Jenks, S., (2006). A Survey of String Matching Approaches in Hardware. University of California Irvine.

9. Lin, C., Huang, C., Jiang, C., Chang S., (2007). Optimization of Pattern Matching Circuits for Regular Expression on FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 15(12), 1303-1310.
10. Canella, M.; Miglioli, F., (2003). Performing DNA comparison on a bio-inspired tissue of FPGAs, International Parallel and Distributed Processing Symposium, 1-8. Tempesti, G., Mange, D., Stauffer, A., Teuscher, C., (2002). The BioWall: An electronic tissue for prototyping bio-inspired systems, IEEE proceedings of NASA/DoD Conference on Evolvable Hardware, 221–230.