Data parallel physics engine
============================

Synopsis
~~~~~~~~
This project's goal is to implement a high-performance, parallel physics engine
using Data Parallel Haskell.

Details
~~~~~~~
Parallel computing has recently become the dominant paradigm in computer
architecture. This is caused by limitations of traditional approaches to
boosting CPU performance. Hyperthreading and multicore architectures are very
common these days, and there is a big demand for libraries and tools which can
exploit the new processor capabilities.

Data Parallel Haskell is the codename for an extension to the Glasgow Haskell
Compiler and its libraries to support nested data parallelism with a focus to
utilise multi-core CPUs. Nested data parallelism (NDP) extends the programming
model of flat data parallelism to irregular parallel computations and irregular
data structures.

Currently NDP extension is under active development. One of the problems is the
lack of code which would intensively use data parallelism.

I plan to implement 2D rigid body physics simulation engine using NDP
extension to Haskell. My goals are the following:
- extensibility -- so that necessary features can be added easy and engine can
  then be developed into a fully-fledged library for a range of applications
  (games, education software, simulations, visualisation etc.)
- high degree of parallelization (see benefits below)

Deliverables
~~~~~~~~~~~~
- Physics engine itself
- Some simple OpenGL interface to be able to demonstrate the capabilities of
  the engine, plus few working (and, possibly, impressing) sample simulations
- QuickCheck tests to ensure correctness of the engine
- Good documentation, including the description of the design and algorithms we
  use to achieve parallelization

Benefits
~~~~~~~~
- Developers of NDP will get the sample code to test the abilities of NDP
- Once NDP is able to run simulations with high performance, this engine can be
  used for promoting the abilities of NDP and Haskell parallelism in general
- The code can be used as starting point for developers which would like to use
  NDP in other areas

Roadmap
~~~~~~~
- Studying papers about data parallel algorithms and rigid body
  simulation (pre-coding period)
- Writing skeleton code. Designing the architecture to be extensible in
  future. Implementing some simple objects and shapes
- Collision detection and reaction
- Creating OpenGL visualisation
Goals for mid-term evaluation: being able to run billiard or domino game.

- Evaluation of sequential and parallel performance by a set of benchmarks
- Identify parallel performance bottlenecks and, depending on the type of
  bottlenecks, investigate alternative parallel algorithms or optimisation
  strategies for the already implemented algorithms
- Adding more features (e.g. joints, more complex shapes), testing extensibility
Goals for final evaluation: perhaps some CPU-intensive simulation, to show
profit from using data parallelism.

Interaction with community
~~~~~~~~~~~~~~~~~~~~~~~~~~
To ensure the success of the project I'm going to make the development as open
as possible. Besides communicating with my mentors directly, I'll create a
weblog where I'll publish my news about the project (such as achievements I've
made or problems I'm experiencing), and mandatory weekly reports on what I've
done and what I'm going to do for the next week. I think it's worth to get this
blog aggregated by Planet Haskell (and possibly some other such aggregators) to
stay in touch with community.

My motivation
~~~~~~~~~~~~~
I am excited about working under the supervision of NDP developers, 
Manuel M T Chakravarty and Roman Leshchinskiy, who are going to be my mentors.
So I can learn more about how NDP works and join NDP development in future.

About myself
~~~~~~~~~~~~
Currently I am a third-year student at Odessa State University, Ukraine.
I am a contributor to xmonad, window manager written in Haskell.
I used to give lectures on Haskell for a local programmers community.

Links
~~~~~
Trac ticket: http://hackage.haskell.org/trac/summer-of-code/ticket/1535
Discussion on Haskell-cafe: http://groups.google.de/group/fa.haskell/browse_thread/thread/6fe229d51dfa5bc3/23502b858d705056?lnk=raot
My homepage, including contact info and more biography: http://ro-che.info/
Data Parallel Haskell: http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell
Wikipedia on data parallelism: http://en.wikipedia.org/wiki/Data_parallelism
Wikipedia on physics engine: http://en.wikipedia.org/wiki/Physics_engine
Wikipedia on parallel computing: http://en.wikipedia.org/wiki/Parallel_computing
"The Free Lunch Is Over", article explaining the importance of parallel computation: http://www.gotw.ca/publications/concurrency-ddj.htm

 vim:tw=80