8

解決しようとしている問題の1つに並列処理を利用することを考えています。問題は大まかにこれです：与えられた入力（ポイントのシーケンス）が最良の出力（これらのポイントから構成される最大の三角形、最長の線など）を見つけます。ポイントのシーケンスには3つの異なる「形状」がありますが、私は「最高のスコア」（通常は「長さ」×係数の形式）を持つものにのみ関心があります。形状をS1、S2、S3と呼びましょう。

S1を解くための2つの異なるアルゴリズムがあります-「S1a」はO（n 2）にあり、「S1b」はほとんどの場合より適切に動作しますが、最悪の場合はO（n 4）についてです。

最初の質問：S1aとS1bを並行して実行し、最初に終了した方を使用してもう一方を停止する簡単な方法はありますか？私がドキュメントを読んでいる限り、これはいくつかのforkIOを使用してプログラムでき、結果が得られたときにスレッドを強制終了します-もっと簡単なものがあるかどうかを尋ねるだけですか？

2番目の質問-はるかに難しい：私は最適化関数を次のように呼び出しています：

optimize valueOfSx input

valueOfSxはすべての形状に固有であり、可能な解決策である「スコア」（またはスコアの推測）を返します。Optimizeはこの関数を呼び出して、最適なソリューションを見つけます。私が興味を持っているのは：

s1 = optimize valueOfS1 input
s2 = optimize valueOfS2 input
s3 = optimize valueOfS3 input
<- maximum [s1,s2,s3]

ただし、S1の結果がわかっている場合は、小さい解をすべて破棄できるため、より良い解が存在しない場合は、s2とs3の収束が速くなります（または、少なくとも最悪の解を破棄して、スペース効率を高めることができます）。私が今していることは：

zeroOn threshold f = decide .f
    where decide x = if (x < threshold) then 0 else x
s1 = optimize valueOfS1 input
s2 = optimize (zeroOn s1 valueOfS2) input
s3 = optimize (zeroOn (max s1 s2) valueOfS3) input

問題は、たとえばS2とS3をこのように並行して実行できるかどうかです。どちらが先に終了しても、他のスレッドで実行されているスコア関数の「しきい値」パラメーターが更新されますか？ある意味で：

threshold = 0
firstSolution = firstOf (optimize (zeroOn threshold valueOfS2), optimize (zeroOn threshold valueofS3))
update threshold from firstSolution
wait for second solution
4

2 に答える 2

5

最初の質問については、ConalElliottのhttp://hackage.haskell.org/package/unambunambをチェックしてください。

于 2010-02-05T10:33:11.203 に答える
5

最終的には、複数のトランザクションを並行して実行する必要があるため、どのソリューションでも内部でForkIOを使用することになります。Conalのunambでさえこのように機能します。

後者の場合、単調に投稿された改善値についてMVarをときどきチェックする前に、バッチ処理してしばらく実行するより複雑なモナドが必要になる可能性がありますが、インターリーブ（1スレッド内）の最も簡単な答えは、Partialityモナドを作成することです。

data Partial a = Return a | Partial (Partial a)

instance Monad Partial where
    return = Return
    Return a >>= f = f a
    Partial m >>= f = Partial (m >>= k)


run :: Partial a -> a
run (Partial m) = run m
run (Return a) = a

race :: Partial a -> Partial a -> Partial a
race (Return a) _ = a
race _ (Return b) = b
race (Partial m) (Partial n) = race m n

yield :: Partial ()
yield = Partial (Return ())

再帰または自由に振りかけられた「yield」呼び出しを処理するための適切なMonadFixインスタンスを使用すると、部分モナドで両方の操作を実行し、それらを競合させて決定論的な結果を得ることができます。

ただし、実際には、並列処理のメリットを最大限に活用したい場合は、MVarを定期的に更新およびチェックする必要があります。

次のようなもの（袖口から、申し訳ありませんが、コンパイラは便利ではありません！）：

import Control.Concurrent.MVar (newMVar, readMVar)
import Control.Parallel.Strategies (using, parList)
import GHC.IOBase (unsafeDupablePerformIO, unsafePerformIO)

diag x = (x,x)

parMax :: (Bounded a, Ord a) => [a] -> a
parMax xs = unsafePerformIO $ do
    threshold <- newMVar minBound
    let optimize x = unsafeDupablePerformIO $
        x `seq` modifyMVar threshold (return . diag . max x)
    return . maximum $ map optimize xs `using` parList

もちろん、それは、最大値だけでなく、べき等可換モノイドをサポートするように書き直すことができるはずです。

于 2010-02-05T22:24:48.597 に答える