2

並行して評価したい一連の問題があります。これらの問題は、これに非常によく似た単純な式タイプを使用して表現されます。

-- Expressions are either a constant value or two expressions
-- combined using a certain operation
data Expr 
    = Const NumType
    | Binary BinOp Expr Expr

-- The possible operations
data BinOp = Add | Sub | Mul | Div
    deriving (Eq)

これらの式はオンザフライで構築され、有効または無効な特定の結果に評価される必要があります。これは、無効な結果に遭遇したときに計算を停止するモナドとして表現されます。

data Result a
    = Val { val :: a }
    | Exc { exc :: String }

instance Monad Result where
    return = Val
    (Exc e) >>= _ = (Exc e)
    (Val v) >>= g = g v

解決された各問題の値を決定するために、2 つの関連する関数があります。

eval :: Expr -> Result NumType
score :: Expr -> NumType

そして最後に、 を返す関数を解決しました[Expr]。これにより、現在のメイン関数は次のようになります。

main :: IO ()
main = do
    strAvailableNumbers <- getLine
    strTargetNumber <- getLine
    let numbers = parseList strAvailableNumbers 
        target = parseTargetNumber strTargetNumber in
            sequence $ map (print) $ 
                solveHeuristic1 (Problem target numbers) [Add] [Sub] ++
                solveHeuristic2 (Problem target numbers) 

    return ()

基本的な考え方は、数値のリストとターゲット数値を stdin から読み取り、式を stdout に出力するというものです。

しかし、解決したい 2 つの問題があり、それらがどのように関連しているかはよくわかりません。

  • これらのヒューリスティックはお互いをまったく認識せずに実行されるためscore、それらのソリューションの が他のどのソリューションよりも高いかどうかはわかりません。Exprスコアが以前に印刷されたものよりも高い場合にのみ新しいものを印刷するように、マップ関数にある種の状態を導入したいと思いExprます。

  • これらの計算を並行して実行したいと考えており、(parMap rseq)代わりに を使用し、オプションを使用してmapコンパイルし、を使用して実行しようとしました。その結果、ランタイムが 5 秒から 7 秒に増加します。予想していたものではありませんが、CPU 使用率がより高いことを示しています。を正しく使用していないか、使用して何か間違っていると思います。では、それぞれが要素のリストを返す独立した関数のリストを並列に実行するにはどうすればよいでしょうか?-threaded+RTS -N2timeparMap++

更新:完全なソース コードを含む Gist を作成しました。

4

1 に答える 1

3

ここでの問題は、 でIOアクションを評価しseqてもほとんど何も起こらないことです。したがって、オーバーヘッドを少し増やして順次実行しているだけです。

物事を屈折させて再び純粋にすることができます

main :: IO ()
main = do
    mapM_ (`seq` print "found it") -- make sure we're not 
                                   -- benchmarking printing stuff
          . concat
          . parMap rdeepseq (solve [1..10000000])
          $ [42, 42]

    return ()

そして、物事を完全に評価NFDataする使用するインスタンスを追加しますrdeepseq

instance NFData BinOp -- Binop is just an enum, WHNF = NF

instance NFData Expr where
  rnf (Const a) = a `deepseq` ()
  rnf (Binary b e1 e2) = b `deepseq` e1 `deepseq` e2 `deepseq` ()

そして今、それを実行すると...スタックオーバーフローが発生します。ベンチマークに値するのに十分な時間がかかるようにするために、検索するサイズを十分に大きくしました。現在、両方の構造をメモリに完全にロードすると、スタックが吹き飛ばされます。すべてを吹き飛ばさないところまでスタック サイズを大きくすると、使用し-N2ない場合よりも 40% 速く実行できます (3 秒対 5 秒)。これは、期待される結果と見なされます。これを実行すると、視覚的には、2 つのコアが 100% まで短時間ジャンプすることがわかります。

最終的なコンパイル シーケンス

> ghc -O2 -threaded -rtsops bench.hs
> ./bench +RTS -K10000000 -N2
于 2013-11-06T20:10:06.960 に答える