समानांतर C ++ 17 एल्गोरिदम का अद्भुत प्रदर्शन। मिथक या वास्तविकता?

शुभ संध्या

हमारे पाठ्यक्रम "सी ++ डेवलपर" से हम आपको समानांतर एल्गोरिदम के बारे में एक छोटा और दिलचस्प अध्ययन प्रदान करते हैं।

चलो चलते हैं।

सी ++ 17 में समानांतर एल्गोरिदम के आगमन के साथ, आप आसानी से अपने "कम्प्यूटेशनल" कोड को अपडेट कर सकते हैं और समानांतर निष्पादन से लाभ उठा सकते हैं। इस लेख में, मैं एसटीएल एल्गोरिथ्म पर विचार करना चाहता हूं, जो स्वाभाविक रूप से स्वतंत्र कंप्यूटिंग के विचार को प्रकट करता है। क्या हम 10-कोर प्रोसेसर के साथ 10x त्वरण की उम्मीद कर सकते हैं? या शायद अधिक? या कम है? चलिए इसके बारे में बात करते हैं।

समानांतर एल्गोरिदम का परिचय



C ++ 17 सबसे एल्गोरिदम के लिए एक निष्पादन नीति सेटिंग प्रदान करता है:

• sequenced_policy - निष्पादन नीति का प्रकार, समानांतर एल्गोरिथ्म अधिभार को समाप्त करने के लिए एक अद्वितीय प्रकार के रूप में उपयोग किया जाता है और आवश्यकता है कि समानांतर एल्गोरिथ्म निष्पादन का समानांतरीकरण असंभव है: संबंधित वैश्विक वस्तु std::execution::seq ;
• समानांतर_पॉलिसी - समानांतर एल्गोरिथ्म अधिभार को खत्म करने के लिए एक अद्वितीय प्रकार के रूप में इस्तेमाल की जाने वाली निष्पादन नीति का प्रकार और इंगित करता है कि समानांतर एल्गोरिथ्म निष्पादन का समानांतर संभव है: संबंधित वैश्विक वस्तु std::execution::par ;
• समानांतर_अनुक्रमित_पॉलिसी - समानांतर एल्गोरिथ्म अधिभार को खत्म करने और समानांतर एल्गोरिदम निष्पादन के समानांतरकरण और वैश्वीकरण को संभव बनाने के लिए एक अद्वितीय प्रकार के रूप में उपयोग की जाने वाली निष्पादन नीति: संबंधित वैश्विक वस्तु std::execution::par_unseq ;

संक्षेप में:

• std::execution::seq उपयोग करें std::execution::seq एल्गोरिथ्म के अनुक्रमिक निष्पादन के लिए std::execution::seq ;
• std::execution::par उपयोग करें std::execution::par समानांतर में एल्गोरिथ्म को निष्पादित करने के लिए std::execution::par (आमतौर पर कुछ थ्रेड पूल कार्यान्वयन (थ्रेड पूल) का उपयोग करके);
• वेक्टर कमांड (उदाहरण के लिए, SSE, AVX) का उपयोग करने की क्षमता के साथ एल्गोरिथ्म के समानांतर निष्पादन के लिए std::execution::par_unseq का उपयोग करें।

एक त्वरित उदाहरण के रूप में, कॉल std::sort समानांतर में std::sort करें:

 std::sort(std::execution::par, myVec.begin(), myVec.end()); // ^^^^^^^^^^^^^^^^^^^ //   

ध्यान दें कि एल्गोरिथ्म में एक समानांतर निष्पादन पैरामीटर जोड़ना कितना आसान है! लेकिन क्या एक महत्वपूर्ण प्रदर्शन सुधार प्राप्त किया जाएगा? क्या यह गति बढ़ाएगा? या कोई मंदी है?

समानांतर std::transform

इस लेख में, मैं std::transform एल्गोरिथ्म पर ध्यान देना चाहता हूं, जो संभवतः अन्य समानांतर विधियों ( std::transform_reduce , for_each , scan , sort ...) के लिए आधार हो सकता है।

हमारा परीक्षण कोड निम्नलिखित टेम्पलेट के अनुसार बनाया जाएगा:

 std::transform(execution_policy, // par, seq, par_unseq inVec.begin(), inVec.end(), outVec.begin(), ElementOperation); 

मान लें कि ElementOperation फ़ंक्शन में कोई सिंक्रनाइज़ेशन विधियां नहीं हैं, जिस स्थिति में कोड में समानांतर निष्पादन या यहां तक ​​कि ElementOperation की क्षमता है। प्रत्येक तत्व गणना स्वतंत्र है, आदेश कोई फर्क नहीं पड़ता है, इसलिए एक कार्यान्वयन तत्वों के स्वतंत्र प्रसंस्करण के लिए कई थ्रेड (संभवतः एक थ्रेड पूल में) स्पॉन कर सकता है।

मैं निम्नलिखित चीजों के साथ प्रयोग करना चाहूंगा:

• वेक्टर फ़ील्ड का आकार बड़ा या छोटा है;
• एक साधारण रूपांतरण जो अधिकांश समय स्मृति तक पहुँचने में खर्च करता है;
• अधिक अंकगणित (ALU) संचालन;
• अधिक यथार्थवादी परिदृश्य में ALU।

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

बेंचमार्क नोट

मेरे परीक्षणों के लिए, मैं विज़ुअल स्टूडियो 2017, 15.8 का उपयोग करता हूं - चूंकि यह लोकप्रिय / एसटीएल संकलक कार्यान्वयन का एकमात्र कार्यान्वयन है जो इस समय (नवंबर, 2018) (रास्ते में जीसीसी!)। इसके अलावा, मैंने केवल execution::par पर ध्यान केंद्रित किया execution::par बाद से execution::par_unseq MSVC में उपलब्ध नहीं है (यह execution::par समान कार्य करता है execution::par )।

दो कंप्यूटर हैं:

• i7 8700 - पीसी, विंडोज 10, i7 8700 - 3.2 गीगाहर्ट्ज, 6 कोर / 12 धागे (हाइपरथ्रेडिंग);
• i7 4720 - लैपटॉप, विंडोज 10, i7 4720, 2.6 GHz, 4 कोर / 8 धागे (हाइपरथ्रेडिंग)।

कोड को x64 में संकलित किया गया है, अधिक जारी करें, ऑटो-वेक्टरकरण डिफ़ॉल्ट रूप से सक्षम है, मैंने कमांड (SSE2) और ओपनएमपी (2.0) का एक विस्तारित सेट भी शामिल किया है।

कोड मेरे गितुब में है : github / fenbf / ParSTLTests / TransformTests / Transformsests.pp

OpenMP (2.0) के लिए, मैं केवल छोरों के लिए समानता का उपयोग करता हूं:

 #pragma omp parallel for for (int i = 0; ...) 

मैं 5 बार कोड चलाता हूं और न्यूनतम परिणाम देखता हूं।

चेतावनी : परिणाम केवल मोटे अवलोकन को दर्शाते हैं, उत्पादन में उपयोग करने से पहले अपने सिस्टम / कॉन्फ़िगरेशन पर जांच करें। आपकी आवश्यकताओं और परिवेश मेरा से अलग हो सकता है।

आप इस पोस्ट में MSVC के कार्यान्वयन के बारे में अधिक पढ़ सकते हैं। और यहां बिल ओ'नील की नवीनतम रिपोर्ट CppCon 2018 (MSVC में समानांतर एसटीएल लागू) के साथ है।

ठीक है, चलो सरल उदाहरणों के साथ शुरू करते हैं!

सरल रूपांतरण

जब आप एक इनपुट वेक्टर के लिए एक बहुत ही सरल ऑपरेशन लागू करते हैं तो मामले पर विचार करें। यह तत्वों की नकल या गुणन हो सकता है।

उदाहरण के लिए:

 std::transform(std::execution::par, vec.begin(), vec.end(), out.begin(), [](double v) { return v * 2.0; } ); 

मेरे कंप्यूटर में 6 या 4 कोर हैं ... क्या मैं 4..6 गुना तेजी से अनुक्रमिक निष्पादन की उम्मीद कर सकता हूं? यहाँ मेरे परिणाम हैं (मिलीसेकंड में समय):

आपरेशन	वेक्टर का आकार	i7 4720 (4 कोर)	i7 8700 (6 कोर)
निष्पादन :: seq	10k	0.002763	0.001924
निष्पादन :: बराबर	10k	0.009869	0.008983
के लिए समानांतर	10k	0.003158	0.002246
निष्पादन :: seq	100k	0.051318	0.028872
निष्पादन :: बराबर	100k	0.043028	0.025664
के लिए समानांतर	100k	0.022501	0.009624
निष्पादन :: seq	1000k	१.६९,५०८	.५२,४१९
निष्पादन :: बराबर	1000k	१.६५,५६१	0.359619
के लिए समानांतर	1000k	१.५०,६७८	0.344863

एक तेज़ मशीन पर, हम देख सकते हैं कि प्रदर्शन सुधार पर ध्यान देने में लगभग 1 मिलियन तत्व लगेंगे। दूसरी ओर, मेरे लैपटॉप पर सभी समानांतर कार्यान्वयन धीमा थे।

इस प्रकार, तत्वों की संख्या में वृद्धि के साथ, ऐसे परिवर्तनों का उपयोग करके किसी भी महत्वपूर्ण प्रदर्शन में सुधार को नोटिस करना मुश्किल है।

ऐसा क्यों?

चूंकि ऑपरेशन प्राथमिक हैं, प्रोसेसर कोर इसे केवल कुछ चक्रों का उपयोग करके, लगभग तुरंत कॉल कर सकते हैं। हालांकि, प्रोसेसर कोर मुख्य मेमोरी के इंतजार में अधिक समय बिताते हैं। तो, इस मामले में, अधिकांश भाग के लिए वे इंतजार करेंगे, गणना नहीं करेंगे।

एक चर को पढ़ने और लिखने से मेमोरी में लगभग 2-3 चक्र हो जाते हैं यदि इसे कैश किया जाता है, और यदि यह कैश नहीं है तो कई सौ चक्र।
https://www.agner.org/optimize/optimizing_cpp.pdf

आप मोटे तौर पर ध्यान दे सकते हैं कि यदि आपका एल्गोरिथ्म मेमोरी निर्भर है, तो आपको समानांतर कंप्यूटिंग के साथ प्रदर्शन में सुधार की उम्मीद नहीं करनी चाहिए।

अधिक गणना

चूंकि मेमोरी बैंडविड्थ महत्वपूर्ण है और चीजों की गति को प्रभावित कर सकता है ... आइए गणना की मात्रा बढ़ाएं जो प्रत्येक तत्व को प्रभावित करती है।

यह विचार है कि मेमोरी के लिए समय बर्बाद करने के बजाय प्रोसेसर चक्र का उपयोग करना बेहतर है।

शुरू करने के लिए, मैं त्रिकोणमितीय कार्यों का उपयोग करता हूं, उदाहरण के लिए, sqrt(sin*cos) (ये गैर-इष्टतम रूप में सशर्त गणना हैं, बस प्रोसेसर पर कब्जा करने के लिए)।

हम sqrt , sin और cos उपयोग करते हैं, जो ~ 20 प्रति sqrt और ~ 100 प्रति त्रिकोणमितीय फंक्शन ले सकता है। गणना की यह राशि मेमोरी एक्सेस विलंब को कवर कर सकती है।

टीम देरी के बारे में अधिक जानकारी के लिए, Agner Fogh द्वारा उत्कृष्ट परफेक्ट गाइड देखें।

यहाँ बेंचमार्क कोड है:

 std::transform(std::execution::par, vec.begin(), vec.end(), out.begin(), [](double v) { return std::sqrt(std::sin(v)*std::cos(v)); } ); 

और अब क्या? क्या हम पिछले प्रयास में प्रदर्शन में सुधार कर सकते हैं?

यहाँ कुछ परिणाम हैं (मिलीसेकंड में समय):

आपरेशन	वेक्टर का आकार	i7 4720 (4 कोर)	i7 8700 (6 कोर)
निष्पादन :: seq	10k	0.105005	0.070577
निष्पादन :: बराबर	10k	0.055661	.०३,१७६
के लिए समानांतर	10k	0.096321	0.024702
निष्पादन :: seq	100k	१.०८,७५५	0.707048
निष्पादन :: बराबर	100k	0.259354	.१७,१९५
के लिए समानांतर	100k	0.898465	0.189915
निष्पादन :: seq	1000k	10.5159	७.१६,२५४
निष्पादन :: बराबर	1000k	२.४४,४७२	१.१०,०९९
के लिए समानांतर	1000k	४.७८,६८१	१.८९,०१७

अंत में, हम अच्छी संख्या देखते हैं :)

1000 तत्वों के लिए (यहां नहीं दिखाया गया), समानांतर और अनुक्रमिक गणना समय समान थे, इसलिए 1000 से अधिक तत्वों के लिए हम समानांतर संस्करण में सुधार देखते हैं।

100 हजार तत्वों के लिए, तेजी से कंप्यूटर पर परिणाम सीरियल संस्करण की तुलना में लगभग 9 गुना बेहतर है (इसी तरह OpenMP संस्करण के लिए)।

एक लाख तत्वों के सबसे बड़े संस्करण में, परिणाम 5 या 8 गुना तेज है।
ऐसी गणनाओं के लिए, मैंने प्रोसेसर कोर की संख्या के आधार पर "रैखिक" त्वरण हासिल किया। जिसकी उम्मीद की जानी थी।

फ्रेस्नेल और तीन आयामी वैक्टर

उपरोक्त अनुभाग में, मैंने "आविष्कार" गणनाओं का उपयोग किया, लेकिन वास्तविक कोड के बारे में क्या?
चलो एक चिकनी, सपाट सतह से प्रकाश के प्रतिबिंब और वक्रता का वर्णन करते हुए फ्रेस्नेल समीकरणों को हल करते हैं। 3 डी गेम में यथार्थवादी प्रकाश उत्पन्न करने के लिए यह एक लोकप्रिय तरीका है।




विकिमीडिया से फोटो

एक अच्छे उदाहरण के रूप में, मुझे यह विवरण और कार्यान्वयन मिला।

GLM लाइब्रेरी का उपयोग करने के बारे में

अपने स्वयं के कार्यान्वयन को बनाने के बजाय, मैंने glm पुस्तकालय का उपयोग किया। मैं अक्सर अपने OpenGl प्रोजेक्ट्स में इसका उपयोग करता हूं।

कॉनन पैकेज प्रबंधक के माध्यम से पुस्तकालय तक पहुंचना आसान है, इसलिए मैं इसका भी उपयोग करूंगा। पैकेज से लिंक करें ।

कॉनन फ़ाइल:

 [requires] glm/0.9.9.1@g-truc/stable [generators] visual_studio 

और लाइब्रेरी को स्थापित करने के लिए कमांड लाइन (यह प्रॉपर फाइलों को उत्पन्न करता है जिसे मैं विज़ुअल स्टूडियो प्रोजेक्ट में उपयोग कर सकता हूं)

 conan install . -s build_type=Release -if build_release_x64 -s arch=x86_64 

लाइब्रेरी में एक हेडर होता है, जिससे आप चाहें तो इसे मैन्युअल रूप से डाउनलोड कर सकते हैं।

वास्तविक कोड और बेंचमार्क

मैंने glat के लिए कोड को scratchapixel.com से लिया :

 //    https://www.scratchapixel.com float fresnel(const glm::vec4 &I, const glm::vec4 &N, const float ior) { float cosi = std::clamp(glm::dot(I, N), -1.0f, 1.0f); float etai = 1, etat = ior; if (cosi > 0) { std::swap(etai, etat); } //  sini     float sint = etai / etat * sqrtf(std::max(0.f, 1 - cosi * cosi)); //    if (sint >= 1) return 1.0f; float cost = sqrtf(std::max(0.f, 1 - sint * sint)); cosi = fabsf(cosi); float Rs = ((etat * cosi) - (etai * cost)) / ((etat * cosi) + (etai * cost)); float Rp = ((etai * cosi) - (etat * cost)) / ((etai * cosi) + (etat * cost)); return (Rs * Rs + Rp * Rp) / 2.0f; } 

कोड कई गणितीय निर्देशों, स्केलर उत्पाद, गुणन, विभाजन का उपयोग करता है, इसलिए प्रोसेसर के पास कुछ करने के लिए है। डबल वेक्टर के बजाय, हम उपयोग किए गए मेमोरी की मात्रा को बढ़ाने के लिए 4 तत्वों के वेक्टर का उपयोग करते हैं।

बेंचमार्क:

 std::transform(std::execution::par, vec.begin(), vec.end(), vecNormals.begin(), //   vecFresnelTerms.begin(), //  [](const glm::vec4& v, const glm::vec4& n) { return fresnel(v, n, 1.0f); } ); 

और यहां परिणाम (मिलीसेकंड में समय) हैं:

आपरेशन	वेक्टर का आकार	i7 4720 (4 कोर)	i7 8700 (6 कोर)
निष्पादन :: seq	1k	0.032764	0.016361
निष्पादन :: बराबर	1k	0.031186	0.028551
के लिए समानांतर	1k	0.005526	0.007699
निष्पादन :: seq	10k	0.246722	0.169383
निष्पादन :: बराबर	10k	0.090794	0.067048
के लिए समानांतर	10k	0.049739	0.029835
निष्पादन :: seq	100k	२.४९,७२२	१.६९,७६८
निष्पादन :: बराबर	100k	0.530157	0.283268
के लिए समानांतर	100k	0.495024	0.291609
निष्पादन :: seq	1000k	25.0828	16.9457
निष्पादन :: बराबर	1000k	५.१५,२३५	२.३३,७६८
के लिए समानांतर	1000k	५.११,८०१	२.९५,९०८

"वास्तविक" कंप्यूटिंग के साथ, हम देखते हैं कि समानांतर एल्गोरिदम अच्छा प्रदर्शन प्रदान करते हैं। अपने दो विंडोज मशीनों पर इस तरह के संचालन के लिए, मैंने कोर की संख्या पर लगभग रैखिक निर्भरता के साथ त्वरण हासिल किया।

सभी परीक्षणों के लिए, मैंने ओपनएमपी और दो कार्यान्वयन से परिणाम दिखाए: एमएसवीसी और ओपनएमपी इसी तरह काम करते हैं।

निष्कर्ष

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

याद रखने योग्य बातें:

• समानांतर निष्पादन, आमतौर पर, अनुक्रमिक से अधिक होता है, क्योंकि पुस्तकालय को समानांतर निष्पादन के लिए तैयार करना चाहिए;
• न केवल तत्वों की संख्या महत्वपूर्ण है, बल्कि प्रोसेसर के निर्देशों की संख्या भी इसके साथ व्याप्त है;
• उन कार्यों को लेना बेहतर है जो एक दूसरे और अन्य साझा संसाधनों से स्वतंत्र हैं;
• समानांतर एल्गोरिदम अलग थ्रेड में काम को विभाजित करने का एक आसान तरीका प्रदान करते हैं;
• यदि आपके ऑपरेशन मेमोरी पर निर्भर हैं, तो आपको प्रदर्शन में सुधार की उम्मीद नहीं करनी चाहिए, और कुछ मामलों में, एल्गोरिदम धीमा हो सकता है;
• एक अच्छा प्रदर्शन सुधार पाने के लिए, हमेशा प्रत्येक समस्या के समय को मापें, कुछ मामलों में परिणाम पूरी तरह से अलग हो सकते हैं।

इस लेख के साथ मदद करने के लिए JFT का विशेष धन्यवाद!

समानांतर एल्गोरिदम के बारे में मेरे अन्य स्रोतों पर भी ध्यान दें:

• समानांतर C एल्गोरिथम पर मेरे C ++ 17 में विस्तार से एक हालिया अध्याय;
• समानांतर एसटीएल और फाइलसिस्टम: फाइलें शब्द गणना उदाहरण ;
• C ++ 17 से समानांतर एल्गोरिदम के उदाहरण ।

समानांतर एल्गोरिदम से संबंधित एक अन्य लेख पर नज़र डालें: इंटेल समानांतर STL और C ++ 17 समानांतर एल्गोरिदम के साथ प्रदर्शन को कैसे बढ़ावा दें

अंत

हम उन टिप्पणियों और प्रश्नों की प्रतीक्षा कर रहे हैं, जिन्हें आप यहां या हमारे शिक्षक के खुले दरवाजे पर छोड़ सकते हैं।