Yıl 2016, Cilt 20 , Sayı 3, Sayfalar 441 - 450 2016-09-02

Yüzde tabanlı String Eşleme Problemi için yeni bir donanım modülü tasarımı
A hardware module design for percentage-based String Matching Problem

Günay Temür [1] , İbrahim Şahin [2]


Bir verinin bir dizgi içerisinde veya bir gen yapısının bir DNA gen dizilimi içerisinde arama işleminin gerçekleştirilmesi için çeşitli algoritmalar kullanılmaktadır. Kullanılan bu algoritmalardan bazıları bize mutlak eşleşme olmadığı durumlarda olumsuz dönüt vermekte, bazıları ise “bunu mu arıyorsunuz” diye alternatifler sunmaktadır. Her iki algoritma da genel amaçlı PC’lerde saniyeler süren işlemler sonucunda bize dönüt verebilmektedir. Bu çalışmada bize hem mutlak eşleşmeyi hem de hedef dizgi içinde yüzdelik eşleşme oranlarının gerçekleştiği konumu veren FPGA çiplerine yönelik yüksek performanslı bir donanım modülü tasarlanmıştır. Geliştirilen modülün veri işleme hızı farklı PC’lerle karşılaştırılmış ve 2300 kata kadar daha hızlı arama gerçekleştirdiği karşılaştırma sonuçlarından elde edilen veriler ile doğrulanmıştır.

Various algorithms are used to perform search operations in an array structure or a gene in a DNA gene sequence data. Some of these algorithms provide results if there is an exact matching between the source and the target arrays while some others provide us some alternative results and ask us "Did you mean this".  Both types of algorithms return results after running for seconds on general purpose computers (PC) depending on the size of the data being searched.  In this study, we designed a hardware module for FPGA chips to perform both exact and percentage based string matching. In the case of percentage based matching, the module provides a location in target string on which the highest percentage of matching between the source and target occurs. The module’s performance was compared to different PCs and it was observed that it can return a result up to 2300 times faster than PCs.

  • . Knuth, Donald "Section 6.1: Sequential Searching,". Sorting and Searching. The Art of Computer Programming 3 (3rd ed.). Addison-Wesley. pp. 396–408. ISBN 0-201-89685-0. 1997.
  • . Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. 1990.
  • . Knuth, Donald. The Art of Computer Programming, volume 3, Sorting and Searching. ss. 506–542. 1973.
  • . 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.
  • . Xilinx Inc, The Programmable Logic Data Book, San Jose, CA, 1994.
  • . Sahin, I., Gloster, C. and Doss, C. 2000. “Feasibility of Floating-Point Arithmetic in Reconfigurable Computing Systems”, NASA Military and Aerospace Applications of Programmable Devices and Technology Conference, Washington, DC.
  • . Rincon, F. and Teres, L. 1998. “Reconfigurable Hardware Systems”. International Semiconductor Conference, vol. 1, pp. 45-54.
  • . Sahin, I. 2002. “A Compilation Tool for Automated Mapping of Algorithms onto FPGA Based Custom Computing Machines”. NC State University, Doktora Tezi, Raleigh-USA.
  • . Sridharan, K. and Priya, T.K. 2007. “A Hardware Accelerator and FPGA Realization for Reduced Visibility Graph Construction Using Efficient Bit Representations”. IEEE Transactions on Industrial Electronics, Vol. 54, No. 3.
  • . Koyuncu, İ. and Şahin, İ. 2007. “Generic Fpga Modules for Integer 2D and 3D Transformations”. 12th. Conference for Computer Aided Engineering and System Modeling with Exhibition. Antalya, Turkey.
  • AHO, A.V., 1990, Algorithms for finding patterns in strings. in Handbook of Theoretical Computer Science, Volume A, Algorithms and complexity, J. van Leeuwen ed., Chapter 5, pp 255-300, Elsevier, Amsterdam.
  • . HORSPOOL R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506.
  • . KARP R.M., RABIN M.O., 1987, Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2):249-260.
Bölüm Uygulama Makalesi
Yazarlar

Yazar: Günay Temür

Yazar: İbrahim Şahin

Tarihler

Başvuru Tarihi : 29 Mayıs 2015
Kabul Tarihi : 17 Ekim 2019
Yayımlanma Tarihi : 2 Eylül 2016

Bibtex @ { saufenbilder270027, journal = {Sakarya University Journal of Science}, issn = {1301-4048}, eissn = {2147-835X}, address = {}, publisher = {Sakarya Üniversitesi}, year = {2016}, volume = {20}, pages = {441 - 450}, doi = {10.16984/saufenbilder.99529}, title = {A hardware module design for percentage-based String Matching Problem}, key = {cite}, author = {Temür, Günay and Şahin, İbrahim} }
APA Temür, G , Şahin, İ . (2016). A hardware module design for percentage-based String Matching Problem. Sakarya University Journal of Science , 20 (3) , 441-450 . DOI: 10.16984/saufenbilder.99529
MLA Temür, G , Şahin, İ . "A hardware module design for percentage-based String Matching Problem". Sakarya University Journal of Science 20 (2016 ): 441-450 <http://www.saujs.sakarya.edu.tr/tr/issue/25594/270027>
Chicago Temür, G , Şahin, İ . "A hardware module design for percentage-based String Matching Problem". Sakarya University Journal of Science 20 (2016 ): 441-450
RIS TY - JOUR T1 - A hardware module design for percentage-based String Matching Problem AU - Günay Temür , İbrahim Şahin Y1 - 2016 PY - 2016 N1 - doi: 10.16984/saufenbilder.99529 DO - 10.16984/saufenbilder.99529 T2 - Sakarya University Journal of Science JF - Journal JO - JOR SP - 441 EP - 450 VL - 20 IS - 3 SN - 1301-4048-2147-835X M3 - doi: 10.16984/saufenbilder.99529 UR - https://doi.org/10.16984/saufenbilder.99529 Y2 - 2019 ER -
EndNote %0 Sakarya Üniversitesi Fen Bilimleri Enstitüsü Dergisi A hardware module design for percentage-based String Matching Problem %A Günay Temür , İbrahim Şahin %T A hardware module design for percentage-based String Matching Problem %D 2016 %J Sakarya University Journal of Science %P 1301-4048-2147-835X %V 20 %N 3 %R doi: 10.16984/saufenbilder.99529 %U 10.16984/saufenbilder.99529
ISNAD Temür, Günay , Şahin, İbrahim . "A hardware module design for percentage-based String Matching Problem". Sakarya University Journal of Science 20 / 3 (Eylül 2016): 441-450 . https://doi.org/10.16984/saufenbilder.99529
AMA Temür G , Şahin İ . A hardware module design for percentage-based String Matching Problem. SAUJS. 2016; 20(3): 441-450.
Vancouver Temür G , Şahin İ . A hardware module design for percentage-based String Matching Problem. Sakarya University Journal of Science. 2016; 20(3): 450-441.