सी ++ ओपनएमपी समानांतर लूप के लिए विकल्प - std :: वेक्टर

Question

इस धागे के आधार पर OpenMP and STL vector, कौन सा डेटा संरचना के लिए अच्छे विकल्प हैं std :: वेक्टर लूप के समानांतर में साझा किए गए हैं? मुख्य पहलू गति है, और वेक्टर को लूप के दौरान आकार बदलने की आवश्यकता हो सकती है।

Answer 1

आपके द्वारा लिंक किया गया सवाल इस तथ्य के बारे में बात कर रहा था कि "एसटीएल वेक्टर कंटेनर उस स्थिति में थ्रेड-सुरक्षित नहीं है जहां एकाधिक धागे एक कंटेनर को लिखते हैं"। यह केवल सत्य है, जैसा कि सही तरीके से कहा गया है, यदि आप उन विधियों को कॉल करते हैं जो std::vector धारण करने वाले अंतर्निहित सरणी के पुनर्वितरण का कारण बन सकते हैं। push_back(), pop_back() और insert() इन खतरनाक तरीकों के उदाहरण हैं।

यदि आपको थ्रेड सुरक्षित रीयलोकेशन की आवश्यकता है, तो लाइब्रेरी intel thread building block आपको concurrent vector containers प्रदान करती है। आपको एकल थ्रेड प्रोग्राम्स में tbb :: concurrent_vector का उपयोग नहीं करना चाहिए क्योंकि यादृच्छिक तत्वों तक पहुंचने में लगने वाला समय std :: वेक्टर ऐसा करने के लिए होता है (जो ओ (1) है)। हालांकि, समवर्ती वेक्टर push_back(), pop_back(), insert() को थ्रेड सुरक्षित तरीके से कॉल करता है, भले ही पुनर्वसन होता है।

संपादित करें 1: स्लाइड 46 और the following Intel presentation 47 का उपयोग कर TBB :: concurrent_vector

संपादित 2 समवर्ती पुनः आबंटन की एक उदाहराणदर्शक उदाहरण दे: यदि आप इंटेल चलने बिल्डिंग ब्लॉक का उपयोग शुरू वैसे, (यह खुला स्रोत है , यह अधिकांश कंपाइलर्स के साथ काम करता है और यह ओपनएमपी की तुलना में सी ++/सी ++ 11 फीचर्स के साथ बहुत बेहतर एकीकृत है), तो आपको parallel_for बनाने के लिए openmp का उपयोग करने की आवश्यकता नहीं है, Here tbb का उपयोग करके parallel_for का एक अच्छा उदाहरण है।

Answer 2

मुझे लगता है कि आप ओपनएमपी के साथ अधिकांश समय std::vector का उपयोग कर सकते हैं और अभी भी अच्छा प्रदर्शन कर सकते हैं। उदाहरण के लिए निम्नलिखित कोड समानांतर में std::vectors भरता है और फिर अंत में उन्हें जोड़ता है। जब तक आपका मुख्य पाश/भरने का कार्य बाधा है, तब तक इसे सामान्य रूप से अच्छी तरह से काम करना चाहिए और थ्रेड सुरक्षित होना चाहिए।

std::vector<int> vec; 
#pragma omp parallel 
{ 
    std::vector<int> vec_private; 
    #pragma omp for nowait //fill vec_private in parallel 
    for(int i=0; i<100; i++) { 
     vec_private.push_back(i); 
    } 
    #pragma omp critical 
    vec.insert(vec.end(), vec_private.begin(), vec_private.end()); 
} 

संपादित करें:

OpenMP 4.0 उपयोगकर्ता परिभाषित #pragma omp declare reduction का उपयोग कर में कटौती की अनुमति देता है। उपरोक्त कोड

#pragma omp declare reduction (merge : std::vector<int> : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end())) 

std::vector<int> vec; 
#pragma omp parallel for reduction(merge: vec) 
for(int i=0; i<100; i++) vec.push_back(i); 

के लिए संपादित करें के साथ सरल किया जा सकता: मैं अब तक क्या पता चला है क्रम में वेक्टर भर नहीं। आदेश मामलों तो यह इस

std::vector<int> vec; 
#pragma omp parallel 
{ 
    std::vector<int> vec_private; 
    #pragma omp for nowait schedule(static) 
    for(int i=0; i<N; i++) { 
     vec_private.push_back(i); 
    } 
    #pragma omp for schedule(static) ordered 
    for(int i=0; i<omp_get_num_threads(); i++) { 
     #pragma omp ordered 
     vec.insert(vec.end(), vec_private.begin(), vec_private.end()); 
    } 
} 

की तरह किया जा सकता है, तो यह प्रत्येक थ्रेड के लिए एक std :: वेक्टर बचत और फिर उन्हें समानांतर क्षेत्र के धारावाहिक के बाहर में विलय से बचा जाता है। मैंने इस "चाल" here के बारे में सीखा। मुझे यकीन नहीं है कि उपयोगकर्ता द्वारा निर्धारित कटौती के लिए यह कैसे करें (या यदि यह भी संभव है)।। उपयोगकर्ता परिभाषित कटौती के साथ ऐसा करना संभव नहीं है।

मुझे अभी एहसास हुआ कि महत्वपूर्ण अनुभाग आवश्यक नहीं है जिसे मैंने इस प्रश्न से parallel-cumulative-prefix-sums-in-openmp-communicating-values-between-thread से निकाला है। इस विधि को ऑर्डर सही भी है

std::vector<int> vec; 
size_t *prefix; 
#pragma omp parallel 
{ 
    int ithread = omp_get_thread_num(); 
    int nthreads = omp_get_num_threads(); 
    #pragma omp single 
    { 
     prefix = new size_t[nthreads+1]; 
     prefix[0] = 0; 
    } 
    std::vector<int> vec_private; 
    #pragma omp for schedule(static) nowait 
    for(int i=0; i<100; i++) { 
     vec_private.push_back(i); 
    } 
    prefix[ithread+1] = vec_private.size(); 
    #pragma omp barrier 
    #pragma omp single 
    { 
     for(int i=1; i<(nthreads+1); i++) prefix[i] += prefix[i-1]; 
     vec.resize(vec.size() + prefix[nthreads]); 
    } 
    std::copy(vec_private.begin(), vec_private.end(), vec.begin() + prefix[ithread]); 
} 
delete[] prefix;