Geri Dön

Effective and efficient parallelization of string matching algorithms using GPGPU accelerators

Dizgi eşleme algoritmalarırnın GPGPU hızlandırıcıları kullanılarak etkili ve verimli hızlandırılması

  1. Tez No: 650818
  2. Yazar: MENGÜ NAZLI
  3. Danışmanlar: DR. ÖĞR. ÜYESİ ADNAN ÖZSOY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2020
  8. Dil: İngilizce
  9. Üniversite: Hacettepe Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 117

Özet

Dizgi eşleme, bilgisayar bilimlerinin en eski ve üzerinde en çok çalışılan konularından biridir. Bilgisayar güvenliği, biyoinformatik, sosyal medya işleme, veri madenciliği, veri sıkıştırma, kodlama teorisi ve benzeri pek çok alanda dizgi işleme uygulamalarına rastlanmaktadır. 1970'lerden bu yana dizgi eşleme problemi üzerine pek çok farklı performans karakteristiğine ve çalışma şekline sahip algoritma önerilmiştir. Bu alandaki çalışmaların çeşitliliği, kapsamlı bir karşılaştırmanın hazırlanmasını zor kılsa da, Thierry Lecroq ve Simone Faro tarafından geliştirilen SMART kütüphanesi gibi bu hedefe ulaşmış birkaç çalışmaya rastlanmaktadır. Bu kütüphane, dizgi işleme alanında çalışmak, literatürdeki algoritmaları karşılaştırmak ve yeni algoritmalar geliştirip mevcut algoritmalarla kıyaslamak isteyen araştırmacılar için değerli bir kaynaktır. Ancak kütüphanedeki kodların seri olarak çalışacak şekilde geliştirilmiş olması, içinde bulunduğumuz yüksek performanslı paralel hesaplama çağında bu kütüphanenin uygulamadaki pratikliğini azaltmaktadır. Bu çalışmada, benzer bir kütüphaneyi Nvidia tarafından geliştirilen CUDA platformundan yararlanarak paralel bir şekilde hazırladık ve dizgi eşleme algoritmalarının paralel çalışma performanslarını incelemeyi amaçladık. CUSMART adı verdiğimiz kütüphanede CUDA C++ programlama arayüzünü kullanarak 85'den fazla dizgi eşleme algoritmasının paralel ortama aktardık ve bu algoritmaları farklı senaryolarda test ederek algoritmaların güçlü ve zayıf yanlarını adil bir şekilde karşılaştırabilmeyi hedefledik. Hazırladığımız algoritmaları hem Nvidia tarafından geliştirilen mobil platform Jetson'da, hem de genel kullanım için piyasaya sürülmüş olan GeForce serisi kartlarda test ettik. Elde ettiğimiz sonuçlar, aynı algoritmaların seri CPU versiyonlarına göre ortalama 40 kat daha hızlı çalıştığını göstermekte ve GPGPU platformunun dizli işleme uygulamalarındaki potansiyeline işaret etmektedir.

Özet (Çeviri)

String matching is one of the oldest and actively studied problems in computer science. It has applications in computer security, bio-informatics, social media processing, data mining, data compression, coding theory, and many other areas. Since the '70s, there have been dozens of proposed algorithms to this problem with different approaches and performance characteristics. While the sheer amount of proposed algorithms makes it hard to put together a comprehensive performance comparison study, there are a few projects like the String Matching Algorithms Research Tool (SMART) library from Thierry Lecroq and Simone Faro achieving this goal. Their library holds the code implementations for the majority of string matching algorithms in the literature. It is an invaluable tool for studying different string matching algorithms, but it lacks practicality because of its serial implementation in the age of parallel computation. Our aim is to present a parallel version of the library realized on the CUDA platform by Nvidia, employing GPGPU programming concepts for improved performance and gain insight on the parallel versions of these algorithms. We have developed CUSMART library, which contains parallelized versions of around 85 string matching algorithms using CUDA API. The performances of these algorithms are tested with different scenarios to get a fair comparison and determine their strong/weak application scenarios. Also, we have investigated some well-known optimization practices to observe how they impact the performance of these algorithms. Our results show an average of 40x speedup compared to the serial CPU version of algorithms indicating the potential of GPGPU computing on string matching applications.

Benzer Tezler

  1. A numerical investigation on passive flow controls of open cavities at transonic speeds

    Açık kavitelerin pasif kontrolünün transonik akışlarda sayısal incelenmesi

    OĞUZHAN DEMİR

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Havacılık Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BAYRAM ÇELİK

    DOÇ. DR. KÜRŞAD MELİH GÜLEREN

  2. Parallel solution of unsteady, incompressible three-dimensional Navier-Stokes equations with a new implicit method

    Zamana bağlı, sıkıştırılamaz, üç boyutlu Navier-Stokes denklemlerinin yeni bir kapalı metodlar paralel çözümü

    VİLDAN ÜSTOĞLU ÜNAL

    Doktora

    İngilizce

    İngilizce

    2003

    Astronomi ve Uzay Bilimleriİstanbul Teknik Üniversitesi

    Astronomi ve Uzay Bilimleri Ana Bilim Dalı

    PROF. DR. ÜLGEN GÜLÇAT

  3. Parallel direct volume rendening of unsructed grids based on object-space decomposition

    Düzensiz ızgaraların obje uzayı bölünmesine dayanan paralel hacim görüntülenmesi

    FERİT FINDIK

  4. Reducing communication volume overhead in large-scale parallel SpGEMM

    Büyük ölçekli paralel SyGEMM'de iletişim hacmini düşürme

    BAŞAK ÜNSAL

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

  5. Fast face detection and recognition on graphics processing units

    Grafik işlemciler üzerinde hızlı yüz saptama ve tanıma

    SALİH CİHAN TEK

    Yüksek Lisans

    İngilizce

    İngilizce

    2012

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. MUHİTTİN GÖKMEN