[ODE] Parallelizing ODE?

[Russ Smith]

> Russel (and everyone else), have you given parallelization of ODE
> a thought? We think it would be a cool idea to run ODE on the
> 64 dual P4 2Ghz Beowulf cluster that we are building right now and
> make that feed a parallelized scenegraph on a 4 node graphics
> cluster.

the easiest ways to parallelize ODE are at the very high level, and
very low level. at the low level, using intel SIMD speedups will get
about a *2 performance increase. at the high level:
  1. split collision, dynamics and rendering as you suggest.
  2. each separate island in ODE can be stepped by a different CPU.
both of these things are rather easy. the second should not require
much modification to ODE, and will use as many processors as you
have islands. this is the best approach, unless your system has
very few, large, islands.

> This would require some profiling of the ODE core to check where
> the bottlenecks are, and how well it actually can be parallelized,

to quote from an earlier email, two things take up 80-90% of the time
in a "typical" system.
  1. filling in a "system matrix" using data from the rigid bodies and
     constraints.  this involves lots of relatively small matrix
     multiplications, with dimensions around 1..6. this operation is
     about O(n)+O(m), where n is the number of rigid bodies and m is
     the number of joints (constraints). every pair of joints connected
     to a body adds another block to the matrix. you can parallelize
     all pairs on all bodies, there are no data dependencies. also, the
     small matmuls are great for SIMD optimization.
  2. factorizing that matrix. the matrix is symmetric positive definite
     so i use an L*D*L' factorization. this operation is O(m^3), so as
     m goes up this starts to dominate. parallelizing factorization is
     an area of intense study, and it can get pretty tricky. the matrix
     graph analysis and other overhead will mean this is only
     worthwhile for large connected systems.

russ.

--
Russell Smith
http://www.q12.org