BibTex RIS Kaynak Göster

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

Yıl 2013, Cilt: 2 Sayı: 2, 30 - 39, 01.06.2013

Öz

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.

Kaynakça

  • Wang W.; Wu S., (2009). A jumping string mode matching algorithm, 4th International Conference on Computer Science & Education, 1181-1185.
  • Dehon, A., (2000). The Density Advantage of Reconfigurable Computing, IEEE Computer, 33, 41-49.
  • 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.
  • Boyer R.S., Moore J.S., (1977). A Fast String Searching Algorithm, Communications of the ACM, 20, 762-772.
  • Knuth D.E., Morris J.H., Pratt V.B., (1977). Fast pattern matching in strings, SIAM Journal of Computing, 6, 323-350.
  • Aho A., Corasick, M., (1975). Efficient string matching: an aid to bibliographic search, Communications of the ACM, 18, 333-340.
  • Sidhu R., Prasanna, V.K., (2001). Fast Regular Expression Matching Using FPGAs, 2272
  • Fide S., Jenks, S., (2006). A Survey of String Matching Approaches in Hardware. University of California Irvine.
  • 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.
  • 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.

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

Yıl 2013, Cilt: 2 Sayı: 2, 30 - 39, 01.06.2013

Öz

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.

Kaynakça

  • Wang W.; Wu S., (2009). A jumping string mode matching algorithm, 4th International Conference on Computer Science & Education, 1181-1185.
  • Dehon, A., (2000). The Density Advantage of Reconfigurable Computing, IEEE Computer, 33, 41-49.
  • 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.
  • Boyer R.S., Moore J.S., (1977). A Fast String Searching Algorithm, Communications of the ACM, 20, 762-772.
  • Knuth D.E., Morris J.H., Pratt V.B., (1977). Fast pattern matching in strings, SIAM Journal of Computing, 6, 323-350.
  • Aho A., Corasick, M., (1975). Efficient string matching: an aid to bibliographic search, Communications of the ACM, 18, 333-340.
  • Sidhu R., Prasanna, V.K., (2001). Fast Regular Expression Matching Using FPGAs, 2272
  • Fide S., Jenks, S., (2006). A Survey of String Matching Approaches in Hardware. University of California Irvine.
  • 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.
  • 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.
Toplam 10 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Bölüm Makaleler
Yazarlar

Süleyman Çakıcı Bu kişi benim

İbrahim Şahin Bu kişi benim

Yayımlanma Tarihi 1 Haziran 2013
Yayımlandığı Sayı Yıl 2013 Cilt: 2 Sayı: 2

Kaynak Göster

APA Çakıcı, S., & Şahin, İ. (2013). Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı. İleri Teknoloji Bilimleri Dergisi, 2(2), 30-39.
AMA Çakıcı S, Şahin İ. Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı. İleri Teknoloji Bilimleri Dergisi. Haziran 2013;2(2):30-39.
Chicago Çakıcı, Süleyman, ve İbrahim Şahin. “Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı”. İleri Teknoloji Bilimleri Dergisi 2, sy. 2 (Haziran 2013): 30-39.
EndNote Çakıcı S, Şahin İ (01 Haziran 2013) Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı. İleri Teknoloji Bilimleri Dergisi 2 2 30–39.
IEEE S. Çakıcı ve İ. Şahin, “Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı”, İleri Teknoloji Bilimleri Dergisi, c. 2, sy. 2, ss. 30–39, 2013.
ISNAD Çakıcı, Süleyman - Şahin, İbrahim. “Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı”. İleri Teknoloji Bilimleri Dergisi 2/2 (Haziran 2013), 30-39.
JAMA Çakıcı S, Şahin İ. Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı. İleri Teknoloji Bilimleri Dergisi. 2013;2:30–39.
MLA Çakıcı, Süleyman ve İbrahim Şahin. “Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı”. İleri Teknoloji Bilimleri Dergisi, c. 2, sy. 2, 2013, ss. 30-39.
Vancouver Çakıcı S, Şahin İ. Dize Eşleştirme Başarımını İyileştirmek İçin FPGA Tabanlı Bir Donanım Modülü Tasarımı. İleri Teknoloji Bilimleri Dergisi. 2013;2(2):30-9.