具有快速随机性和纯度的并行计算？

我的目标是并行使用parMap从parallel package计算，但我也想有点随机性添加到我的采样功能。具有快速随机性和纯度的并行计算？

没有随机性我的计算仅仅是一些数字运算，所以它是纯粹的，我可以用parMap。为了获得好的结果，我需要在每个步骤取多个样本并对结果进行平均。采样需要随机化。

一个解决方案可能是使用random package，调用randoms，然后在计算过程中使用该列表（通过将纯懒惰列表传递给计算，我会保持纯净）。不幸的是，这是一个非常缓慢的随机数生成器，我需要大量的随机数，所以我宁愿为使用mwc-random或mersenne-random（虽然，我不认为梅森随机仍维持）。

使用类似unsafePerformIO和mwc-random一起编写像randoms这样的函数是否安全？这样的事情：

randomsMWC :: Variate a => GenST s -> [a] 
randomsMWC g = unsafePerformIO $ unsafeSTToIO $ randomsMWC' g 
    where 
    randomsMWC' g = do 
    a <- uniform g 
    as <- unsafeInterleaveST $ randomsMWC' g 
    return (a : as)

我是否需要改为parallel number generator？还是我需要咬紧牙关，并承认我的算法不是纯粹的，而不使用慢速随机包？

对此提出建议？谢谢！

来源

2013-04-27 Jason Dagit

梅森 - 随机pure64既快速又允许多台发电机 - 所以你可以每个线程一个。 – 2013-04-27 12:07:52

@DonStewart多个生成器对于并行哈希克来说完全没用。没有必要使用并行代码中的线程特定资源，也不应该有 - 它会引入非确定性。这确实是一个难题。 – Carl 2013-04-27 18:05:40

卡尔 - 不是。您可以以数据并行方式复制随机生成，避免共享资源上的争用。例如，考虑树形结构的缩减。 – 2013-04-28 09:20:00

如果有随机性的单线程来源不是性能的问题，让您可以MWC随机纯包装

import Control.Monad.ST.Lazy 
import Control.Monad 
import System.Random.MWC 

rList :: Variate a => Seed -> [a] 
rList s = runST $ do 
    g <- strictToLazyST $ restore s 
    advance g 

advance :: Variate a => Gen s -> ST s [a] 
advance g = do 
    x <- strictToLazyST $ uniform g 
    xs <- x `seq` advance g 
    return (x:xs)

这里rList需要的种子，然后懒洋洋地产生确定性的无限数量的懒惰数字。我不确定strictToLazyST是否真的安全，但似乎没有人反对。我没有做任何基准测试，但我怀疑这很快。我假设mwc-random是线程安全的，因为用生成器编码的explit数据流，并且它可以在ST monad中使用。邀请某人使用上面的黑客。我不认为seq是必要的，但它使我不那么怀疑strictToLazyST，我知道我有确定性的评估顺序（并且它仍然足够工作）。

你仍然需要随机性（即IO）在某处产生一个真正的随机种子，但是这应该让你保持大部分代码是纯的，并且允许你将seed存储到文件中，或者在必要时重用它。

GHCI：

λ: gen <- create 
λ: x <- save gen 
λ: drop 1 $ take 10 $ rList x :: [Int] 
[4443157817804305558,-6283633474236987377,3602072957429409483, 
-5035101780705339502,-925260411398682800,423158235494603307, 
-6981326876987356147,490540715145304360,-8184987036354194323]

来源

2013-04-27 08:34:39

我的猜测是，梅森随机不是线程安全的，所以使用任何unsafe...和并行化会导致你的问题从多个线程调用它。（又见GHC manual节8.2.4.1）

功能需要随机性不是纯，他们需要随机性一些源，其或者是外部的（hardware - 等的装置采样噪声），因此结合于IO，或伪随机，在计算过程中需要保持某种状态。无论哪种方式，他们不能是纯粹的Haskell功能。

我与像

class Monad m => MonadParRand m where 
    random  :: MTRandom a => m a 
    parSequence :: [m a] -> m [a]

，这将让你写你的主代码没有被绑定到特定的实现分离的要求，以特定的单子类型的类，例如东西开始。或者，如果你感觉大胆，你可以使用monad-parallel和定义类似

class MonadParallel m => MonadParRand m where 
    random  :: MTRandom a => m a

现在棘手的问题是如何界定既random和parSequence（或MonadParallel的bindM2）和使其快。由于您掌控bindM2，因此您可以管理线程的产生方式以及它们保持的状态。因此，您可以将缓冲区绑定到每个线程，并从中抽取随机数字。如果缓冲区为空，它会对mersenne-random（或另一个基于IO的数字发生器）进行同步调用，填充缓冲区并继续。

（如果你实现这样的事情，那么从中创建一个独立的库会非常好。）

注意randoms从梅森随机已经使用unsafeInterleaveIO产生懒惰的名单，但我想说的列表旨在从单个线程只消耗。而且它也有改进的余地。它使用unsafeInterleaveIO，它有一些开销，如its comment所述：

这里有实际的开销。考虑急切地填充块和分段提取元素。

来源

2013-04-27 08:12:17

接受PRNG并返回PRNG以及其他内容的函数仍然很纯粹。 – Carl 2013-04-27 18:00:09

@Carl我明白，这只是关于术语。我使用_pure_的意思是说，如果类型为'a'_，则产生'a'类型的值的函数是纯粹的。你使用它可能是因为如果不涉及'IO'_，那么产生'a'类型的函数是纯粹的。关于_pure_的含义的有趣和鼓舞人心的帖子是Conal Elliots [C语言纯粹是功能性的]（http://conal.net/blog/posts/the-c-language-is-purely-functional）。 – 2013-04-27 18:42:20

不，我使用它的意思是“输出仅由输入决定。”这是“纯”的实际有用含义。 – Carl 2013-04-27 19:03:05

我有一个不太准备发布的包hsrandom123上Github可能会有所帮助在这里。我已经开始实施这个软件包，以便为并行计算提供合适的RNG。它从the random123 C library重新实现了Philox和Threefry RNG（还有一篇文章描述了这里的想法）。但是，我的图书馆还没有发布的原因是：虽然实际的RNG实现已经完成，并且似乎产生与C版本相同的结果，但我一直未定什么Haskell接口使用，并且该库几乎没有记录。尽管如果您需要更多信息或帮助使用它，请随时与我联系。

来源

2013-04-27 12:10:30 kosmikus

有趣。如果它没有发布，我不认为我想要使用它，但我期待未来尝试它。 – 2013-04-27 16:56:54

有趣的是，最近我一直在研究Random123的Haskell端口，尽管我发誓我事先做过谷歌搜索，并且找不到其他的Haskell实现。 Mine可以在github.com/Manticore/haskell-random123找到，也可以在Hackage上找到Random123（我准备放弃Hackage条目，因为你显然有优先权）。 – fjarri 2013-05-08 05:08:54

啊，太糟糕了，我们没有协调工作。我的版本在github上已经有一段时间了，但由于它不在Hackage上，我猜这很容易忽视。我会很快看看你的版本。我想我会坚持使用'hsrandom123'这个名字。如果我们达成明确的协议，我们应该将它们包含在文档中，以便用户可以做出明智的选择。 – kosmikus 2013-05-08 08:16:35

为了完整的答案，让我解释我目前在做什么来解决这个问题。

而不是试图使计算纯粹，我选择使用async包而不是parallel。

如果我决定修改我目前的解决方案是纯粹的，我将首先尝试菲利普JF提出的解决方案，所以我已将他的答案标记为已接受的解决方案。

我的下一个挑战是搞清楚如何来近似工作最佳分块，使线程减少的时间量，而不是使其成为需要更长的:)

来源

2013-04-30 03:33:31

具有快速随机性和纯度的并行计算？

回答

相关问题