Parallelization of the needleman-wunsch algorithm on graphical processing units
Grafik işlem birimleri üzerinde needleman-wunsch algoritmasının paraleleştirilmesi
- Tez No: 952978
- Danışmanlar: DR. ÖĞR. ÜYESİ AYŞE YILMAZER METİN
- 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: 2022
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 55
Özet
Benzerlik araştırması, iki seri arasındaki eşleşmeleri inceleyen tekniğin adırır. Bu teknik doğal dil işleme, biyoinformatik gibi birçok alanda kullanılır. Biyoinformatikte sıkça kullanılmasına rağmen uzun çalışma zamanına ihtiyaç duyan bir tekniktir. Elde edilen sonuca göre benzerlik araştırması iki ayrı gruba ayrılabilir. Yerel hizalama ve global hizalama, iki dizi arasındaki benzerlikleri hesaplamak için kullanılan iki yöntemdir. Yerel hizalama yöntemleri, dizilerin en benzer kısımlarına odaklanır ve elde edilen hizalama sonucu dizilerin boylarından daha kısa olabilir. Uzunlukları birbirinden çok farklı ya da aralarındaki benzerliğin görece düşük olduğu tahmin edilen dizilerin karşılaştırılması için ideal bir yöntemdir. Küresel hizalama yöntemleri tüm dizilere odaklanır ve elde edilen hizalama sonucu dizi boylarıyla, istisnai durumlar haricinde, aynıdır. Uzunlukları birbirine yakın ya da aralarındaki benzerliğin görece fazla olduğu tahmin edilen dizilerin karşılaştırılması için idealdir. Hizalama problemlerinin çözümü için birçok farklı algoritma önerilmiştir. Bunlardan en sık kullanılanları dinamik programlama tabanlı yöntemler ve sezgisel algoritmalardır. Dinamik programlama tabanlı algoritmalar kesin benzerlik sonucunu hesaplamarına karşın zaman ve alan karmaşıklıkları yüksektir. Bu nedenle kullanımları esnasında belirli kısıtlarla karşılaşabilirler. Sezgisel algoritmalar daha düşük karmaşıklığa sahip olmalarına rağmen hesaplama sonucu tahminidir. Bu nedenle her alanda kullanıma uygun olmayabilirler. Needleman-Wunsch algoritması, global dizi hizalamaları için kullanılan, dinamik programlama tabanlı, en yaygın olarak kullanılan algoritmalardan birisidir. Algoritma O(n^2) zaman ve uzay karmaşıklığına sahiptir. Üstel karmaşıklık derecesi ile birlikte incelenen dizi boylarının artması, algoritmanın koşma zamanının çok uzun olmasına ya da hizalama için gereken alanın çok büyük olmasına neden olmaktadır. Bu nedenle algoritmanın kullanımı görece daha küçük dizilerle sınırlanabilir. Algoritmanın üstel karmaşıklık derecesinin neden olduğu kısıtlamaları çözmek için çeşitli paralel ve dağıtılmış yöntemler önerilmiştir. Needleman-Wunsch algoritmasının paralelleştirilmesi için en sık kullanılan araçlardan biri de Grafik işleme birimleridir(Graphics Processing Unit[GPU]). GPU mimarilerinde bulunan ve paralel olarak çalışan çekirdekler, verileri aynı anda işlemelerine olanak tanır. Veriler her bir GPU çekirdeğinde işlenebilir. Bu Tek Komutlu Çoklu Veri(Single Instruction Multiple Data[SIMD]) yapısı, Needleman-Wunsch algoritmasında kullanılan matris işlemlerinin performansını artırır. Needleman-Wunsch algoritması ağırlıklı olarak matris işlemlerine dayanır. Bu nedenle GPU paralelleştirmesi için uygundur. Needleman-Wunsch algoritmasını bir GPU cihazında çalıştırmak performansını önemli ölçüde artırabilir. Ancak, GPU çekirdeği başlatma yükü ve düşük veri çıkışı cihazın performansından tam olarak yararlanılamamasına neden olabilir. Bu sorunun üstesinden gelmek için bu çalışmada, varolan GPU paralelleştirilme tekniklerinin yanı sıra CUDA Stream ve yeni senkronizasyon mekanizması olan CUDA Cooperative Groups kullanımının algoritma performansı üzerindeki etkileri incelendi. Önerilen paralel yaklaşımı daha uygun hale getirmek için Needleman-Wunsch verilerinin ana bellekte saklanma biçimi değiştirildi. Özetle, bu araştırma, paralel mimari kullanımı ile beraber verilerin bellekteki temsil biçimini değiştirerek veri aktarım performansını artırarak ve CUDA Cooperative Groups kullanarak GPU çağrılarının ek yükünü azaltarak daha uzun diziler için tek bir GPU ile benzerlik aramasını mümkün kılar.
Özet (Çeviri)
Similarity search is a fundamental yet time-consuming algorithm in bioinformatics. Local alignment and global alignment are two methods that are used to calculate similarities between two sequences. Local alignment methods focus on the most similar parts of sequences while global alignment methods focus on entire sequences. Many dynamic programming-based and heuristic algorithms are proposed to solve alignment problems. The Needleman-Wunsch algorithm is a well-known dynamic programming-based algorithm for global sequence alignments. The algorithm has O(n^2) time and space complexity. The quadratic complexity limits the use of the algorithm with relatively smaller sequences. Various parallel and distributed methods were proposed to overcome the quadratic complexity of the algorithm. Graphics processing units(GPU) are widely used in parallel computing. Their massively parallel architectures allow them to process data simultaneously. Data can be processed on each GPU core. This Single Instruction Multiple Data(SIMD) structure increases the performance of matrix operations. The Needleman-Wunsch algorithm heavily relies on matrix operations. Thus, it is suitable for GPU parallelization. Running the Needleman-Wunsch algorithm on a GPU device can be increase its performance significantly. However, GPU kernel launch overhead and low data throughput can limit the performance. To overcome this problem, CUDA Streams and new synchronization mechanism Cooperative Groups were applied to the parallel implementation. The memory representation of the Needleman-Wunsch data is changed in order to make it more suitable for the proposed parallel approach. In summary, this research makes similarity search with a single GPU possible for longer sequences by using massive parallelism, increasing data transfer throughput by changing memory representation, and decreasing API call overhead by using CUDA Cooperative Groups.
Benzer Tezler
- Parallelization of the fast multipole solution of the electromanyetic scattering problem
Elektromanyetik saçılım probleminin hızlı multipole çözümü paralelleştirme
ALİ AYUB KALUFYA
Yüksek Lisans
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Parallelization of the forward and inverse problems of electro-magnetic source imaging of the human brain
Elektro-manyetik kaynak görüntüleme ileri probleminin paralel bilgisayar ortamında çözülmesi
CAN ERKİN ACAR
Doktora
İngilizce
2003
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. NEVZAT GÜNERİ GENÇER
- Parçacık sürü ve karınca koloni optimizasyon algoritmalarının aç gözlü bilgi takası stratejisi kullanılarak paralelleştirilmesi
Parallelization of the particle swarm and ant colony optimization algorithms by using the greedy information swap strategy
ŞABAN GÜLCÜ
Doktora
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HALİFE KODAZ
- Çarpanlarına ayırma algoritmalarının paralelleştirilmesi
On parallelization of prime factorization algorithms
SELÇUK KESKİN
- Parallelization of K-means and DBSCAN clustering algorithms on a HPC cluster
DBSCAN ve K-means kümeleme algoritmalarının bir HPC kümesi üzerinde paralelleştirilmesi
HUNAIN DURRANI
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET COŞAR