CUDA ile çalışan quicksort algoritması geliştirdim.

Aşağı Git Tüm Forumlar Web Tasarım - Programlama Yazılım Geliştirme Delphi / C++ /Vb CUDA ile çalışan quicksort algoritması geliştirdim.

Bu konudaki kullanıcılar: 1 misafir

11
Cevap 360
Tıklama 1
Öne Çıkarma

1. sayfa

CUDA ile çalışan quicksort algoritması geliştirdim.

Cevap Yaz

Tugrul_512bit

geçen yıl (15004 mesaj)

Yarbay

Konu Sahibi

std::sort 'un 5 katı, std::qsort 'un 10 katı hızda. Sıralama yapılırken işlemci asenkron olarak başka iş yapabiliyor yani bekleme yapmıyor.

tugrul512bit/TurtleSort: Quicksort with 3 pivots, CUDA acceleration and adaptive sorting algorithm for different chunk sizes. (github.com)

Şu anda tamamen optimize değil. Bi 5 kat daha hızlandırılabilir belki.

Mantık şöyle:

Diziyi 4 parçaya bölüyor. Ama bölümler birbirini ayıran noktalara göre sıralı. Sonra onları da kendi içlerinde bölmeye devam ediyor. En sonunda dizi sıralanmış oluyor.

Sıralanmış dizi verilince 2 kat yavaşlıyor yani hala std::sort'un üstünde.

Bölümlerden biri 1024 eleman veya daha az ise, daha hızlı çalışan bir sıralama algoritması kullanıyor. 1024 thead ile paralel çalışan bubble sort (odd-even olan) kullanıyor. Eleman sayısı 2-3 ise doğrudan sıralamayı 2 satırda yapıp veriyor.

Çok sayıda tekrar eden sayı varsa yaklaşık 3 kat daha hızlanıyor. Mesela 64 milyon elemanı 0.15 saniyede sıralıyor. Rastgeleyken 0.5 saniye. Sıralıyken 1 saniye. Sistemde rtx 4070 ve ryzen 7900 varken bu hızda. 4090 olsa 2-3 kat daha hızlanır.

< Bu mesaj bu kişi tarafından değiştirildi Tugrul_512bit -- 26 Eylül 2024; 10:21:9 >

< Bu ileti mobil sürüm kullanılarak atıldı >

Cevap Yaz

1. sayfa

Tüm Forumlar Web Tasarım - Programlama Yazılım Geliştirme Delphi / C++ /Vb CUDA ile çalışan quicksort algoritması geliştirdim.