जीएलएसएल में त्वरित प्रकार?

Question

मैं एक जीएलएसएल शेडर का उपयोग कर GPU को प्रसंस्करण के एक बड़े हिस्से को पोर्ट करने पर विचार कर रहा हूं। मैंने जिन समस्याओं को ठोकर खाई उनमें से एक यह है कि एक चरण में, एल्गोरिदम को तत्वों की एक सूची बनाए रखने, उन्हें क्रमबद्ध करने और कुछ सबसे बड़े (डेटा संख्या पर निर्भर है) लेने की आवश्यकता है। सीपीयू पर यह एक एसटीएल वेक्टर और qsort() का उपयोग करके किया जाता है लेकिन जीएलएसएल में मेरे पास ऐसी सुविधाएं नहीं हैं। क्या इस कमी से निपटने का कोई तरीका है?

Answer 1

प्रकटीकरण: मैं वास्तव में जीएलएसएल नहीं जानता - मैं एएमडी स्ट्रीम एसडीके के साथ जीपीजीपीयू प्रोग्रामिंग कर रहा हूं, जिसमें विभिन्न प्रोग्रामिंग भाषा है।

से आप ब्योर्न के जवाब पर टिप्पणी, मैं इकट्ठा कि आप एक विशाल डेटाबेस सॉर्ट करने के लिए GPU का उपयोग करके में कोई दिलचस्पी नहीं कर रहे हैं - एक रिवर्स फोन बुक या जो कुछ भी बनाने की तरह, लेकिन इसके बजाय, आप एक छोटे डाटासेट और प्रत्येक राशि खंड के क्रम में इसका अपना डेटासेट है। औसत पिक्सेल फ़िल्टरिंग करने की कोशिश करने की तरह?

मैं केवल सामान्य रूप में कह सकते हैं:

छोटे डेटासेट के लिए, प्रकार एल्गोरिथ्म वास्तव में कोई फर्क नहीं पड़ता। जबकि लोगों ने करियर खर्च किए हैं, इस बारे में चिंता करते हुए कि बहुत बड़े डेटाबेस के लिए सबसे अच्छा सॉर्ट एल्गोरिदम कौन सा है, छोटे एन के लिए यह वास्तव में कोई फर्क नहीं पड़ता कि आप त्वरित प्रकार, हीप सॉर्ट, रेडिक्स सॉर्ट, शैल सॉर्ट, ऑप्टिमाइज्ड बबल सॉर्ट, अनपॉटीमाइज्ड बबल सॉर्ट का उपयोग करते हैं या नहीं, आदि। कम से कम यह एक सीपीयू पर कोई फर्क नहीं पड़ता।

जीपीयू सिम डिवाइस हैं, इसलिए वे प्रत्येक कर्नेल को लॉक चरण में एक ही ऑपरेशन निष्पादित करना चाहते हैं। गणना सस्ते हैं लेकिन शाखाएं महंगी और डेटा-निर्भर शाखाएं हैं जहां प्रत्येक कर्नेल अलग-अलग तरीके से शाखाएं बहुत ही महंगी होती है।

तो यदि प्रत्येक कर्नेल के पास इसका छोटा डेटासेट सॉर्ट करने के लिए है, और सॉर्ट करने के लिए डेटा का # डेटा निर्भर है और यह प्रत्येक कर्नेल के लिए एक अलग संख्या हो सकता है, तो संभवतः आप अधिकतम आकार चुनने से बेहतर हैं (यदि आप कर सकते हैं), इन्फिनिटी या कुछ बड़ी संख्या के साथ सरणी को पैडिंग करना, और प्रत्येक कर्नेल एक ही प्रकार का सटीक प्रदर्शन करता है, जो एक अनियमित शाखा रहित बबल प्रकार होगा, इस तरह कुछ:

छद्मोकोड (चूंकि मुझे जीएलएसएल नहीं पता है) , 9 अंक

#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]); 
    } 
} 

Answer 2

क्या आपने यह लेख देखा है? https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html

मुझे यकीन नहीं था कि आप एक क्विक्सोर्ट एल्गोरिदम या त्वरित सॉर्टिंग एल्गोरिदम खोज रहे थे। आलेख में एल्गोरिदम मर्ज सॉर्ट का उपयोग करता है ...

Answer 3

की तरह मैं GPU प्रोग्रामिंग के बारे में कोई ज्ञान नहीं मिला है।

मैं क्विकॉर्ट के बजाए हेपसोर्ट का उपयोग करता हूं, क्योंकि आपने कहा था कि आपको केवल शीर्ष कुछ मानों को देखने की आवश्यकता है। ढेर O(n) समय में बनाया जा सकता है, लेकिन शीर्ष मूल्य प्राप्त करना log(n) है। इसलिए यदि आपको आवश्यक मूल्यों की संख्या उन तत्वों की कुल संख्या से काफी छोटी है जो आप कुछ प्रदर्शन प्राप्त कर सकते हैं।