Geri Dön

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

PDF İndir

  1. Tez No: 926203
  2. Yazar: BEYZA ÇAVUŞOĞLU
  3. Danışmanlar: DOÇ. DR. DİDEM UNAT ERTEN
  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: 2024
  8. Dil: İngilizce
  9. Üniversite: Koç Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Ö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

  1. Tez No

    401773

    A framework for analyzing application interference on GPUS

    Başlık çevirisi yok

    TUBA KESTEN

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolThe Pennsylvanıa State Unıversıty

    PROF. CHITA R. DAS

    PROF. MAHMUT T. KANDEMİR

  2. Tez No

    315266

    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

  3. Tez No

    835632

    Autonomous execution for multi-GPU systems: CPU-free blueprint and compiler support

    Çoklu GPU sistemleri için otonom yürütme: CPU'suz tasarım ve derleyici desteği

    JAVID BAYDAMIRLI

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    Assoc. Prof. Dr. DİDEM UNAT ERTEN

  4. Tez No

    416480

    GPU accelerated high-order discontinuous galerkin level set methods for incompressible multiphase flows

    Çok fazlı akışlar için yüksek başarımlı yüksek seviyeli süreksiz Galerkin metodları

    ALİ KARAKUŞ

    Doktora

    İngilizce

    İngilizce

    2015

    Makine MühendisliğiOrta Doğu Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET HALUK AKSEL

    YRD. DOÇ. DR. CÜNEYT SERT

  5. Tez No

    1013993

    Multi-Task U-Net Surrogate for Aerodynamic and Aeroacoustic Source Field Prediction of Airfoils

    Kanat Profillerinin Aerodinamik ve Aeroakustik Kaynak Alanı Tahmini için Çoklu Görev U-Net Vekil Modeli

    YUSUF AKTAŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    2026

    Uçak Mühendisliğiİstanbul Teknik Üniversitesi

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

    DOÇ. DR. BAHA ZAFER

Geri Dön