हास्केल में कोई अंतर्निहित समांतरता क्यों नहीं है?

Question

हास्केल कार्यात्मक और शुद्ध है, इसलिए मूल रूप से इसमें implicit parallelism से निपटने में सक्षम होने के लिए एक कंपाइलर के लिए आवश्यक सभी गुण हैं।

   do 
       | 
     +---------+---------+ 
     |     | 
    a <- Just 1  b <- Just $ Just 2 
     |     | 
     |     c <- b 
     |     | 
     +---------+---------+ 
       | 
      return (a, c) 

क्यों दिया गया झंडा या अभी तक एक pragma साथ संकलक में लागू ऐसी कोई कार्यक्षमता है:

f = do 
    a <- Just 1 
    b <- Just $ Just 2 
    --^The above line does not utilize an `a` variable, so it can be safely 
    -- executed in parallel with the preceding line 
    c <- b 
    --^The above line references a `b` variable, so it can only be executed 
    -- sequentially after it 
    return (a, c) 
    -- On the exit from a monad scope we wait for all computations to finish and 
    -- gather the results 

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

इस तुच्छ उदाहरण पर विचार करें? व्यावहारिक कारण क्या हैं?

Answer 1

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

तो तुम बही खाता पर खर्च प्रयास खत्म, तेजी से चीजों को नहीं चल रहा है। भी मोटे और वहाँ निष्क्रिय प्रोसेसर भी फाई ne हो जाएगा और ओवरहेड्स अस्वीकार्य होगा -

जब से हम अनंत समानांतर हार्डवेयर की जरूरत नहीं है, यह सब के बारे में सही विवरण के स्तर को उठा है।

हमारे पास हजारों या लाखों समानांतर कार्यों (इसलिए निर्देश स्तर पर नहीं) उत्पन्न करने के लिए उपयुक्त अधिक मोटे अनाज वाले समांतरता (स्पार्क्स) हैं, जो कि हम केवल मुट्ठी भर कोरों पर नक्शा करते हैं जो हम आम तौर पर आज उपलब्ध हैं।

ध्यान दें कि कुछ सबसेट (जैसे सरणी प्रसंस्करण) के लिए वहाँ तंग लागत मॉडल के साथ पूरी तरह से स्वचालित बनता पुस्तकालय हैं।

इस पर पृष्ठभूमि के लिए, http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf, जहां वे par को मनमाने ढंग से हास्केल कार्यक्रमों में सम्मिलित करने के लिए एक स्वचालित दृष्टिकोण प्रस्तुत करते हैं।

Answer 2

अपने कोड ब्लॉक a और b के बीच निर्भरता निहित डेटा की वजह से सबसे अच्छा उदाहरण नहीं हो सकता है, यह ध्यान देने योग्य है कि इन दो बाइंडिंग कि

f = do 
    a <- Just 1 
    b <- Just $ Just 2 
    ... 

में निकल ही परिणाम दे देंगे

f = do 
    b <- Just $ Just 2 
    a <- Just 1 
    ... 

तो यह अभी भी एक सट्टा फैशन में समानांतर हो सकता है। यह ध्यान देने योग्य है कि इसे मोनाड्स के साथ कुछ भी करने की आवश्यकता नहीं है। उदाहरण के लिए, हम let में सभी स्वतंत्र अभिव्यक्तियों का मूल्यांकन कर सकते हैं-समानांतर में अवरुद्ध करें या हम let के संस्करण को प्रस्तुत कर सकते हैं जो ऐसा करेगा। आम लिस्प के लिए lparallel library यह करता है।

अब, मैं इस विषय पर कोई विशेषज्ञ नहीं हूं, लेकिन यह मेरी समझ समस्या है। एक प्रमुख ठोकरें ब्लॉक यह निर्धारित कर रहा है कि एकाधिक अभिव्यक्तियों के मूल्यांकन को समानांतर करने के लिए फायदेमंद है। के मूल्यांकन के लिए अलग-अलग धागे शुरू करने के साथ ओवरहेड जुड़ा हुआ है, और, जैसा कि आपका उदाहरण दिखाता है, यह परिणामस्वरूप बर्बाद काम में हो सकता है। ओवरहेड के बराबर समानांतर मूल्यांकन बनाने के लिए कुछ अभिव्यक्ति बहुत छोटी हो सकती हैं। जैसा कि मैं इसे समझता हूं, एक अभिव्यक्ति की लागत का एक पूरी तरह से सटीक मीट्रिक होगा, जो रोकथाम की समस्या को हल करने के लिए होगा, इसलिए आपको को समानांतर में मूल्यांकन करने के लिए एक ह्युरिस्टिक दृष्टिकोण का उपयोग करने के लिए रेलेगेट किया गया है।

फिर किसी समस्या पर अधिक कोर फेंकना हमेशा तेज़ नहीं होता है। यहां तक ​​कि कई Haskell पुस्तकालयों के साथ समस्या को स्पष्ट रूप से समानांतर करते हुए, भारी मेमोरी आवंटन और उपयोग और कचरा कलेक्टर और सीपीयू कैश पर रखे तनाव के कारण आपको समानांतर में अभिव्यक्तियों का मूल्यांकन करके अक्सर अधिक गति दिखाई नहीं देगी। बुद्धिमानी से अपने डेटा को पार करने के लिए आपको एक अच्छा कॉम्पैक्ट मेमोरी लेआउट और की आवश्यकता होती है। 16 धागे ट्रांस्ड लिंक्ड सूचियों के साथ आपको बस अपनी मेमोरी बस पर बाधा डाल देगा और वास्तव में चीजों को धीमा कर सकता है।

कम से कम, क्या भाव को प्रभावी ढंग से parallelized किया जा सकता है कि कई प्रोग्रामर (कम से कम यह इस एक के लिए नहीं है) करने के लिए स्पष्ट नहीं है है, इसलिए करने के लिए एक संकलक हो रही यह प्रभावी रूप से गैर तुच्छ है ।

Answer 3

लघु जवाब: कभी-कभी समानांतर में सामान चल निकला तेजी से धीमी, नहीं किया जाना है। और यह पता लगाना कि यह कब होता है और जब यह एक अच्छा विचार नहीं है, तो एक अनसुलझा अनुसंधान समस्या है।

हालांकि, अगर आप अभी भी हो सकता है "अचानक कभी सूत्र, गतिरोध और दौड़ की स्थिति के साथ परेशान कर रहा बिना उन सभी कोर का उपयोग"। यह स्वचालित नहीं है; आपको बस कंपाइलर को यह कहने के बारे में कुछ संकेत देने की ज़रूरत है! क्योंकि हास्केल गैर सख्त है और यह डिफ़ॉल्ट रूप से कुछ भी मूल्यांकन नहीं है :-D

Answer 4

कारण में से एक है।

x :: Maybe ([Int], [Int]) 
x = Just undefined 
y :: Maybe ([Int], [Int]) 
y = Just (undefined, undefined) 
z :: Maybe ([Int], [Int]) 
z = Just ([0], [1..]) 
a :: Maybe ([Int], [Int]) 
a = undefined 
b :: Maybe ([Int], [Int]) 
b = Just ([0], map fib [0..]) 
    where fib 0 = 1 
      fib 1 = 1 
      fib n = fib (n - 1) + fib (n - 2) 

निम्नलिखित कार्य

main1 x = case x of 
       Just _ -> putStrLn "Just" 
       Nothing -> putStrLn "Nothing" 

(a, b) भाग की जरूरत नहीं है के लिए यह विचार करें: सामान्य में संकलक a और b की कि गणना पता नहीं है समाप्त हो जाता है इसलिए गणना करने के लिए यह संसाधनों की बर्बादी होगी कोशिश कर मूल्यांकन के लिए। जैसे ही आप कि एक्स = बस _ आप शाखा लिए आगे बढ़ सकते हैं - इसलिए यह सभी मूल्यों के लिए काम करेगा, लेकिन a

main2 x = case x of 
       Just (_, _) -> putStrLn "Just" 
       Nothing -> putStrLn "Nothing" 

इस समारोह टपल के मूल्यांकन लागू करता है। इसलिए x त्रुटि के साथ समाप्त हो जाएगा जबकि बाकी काम करेंगे।

main3 x = case x of 
       Just (a, b) -> print a >> print b 
       Nothing -> putStrLn "Nothing" 

यह फ़ंक्शन पहले पहली सूची मुद्रित करेगा और फिर दूसरा। यह z के लिए काम करेगा (जिसके परिणामस्वरूप संख्याओं की अनंत स्ट्रीम प्रिंटिंग होगी लेकिन हास्केल इससे निपट सकता है)। b अंततः स्मृति से बाहर हो जाएगा।

अब सामान्य रूप से आप नहीं जानते कि गणना गणना समाप्त हो गई है या नहीं और यह कितने संसाधनों का उपभोग करेगा। अनंत सूचियों हास्केल में बिल्कुल ठीक हैं:

main = maybe (return()) (print . take 5 . snd) b -- Prints first 5 Fibbonacci numbers 

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

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

हालांकि हैस्केल ने par और इसी तरह के कार्यों द्वारा भाषा की शुद्धता को तोड़ने के बिना समांतरता निर्देशित किया है।

Answer 5

वास्तव में ऐसे प्रयास थे, लेकिन कम उपलब्ध मात्रा में कोर के कारण सामान्य हार्डवेयर पर नहीं। परियोजना को कहा जाता है। यह हास्केल कोड को समानांतरता के उच्च स्तर के साथ चलाता है। यदि इसे proper 2 GHz ASIC core के रूप में कभी भी जारी किया गया था, तो हम हास्केल निष्पादन गति में गंभीर सफलता प्राप्त करेंगे।