हास्केल में रणनीतियों का उपयोग करके मैं समानांतर कमी कैसे लिखूं?

Question

उच्च प्रदर्शन कंप्यूटिंग, रकम, उत्पाद इत्यादि में अक्सर "समानांतर कमी" का उपयोग करके गणना की जाती है जो n तत्व लेता है और ओ (लॉग एन) समय (पर्याप्त समांतरता प्रदान करता है) में पूरा करता है। हास्केल में, हम आमतौर पर इस तरह की गणना के लिए गुना का उपयोग करते हैं, लेकिन मूल्यांकन समय हमेशा सूची की लंबाई में रैखिक होता है।

डेटा समांतर हास्केल में इनमें से कुछ निर्मित हैं, लेकिन सूची के सामान्य ढांचे में क्या है? क्या हम इसे Control.Parallel.Strategies के साथ कर सकते हैं?

तो, f संभालने साहचर्य है, हम कैसे लिख सकता हूँ

parFold :: (a -> a -> a) -> [a] -> a

ताकि parFold f xs केवल समय लघुगणक length xs में जरूरत है?

Answer 1

मुझे नहीं लगता कि सूची इसके लिए सही डेटा प्रकार है। चूंकि यह सिर्फ एक लिंक की गई सूची है, इसलिए डेटा को अनुक्रमिक रूप से एक्सेस किया जाएगा। यद्यपि आप समानांतर में वस्तुओं का मूल्यांकन कर सकते हैं, आप कमी चरण में ज्यादा लाभ नहीं उठाएंगे। क्या तुम सच में एक सूची की जरूरत है, मुझे लगता है कि सबसे अच्छा समारोह सिर्फ

parFold f = foldl1' f . withStrategy (parList rseq) 

या शायद

parFold f = foldl1' f . withStrategy (parBuffer 5 rseq) 

तो कमी कदम जटिल है, यदि आप एक लाभ इस तरह सूची subdividing द्वारा प्राप्त कर सकते हैं होगा:

parReduce f = foldl' f mempty . reducedList . chunkList . withStrategy (parList rseq) 
where 
    chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls 
    reducedList = parMap rseq (foldl' f mempty) 

मैं अपने डेटा संभालने की स्वतंत्रता लिया है, mempty के लिए एक Monoid है अगर यह संभव नहीं है कि आप या तो अपने स्वयं के खाली प्रकार के साथ mempty जगह ले सकता है, या बुरा मामले उपयोग foldl1'।

यहां उपयोग में Control.Parallel.Strategies से दो ऑपरेटर हैं। parList समानांतर में सूची के सभी आइटमों का मूल्यांकन करता है। उसके बाद, chunkList सूची को 1000 तत्वों के हिस्सों में विभाजित करता है। उन हिस्सों में से प्रत्येक को parMap द्वारा समानांतर में कम किया जाता है।

तुम भी वास्तव में कैसे काम वितरित किया जाता है पर निर्भर करता है

parReduce2 f = foldl' f mempty . reducedList . chunkList 
where 
    chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls 
    reducedList = parMap rseq (foldl' f mempty) 

कोशिश कर सकते हैं, इनमें से एक दूसरों की तुलना में अधिक कुशल हो सकता है।

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

Answer 2

यह एक अच्छी शुरुआत की तरह लगता है:

parFold :: (a -> a -> a) -> [a] -> a 
parFold f = go 
    where 
    strategy = parList rseq 

    go [x] = x 
    go xs = go (reduce xs `using` strategy) 

    reduce (x:y:xs) = f x y : reduce xs 
    reduce list  = list -- empty or singleton list 

यह काम करता है, लेकिन समानांतरवाद इतना महान नहीं है। parList को parListChunks 1000 जैसे कुछ के साथ बदलना थोड़ा सा मदद करता है, लेकिन 8-कोर मशीन पर गति 1.5x से कम तक सीमित है।

Answer 3

सुनिश्चित नहीं है कि आपका parFold फ़ंक्शन क्या करना है। यदि यह फ़ोल्डर या फोल्डल का समांतर संस्करण होने का इरादा है, तो मुझे लगता है कि इसकी परिभाषा गलत है।

parFold :: (a -> a -> a) -> [a] -> a 

// fold right in haskell (takes 3 arguments) 
foldr :: (a -> b -> b) -> b -> [a] -> b 

मोड़ सूची के प्रत्येक तत्व में एक ही फ़ंक्शन लागू करता है और प्रत्येक एप्लिकेशन के परिणाम जमा करता है। इसके समानांतर संस्करण के साथ आ रहा है, मुझे लगता है कि, तत्वों के लिए फ़ंक्शन एप्लिकेशन समानांतर में किया जाता है - थोड़ा सा parList करता है।

par_foldr :: (NFData a, NFData b) => (a -> b -> b) -> b -> [a] -> b 
    par_foldr f z [] = z 
    par_foldr f z (x:xs) = res `using` \ _ -> rseq x' `par` rdeepseq res 
         where x' = par_foldr f z xs 
          res = x `f` x'