High-performance multi-GPU concurrent queues: Case study with parallel Bellman-Ford SSSP
Yüksek performanslı çoklu-GPU eşzamanlı kuyruk algoritmalarınınimplementasyonu: Bellman-Ford SSSP'nin paralelleştirilmesi
- Tez No: 926203
- Danışmanlar: DOÇ. DR. DİDEM UNAT ERTEN
- 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: 2024
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 63
Özet
Bu tez, tek-GPU ve çoklu-GPU ortamlarında uygulanan yeni bir eşzamanlı FIFO kuyruk algoritmasının implementasyonunu sunmaktadır. Bu algoritma, Tek Kaynaklı En Kısa Yol (SSSP) problemi için Bellman-Ford algoritmasına uygulanmıştır. Bu çalışmanın temel katkısı, daha önce keşfedilmemiş olan, NVIDIA'nın NVSHMEM teknolojisini kullanan çoklu-GPU concurrent kuyruk sisteminin tasarımı ve implementasyonudur. Bellman-Ford algoritması, önerilen kuyruk sisteminin performansını değerlendirmek amacıyla bir vaka çalışması olarak kullanılmaktadır ve bu çoklu-GPU implementasyonu, bilinen ilk örnek olarak öne çıkmaktadır. Deneysel sonuçlar, çoklu-GPU kuyruk implementasyonunun, dört NVIDIA A100 GPU üzerinde tek-GPU temel performansına kıyasla maksimum 3.92x hız artışı ve ortalama 3.04x hız artışı sağladığını göstermektedir. Bellman-Ford algoritması uygulandığında ise, çoklu-GPU sistemi, tek-GPU implementasyonuna kıyasla maksimum 3.794× hız artışı ve ortalama 3.573× hız artışı elde etmektedir, üretilmiş bir graf ve SuiteSparse Matrix Collection'dan alınan 10 farklı türde graf üzerinde test edilmiştir. Bu bulgular, çoklu-GPU kuyruk sisteminin grafik işleme görevlerinde verimliliğini vurgulamaktadır ve paralel hesaplamadaki pratik zorlukları ele alarak yüksek performanslı hesaplama alanında önemli bir katkı sağlamaktadır.
Özet (Çeviri)
This thesis presents a novel implementation of a concurrent FIFO queue algorithm for both single-GPU and multi-GPU environments, applied to the Single-Source Shortest Path (SSSP) Bellman-Ford algorithm. The primary contribution of this work is the design and implementation of a multi-GPU concurrent queue system using NVIDIA's NVSHMEM, which has not been previously explored. The Bellman-Ford algorithm is used as a case study to evaluate the performance of the proposed queue system, with this multi-GPU implementation being the first known instance of its kind. Experimental results demonstrate that the multi-GPU queue implementation achieves a maximum speedup of 3.92x and an average speedup of 3.04x over the single-GPU baseline on four NVIDIA A100 GPUs. When applied to the Bellman-Ford algorithm, the multi-GPU system achieves a maximum speedup of 3.794× and an average speedup of 3.573× compared to the single-GPU implementation, tested on a generated benchmark and 10 graphs of different kinds taken from the SuiteSparse Matrix Collection. These findings highlight the efficiency of the multi-GPU queue system for graph processing tasks and contribute to advancements in high-performance computing by addressing practical challenges in parallel computing.
Benzer Tezler
- A framework for analyzing application interference on GPUS
Başlık çevirisi yok
TUBA KESTEN
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolThe Pennsylvania State UniversityPROF. CHITA R. DAS
PROF. MAHMUT T. KANDEMİR
- 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
- GPU-centric communication schemes: When CPUs take a back seat
GPU-odaklı haberleşme sistemleri: CPU'ların arka koltuğa geçtiği zamanlar
ISMAYIL ISMAYILOV
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. DİDEM UNAT ERTEN
- Ultra-fast influence maximization with fused sampling and sketches
Örneklem birleştirme ve veri özetleri ile yüksek performanslı etki eniyilemesi
GÖKHAN GÖKTÜRK
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ KAMER KAYA
- Çoklu otonom insansız hava araçları için paralel programlama tabanlı yol planlaması
Parallel programming based path planning for multi autonomous unmmaned vehicles
ÖMER ÇETİN
Doktora
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHava Harp Okulu KomutanlığıBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜRAY YILMAZ