इंटेल Cilk प्लस में बातचीत

मान लीजिए कि किसी कारण से हमें किसी सरणी के तत्वों का योग खोजने की आवश्यकता है। हम सरणी को दो भागों में विभाजित कर सकते हैं, प्रत्येक भाग को अलग से जोड़ सकते हैं और परिणाम जोड़ सकते हैं। इस मामले में, आप इन भागों को समानांतर में सारांशित कर सकते हैं। लेकिन सरणी के एक हिस्से को संक्षेप में प्रस्तुत करना मूल कार्य है, और प्रत्येक भाग को फिर से दो भागों में विभाजित किया जा सकता है और प्रत्येक भाग को अलग-अलग विभाजित किया जा सकता है, और फिर परिणाम जोड़ सकते हैं, आदि। इस गणना की रणनीति को " फूट डालो और जीतो " कहा जाता है।

इस तरह, आप सरणियों के कई अन्य कार्यों की गणना कर सकते हैं, लेख के पहले भाग में नीचे इस विचार का गणितीय विवरण दिया जाएगा, और दूसरे में - Intel Cilk Plus का उपयोग करके अपने कार्यक्रमों में इस विचार का उपयोग कैसे करें।

इसलिए, यदि आप गर्मियों के अंतिम दिनों में गणितीय सूत्रों और C ++ कोड के टुकड़ों को देखना चाहते हैं, तो habrakat में आपका स्वागत है।

Monoids और homomorphism

कई उदाहरणों और एक बहुत विस्तृत विवरण के साथ एक मोनॉइड की परिभाषा को हाब्रस्टैट मोनॉयड्स और उनके अनुप्रयोगों में पाया जा सकता है : पेड़ों में मोनोइडल संगणना , इसलिए हम खुद को एक परिभाषा और उदाहरणों के एक जोड़े तक सीमित करते हैं।

एक मोनॉइड एक ट्रिपल ( एम , oid, ई ) है, जहां एम एक नॉनमिप्ट सेट है, ⋅ सेट एम पर एक द्विआधारी साहचर्य संचालन है, ई ऑपरेशन एम के संबंध में सेट एम का एक तटस्थ तत्व है।

चूंकि ऑपरेशन any साहचर्य है, जो कि किसी भी x , y और z के लिए M से है। यह सत्य है कि x ⋅ ( y ⋅ z ) = ( x ) y ), z है , तो अभिव्यक्ति x ₁ ⋅ x ₂ computing की गणना करने का परिणाम ... ⋅ x _n कोष्ठक की व्यवस्था पर निर्भर नहीं करता है, इसलिए, कोष्ठक को पूरी तरह से छोड़ा जा सकता है। इस सरल लेकिन महत्वपूर्ण तथ्य (और साथ ही बाद के सभी सरल लेकिन महत्वपूर्ण तथ्य) का प्रमाण कुछ पाठ्यपुस्तक में उच्च बीजगणित पर पाया जा सकता है या खुद के साथ आ सकता है।

उदाहरणों के बहुत सारे उदाहरण हैं, उदाहरण के लिए, स्कूल की छठी कक्षा से, हर कोई जानता है कि इसके अलावा पूर्णांक का सेट ( Z , +, 0) एक मोनॉइड है। एक मोनॉइड का दूसरा उदाहरण एक सूची मोनॉइड है। अर्थात्, एक्स को एक मनमाना सेट होने दें, हम एक्स by द्वारा सेट एक्स के तत्वों के सभी परिमित अनुक्रमों के सेट को खाली क्रम सहित []], + + द्वारा हम सूचियों के संघटन के संचालन को निरूपित करते हैं। फिर, जैसा कि यह सत्यापित करना मुश्किल नहीं है, ट्रिपल ( एक्स ++, ++, []) एक मोनॉयड है।

अगला, हमें समरूपता की अवधारणा की आवश्यकता है। Let ( M , ( M , e _M ) और ( N , ⋅ _N , e _N ) दो मनमाने मोनॉयड हो सकते हैं। एक फ़ंक्शन h : M → N को एक होमोमोर्फिज़्म कहा जाता है यदि h ( x ) _M y ) = h ( x )) _N h ( y ) से M और y से किसी भी x और y के लिए ( e _M ) = e _N।

ध्यान दें कि, शिथिल रूप से बोलना, एक फ़ंक्शन एक समरूपता है यदि इसे बाइनरी ऑपरेशन के संकेत के माध्यम से खींचा जा सकता है। यह स्पष्ट है कि पहचान मानचित्रण एक समरूपतावाद है, लेकिन स्कूल और विश्वविद्यालय के पाठ्यक्रमों में गणित से हर कोई होमरॉफिज्म के कई और दिलचस्प उदाहरण जानता है। उदाहरण के लिए, उत्पाद लघुगणक लघुगणक के योग के बराबर है , ln ( xy ) = ln x + ln y , और हमारे शब्दों में इसका अर्थ यह है कि मैप ln सकारात्मक संख्याओं के मोनोड से एक समरूपता है, जो वास्तविक संख्याओं के गुणा ( R ₊ , ⋅, 1) को वास्तविक संख्याओं के गुणा में गुणा करके करता है। इसके अलावा ( आर , +, 0)। इसके अलावा, मैट्रिस के उत्पाद का निर्धारक इन मैट्रिस के निर्धारकों के उत्पाद के बराबर होता है , det ( AB ) = det A B det B , यानी, mapping det एक गुणा (mat _n ( R ),,, I ) के मोनॉइड द्वारा स्क्वायर मेट्रिसेस के मोनोड से एक समरूपता है। गुणन संख्या ( R , ⋅, 1)। आशा है कि विचार स्पष्ट है। अब हम होमोमोर्फिज्म को सूचीबद्ध करने की ओर मुड़ते हैं।

किसी भी होमोमोर्फिज्म को एक सूची मोनॉइड ( X ++, ++, []) से एक मनमाना monoid ( M , (, e ) की सूची होमोमोर्फिज्म कहा जाता है। सूची होमोमोर्फिम्स में निम्नलिखित उपयोगी गुण हैं। [ X ₁ , x ₂ , ..., x _n ] को एक मनमानी सूची होने दें, फिर h ([ x ₁ , x ₂ , ..., x _n ]) = h ([ x ₁ ] ++ [ x ₂ ] ++ ... + + [ x _n ]) = h ([ x ₁ ]) [ h ([ x ₂ ]) ⋅ ... x h ([ x _n ])। इस प्रकार, कोई भी सूची होमोमोर्फिज्म विशिष्ट रूप से सिंगलटन सूचियों पर अपने मूल्यों से निर्धारित होती है। तो, f : X → M एक फ़ंक्शन है जैसे कि f ( x ) = h ([ x ]), तो हम विशिष्ट रूप से परिभाषित सूची homomorphism h को फॉर्म होम (⋅, f , e ) में लिखेंगे।

अब कुछ उदाहरण।

1. संख्याओं की एक सूची के तत्वों का योग, संख्याओं की सूची के तत्वों का एक उत्पाद, संख्याओं की सूची के न्यूनतम और अधिकतम तत्वों को खोजने के लिए सूची homomorphisms hom (+, id, 0), घर (⋅, id, 1), घर (अधिकतम, आईडी, −∞) और के रूप में माना जा सकता है। घर (न्यूनतम, आईडी, +,), क्रमशः। इसी तरह की सूची होमोमोर्फिम्स, जिसमें दूसरा पैरामीटर आईडी का पहचान मानचित्र है, हम संक्षेप में कम लिखते हैं (), ई)।
2. लंबाई फ़ंक्शन, जो सूची की लंबाई की गणना करता है, एक सूची होमोमोर्फिज्म होम (+, एक, 0) है, जहां एक ( x ) = 1।
3. एक फ़ंक्शन जो सूची के प्रत्येक तत्व के लिए कुछ फ़ंक्शन एफ लागू करता है, वह भी एक सूची होमोमोर्फिज्म है, अर्थात् होम (++, जी , []), जहां जी ( एक्स ) = [ एफ ( एक्स )]। इस तरह के कार्यों को संक्षेप में मानचित्र ( एफ ) के रूप में लिखा जाएगा।
4. सॉर्टिंग फ़ंक्शन को सूची होमोमोर्फिज्म के रूप में भी दर्शाया जा सकता है। अर्थात्, दो मर्ज किए गए सूचियों को मिलाने का कार्य करते हैं, सूची ( x ) = [ x ] एक फ़ंक्शन है जो एक तत्व को एक सिंगलटन सूची में बदल देता है। फिर समरूपता गृह (मर्ज, सूची, []) वांछित सूची समरूपता होगी।

ध्यान दें कि यद्यपि होमोमोर्फिज्म को सूची गृहविज्ञान कहा जाता है, सूची का मतलब मक्खी पर उत्पन्न सरणियों, तारों या अनुक्रमों से हो सकता है। अब, हम होमोमोर्फिज्म प्रमेय के रूप में जाना जाने वाले तीन उपयोगी बयान देते हैं।

पहला होमोमोर्फिज्म प्रमेय। किसी भी सूची homomorphism को एक कंपोजिशन होम ( f , f , e ) = कम ( f , e ) (मैप ( f ) के रूप में दर्शाया जा सकता है ।

यह इस सरल अवलोकन पर है कि MapReduce का विचार आधारित है। MapReduce का एक सरल परिचय MapReduce habrastas या मेमोरी और प्रोसेसर की क्षमताओं से परे गणना में पाया जा सकता है (मैं zaumi के बिना कोशिश करूँगा) और MapReduce: अधिक उन्नत उदाहरण, हम zaumi के बिना कोशिश करेंगे ।

आज्ञा दें [ x ₁ , x ₂ , ..., x _n ] एक मनमानी सूची, फ़ंक्शन फोल्ड (, _L , e _L ) ([ x ₁ , x ₂ , ..., x _n ]) = (... (e _L) ⋅ _L x ₁ ) x _L x ₂ ) ⋅ _L ... _{n L} x _n ), और दाईं ओर फंक्शन फोल्डर (the _R , e _R ) ([ x ₁ , x ₂ , ..., x _n ]) = ( x _{1) है} ⋅ _R ( x ₂ ... _R ... _{2 R} ( x _{n R R} e _{R R} ...))। दूसरा होमोमोर्फिज्म प्रमेय निम्नलिखित बताता है।

दूसरा समरूपता प्रमेय । किसी भी सूची होमोमोर्फिज्म को बाएं और दाएं कनवल्शन के रूप में व्यक्त किया जाता है, अर्थात होम (, f , e ) = foldl (⋅ _L , e ) = foldr (, _R , e ), जहां x ⋅ _L y = x ph f ( y ), x y _R y = f ( x ) x y ।

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

हमारे लिए, सूची homomorphism h = hom ( f , f , e) के समानांतर गणना की विधि अधिक दिलचस्प है। याद रखें कि एक सूची होमोमोर्फिज्म h ( x ++ y ) = h ( x ), h ( y ) की परिभाषा से, दूसरे शब्दों में, स्वतंत्र रूप से संभव है और इसलिए, समानांतर, गणना h ( x ) और h ( y ), और तब पहले से ही h ( x ++ y ) के अंतिम मान की गणना करें। लेकिन हम प्रत्येक सूची x और y को भी दो भागों में विभाजित कर सकते हैं, और होमोमोर्फिज्म की परिभाषा का उपयोग करते हुए, उनके लिए एच के मूल्यों की स्वतंत्र रूप से गणना करते हैं, और फिर परिणाम एकत्र करते हैं, आदि यह विभाजन और रणनीति से अधिक कुछ नहीं है। ।

मान लीजिए कि ऑपरेशन ⋅ की गणना निरंतर समय C में की जाती है , और सूची x में n तत्व होते हैं। बाएं कनवल्शन की गणना के लिए, ऑपरेशन की गणना ठीक से n बार करना आवश्यक है, अर्थात, Cn समय लगता है। यदि हमारे पास p प्रोसेसर है, तो हम सूची x को p बराबर भागों x _i में विभाजित करते हैं और समय x / p के लिए h की गणना _{करने के} लिए प्रत्येक x _{i के} लिए बाएं कनवल्शन का उपयोग करते हैं, और फिर C के लिए लॉग ₂ p हम अंतिम परिणाम की गणना करते हैं। इस प्रकार, कुल समय C ( n / p + log ₂ p ) है।

अंत में, हम तीसरे होमोमोर्फिज्म प्रमेय का वर्णन करते हैं, जो कहता है कि जब कोई फ़ंक्शन एक सूची होमोमोर्फिज्म है।

तीसरा समरूपता प्रमेय। यदि एक सूची मोनॉइड से एक निश्चित मोनॉइड के लिए एक फ़ंक्शन को बाएं फोल्ड (, _L , e ) के रूप में और एक सही कनवल्शन फोल्डर (, _R , e ) के रूप में व्यक्त किया जाता है , तो यह एक सूची होमोमोर्फिज्म है।

इन तीन प्रमेयों के साक्ष्य जेरेमी गिबन्स के लेख द थर्ड होमोमोर्फिज्म प्रमेय में पाए जा सकते हैं, और हम Intel Cilk Plus पर आगे बढ़ते हैं।

इंटेल Cilk प्लस में बातचीत

Intel Cilk Plus मल्टी-थ्रेडेड प्रोग्राम लिखने के लिए C ++ भाषा का एक विस्तार है, जिसमें अन्य बातों के अलावा, निम्नलिखित शामिल हैं:

1. कीवर्ड cilk_spawn और cilk_sync (पहला इंगित करता है कि फ़ंक्शन समानांतर में निष्पादित किया जा सकता है, दूसरा सिंक्रनाइज़ेशन के लिए उपयोग किया जाता है),
2. cilk_for को समानांतर करने के लिए cilk_for कीवर्ड,
3. थ्रेड-सुरक्षित डेटा साझा करने के लिए हाइपरोबॉजेक्ट्स
4. सरणियों पर सरणियों और संचालन लिखने के लिए विशेष वाक्यविन्यास, उदाहरण के लिए, सरणियों के मूल तत्व जोड़ के रूप में लिखा जा सकता है c[:] = a[:] + b[:] ।

यहां केवल दूसरे और तीसरे अंक प्रभावित होंगे। Intel Cilk Plus के बारे में दस्तावेज़ीकरण और अन्य सामग्री http://software.intel.com/en-us/articles/intel-cilk-plus/ पर देखी जा सकती है।

तो, मान लीजिए कि हमें पूर्णांकों की एक सरणी के तत्वों की राशि की गणना करने की आवश्यकता है। एक संभावित अनुक्रमिक कार्यान्वयन नीचे दिया गया है।

 int sum = 0; for (int i = 0; i < n; ++i) { sum += a[i]; } std::cout << sum << std::endl; 

ध्यान दें कि यह बाएं कनवल्शन के कार्यान्वयन से ज्यादा कुछ नहीं है। लेकिन सरणी के तत्वों का योग एक सूची होमोमोर्फिज्म है, और इसलिए समानांतर कार्यान्वयन के लिए भी अनुमति देता है, जैसा कि ऊपर बताया गया है। Intel Cilk Plus आपको बिना किसी प्रयास के ऐसा कार्यान्वयन करने की अनुमति देता है, यह निम्नलिखित करने के लिए पर्याप्त है:

1. हेडर फ़ाइलें cilk/reducer_opadd.h और cilk/cilk.h शामिल करें
2. प्रकार reducer_opadd<int> ,
3. cilk_for for परिवर्तन,
4. परिणाम प्राप्त करने के लिए get_value() का उपयोग करें।

 #include <cilk/cilk.h> #include <cilk/reducer_opadd.h> ... cilk::reducer_opadd<int> sum; cilk_for (int i = 0; i < n; ++i) { sum += a[i]; } std::cout << sum.get_value() << std::endl; 

इस मामले में, लगभग निम्नलिखित होगा। संकलक cilk_for चक्र के शरीर को एक फ़ंक्शन में परिवर्तित करता है जो विभाजन को लागू करता है और रणनीति को cilk_for है; यह छद्म कोड में निम्नानुसार लिखा गया है।

 void run_loop(first, last) { if ((last - first) < grainsize) { for (int i = first; i < last; ++i) { LOOP_BODY; } } else { int mid = (last - first) / 2; cilk_spawn run_loop(first, mid); run_loop(mid, last); } } 

और चूंकि योग चर एक reducer है, धागे को दो में विभाजित करने और उनके समानांतर निष्पादन के मामले में, बच्चा पुराने प्रतिनिधित्व का उपयोग करेगा, और निरंतरता को शून्य के लिए एक नया प्रतिनिधित्व मिलेगा, दोनों सिंक्रनाइज़ेशन को सिंक्रनाइज़ेशन के दौरान जोड़ा जाएगा।

reducer_opadd अतिरिक्त reducer_opadd Intel Cilk Plus Reducers की एक विस्तृत श्रृंखला प्रदान करता है: reducer_list_append , reducer_list_prepend , reducer_min , reducer_max , reducer_min_index , reducer_max_index , reducer_opor , reducer_opand , reducer_ostream यदि उनमें से कोई भी काम नहीं करता है, तो आप अपना खुद का Reducer बना सकते हैं।

एक Monoid बनाने के लिए, आपको एक Monoid क्लास बनाने की ज़रूरत है जो एक मोनोइड को लागू करता है। इस वर्ग में निम्नलिखित कार्य होने चाहिए:

• reduce(T *left, T *right) गणना करता है *left = *left OP *right ,
• identity(T *p) p द्वारा इंगित मेमोरी क्षेत्र में एक तटस्थ तत्व बनाता है,
• destroy(T *p) p द्वारा बताई गई वस्तु के लिए विध्वंसक कहता है,
• allocate(size) एक पॉइंटर को साइज़ size बाइट्स के मेमोरी एरिया में लौटाता है,
• deallocate(p) p द्वारा इंगित की गई मेमोरी को मुक्त करता है।

ज्यादातर मामलों में, इन सभी तरीकों को लागू करने की आवश्यकता नहीं है; यह cilk::monoid_base<T> से प्राप्त करने के लिए पर्याप्त है cilk::monoid_base<T> वर्ग और कार्यान्वयन को reduce() और, संभवतः, identity() ।

इसके अलावा, reducer को लागू करने वाले वर्ग में cilk::reducer<Monoid> imp_ और इस हाइपरोबॉज़ को एक्सेस करने के तरीके और इसे एक छिपे हुए सदस्य के रूप में बदलने के लिए विधियाँ होनी चाहिए।

हम एक सरणी संख्या के तत्वों के गुणनफल ज्ञात करने के लिए एक reducer लिखेंगे।

 #include <cilk/reducer.h> #include <cilk/cilk.h> #include <iostream> class reducer_prod { public: struct Monoid: cilk::monoid_base<double> { void reduce(double *left, double *right) const { *left *= *right; } void identity(double* p) const { new ((void*) p) double(1.0); } }; reducer_prod(): imp_(1.0) { } reducer_prod &operator*=(const double &v) { imp_.view() *= v; return *this; } double get_value() const { return imp_.view(); } private: cilk::reducer<Monoid> imp_; }; 

 reducer_prod prod; cilk_for (int i = 0; i < n; ++i) { prod *= a[i]; } std::cout << prod.get_value() << std::endl;