हास्केल के समांतरता ओवरहेड को कैसे कम करें?

Question

मैं हास्केल के समांतरता प्रदर्शन को समझने की कोशिश कर रहा हूं।

मेरे पास एक लंबी सूची (लंबाई> 1000) है कि मैं समानांतर में parMap का उपयोग करके समानांतर में मूल्यांकन कर रहा हूं। (: पूर्ण आँकड़े उत्पादन संपादित करें):

 54,248,802,288 bytes allocated in the heap 
      324,451,424 bytes copied during GC 
      2,970,272 bytes maximum residency (4 sample(s)) 
       52,064 bytes maximum slop 
        217 MB total memory in use (1 MB lost due to fragmentation) 

              Tot time (elapsed) Avg pause Max pause 
     Gen 0  251 colls,  0 par 1.45s 1.49s  0.0059s 0.0290s 
     Gen 1   4 colls,  0 par 0.03s 0.05s  0.0125s 0.0319s 

     TASKS: 4 (1 bound, 3 peak workers (3 total), using -N1) 

     SPARKS: 6688 (0 converted, 0 overflowed, 0 dud, 1439 GC'd, 5249 fizzled) 

     INIT time 0.00s ( 0.03s elapsed) 
     MUT  time 19.76s (20.20s elapsed) 
     GC  time 1.48s ( 1.54s elapsed) 
     EXIT time 0.00s ( 0.00s elapsed) 
     Total time 21.25s (21.78s elapsed) 

     Alloc rate 2,745,509,084 bytes per MUT second 

     Productivity 93.0% of total user, 90.8% of total elapsed 

     gc_alloc_block_sync: 0 
     whitehole_spin: 0 
     gen[0].sync: 0 
     gen[1].sync: 0 

अगर मैं दो धागे पर चलाने के लिए, +RTS -N2 का उपयोग कर, मैं:

 54,336,738,680 bytes allocated in the heap 
      346,562,320 bytes copied during GC 
      5,437,368 bytes maximum residency (5 sample(s)) 
       120,000 bytes maximum slop 
        432 MB total memory in use (0 MB lost due to fragmentation) 

              Tot time (elapsed) Avg pause Max pause 
     Gen 0  127 colls, 127 par 2.07s 0.99s  0.0078s 0.0265s 
     Gen 1   5 colls,  4 par 0.08s 0.04s  0.0080s 0.0118s 

     Parallel GC work balance: 41.39% (serial 0%, perfect 100%) 

     TASKS: 6 (1 bound, 5 peak workers (5 total), using -N2) 

     SPARKS: 6688 (6628 converted, 0 overflowed, 0 dud, 0 GC'd, 60 fizzled) 

     INIT time 0.00s ( 0.01s elapsed) 
     MUT  time 25.31s (13.35s elapsed) 
     GC  time 2.15s ( 1.03s elapsed) 
     EXIT time 0.01s ( 0.01s elapsed) 
     Total time 27.48s (14.40s elapsed) 

     Alloc rate 2,146,509,982 bytes per MUT second 

     Productivity 92.2% of total user, 175.9% of total elapsed 

     gc_alloc_block_sync: 19922 
     whitehole_spin: 0 
     gen[0].sync: 1 
     gen[1].sync: 0 

यहाँ पूर्ण आँकड़े उत्पादन किसी एकल थ्रेड के लिए +RTS -s उपयोग कर रहा है

और चार धागे पर:

 54,307,370,096 bytes allocated in the heap 
      367,282,056 bytes copied during GC 
      8,561,960 bytes maximum residency (6 sample(s)) 
      3,885,784 bytes maximum slop 
        860 MB total memory in use (0 MB lost due to fragmentation) 

              Tot time (elapsed) Avg pause Max pause 
     Gen 0  62 colls, 62 par 2.45s 0.70s  0.0113s 0.0179s 
     Gen 1   6 colls,  5 par 0.20s 0.07s  0.0112s 0.0146s 

     Parallel GC work balance: 40.57% (serial 0%, perfect 100%) 

     TASKS: 10 (1 bound, 9 peak workers (9 total), using -N4) 

     SPARKS: 6688 (6621 converted, 0 overflowed, 0 dud, 3 GC'd, 64 fizzled) 

     INIT time 0.01s ( 0.01s elapsed) 
     MUT  time 37.26s (10.95s elapsed) 
     GC  time 2.65s ( 0.77s elapsed) 
     EXIT time 0.01s ( 0.01s elapsed) 
     Total time 39.94s (11.76s elapsed) 

     Alloc rate 1,457,427,453 bytes per MUT second 

     Productivity 93.4% of total user, 317.2% of total elapsed 

     gc_alloc_block_sync: 23494 
     whitehole_spin: 0 
     gen[0].sync: 10527 
     gen[1].sync: 38 

तो विलुप्त समय के अनुसार (वें ई प्रत्येक आउटपुट में अंतिम संख्या), दो कोर के साथ कार्यक्रम एकल-थ्रेडेड संस्करण का ~ 66% लेता है, और चार कोर के साथ इसमें 54% समय लगता है। यह गति बहुत खराब नहीं है, लेकिन कोर की संख्या के साथ सैद्धांतिक रूप से अपेक्षित रैखिक सुधार से कहीं भी बदतर है, जिसके परिणामस्वरूप चार कोर के साथ 25% रनटाइम होगा।

अब, उपरोक्त सांख्यिकीय आउटपुट को देखते समय, मैं देख सकता हूं कि कार्यक्रम के लिए वास्तविक कामकाजी CPU समय (MUT से शुरू होने वाली पंक्तियां) अधिक कोर का उपयोग करने के साथ उल्लेखनीय रूप से बढ़ती हैं। 1, 2 और 4 कोर के साथ मुझे सीपीयू का समय 19.76, 25.31 और 37.26 एस मिलता है, और यह वृद्धि है - मुझे विश्वास है - मेरे समांतरता प्रदर्शन को खा रहा है।

कई कोर कि मेरे मन के लिए आते हैं के साथ इस तरह के एक सीपीयू क्रम भूमि के ऊपर के लिए विशिष्ट कारण हैं:

• काम का बोझ वितरण की भी ठीक पठन स्तर। हालांकि, मैंने 10 का उपयोग parallel पैकेज से 10 के एक खंड आकार के साथ उसी प्रोग्राम की कोशिश की। लेकिन परिणाम बहुत समान है, इसलिए मुझे इस समय नहीं लगता कि ओवरहेड बहुत बढ़िया ग्रैन्युलरिटी के कारण है।
• कचरा संग्रह: यह अतीत में मेरे कोड के लिए एक बड़ा प्रदर्शन हत्यारा था, लेकिन चूंकि मैंने जीसी आकार में 100 एमबी तक वृद्धि की है, इसलिए जीसी में व्यतीत कुल समय काफी छोटा है, जैसा उपर्युक्त आंकड़ों में देखा गया है।

ऐसे मजबूत ओवरहेड के अन्य कारण क्या हैं, और मैं उन्हें कैसे कम कर सकता हूं?

Answer 1

मैं देख रहा हूँ लोग वजह से नहीं है वहाँ पर्याप्त विवरण प्रश्न बंद करने के लिए मतदान कर रहे हैं, लेकिन मेरा मानना ​​है कि इस सवाल का जवाब पहले से ही उपलब्ध कराई गई जानकारी का उपयोग कर पाया जा सकता है (हालांकि अधिक जानकारी के हमेशा स्वागत कर रहे हैं।)

मेरे नाक मुझसे कहता है कि आप स्मृति थ्रूपुट द्वारा सीमित हैं। मैं यह बताने की कोशिश करूंगा कि मुझे ऐसा क्यों लगता है, लेकिन मैं हार्डवेयर विशेषज्ञ नहीं हूं, इसलिए मैं आंशिक रूप से या पूरी तरह गलत हो सकता हूं। आखिरकार, यह हार्डवेयर वास्तुकला मिथकों के अपने व्यक्तिगत सेट पर आधारित है।

मानते हैं कि सीमा प्रति सेकंड 50-100Gb बीच में कहीं है की सुविधा देता है (मुझे यकीन है कि यह है सही संख्या, मुझे सही करें अगर आपके पास है बेहतर नहीं कर रहा हूँ।)

आप 10 सेकंड में 54Gb आवंटन कर रहे हैं (-N4 केस), तो आपके पास 5 जीबी/सेक थ्रूपुट है। यह बहुत अधिक है, लेकिन आमतौर पर यह स्वयं पर कोई मुद्दा नहीं है।

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

लेकिन आपने नर्सरी आकार में 100 एमबी बढ़ाया। यह एल 2 कैश फिट नहीं होगा, और मुख्य स्मृति में स्थानांतरित किया जाएगा। यह पहले से ही एक बुरा संकेत है।

ठीक है, 5 जीबी/सेकंड सीमा से बहुत दूर है। लेकिन एक कारण है कि आपने नर्सरी आकार में वृद्धि क्यों की - आपका डेटा छोटा नहीं है। यह कुछ अंतराल के बाद कहीं और इस्तेमाल किया जाएगा। इसका मतलब है कि यह 54 जीबी मुख्य स्मृति से जल्द या बाद में कैश तक लोड हो जाएगा। तो आपके पास कम से कम 10 जीबी/सेक थ्रूपुट है।

यह अभी भी सीमा से बहुत दूर है, लेकिन ध्यान दें, कि यह सबसे अच्छा केस परिदृश्य - अनुक्रमिक स्मृति पहुंच पैटर्न है। हकीकत में आप यादृच्छिक क्रम में स्मृति तक पहुंच रहे हैं, इसलिए एक ही कैश लाइनें लोड हो जाती हैं और कई बार अनलोड हो जाती हैं, और आप आसानी से 100 जीबी/सेकंड तक पहुंच जाते हैं।

समस्या को ठीक करने के लिए, आपको यह पता होना चाहिए कि हमारा डेटा छोटा नहीं है और इसे ठीक करने का प्रयास क्यों करें। यदि यह संभव नहीं है, तो आप डेटा क्षेत्र को बढ़ाने और अनुक्रमिक बनाने के लिए स्मृति पहुंच पैटर्न को बदलने का प्रयास कर सकते हैं।

मैं जानना चाहता हूं कि हार्डवेयर विशेषज्ञ मेरे निष्पक्ष स्पष्टीकरण के बारे में क्या सोचते हैं :)