एसटीएल के समांतर एल्गोरिदम का उपयोग कर उपयोगकर्ता पर बाधाएं क्या हैं?

Question

जैक्सनविले में प्रस्ताव P0024r2 को प्रभावी ढंग से Parallelism TS से विनिर्देशों को अपनाने के लिए C++17 (draft) में स्वीकार किया गया था। यह प्रस्ताव निष्पादन नीति तर्क लेने वाले कई एल्गोरिदम के लिए अधिभार जोड़ता है यह इंगित करने के लिए कि किस प्रकार की समांतरता पर विचार किया जाना चाहिए।

• std::execution::sequenced_policy एक constexpr वस्तु के साथ (20.19.4 [execpol.seq]) std::execution::seq (20.19.7 [parallel.execpol.objects: तीन निष्पादन नीतियों पहले से ही में <execution> (20.19.2 [निष्पादन]) में परिभाषित कर रहे हैं ]) निष्पादन नीति के बिना एल्गोरिदम को कॉल करने के समान अनुक्रमिक निष्पादन को इंगित करने के लिए।
• std::execution::parallel_policy (20.19.5 [execpol.par]) constexpr ऑब्जेक्ट std::execution::par (20.19.7 [parallel.execpol.objects]) के साथ संभावित रूप से एकाधिक धागे का उपयोग करके एल्गोरिदम के निष्पादन को इंगित करने के लिए।
• std::execution::parallel_unsequenced_policy एक constexpr वस्तु std::execution::par_unseq (20.19.7 [parallel.execpol.objects]) एल्गोरिदम संभावित वेक्टर निष्पादन और/या एक से अधिक थ्रेड का उपयोग कर के निष्पादन को इंगित करने के साथ (20.19.6 [execpol.vec])।

एसटीएल एल्गोरिदम आमतौर पर उपयोगकर्ता परिभाषित वस्तुओं (इटरेटर, फ़ंक्शन ऑब्जेक्ट्स) तर्क के रूप में लेते हैं। मानक निष्पादन नीतियों का उपयोग करके समांतर एल्गोरिदम के साथ उपयोग करने योग्य बनाने के लिए उपयोगकर्ता द्वारा परिभाषित वस्तुओं पर बाधाएं क्या हैं?

उदाहरण के लिए, नीचे दिए गए उदाहरण में एल्गोरिदम का उपयोग करते समय, FwdIt और Predicate के लिए क्या प्रभाव हैं? निष्पादन नीति std::execution::parallel का उपयोग कर एल्गोरिदम के साथ प्रयोग किया, (नीचे विवरण देखें अनिवार्य रूप से संचालन के लिए विभिन्न तर्क पर एल्गोरिदम द्वारा अपेक्षित) डेटा पैदा करने के लिए अनुमति नहीं है

template <typename FwdIt, typename Predicate> 
FwdIt call_remove_if(FwdIt begin, FwdIt end, Predicate predicate) { 
    return std::remove_if(std::execution::par, begin, end, predicate); 
} 

Answer 1

संक्षिप्त उत्तर है कि तत्व पहुंच कार्यों है दौड़ या मृत-ताले। निष्पादन नीति std::execution::parallel_unsequenced_policy का उपयोग करके एल्गोरिदम के साथ उपयोग किए जाने वाले तत्व पहुंच फ़ंक्शंस अतिरिक्त रूप से किसी अवरुद्ध सिंक्रनाइज़ेशन का उपयोग नहीं कर सकते हैं।

विवरण

वर्णन मतदान दस्तावेज़ N4604 पर आधारित है। मैंने सत्यापित नहीं किया है कि कुछ खंडों को राष्ट्रीय निकाय टिप्पणियों के जवाब में संशोधित किया गया था (एक सरसरी जांच का अर्थ यह है कि अब तक कोई संपादन नहीं था)।

धारा 25.2 [एल्गोरिदम .parallel] समांतर एल्गोरिदम के अर्थशास्त्र निर्दिष्ट करता है।

1. 25.2.2 में [algorithms.parallel.user] रोकें क्या विधेय कार्यों उनके तर्कों को कर सकते हैं: एक से अधिक की कमी जो एल्गोरिदम पर लागू नहीं हैं एक निष्पादन नीति, कई वर्गों में टूट नहीं ले रहे हैं :

   समारोह वस्तुओं प्रकार Predicate, BinaryPredicate, Compare की वस्तुओं के रूप में समानांतर एल्गोरिदम में पारित कर दिया, और BinaryOperation नहीं करेगा प्रत्यक्ष या परोक्ष रूप उनके तर्कों के माध्यम से वस्तुओं को संशोधित।

   रास्ता खंड लिखा है लगता है कि खुद वस्तुओं रूप में लंबे समय के रूप में अन्य बाधाओं (नीचे देखें) का पालन कर रहे हैं संशोधित किया जा सकता। ध्यान दें कि यह बाधा निष्पादन नीति से स्वतंत्र है और इस प्रकार, std::execution::sequenced_policy का उपयोग करते समय भी लागू होती है। पूरा उत्तर उससे अधिक जटिल है और ऐसा लगता है कि विनिर्देश वर्तमान में अनजाने में बाधित है (नीचे अंतिम पैराग्राफ देखें)।

   • std::execution::sequenced_policy तत्व पहुंच कार्यों का उपयोग करते समय:

   • 25.2.3 [algorithms.parallel.exec] में तत्व पहुंच कार्यों पर बाधाओं (देखें नीचे) जो विभिन्न निष्पादन नीतियों के लिए विशिष्ट हैं कहते हैं सभी को एक ही धागे से बुलाया जाता है, यानी, निष्पादन किसी भी रूप में interleaved नहीं है।

   • std::execution::parallel_policy का उपयोग करते समय विभिन्न धागे अलग-अलग धागे से तत्व पहुंच कार्यों को एक साथ जोड़ सकते हैं। विभिन्न धागे से तत्व पहुंच कार्यों को आमंत्रित करने से डेटा दौड़ या मृत-ताले का कारण बनने की अनुमति नहीं है। हालांकि, एक ही थ्रेड से तत्व पहुंच के आविष्कार [अनिश्चित रूप से] अनुक्रम हैं, यानी, एक ही थ्रेड से तत्व पहुंच फ़ंक्शन का कोई अंतःस्थापित आमंत्रण नहीं है। उदाहरण के लिए, यदि Predicatestd::execution::par के साथ उपयोग किया जाता है तो यह कितनी बार कहा जाता है, संबंधित गणना को उचित रूप से सिंक्रनाइज़ करने की आवश्यकता होगी।

   • std::execution::parallel_unsequenced_policy का उपयोग करते समय तत्व पहुंच कार्यों का आविष्कार अलग-अलग थ्रेड के साथ-साथ निष्पादन के एक थ्रेड के बीच दोनों को अलग किया जा सकता है। यही है, अवरुद्ध सिंक्रनाइज़ेशन आदिम (जैसे std::mutex) का उपयोग मृत-लॉक का कारण बन सकता है क्योंकि एक ही थ्रेड कई बार सिंक्रनाइज़ करने का प्रयास कर सकता है (और, उदाहरण के लिए, एक ही म्यूटेक्स को कई बार लॉक करने का प्रयास करें)। तत्व पहुंच कार्यों के लिए मानक पुस्तकालय कार्यों का उपयोग करते समय मानक में बाधा है (25.2.3 [algorithms.parallel.exec] पैरा 4):

     एक मानक पुस्तकालय समारोह vectorization-असुरक्षित अगर यह सिंक्रनाइज़ करने के लिए निर्दिष्ट किया जाता है है किसी अन्य फ़ंक्शन आमंत्रण के साथ, या किसी अन्य फ़ंक्शन आमंत्रण को इसके साथ सिंक्रनाइज़ करने के लिए निर्दिष्ट किया गया है, और यदि यह स्मृति आवंटन या डेलोकेशन फ़ंक्शन नहीं है। वेक्टरेशन-असुरक्षित मानक लाइब्रेरी फ़ंक्शंस को उपयोगकर्ता कोड द्वारा execution::parallel_unsequenced_policy एल्गोरिदम से बुलाया नहीं जा सकता है।

   • क्रियान्वयन परिभाषित निष्पादन नीतियों का उपयोग करते समय क्या होता है, असुरक्षित रूप से, कार्यान्वयन परिभाषित किया जाता है।

2. 25.2.4 में [algorithm.parallel.exception] तत्व पहुंच कार्यों से फेंका अपवाद के उपयोग एक तरह से विवश है: एक तत्व का उपयोग समारोह एक अपवाद फेंकता है जब, std::terminate() कहा जाता है। यही है, अपवाद फेंकना कानूनी है लेकिन यह संभावना नहीं है कि परिणाम वांछनीय है। ध्यान दें कि को std::execution::sequenced_policy का उपयोग करते समय भी कॉल किया जाएगा।

तत्व पहुंच

उपयोग ऊपर की कमी अवधि तत्व पहुंच समारोह कार्य करता है। यह शब्द 25.2.1 [algorithm.parallel.defns] अनुच्छेद 2 में परिभाषित किया गया है।

• iterators कि एल्गोरिथ्म के साथ instantiated है श्रेणियों में से सभी आपरेशनों: तत्व पहुंच कार्यों के रूप में वर्गीकृत कार्यों के चार समूहों रहे हैं।
• उनके अनुक्रम द्वारा आवश्यक अनुक्रम तत्वों पर संचालन।
• उपयोगकर्ता द्वारा प्रदत्त फ़ंक्शन ऑब्जेक्ट्स को एल्गोरिदम के निष्पादन के दौरान लागू किया जाना चाहिए, यदि विनिर्देशन के अनुसार आवश्यक हो।
• विनिर्देशन द्वारा आवश्यक उन फ़ंक्शन ऑब्जेक्ट्स पर संचालन।

अनिवार्य रूप से, तत्व पहुंच कार्यों सभी कार्यों जो मानक स्पष्ट रूप से एल्गोरिदम या इन एल्गोरिदम के साथ प्रयोग किया अवधारणाओं के विनिर्देश में को संदर्भित करता है। फ़ंक्शंस का उल्लेख नहीं किया गया है और, उदाहरण के लिए, मौजूद होने के लिए पता चला है (उदा।, SFINAE का उपयोग करके) को बाध्य नहीं किया जाता है और प्रभावी रूप से, उनके उपयोग पर सिंक्रनाइज़ेशन बाधाओं को लागू करने वाले समांतर एल्गोरिदम से नहीं कहा जा सकता है।

समस्या

यह थोड़ा के विषय में है तो कोई गारंटी नहीं है कि वस्तुओं [परिवर्तनशील] तत्व पहुंच कार्यों पर लागू होने वाली विभिन्न धागे के बीच अलग हैं प्रतीत हो रहा है कि। विशेष रूप से, मुझे कोई गारंटी नहीं दिखाई दे रही है कि इटरेटर ऑब्जेक्ट पर लागू इटरेटर ऑपरेशंस को दो अलग-अलग धागे से उसी इटरेटर ऑब्जेक्ट पर लागू नहीं किया जा सकता है! निहितार्थ यह है कि, उदाहरण के लिए, एक इटरेटर ऑब्जेक्ट पर operator++() किसी भी तरह से इसके राज्य को सिंक्रनाइज़ करने की आवश्यकता होगी। मैं नहीं देख सकता कि कैसे, उदाहरण के लिए, operator==() कुछ उपयोगी कर सकता है यदि ऑब्जेक्ट को किसी भिन्न थ्रेड में संशोधित किया गया हो। ऐसा लगता है कि एक ही ऑब्जेक्ट पर संचालन को सिंक्रनाइज़ करने की आवश्यकता है क्योंकि यह किसी ऑब्जेक्ट के साथ एक साथ [mutating] तत्व पहुंच कार्यों को लागू करने का कोई अर्थ नहीं बनाता है। हालांकि, मुझे कोई भी पाठ नहीं दिख रहा है जिसमें विभिन्न वस्तुओं का उपयोग किया जाता है (मुझे लगता है, मुझे इसके लिए एक दोष उठाना होगा)।