Yüksek performanslı çoklu-GPU eşzamanlı kuyruk algoritmalarınınimplementasyonu: Bellman-Ford SSSP'nin paralelleştirilmesi

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.