Making new Unboxed Algebraic Types? (A Repa Problem)

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

Making new Unboxed Algebraic Types? (A Repa Problem)

Hans Georg Schaathun
Hi,

could someone offer som advice on handling composite types with
the Repa library?  I can see a /long/ way around my problem, but
I wonder what is the /best/ way ...

The problem is that I am trying to parallellise a probabilistic
algorithm using Repa.  To handle pseudo-randomness in parallel,
I couple each data element with a generator state, in a tuple.
The generator state is of type TFGen (tf-random package) or
StdGen¹ (random package), neither of which is an Unbox instance.
Hence, I have been using boxed repa arrays.

The code does not execute in parallel, and if I understand correctly
this is because of the Boxed type.  There is a workaround², but that
requires an NFData instance.

To make a NFData instance and work through the code to support it
should be as simple as it is tedious, but it would still leave the
other drawbacks of a boxed type.  (In particular, I do sequential
fold because the Repa fold function did not support boxed types.)

I could of course rewrite the published libraries to use tuples instead
of algebraic types, and benefit from the pre-made Unbox instances, but
sounds messy and error-prone (as well as boring).  If I have to I have
to.

Is there a quick and robust way to make Unbox instances from composite
datatypes?  Or any other advice on how to approach the matter?
Both random ideas, references, and concrete solutions are welcome.

[The other element of the tuple is an vector of unboxed constituent
type.  I am not sure how that's going to work, but I'll cross that
bridge when I get there.  For the time being it is the generator that
stops type checking.]

TIA


¹ Yes, I know that StdGen is statistically unsound.
² http://stackoverflow.com/questions/16097418/parallel-repa-code-doesnt-create-sparks


--
:-- Hans Georg
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Making new Unboxed Algebraic Types? (A Repa Problem)

Carter Schonwald
boxity has nothing to do with parallelism. none :) 


On Mon, Jun 30, 2014 at 2:55 PM, Hans Georg Schaathun <[hidden email]> wrote:
Hi,

could someone offer som advice on handling composite types with
the Repa library?  I can see a /long/ way around my problem, but
I wonder what is the /best/ way ...

The problem is that I am trying to parallellise a probabilistic
algorithm using Repa.  To handle pseudo-randomness in parallel,
I couple each data element with a generator state, in a tuple.
The generator state is of type TFGen (tf-random package) or
StdGen¹ (random package), neither of which is an Unbox instance.
Hence, I have been using boxed repa arrays.

The code does not execute in parallel, and if I understand correctly
this is because of the Boxed type.  There is a workaround², but that
requires an NFData instance.

To make a NFData instance and work through the code to support it
should be as simple as it is tedious, but it would still leave the
other drawbacks of a boxed type.  (In particular, I do sequential
fold because the Repa fold function did not support boxed types.)

I could of course rewrite the published libraries to use tuples instead
of algebraic types, and benefit from the pre-made Unbox instances, but
sounds messy and error-prone (as well as boring).  If I have to I have
to.

Is there a quick and robust way to make Unbox instances from composite
datatypes?  Or any other advice on how to approach the matter?
Both random ideas, references, and concrete solutions are welcome.

[The other element of the tuple is an vector of unboxed constituent
type.  I am not sure how that's going to work, but I'll cross that
bridge when I get there.  For the time being it is the generator that
stops type checking.]

TIA


¹ Yes, I know that StdGen is statistically unsound.
² http://stackoverflow.com/questions/16097418/parallel-repa-code-doesnt-create-sparks


--
:-- Hans Georg
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Making new Unboxed Algebraic Types? (A Repa Problem)

Hans Georg Schaathun
On Mon, Jun 30, 2014 at 03:53:55PM -0400, Carter Schonwald wrote:
> boxity has nothing to do with parallelism. none :)

No, but it may affect /when/ haskell computes a value, and
if the computation is delayed until the value is requested,
then --hey-- we just missed the parallel opportunity.

Quite simply, Repa's computeP does not work as expected out of the
box when it is applied to a boxed return type.
If that amounts to «nothing to do with» in your book, that's ok;
it is still a problem which requires a solution.

BTW, I thought a bit more and the solution using NFData suggested in
http://stackoverflow.com/questions/16097418/parallel-repa-code-doesnt-create-sparks
was easier to implement than I feared, and more importantly, it
works.  I don't find it entirely satisfactory though, so any hints on
how to use unboxed arrays with composite constituent types are still
very welcome.

--
:-- Hans Georg
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Making new Unboxed Algebraic Types? (A Repa Problem)

Hans Georg Schaathun
In reply to this post by Hans Georg Schaathun
On Tue, Jul 01, 2014 at 01:43:32AM +0400, Dmitry Dzhus wrote:
> This implies that the amount of generator states used in your parallel
> computation is equal to data array size N. This is not the case in
> general (unless the computation is split into N processes running in
> parallel by the scheduler). On the contrary, commonly you would even
> want to minimize the amount of generator states used (for resource
> efficiency reasons).

Fair point.  The large number of states may be a disadvantage.

> Generator states may be implicitly passed into sequential
> subcomputations (scheduled by the parallel planner). This of course
> calls for some hacking on Repa harness that runs the computations in
> parallel (computeP).

Such a solution would probably not be determinstic, and it would
definitely make the output depend on the run-time environment
(such as the number of threads).  I am interested in the particular
problem of pseudo-random, /deterministic/, parallel programs.

I think the large number of generator states is necessary to achieve
deterministic, parallel behaviour.  If someone knows otherwise,
I would be curious to learn.

> Some time ago I was also struggling find a way to parallelize a
> probabilistic algorithm (Monte-Carlo molecular simulation) and
> eventually I settled with even simpler solution based on strategies
> instead of Repa:
> https://github.com/dzhus/dsmc/blob/master/src/Control/Parallel/Stochastic.hs.
> It can be easily ported to any stateful mapping computation that needs
> parallelization (including your PRNGs of choice). See the whole package
> for usage examples.

Thanks a lot for the pointer.  I shall have a look.  In fact I am
curious to learn about strategies as well.  (Contrary to low-level
hacking of Repa features which I am not at all curious about :-)

--
:-- Hans Georg
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Making new Unboxed Algebraic Types? (A Repa Problem)

Ben Gamari-2
In reply to this post by Hans Georg Schaathun
Hans Georg Schaathun <[hidden email]> writes:

>
> Is there a quick and robust way to make Unbox instances from composite
> datatypes?
>
You will probably want to look at the vector-th-unbox package[1].

Cheers,

- Ben

[1] http://hackage.haskell.org/package/vector-th-unbox

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

attachment0 (482 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Making new Unboxed Algebraic Types? (A Repa Problem)

Niklas Hambüchen
vector-th-unbox describes one way to make an Unbox instance, but this
StackOverflow answer goes into much more detail:

http://stackoverflow.com/questions/22882228/how-to-store-a-haskell-data-type-in-an-unboxed-vector-in-continuous-memory

On 30/06/14 23:40, Ben Gamari wrote:

> Hans Georg Schaathun <[hidden email]> writes:
>
>>
>> Is there a quick and robust way to make Unbox instances from composite
>> datatypes?
>>
> You will probably want to look at the vector-th-unbox package[1].
>
> Cheers,
>
> - Ben
>
> [1] http://hackage.haskell.org/package/vector-th-unbox
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe