मैं डी प्रोग्रामिंग भाषा के लिए समांतरता पुस्तकालय पर काम कर रहा हूं। अब जब मैं बुनियादी प्राइमेटिव (समांतर फोरैच, मानचित्र, कम और कार्य/वायदा) से बहुत खुश हूं, तो मैं कुछ उच्च स्तर के समांतर एल्गोरिदम के बारे में सोचना शुरू कर रहा हूं। समांतरता के लिए अधिक स्पष्ट उम्मीदवारों में से एक है।(कब) समानांतर प्रकार के व्यावहारिक हैं और आप एक कुशल कैसे लिखते हैं?
मेरा पहला सवाल है, वास्तविक दुनिया में उपयोगी एल्गोरिदम को क्रमबद्ध करने के समानांतर संस्करण हैं, या वे ज्यादातर अकादमिक हैं? अगर वे उपयोगी हैं, तो वे कहाँ उपयोगी हैं? मैं व्यक्तिगत रूप से शायद ही कभी अपने काम में उनका उपयोग करता हूं, क्योंकि मैं आमतौर पर एक ही प्रकार() कॉल की तुलना में समांतरता के एक बहुत अधिक समेकित स्तर का उपयोग करके 100% पर अपने सभी कोरों को पेग करता हूं।
दूसरा, ऐसा लगता है कि त्वरित तरह से बड़े सरणी के लिए लगभग शर्मनाक समानांतर है, फिर भी मुझे लगता है कि मुझे लगता है कि मुझे मिलना चाहिए कि मुझे निकट-रैखिक गति मिल सकती है। एक त्वरित क्रम के लिए, केवल अंतर्निहित धारावाहिक भाग पहला विभाजन है। मैंने प्रत्येक विभाजन के बाद, समानांतर में दो subarrays को क्रमबद्ध करके, एक त्वरित क्रमांतर समानांतर करने की कोशिश की। सरलीकृत स्यूडोकोड में:
// I tweaked this number a bunch. Anything smaller than this and the
// overhead is smaller than the parallelization gains.
const smallestToParallelize = 500;
void quickSort(T)(T[] array) {
if(array.length < someConstant) {
insertionSort(array);
return;
}
size_t pivotPosition = partition(array);
if(array.length >= smallestToParallelize) {
// Sort left subarray in a task pool thread.
auto myTask = taskPool.execute(quickSort(array[0..pivotPosition]));
quickSort(array[pivotPosition + 1..$]);
myTask.workWait();
} else {
// Regular serial quick sort.
quickSort(array[0..pivotPosition]);
quickSort(array[pivotPosition + 1..$]);
}
}
यहां तक कि बहुत बड़ी सरणियाँ, जहां समय पहले विभाजन लेता नगण्य है के लिए, मैं यह कर सकते हैं केवल एल्गोरिथ्म के एक विशुद्ध रूप से धारावाहिक संस्करण की तुलना में एक दोहरे कोर पर एक 30% speedup, के बारे में मिलता है । मैं अनुमान लगा रहा हूं कि बाधा उत्पन्न स्मृति मेमोरी एक्सेस है। इस बाधा को खत्म करने के बारे में कोई अंतर्दृष्टि या बाधा क्या हो सकती है?
संपादित करें: मेरे कार्य पूल में सिस्टम की कम से कम कोर की संख्या के बराबर थ्रेड की निश्चित संख्या है (मुख्य धागा भी काम करता है)। साथ ही, जिस प्रकार का इंतजार मैं उपयोग कर रहा हूं वह एक काम प्रतीक्षा है, यानी यदि कार्य शुरू हो गया है लेकिन समाप्त नहीं हुआ है, तो workWait() कॉल करने वाले थ्रेड पूल से अन्य नौकरियों को चुरा लेता है और जब तक वह इंतजार कर रहा है तब तक ऐसा करता है। यदि कार्य शुरू नहीं हुआ है, तो यह वर्तमान धागे में पूरा हो गया है। इसका मतलब है कि प्रतीक्षा अक्षम नहीं है। जब तक काम करने के लिए काम किया जाता है, तब तक सभी धागे व्यस्त रहेंगे।
मैं नहीं जानता कि कैसे अपने quicksort बेहतर parallelize बनाने के लिए, लेकिन वहाँ एक संस्करण samplesort कहा जाता है जो मूल रूप से एक वेनिला quicksort की तुलना में बहुत तेजी से होता है, और है के रूप में जहाँ तक मैं देख सकते हैं, यह समानांतर समान होना चाहिए। –