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ı
- Tez No: 650818
- Danışmanlar: DR. ÖĞR. ÜYESİ ADNAN ÖZSOY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Hacettepe Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2019
Havacılık Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. BAYRAM ÇELİK
DOÇ. DR. KÜRŞAD MELİH GÜLEREN
- 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
2003
Astronomi ve Uzay Bilimleriİstanbul Teknik ÜniversitesiAstronomi ve Uzay Bilimleri Ana Bilim Dalı
PROF. DR. ÜLGEN GÜLÇAT
- 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
Yüksek Lisans
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiDOÇ. DR. CEVDET AYKANAT
- 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
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- 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
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MUHİTTİN GÖKMEN