12

Haskell は、現在のスレッドと並行して可能なpar評価のために「スパーク」をキューに入れるコンビネータを提供します。また、純粋なコードの評価を特定の順序で強制的に実行するコンビネータも提供します。pseq

Haskell が提供していないように見えるのは、いくつかのスパークを生成し、それらがすべて終了するのを待つ方法です。これは、明示的な並行性で達成するのは非常に簡単ですが、純粋なスパークでは不可能のようです。

部分的には、これはおそらくスパークの意図されたユースケースによるものです。それらは投機的評価用に設計されているようです。つまり、必要かもしれないがそうではないかもしれない仕事をすることです。したがって、スパークはアイドル状態のコアでのみ実行されます。

ただし、これは私のユースケースではありません。実際、すぐに必要になるとわかっている結果がたくさんあります。そして、火花が出る前に結果を処理しようとすると、再びシングル スレッドになってしまい、たくさんの火花が散らばってしまいます。

もちろん、スパークが完了するのをpar 待っても、並列処理は実現しません! しかし、いくつかの火花を生成し、それらがすべて終了するのを待つ方法があれば、非常に便利です。私はそれを行う方法を見つけることができません。

誰にも有用な提案はありますか? (明らかに、「明示的な並行性を使用する」以外は。)

4

2 に答える 2

6

本当に短い答え

できません。

短い答え

スパークが終了するのを待つには、スパークが評価していたものを評価してみてください。たとえば、aとbを計算する式がある場合a + b、次のように実行できます。

a `par` b `par` (a + b)

また

a `par` b `pseq` (a + b)

長い答え

を使用してスパークを作成するparと、ランタイム システムに「後でこの値が必要になるので、並行して評価する必要があります」と伝えられます。後で値が必要になったときに、スパークが式を評価したか、評価していないかのどちらかです。存在する場合、サンクは値に置き換えられるため、再評価にコストはかかりません。値をフェッチするだけです。スパークで評価されていない場合、スパークを待っても無駄です。スケジュールを取得するのに時間がかかる可能性があり、スレッドの待機は時間を無駄にします。待つ代わりに、自分で式を評価するだけです。基本的に、スパークを待つ必要はありません。元の式を評価して、パフォーマンス上のメリットを得ようとするだけです。

また、投機に関する注意 - 火花は投機に使用される可能性があり、多くの場合投機に使用されますが、それは完全に投機のために設計されたものではありません。par以下のように、単純な並列化に使用されることpfibが多く、推測に使用されるよりもはるかに頻繁に使用されます。

例

標準的な例は、シリアルからフィボナッチ数を並列化することです

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

パラレルへ

pfib 0 = 0
pfib 1 = 1
pfib n = l `par` r `pseq` (l + r) where
    l = pfib (n - 1)
    r = pfib (n - 2)

.

次に、投機を使用した例を示します。

spec :: a -- a guess to the input value
    -> (a -> b) -- a function to tranform the input value
    -> a -- the actual input value - this will require computation
    -> b -- the function applied to the input value
spec guess f input = let speculation = f guess in speculation `par`
    if guess == input
        then speculation
        else f input

私がこれを入手した投機パッケージには、実際には単一のコアでこれを行わず、入力が既に評価されているかどうかを確認するなどのいくつかの最適化がありましたが、それは関数の動作には関係ありません。

物事をより明確にするその他のソリューション

  • モナドパー
  • を利用する戦略par。
  • IOをいじる。ここにはたくさんのことがあります。
于 2012-08-07T04:19:52.720 に答える
6

スパークした計算の結果を厳密なデータ構造に入れてみることができます

{-# LANGUAGE BangPatterns #-}
module Main where

import Control.Parallel

fib :: Int -> Int
fib n
    | n < 1     = 0
    | n == 1    = 1
    | otherwise = fib (n-1) + fib (n-2)

trib :: Int -> Int
trib n
    | n < 1     = 0
    | n < 3     = 1
    | otherwise = trib (n-1) + trib (n-2) + trib (n-3)

data R = R { res1, res2 :: !Int }

main :: IO ()
main = do
    let !r = let a = fib 38
                 b = trib 31
             in a `par` b `pseq` (R a b)
    print $ res1 r
    print $ fib 28
    print $ res2 r

それはここで働いた：

$ ./spark +RTS -N2 -s
39088169
317811
53798080
          65,328 bytes allocated in the heap
           9,688 bytes copied during GC
           5,488 bytes maximum residency (1 sample(s))
          30,680 bytes maximum slop
               2 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0         1 colls,     0 par    0.00s    0.00s     0.0001s    0.0001s
  Gen  1         1 colls,     1 par    0.00s    0.00s     0.0001s    0.0001s

  Parallel GC work balance: 1.33 (686 / 515, ideal 2)

                        MUT time (elapsed)       GC time  (elapsed)
  Task  0 (worker) :    0.59s    (  0.59s)       0.00s    (  0.00s)
  Task  1 (worker) :    0.00s    (  0.59s)       0.00s    (  0.00s)
  Task  2 (bound)  :    0.59s    (  0.59s)       0.00s    (  0.00s)
  Task  3 (worker) :    0.00s    (  0.59s)       0.00s    (  0.00s)

  SPARKS: 1 (1 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    1.17s  (  0.59s elapsed)
  GC      time    0.00s  (  0.00s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    1.18s  (  0.59s elapsed)

  Alloc rate    55,464 bytes per MUT second

  Productivity  99.9% of total user, 199.1% of total elapsed

gc_alloc_block_sync: 0
whitehole_spin: 0
gen[0].sync: 0
gen[1].sync: 0
于 2012-08-06T13:04:04.683 に答える