分治算法的并行性

我遇到了问题，使我的代码并行运行。 这是一款使用名为DeWall的分而治之算法的3D Delaunay生成器。

主要功能是：

deWall::[SimplexPointer] -> SetSimplexFace -> Box -> StateT DeWallSets IO ([Simplex], [Edge])
deWall p afl box = do
   ...
   ...
   get >>= recursion box1 box2 p1 p2 sigma edges
   ...
   ...

它调用可能调用dewall函数的“递归”函数。 在这里，平滑机会出现在这里。 以下代码显示了顺序解决方案。

recursion::Box -> Box -> [SimplexPointer] -> [SimplexPointer] -> [Simplex] -> [Edge] -> DeWallSets -> StateT DeWallSets IO ([Simplex], [Edge])    
recursion box1 box2 p1 p2 sigma edges deWallSet
        | null afl1 && null afl2 = return (sigma, edges)
        | (null) afl1 = do
            (s, e) <- deWall p2 afl2 box2
            return (s ++ sigma, e ++ edges)
        | (null) afl2 = do
            (s,e) <- deWall p1 afl1 box1
            return (s ++ sigma, e ++ edges)
        | otherwise   = do
            x <- get
            liftIO $ do
                (s1, e1) <- evalStateT (deWall p1 afl1 box1) x
                (s2, e2) <- evalStateT (deWall p2 afl2 box2) x
                return (s1 ++ s2 ++ sigma, e1 ++ e2 ++ edges)

        where   afl1 = aflBox1 deWallSet
                afl2 = aflBox2 deWallSet

状态和IO monads用于管道状态并为使用MVar发现的每个四面体生成UID。 我的第一个尝试是添加一个forkIO，但它不起作用。 由于合并过程中缺乏控制，不会等待两个线程完成，因此它会给出错误的输出。 我不知道如何让它等待它们。

            liftIO $ do
                let 
                    s1 = evalStateT (deWall p1 afl1 box1) x
                    s2 = evalStateT (deWall p2 afl2 box2) x
                    concatThread var (a1, b1) = takeMVar var >>= (a2, b2) -> putMVar var (a1 ++ a2, b1 ++ b2)
                mv <- newMVar ([],[])
                forkIO (s1 >>= concatThread mv)
                forkIO (s2 >>= concatThread mv)
                takeMVar mv >>= (s, e) -> return (s ++ sigma, e ++ edges)

所以，我的下一个尝试是使用更好的并行策略“par”和“pseq”，它提供了正确的结果，但根据threadScope没有并行执行。

        liftIO $ do
            let
                s1 = evalStateT (deWall p1 afl1 box1) x
                s2 = evalStateT (deWall p2 afl2 box2) x
                conc = liftM2 ((a1, b1) (a2, b2) -> (a1 ++ a2, b1 ++ b2))
            (stotal, etotal) = s1 `par` (s2 `pseq` (s1 `conc` s2))
            return (stotal ++ sigma, etotal ++ edges)

我究竟做错了什么？

更新 ：不知何故，这个问题似乎与IO单子的存在有关。 在没有IO monad的其他（旧）版本中，只有状态monad，并行执行以'par'和'pseq' 。 GHC -sstderr提供SPARKS: 1160 (69 converted, 1069 pruned) 。

recursion::Box -> Box -> [SimplexPointer] -> [SimplexPointer] -> [Simplex] -> [Edge] -> DeWallSets -> State DeWallSets ([Simplex], [Edge])  
recursion p1 p2 sigma deWallSet
     | null afl1 && null afl2 = return sigma
     | (null) afl1 = do
         s <- deWall p2 afl2 box2
         return (s ++ sigma)
     | (null) afl2 = do
         s <- deWall p1 afl1 box1
         return (s ++ sigma)
     | otherwise   = do
                     x <- get
                     let s1 = evalState (deWall p1 afl1 box1) x
                     let s2 = evalState (deWall p2 afl2 box2) x
                     return $ s1 `par` (s2 `pseq` (s1 ++ s2 ++ sigma))
     where   afl1 = aflBox1 deWallSet
             afl2 = aflBox2 deWallSet

云有人解释这一点？

---

使这项工作最简单的方法是使用类似于：

liftIO $ do
            let 
                s1 = evalStateT (deWall p1 afl1 box1) x
                s2 = evalStateT (deWall p2 afl2 box2) x
            mv1 <- newMVar ([],[])
            mv2 <- newMVar ([],[])
            forkIO (s1 >>= putMVar mv1)
            forkIO (s2 >>= putMVar mv2)
            (a1,b1) <- takeMVar mv1
            (a2,b2) <- takeMVar mv2
            return (a1++a2++sigma, b1++b2++edges)

这工作，但有一些不必要的开销。 更好的解决方案是：

liftIO $ do
            let 
                s1 = evalStateT (deWall p1 afl1 box1) x
                s2 = evalStateT (deWall p2 afl2 box2) x
            mv <- newMVar ([],[])
            forkIO (s2 >>= putMVar mv2)
            (a1,b1) <- s1
            (a2,b2) <- takeMVar mv2
             return (a1++a2++sigma, b1++b2++edges)

或者如果结果没有被评估，你可能会希望它们是：

liftIO $ do
        let 
            s1 = evalStateT (deWall p1 afl1 box1) x
            s2 = evalStateT (deWall p2 afl2 box2) x
        mv <- newMVar ([],[])
        forkIO (s2 >>= evaluate >>= putMVar mv2)
        (a1,b1) <- s1
        (a2,b2) <- takeMVar mv2
         return (a1++a2++sigma, b1++b2++edges)

（这些是我在#haskell给海报的答案，我认为这也是有用的）

编辑：删除不必要的评估。

---

par和pseq应发生在“执行路径”上，即不在本地let 。 试试这个（修改你的最后一个片段）

let s1 = ...
    s2 = ...
    conc = ...
case s1 `par` (s2 `pseq` (s1 `conc` s2)) of
  (stotal, etotal) ->
     return (stotal ++ sigma, etotal ++ edges)

在其分支机构继续进行之前，一个case迫使对弱头标准形式（WHNF）的论证进行评估。 WHNF意味着参数被评估直到最外层的构造函数可见。 字段可能仍然是未评估的。

要强制全面评估参数，请使用deepseq 。 不过，要小心，因为deepseq有时候会因做太多工作而让速度变慢。

增加严格性的更轻量级方法是使字段严格：

data Foo = Foo !Int String

现在，只要Foo类型的值被评估为WHNF，它的第一个参数（但不是第二个参数）也是如此。

---

如果您想坚持使用显式线程而不是pseq，则需要一些方法来等待工作线程结束。 对于数量信号来说，这是一个很好的用例。 在完成要完成的工作之后，让每个工作者在终止时发出线程信号，告知信号量已经完成了多少工作。

然后等待所有工作单元完成。

http://www.haskell.org/ghc/docs/6.8.3/html/libraries/base/Control-Concurrent-QSemN.html

编辑：一些伪代码来帮助解释这个概念

do
 let workchunks :: [(WorkChunk, Size)]
     workchunks = dividework work

  let totalsize = sum $ map snd workchunks

 sem <- newQSem 0

 let forkworkThread (workchunk, size) = do
        executeWorkChunk workchunk
        signalQSem size

 mapM_ forkWorkThread workchunks
 waitQSem totalsize

 -- now all your work is done.

链接地址: http://www.djcxy.com/p/68025.html

上一篇: Parallelism on divide & conquer algorithm

下一篇: Can I record/play macros in Visual Studio 2012/2013/2015?