Bir GLSL gölgelendirici kullanarak GPU'ya büyük bir yığın işleme koymayı düşünüyorum. Karşılaştığım acil problemlerden biri, adımlardan birinde algoritmanın bir elemanlar listesi tutması, sıralaması ve en az birkaçını alması gerektiğidir (bu sayı verilere bağlıdır). CPU üzerinde bu sadece bir STL vektörü ve qsort() kullanılarak yapılır, ancak GLSL'de böyle bir olanak yok. Bu eksiklikle başa çıkmanın bir yolu var mı?GLSL'de hızlı sıralama?
Bildirim: Gerçekten GLSL'yi bilmiyorum - Farklı programlama diline sahip AMD Stream SDK ile GPGPU programlama yapıyorum.
Eğer Bjorn'ün cevap üzerine yorum itibaren
, sana büyük bir veritabanı sıralamak için GPU kullanarak içinde ilgilenmiyor olduğunu toplamak - bir ters telefon rehberi ya da her neyse oluşturma gibi, ancak bunun yerine, küçük bir veri kümesi ve her biri Parça, sıralamak için kendi veri kümesine sahiptir. Daha çok medyan piksel filtreleme yapmaya çalışmak gibi mi?Ben sadece genel olarak söyleyebiliriz: küçük veri kümelerinde için
, sıralama algoritması gerçekten önemli değil. Insanlar çok büyük veritabanları için en iyi sıralama algoritması hakkında endişe verici kariyer yaparken, küçük N için gerçekten hızlı sıralama, yığın sıralaması, Radix sıralama, kabuk sıralamasında, optimize edilmiş kabarcık sıralamasında, Unoptimized Kabarcık sort, En azından bir CPU üzerinde çok önemli değil.
GPU'lar SIMD aygıtlarıdır, bu nedenle her çekirdek işleminin aynı işlemleri kilit adımında yürütmesini isterler. Hesaplamalar ucuzdur, ancak dallar pahalıdır ve her çekirdeğin dallarının farklı bir şekilde birbirinden farklı olduğu dallara çok, çok, çok pahalıdır.
Bu nedenle, her çekirdeğin sıralamak için kendi küçük veri kümesi varsa ve sıralanacak veri sayısı veriye bağımlıysa ve her çekirdek için farklı bir sayı olabilirse, muhtemelen maksimum boyut seçmenizden daha iyidir. can), dizileri Sonsuzluk veya bazı büyük sayılarla doldurma ve her çekirdeğin tam olarak aynı sıralama gerçekleştirmesi, ki bu da bu gibi bir şeysizleştirilmiş dalsız kabarcık dizisi olurdu:
Pseudocode (GLSL'yi bilmiyorum) 9 puan
#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; }
for (size_t n = 8; n ; --n) {
for (size_t i = 0; i < n; ++i) {
TwoSort (A[i], A[i+1]);
}
}
Çok hoş. Tam olarak aradığım şey bu. Veriye bağlı şubelerin dezavantajları ile ilgili referanslarınız var mı? – shoosh
Başımın üst kısmından hiç referansım yok. BTW, Quicksort'un GPU'larda çalışmadığı başka bir nedenden dolayı, özyinelemeyi desteklemiyorlar. –
Özyineleme sadece başka bir döngüdür. Yani hemen hemen tüm özyineleme durumları while/For döngüler olarak yeniden yazılabilir. –
Bu makaleyi gördünüz mü? https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html
Quicksort algoritması veya hızlı sıralama algoritması aradığınızdan emin değildim. Makaledeki algoritma birleştirme sıralamasını kullanır ...
Evet, MergeSort'un bir SIMD platformunda (bellek lokalizasyonu nedeniyle) QuickSort'tan daha çok çalışmasını sağladığını düşünüyorum. –
Bir geçişte tam bir sıralama arıyordum çünkü sıralama, algoritmamda her parça için çalışması gereken tek adım. – shoosh
Çok iyi cevap. Makaledeki algoritmalar iyidir. Bitonik sıralayıcı FTW :-) – ypnos
tür ben GPU programlama hakkında herhangi bir bilgi yok.
Quicksort yerine heapsort kullanırdım, çünkü yalnızca en az birkaç değere bakmanız gerektiğini söylediniz. Yığın O(n) zamanında yapılabilir, ancak en üstteki değer log(n) olur. Bu nedenle, ihtiyacınız olan değerlerin sayısı, toplam öğe sayısından önemli ölçüde daha küçükse, performansınızı artırabilirsiniz.
GPU'nun hızlı ayrıştırmada iyi olup olmadığını merak ediyorum ... –