# [Haskell-cafe] Re: [GSoC] A data parallel physics engine

Manuel M T Chakravarty chak at cse.unsw.edu.au
Mon Mar 10 19:48:25 EDT 2008

```Roman Cheplyaka:
> I'm looking for interesting project to work on during Google Summer of
> Code. So I found [1]"A data parallel physics engine" ticket and got
> excited about it. I'd like to know interested mentors and community
> opinion about the complexity of such project.
>
> I have not very deep knowledge about both NDP and physics engines. Is
> it feasible to learn all the necessary stuff during these 2 month
> before
> SoC starts?
>

Using NDP is actually pretty easy, that is, for somebody who is
already used to functional programming.  The idea is, for anything you
want to have running in parallel, don't use explicit recursion, but
use list comprehensions (well, array comprehensions, but it's the same
idea) and combinators like mapP, foldP, scanP, etc (which are also
like their list variants).  Here, for example, is quicksort:

> qsort      :: Ord a => [:a:] -> [:a:]
> qsort [::]  = [::]
> qsort xs    = let
> 	        m  = xs!:0
> 		ss = [:x | x <- xs, x <  m:]
> 		ms = [:x | x <- xs, x == m:]
> 		gs = [:x | x <- xs, x >  m:]
> 	        qs = [:qsort ys | ys <- [:ss, gs:]:]
> 	      in
> 	      qs!:0 +:+ ms +:+ qs!:1

where [:a:] is the type of arrays of as, [::] is an empty array, [: ..
| .. :] are array comprehensions, (!:) is array indexing, and (+:+)
array concatenation.  The only funny thing is the bindings of qs,
where we put ss and gs into an array and apply qsort recursively
*inside* an array comprehension.  This is so that the two recursive
calls to qsort happen in parallel.

Getting good parallel performance is the tricky bit, but in a project
like the physics engine for GSoC, a basic parallelisation strategy is
sufficient and performance can then be improved incrementally.  We
don't expect anybody to implement a fully-fledged, fully parallelised,
high-performance physics engine during GSoC.  It is rather about
laying a solid foundation on which we can then build over time.  (GSoC
is a lot about getting exciting open source projects of the ground,
not about producing a polished product that doesn't change anymore
after GSoC.)

Besides, there is more to physics engines than just collision
detection.  Another aspect is physical simulations of non-solid
bodies, such as liquids and cloth - re the latter, see <http://graphics.snu.ac.kr/~kjchoi/publication/cloth.pdf
> for an interesting SIGGRAPH paper.  What aspect we'd cover in the
GSoC project would really be a matter of what you are most interested
in.

So, overall, I agree with that this is an exciting project ;)

Manuel

```