मुझे GPU पर एक सुंदर मानक समस्या हल करने के लिए मिला है, लेकिन मैं व्यावहारिक GPGPU के लिए काफी नया हूं, इसलिए मैं इस समस्या से संपर्क करने के लिए विचारों की तलाश में हूं।बिखरे हुए खंडों के साथ खंडित कमी
मेरे पास 3-स्पेस में बहुत से अंक हैं जो समूहों की एक बहुत छोटी संख्या (प्रत्येक बिंदु एक समूह से संबंधित है) को सौंपा गया है, विशेष रूप से 15 इस मामले में (कभी नहीं बदला जाता है)। अब मैं सभी समूहों के माध्य और कॉन्वर्सिस मैट्रिक्स की गणना करना चाहता हूं। तो CPU पर यह मोटे तौर पर के रूप में ही है:
for each point p
{
mean[p.group] += p.pos;
covariance[p.group] += p.pos * p.pos;
++count[p.group];
}
for each group g
{
mean[g] /= count[g];
covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}
के बाद से समूहों की संख्या अत्यंत छोटा है, अंतिम चरण के सीपीयू (मैं CPU पर उन मूल्यों, वैसे भी जरूरत है) पर किया जा सकता। पहला कदम वास्तव में सिर्फ एक खंडित कमी है, लेकिन आसपास के खंडों के साथ।
तो पहला विचार जो मैं आया था, पहले अपने समूहों द्वारा अंक को क्रमबद्ध करना था। मैंने बाल्टी आकार और प्रति-बिंदु स्थानांतरण स्थान की गणना करने के लिए atomic_inc का उपयोग करके एक साधारण बाल्टी सॉर्ट के बारे में सोचा (सॉर्टिंग के लिए एक बेहतर विचार मिला ?, परमाणु सबसे अच्छा विचार नहीं हो सकता है)। उसके बाद उन्हें समूहों द्वारा क्रमबद्ध किया जाता है और मैं संभवतः here प्रस्तुत खंडित स्कैन एल्गोरिदम के अनुकूलन के साथ आ सकता हूं।
लेकिन इस विशेष मामले में, मुझे प्रति बिंदु (9-10 फ्लोट्स, शायद आवश्यकता होने पर भी दोगुना हो सकता है) में बहुत बड़ी मात्रा मिली है, इसलिए प्रति थ्रेड प्रति साझा किए गए मेमोरी तत्व का उपयोग करके मानक एल्गोरिदम और प्रति थ्रेड बिंदु प्रति-मल्टीप्रोसेसर संसाधनों के बारे में साझा स्मृति या रजिस्टरों के रूप में समस्याएं उत्पन्न कर सकता है (ठीक है, 2.x की तुलना में गणना क्षमता 1.x पर बहुत अधिक है, लेकिन फिर भी)।
समूहों की बहुत छोटी और निरंतर संख्या के कारण मैंने सोचा कि बेहतर दृष्टिकोण हो सकते हैं। हो सकता है कि इस तरह की एक मानक समस्या के इन विशिष्ट गुणों के लिए पहले से ही मौजूदा विचार उपयुक्त हैं। या शायद मेरा सामान्य दृष्टिकोण बुरा नहीं है और आपको अलग-अलग चरणों में सुधार के लिए विचार मिलते हैं, जैसे कि एक बहुत ही कम संख्या में कुंजी या कुछ खंडित कमी एल्गोरिदम साझा स्मृति/पंजीकरण उपयोग को कम करने के लिए उपयुक्त एक अच्छा सॉर्टिंग एल्गोरिदम।
मैं सामान्य दृष्टिकोण ढूंढ रहा हूं और बाहरी पुस्तकालयों का उपयोग नहीं करना चाहता हूं। एफडब्ल्यूआईडब्ल्यू मैं ओपनसीएल का उपयोग कर रहा हूं, लेकिन यह वास्तव में कोई फर्क नहीं पड़ता क्योंकि GPU कंप्यूटिंग की सामान्य अवधारणाएं मुख्य ढांचे पर वास्तव में भिन्न नहीं होती हैं।
यह एक सुंदर आम पैटर्न है। जोर का उपयोग करके, आप प्रत्येक सेगमेंट में डेटा को एक साथ लाने के लिए पहले 'sort_by_key' और फिर प्रत्येक समूह के माध्य और कॉन्वर्सिस की गणना करने के लिए' reduce_by_key' 'करेंगे। –