[ODE] Parallelizing ODE?

[Kenneth Holmlund]

Russ Smith wrote:

>>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.
>>
These are the ovious things to do, and that would be of great interest 
in the
simulation industry where more and more solutions are based on Beowulf 
clusters.
The cost of a pile of PC:s is negligible compared to development costs 
and what
the industry traditionally has invested in SME hardware.

All this requires an efficient simulation kernel with a broker that 
manages load
and synchronization of e.g. multi-pipe rendering, collisions, dynamics, I/O
and interaction, rendering of spatial audio, AI/behavioural engines, etc...
Does anyone know about scientific publications or examples of 
implementations
that deal with this problem?

>>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.
>>
How large is a "large connected system"? 500 bodies? More?
This isn't really my own field of expertize, but we do have a research 
group here with
a very strange desire for matrix algebra 
(http://www.cs.umu.se/research/parallel/)
so if we find a student that is interested we might take a look at it.

/Kenneth

-- 
Kenneth Holmlund
Director VRlab
HPC2N, Umeå University, Sweden
holmlund at hpc2n.umu.se
T: +46-90-786 9655
C: +46-70-631 5520