parallelism and state

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

parallelism and state

Dennis Raddle
I'm trying to parallelize a Monte Carlo backtracking search algorithm. The trick is that my algorithm is expressed in a State monad, because I need to hold a StdGen as well as keep several records of computations and metrics.

So I know that if I'm going to run a State computation in several parallel lines of execution, I need to conceive of a way to split the state and later recombine it.

Here is a simple example I came up with. I have no idea if I'm doing this in a good way, so any comments are welcome.

http://lpaste.net/356879

D


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: parallelism and state

Li-yao Xia-2
For a splittable PRNG, check out tf-random.

LY

On 07/11/2017 09:11 PM, Dennis Raddle wrote:

> I'm trying to parallelize a Monte Carlo backtracking search algorithm. The
> trick is that my algorithm is expressed in a State monad, because I need to
> hold a StdGen as well as keep several records of computations and metrics.
>
> So I know that if I'm going to run a State computation in several parallel
> lines of execution, I need to conceive of a way to split the state and
> later recombine it.
>
> Here is a simple example I came up with. I have no idea if I'm doing this
> in a good way, so any comments are welcome.
>
> http://lpaste.net/356879
>
> D
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: parallelism and state

Oleg Grenrus
I recently made a SplitMix implentation:
http://hackage.haskell.org/package/splitmix

When generating `Word64`s it's noticeable faster than `tf-random` (and
`mwc-random` and obviously `random). I didn't benchmark `Double`
generation, as `tf-random` own `Random` class doesn't support it [1],
and using `random`'s class would be very unfair.

I haven't announced it (well, mentioned on Twitter), but please give it
a try!

- Oleg

-[1]
http://hackage.haskell.org/package/tf-random-0.5/docs/System-Random-TF-Instances.html

On 12.07.2017 04:21, Li-yao Xia wrote:

> For a splittable PRNG, check out tf-random.
>
> LY
>
> On 07/11/2017 09:11 PM, Dennis Raddle wrote:
>> I'm trying to parallelize a Monte Carlo backtracking search
>> algorithm. The
>> trick is that my algorithm is expressed in a State monad, because I
>> need to
>> hold a StdGen as well as keep several records of computations and
>> metrics.
>>
>> So I know that if I'm going to run a State computation in several
>> parallel
>> lines of execution, I need to conceive of a way to split the state and
>> later recombine it.
>>
>> Here is a simple example I came up with. I have no idea if I'm doing
>> this
>> in a good way, so any comments are welcome.
>>
>> http://lpaste.net/356879
>>
>> D
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>> Only members subscribed via the mailman list are allowed to post.
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: parallelism and state

Dominic Steinitz-2
In reply to this post by Dennis Raddle
Excellent news! How did you test it? One way would be to make it callable by C and then use testu01 but perhaps you have already done this or similar? See here for a bit more detail: https://idontgetoutmuch.wordpress.com/2017/01/14/calling-haskell-from-c/. Testing the split function might need thinking about though.

I recently made a SplitMix implentation:
http://hackage.haskell.org/package/splitmix

When generating `Word64`s it's noticeable faster than `tf-random` (and
`mwc-random` and obviously `random). I didn't benchmark `Double`
generation, as `tf-random` own `Random` class doesn't support it [1],
and using `random`'s class would be very unfair.

I haven't announced it (well, mentioned on Twitter), but please give it
a try!

- Oleg



_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.