[Haskell-cafe] Parallel graphics

[Edward Kmett]

Block, line or 'beam' decomposition tends to work well for raytracing tasks,
because they tend to give you a good cache locality and don't create a
ridiculous explosion of parallel jobs.

You'll need to do some tuning to figure out the right granularity for the
decomposition. But typically a few hundred tasks works a lot better than
tens of thousands or millions. You need to balance the tension between
having too much overhead maintaining the decomposition with wasted work from
lumpy task completion times and coarse grain sizes.

Unfortunately, using Haskell it is hard to do what you can do, say, in C++
with Intel Thread Building Blocks to get a self-tuning decomposition of your
range, which self-tunes by splitting stolen tasks. You don't get the same
visibility into whether or not the task you are doing was stolen from
elsewhere when using GHC's sparks.

-Edward Kmett

On Tue, Sep 15, 2009 at 7:48 AM, Andrew Coppin
<andrewcoppin at btinternet.com>wrote:

> I have a number of compute-bound graphics programs written in Haskell.
> (Fractal generators, ray tracers, that kind of thing.) GHC offers several
> concurrency and parallelism abstractions, but what's the best way to use
> these to get images rendered as fast as possible, using the available
> compute power?
>
> (OK, well the *best* way is to use the GPU. But AFAIK that's still a
> theoretical research project, so we'll leave that for now.)
>
> I've identified a couple of common cases. You have a 2D grid of points, and
> you want to compute the value at each point. Eventually you will have a grid
> of *pixels* where each value is a *colour*, but there may be intermediate
> steps before that. So, what cases exist?
>
> 1. A point's value is a function of its coordinates.
>
> 2. A point's value is a function of its previous value from the last frame.
>
> 3. A point's value is a function of *several* points from the last frame.
>
> How can we accelerate this? I see a few options:
>
> - Create a spark for every point in the grid.
> - Create several explicit threads to populate non-overlapping regions of
> the grid.
> - Use parallel arrays. (Does this actually works yet??)
>
> I'm presuming that sparking every individual point is going to create
> billions of absolutely tiny sparks, which probably won't give great
> performance. We could spark every line rather than every point?
>
> Using explicit threads has the nice side-effect that we can produce
> progress information. Few things are more frustrating than staring at a
> blank screen with no idea how long it's going to take. I'm thinking this
> method might also allow you to avoid two cores tripping over each other's
> caches.
>
> And then there's parallel arrays, which presumably are designed from the
> ground up for exactly this type of task. But are they usable yet?
>
> Any further options?
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090915/e11f4d96/attachment-0001.html