ओपनएमपी: गहराई के लिए अच्छी रणनीतियां- पहली खोज

Question

मैं एक सी ++ प्रोग्राम लिख रहा हूं जो बंद Knight's tours बंद करने के लिए एक ब्रूट-फोर्स खोज करता है। कोड here है।

मैं ओपनएमपी का उपयोग करके इसे समानांतर करना चाहता हूं। मेरी समस्या यह इस तरह से करना है जो समानांतरता की पर्याप्त डिग्री बनाता है। वर्तमान में मेरे कोड का the relevant portion की तरह इस

#pragma omp parallel for reduction(+:count) if (depth==4) 
    for (size_t i=0;i<g.neighbours[last].size();i++){ 
    auto n = g.neighbours[last][i]; 
    // See if n can be used to extend or complete the tour 

if (depth==4) लग रहा है यकीन नहीं भी कई समानांतर कार्यों बनाए जाते हैं लेकिन दूसरी ओर पर्याप्त सभी प्रोसेसर व्यस्त रखने के लिए बनाई गई हैं पर बनाने के लिए मेरे प्रयास है। depth==2 सेट करना प्रोग्राम के रनटाइम को नहीं बदलता है।

ऐसा लगता है कि यह काम नहीं कर रहा है। 3x12 समस्या के लिए, मेरे दोहरे कोर प्रोसेसर पर ओपनएमपी संस्करण द्वारा खपत कुल CPU समय लगभग 130 है जबकि ओपनएमपी के बिना एकल-थ्रेडेड संस्करण लगभग 40 के CPU समय लेता है।

मैं ओपनएमपी का उपयोग करने के बेहतर तरीके या इस समस्या के लिए अनुपयुक्त क्यों है, इस पर सुझावों की सराहना करता हूं।

अद्यतन: @Zulan के लिए धन्यवाद मेरे पास newer version है जो ओपनएमपी कार्यों का उपयोग करके बहुत तेजी से अनुक्रमिक प्रदर्शन के साथ-साथ अच्छे समांतरता के साथ है।

Answer 1

सबसे पहले, की सुविधा देता है, जहां आपके आवेदन अपने समय खर्च करता है पर एक सुपर शीघ्रता से अवलोकन करना perf का उपयोग करके:

perf record ./knights_tour_omp 3 12 
perf report 

# Overhead Command   Shared Object  Symbol                       
# ........ ............... ................... ................................................................................................. 
# 
    53.29% knights_tour_om libc-2.19.so   [.] malloc                      
    23.16% knights_tour_om libc-2.19.so   [.] _int_free                      
    10.31% knights_tour_om libc-2.19.so   [.] _int_malloc                     
    4.78% knights_tour_om knights_tour_omp  [.] _Z13continue_tourIZ4mainEUlRKSt6vectorIiSaIiEEE_EmRK5GraphS4_RKS0_IcSaIcEEiiRT_.constprop.119 
    2.64% knights_tour_om libc-2.19.so   [.] __memmove_ssse3_back                   
    1.48% knights_tour_om libc-2.19.so   [.] malloc_consolidate                 

आप आवेदन यह सब समय का आवंटन और स्मृति को मुक्त है खर्च करता है। हालांकि कुछ रिपोर्टें हैं कि malloc is is not fully locked, यह अच्छी तरह से समानांतर समान प्रतीत नहीं होता है।

यह पता लगाने के लिए और अधिक जांच की आवश्यकता नहीं है कि यह प्रत्येक पुनरावृत्ति के लिए visited और path वैक्टरों की प्रतिलिपि बनाकर होता है। सौभाग्य से डीएफएस, अच्छा संपत्ति है कि आप आवश्यक रूप से राज्य का पुन: उपयोग और पुनर्स्थापित कर सकते हैं, कि क्या करने की जरूरत नहीं है:

visited[n] = 1; 
path.emplace_back(n); 
count += continue_tour(g, path, visited, depth+1,remain-1, cb); 
visited[n] = 0; 
path.pop_back(); 

हालांकि, समानांतर पाश के लिए, आप प्रत्येक थ्रेड के लिए काम कर रहे प्रतियां बनाने की जरूरत , इसलिए आपको मूल व्यवहार के साथ इस मामले के लिए एक अलग रास्ता बनाना होगा।

यह छोटा बदलाव पहले ही धारावाहिक रनटाइम को 22 से 2.65 एस तक लाता है। इसके अलावा 2 धागे के साथ यह 2.0 एस तक चला जाता है। एक गति है, लेकिन यह इतना अच्छा नहीं है - क्यों? उदाहरण के लिए, मैंने 4 धागे (एक बड़ी-पर्याप्त प्रणाली पर) का उपयोग किया। Vampir में दिखाए गए score-p के साथ रिकॉर्ड किए गए समय के साथ एप्लिकेशन का निष्पादन यहां दिया गया है।

लाल वास्तविक कार्य, नीले, एक अंतर्निहित बाधा नहीं है, जिसका अर्थ है धागे सुस्ती कर रहे हैं। हमेशा 3 या 1 सक्रिय धागा प्रतीत होता है। कारण सरल है: बोर्ड की अधिकांश स्थिति में या तो 4 या 2 पड़ोसी हैं, लेकिन उनमें से एक पहले से ही दौरा किया गया है, इसलिए यह लूप पुनरावृत्ति तुरंत पूरा हो जाता है। तो वास्तविक कार्य लूप के 3 या 1 पुनरावृत्ति में है। यह 2 धागे के लिए एक विशेष रूप से खराब मैच है। 3 धागे के साथ, रनटाइम 1.7 एस

नोट: हर बार g5 5.3 के साथ E5-2690 @ 2.90 गीगाहर्ट्ज कोई टर्बो पर नहीं जाता है। रनटाइम में भिन्नता की भरपाई करने के लिए कोई परवाह नहीं की गई थी।

ध्यान में रखते हुए कि एक ही लूप उस समस्या के लिए बहुत खराब समांतरता का खुलासा करता है, तो आप समानांतर लूप घोंसला करने के लिए लुभाने वाले हो सकते हैं। मैं आपको कोशिश करने के लिए प्रोत्साहित करता हूं, लेकिन मुझे नहीं लगता कि यह अच्छी तरह से काम करेगा। मुझे लगता है कि कार्य इस संदर्भ में अच्छी तरह से काम करते हैं, क्योंकि कार्य अन्य कार्यों को जन्म दे सकते हैं। तो आप एक कार्य के रूप में प्रत्येक रिकर्सिव चरण को बढ़ा सकते हैं और ओएमपी रनटाइम को एक अच्छा शेड्यूलिंग करने दें। लेकिन इसे एक निश्चित depth तक सीमित करना सुनिश्चित करें, ताकि कार्य बहुत कम न हो जाएं।

मैं उपकरण का उपयोग करने के महत्व पर जोर देना चाहता हूं: प्रदर्शन विश्लेषण उपकरण के बिना प्रदर्शन समस्याओं को समझने का प्रयास करना डीबगर के बिना बग को ढूंढना है। perf लिनक्स के लिए आसानी से उपलब्ध है और इसका मूल रूप उपयोग करने में बेहद आसान है। फिर भी यह बहुत शक्तिशाली है (हालांकि उन्नत उपयोग में कुछ नुकसान हो सकते हैं)।

एक अतिरिक्त टिप्पणी: ओपनएमपी के साथ अक्सर विभिन्न कंपाइलर्स को आजमाने के लिए बेकार है। उदाहरण के लिए (फिक्स्ड) टास्किंग कोड के साथ, जीसीसी अब 4 धागे से अधिक नहीं स्केल करता है, जबकि इंटेल कंपाइलर/ओएमएम रनटाइम 24 धागे तक भी गति प्रदान करता है।