हास्केल

Question

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

यह समानांतर एन क्वींस के लिए कोड,

import Control.Monad 
import System.Environment 
import GHC.Conc 
import Control.Parallel.Strategies 
import Data.List 
import Data.Function 

type PartialSolution = [Int] -- per column, list the row the queen is in 
type Solution = PartialSolution 

type BoardSize = Int 

chunk :: Int -> [a] -> [[a]] 
chunk n [] = [] 
chunk n xs = case splitAt n xs of 
     (ys, zs) -> ys : chunk n zs 

-- Generate all solutions for a given board size. 
queens :: BoardSize -> [Solution] 
--queens n = iterate (concatMap (addQueen n)) [[]] !! n 
queens n = iterate (\l -> concat (map (addQueen n) l `using` parListChunk (n `div`   numCapabilities) rdeepseq)) [[]] !! n 


-- Given the size of the problem and a partial solution for the 
-- first few columns, find all possible assignments for the next 
-- column and extend the partial solution. 
addQueen :: BoardSize -> PartialSolution -> [PartialSolution] 
addQueen n s = [ x : s | x <- [1..n], safe x s 1 ] 

-- Given a row number, a partial solution and an offset, check 
-- that a queen placed at that row threatens no queen in the 
-- partial solution. 
safe :: Int -> PartialSolution -> Int -> Bool 
safe x [] n = True 
safe x (c:y) n = x /= c && x /= c + n && x /= c - n && safe x y (n + 1) 

main = do 
     [n] <- getArgs 
     print $ length $ queens (read n) 

लाइन (\l -> concat (map (addQueen n) l using parListChunk (n div numCapabilities) rdeepseq)) मैं क्या मूल कोड से बदल रहा है। मैंने साइमन मार्लो के समाधान को देखा है लेकिन मैं अपने कोड में मंदी और त्रुटि के कारण को जानना चाहता था।

अग्रिम धन्यवाद।

Answer 1

आप बहुत अधिक काम कर रहे हैं। parListChunkdiv n numCapabilities का पैरामीटर शायद आपके सिस्टम पर 7, 2 कोर और आप एन ~ 14 के साथ चल रहे हैं)। सूची बहुत तेजी से बढ़ने जा रही है, इसलिए काम की ऐसी छोटी इकाइयों को चमकाने में कोई बात नहीं है (और मुझे नहीं लगता कि यह n के मूल्य पर क्यों लगा रहा है)।

यदि मैं दस का कारक जोड़ता हूं (इस मामले में स्पार्किंग इकाई 70 बना रहा हूं) तो मुझे सिंगल थ्रेडिंग पर स्पष्ट प्रदर्शन जीत मिलती है। साथ ही, मेरे पास स्टैक समस्या नहीं है जिसका आप उल्लेख करते हैं - यदि यह आपके parListChunk मान में परिवर्तन के साथ चला जाता है तो मैं उस बग के रूप में रिपोर्ट करूंगा।

यदि मैं हर 800 को तोड़ देता हूं तो समय 5.375 के बनाम 7.9 के ऊपर रहता है। 800 से अधिक और प्रदर्शन फिर से खराब हो जाना शुरू होता है, ymmv।

संपादित करें:

[tommd@mavlo Test]$ ghc --version 
The Glorious Glasgow Haskell Compilation System, version 7.0.4 
[tommd@mavlo Test]$ ghc -O2 so.hs -rtsopts -threaded -fforce-recomp ; time ./so 13 +RTS -N2 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
73712 
real 0m5.404s 

[tommd@mavlo Test]$ ghc -O2 so.hs -rtsopts -fforce-recomp ; time ./so 13 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
73712 
real 0m8.134s