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

[Manuel M T Chakravarty]

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?
>
>  1. http://hackage.haskell.org/trac/summer-of-code/ticket/1535

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