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

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.

Türkçe insan dili ve edebiyatı dili ile anlamı nedir?

Bu algoritma, verilen bir sayı dizisinin elemanlarının sıralamasını, o sayıların birbirlerine olan büyüklük/küçüklük durumlarına göre değiştiriyor. Bunu yaparken de CPU kullanmıyor, yani o sırada CPU başka işleri yaparak programın çalışması daha da hızlandırılabiliyor. İlk mesajı dolmuşta telefondan tek parmakla basa basa, elimde alışveriş torbalarıyla atmıştım.

cevap için teşekkürler, peki bu yaptığı işlem nerelerde kullanılır?

Mesela 4 milyon tane atom var ve fiziksel modellemeyle çarpıştırılıyorlar ama atomların yerleri aynı zamanda RAM içerisindeki yeriyle de alakalı diyelim (atıyorum, uzayı sanal küplere böldük ve her küp içine bakarak, atom varsa hesap yapıyoruz). Çarpışa çarpışa yerleri değişiyor ve bir süre sonra RAM üzerinde rastgele erişim yapılmaya başlanıyor. Bu da performansı düşürüyor. Atomları bellek üzerinde yeniden sıralamak, erişimi tekrar doğrusal hale getirip işlemleri hızlandırır.

Sıralı bir veriyi işlemek daha hızlıdır. İşlemci mimarisi yüzünden böyle. Rastgele veriyi işlerken, işlemci sonraki adımın ne olduğunu tahmin edemiyor.

Aslında sıralı veriyi yavaş işlediğini bildiğim tek algoritma, quick-sort algoritması. Çünkü, algoritma, verinin sırasız olduğunu varsayarak çalışıyor. Bu yüzden de sıralı olan veriyi görünce çok yavaşlamayacak şekilde tasarladım. Hatta sıralı-sırasız ne gelirse önce biraz karıştırıyor da öyle işliyor.

Yazılımcı olmak istiyorum, nereden başlayabilirim, ne önerirsiniz? diye soranlar... şu kodu bir inceleyin, anlamaya gayret edin, kurcalayın...

Tebrikler bu arada!

Sağolun hocam. Algoritmayı biraz daha hızlandırdım ama thrust kütüphanesine göre çok yavaş kalıyor. Mesela thrust veya cuda'nın kendi sıralama algoritmalarının olduğu cub kütüpheneleri 1milyon elemanı 1 milisaniyeden kısa sürede sıralarken benimki 4-5 milisaniyede sıralıyor. Onların kullandığı algoritma binlerce küçük parçayı sıralayıp birleştirme üzerine kurulu. Benimki sadece 8 parçaya ayırıp sıralıyor. İçerisinde binary-search, reduction, vb çok çeşitli algoritma kullanıyor ama henüz açıklamaları eklemedim.

Ne iş olursa yaparım abi. Web sitesi, fiziksel simülasyon, veri tabanı, veri tabanı yonetimi, kimyasal simulasyon, ışın izleme ile görüntü oluşturma, fft ile gürültü azaltma, kalman filtresi ile gürültü azaltma, yeter ki iş olsun. Dershane yonetim programı, envanter kayıt programı, resim işleme programları, ... yeter ki ailem aç kalmasın. Cuda, OpenCL, biraz OpenGL bilgim de var. Labview, C++17, Qbasic, Java, Javascript, C# deneyimim var sadece ama olsun gerekirse yenisini de öğrenirim.

İyi de...

Ne iş olsa yaparım

ile

programcı/yazılımcı olarak ne iş yapabilirim

nasıl çok para kazanırım

vs.

... farklı yaklaşımlar.

Benim lafım yaklaşımı ikincideki gibi olanlara.

Hocam gpularda normal cpu kodu çalıştırabiliyormuyuz? Bir de nvidiaya bağımlı olmadan yazabilirmiyiz?

Hocam gpu'lar C ve C++ destekleyen cuda/opencl sürücülerine sahipler. Derleme işlemi benzer şekilde gerçekleşiyor ama derlemenin başında önce ara dile çevriliyor sonra gpu diline çevriliyor. Normal cpu kodundan kastınız buysa tabi. Yoksa dosya okuma, internete girme, cpu'ya komut gönderme gibi şeyler yok. Sadece kendi içerisinde yapabiliyorsa yapıyor.