हास्केल वैक्टर के साथ समांतर कोड कैसे लिखें?

Question

एक हाथ, हास्केल Vector a में संख्याओं की सरणी के रूप में उपयोग करने के लिए पसंदीदा प्रकार प्रतीत होता है। यहां तक ​​कि एक (अपूर्ण) Vector Tutorial भी है।

दूसरी ओर, Control.Parallel.Strategies अधिकतर Traversable के संदर्भ में परिभाषित किया गया है। वेक्टर पुस्तकालय इन उदाहरणों को प्रदान नहीं करता है।

Traversable t के न्यूनतम पूरा परिभाषा भी परिभाषित करना चाहिए Foldable और

traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 
sequenceA :: Applicative f => t (f a) -> f (t a) 

मैं नहीं दिख रहा है कि कैसे sequenceAData.Vector.Unboxed.Vector के लिए परिभाषित किया जा सकता है। तो, अनबॉक्स किए गए वैक्टर के साथ समांतर कोड लिखने का सबसे अच्छा तरीका क्या है? evalVector जैसी कुछ नई विज्ञापन रणनीतियों को परिभाषित करना या par और pseq स्पष्ट रूप से या वैक्टरों के बजाय सादे Data.Array का उपयोग करना?

पीएस सादा Array रों समस्याओं के बिना चलाने योग्य हैं: https://gist.github.com/701888

Answer 1

यह parVector के लिए एक हैक काम है लेकिन यह मेरे लिए काम किया:

import qualified Data.Vector as V 
import Control.Parallel.Strategies 
import Control.Parallel 
import Control.DeepSeq 

ack :: Int -> Int -> Int 
ack 0 n = n+1 
ack m 0 = ack (m-1) 1 
ack m n = ack (m-1) (ack m (n-1)) 

main = do 
    let vec = V.enumFromN 1 1000 
    let res = (V.map (ack 2) vec) `using` parVector 
    print res 

parVector :: NFData a => Strategy (V.Vector a) 
parVector vec = eval vec `seq` Done vec 
    where 
    chunkSize = 1 
    eval v 
    | vLen == 0 =() 
    | vLen <= chunkSize = rnf (v V.! 0) -- FIX this to handle chunks > 1 
    | otherwise = eval (V.take half v) `par` eval (V.drop half v) 
    where vLen = V.length v 
      half = vLen `div` 2 

और इस कोड चलाने:

[tommd@Mavlo Test]$ ghc --make -O2 -threaded t.hs 
... dumb warning ... 
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null 
real 0m1.962s user 0m1.951s sys  0m0.009s 
[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null 
real 0m1.119s user 0m2.221s sys 0m0.005s 

जब मैं Integer बजाय Int में साथ कोड को चलाने प्रकार हस्ताक्षर:

[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null 

real 0m4.754s 
user 0m9.435s 
sys  0m0.028s 
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null 

real 0m9.008s 
user 0m8.952s 
sys  0m0.029s 

रॉक!

संपादित करें: और एक समाधान है कि एक सा अपने पहले प्रयास के करीब है क्लीनर है (यह तीन अलग-अलग मॉड्यूल से कार्यों का उपयोग नहीं करता है) और अच्छा काम करता है:

parVector :: NFData a => Strategy (V.Vector a) 
parVector vec = 
    let vLen = V.length vec 
     half = vLen `div` 2 
     minChunk = 10 
    in if vLen > minChunk 
     then do 
     let v1 = V.unsafeSlice 0 half vec 
      v2 = V.unsafeSlice half (vLen - half) vec 
     parVector v1 
     parVector v2 
     return vec 
     else 
     evalChunk (vLen-1) >> 
     return vec 
    where 
    evalChunk 0 = rpar (rdeepseq (vec V.! 0)) >> return vec 
    evalChunk i = rpar (rdeepseq (vec V.! i)) >> evalChunk (i-1) 

हालात इस समाधान से जानने के लिए:

1. यह Eval इकाई है, जो सख्त है का उपयोग करता है तो हम (let में चीजों को लपेटकर और धमाके के पैटर्न का उपयोग करने के याद की तुलना में) सब कुछ चिंगारी करने के लिए सुनिश्चित कर रहे हैं।
2. अपने प्रस्तावित कार्यान्वयन के विपरीत यह (क) एक नई वेक्टर, जो महंगा है (ख) evalChunk बलों rpar और rdeepseq का उपयोग कर प्रत्येक तत्व के मूल्यांकन का निर्माण नहीं करता है (मैं rpar vec बलों पर विश्वास नहीं करते वेक्टर के तत्वों के किसी भी) ।
3. मेरी धारणा के विपरीत, slice एक प्रारंभ सूचकांक और लंबाई लेता है, न कि प्रारंभ और अंत अनुक्रमणिका। ऊप्स!
4. हमें अभी भी Control.DeepSeq (NFData) आयात करने की आवश्यकता है, लेकिन मैंने उस समस्या को हल करने और ठीक करने के लिए पुस्तकालय सूची को ई-मेल किया है।

प्रदर्शन इस उत्तर में पहले parVector समाधान के समान लगता है, इसलिए मैं संख्या पोस्ट नहीं करूंगा।

Answer 2

1) आप शायद जानते हैं, vectorDPH काम है कि शोधकर्ताओं ने शुरू में उम्मीद की तुलना में कठिन साबित हो गया है की एक उत्पाद है।

2) अनबॉक्स किए गए वैक्टर एकाधिक CPUs में अलग-अलग तत्वों के लिए काम को विभाजित नहीं कर सकते हैं।

3) मैं बॉक्स किए गए वैक्टरों के लिए बहुत अधिक आशावादी हूं। कुछ ऐसा:

using (map (rnf . (vec !)) [0..V.length vec - 1]) (parList rdeepseq) 

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

parVector :: Strategy (Vector a) 
parVector = let !_ = eval vec in Done vec 
    where 
    chunkSize = 1 
    eval v 
    | vLen == 0 =() 
    | vLen <= chunkSize = rnf (v ! 0) -- FIX this to handle chunks > 1 
    | otherwise = eval (V.take half v) `par` eval (V.drop half v) 
    where vLen = V.length v 
      half = vLen `div` 2