search

sofa-framework / sofa

Real-time multi-physics simulation with an emphasis on medical simulation.
https://www.sofa-framework.org
GNU Lesser General Public License v2.1
871 stars 297 forks source link

[LinearSystem] Introduce ConstantSparsityProjectionMethod #4552

Closed alxbilger closed 2 months ago

alxbilger commented 2 months ago

Based on https://github.com/sofa-framework/sofa/pull/4547. The diff: https://github.com/alxbilger/sofa/compare/sparsematrixproduct...alxbilger:sofa:constantsparsityprojection

Matrix projection method taking advantage of the constant sparsity of the matrices in the computation of sparse matrix product. A boolean Data enables parallel computation.

Benchmark on the reduced diamond for 1000 time steps (previous results in https://github.com/sofa-framework/sofa/pull/4490):

MatrixProjectionMethod + areJacobiansConstant=False

This is the most generic method

[INFO]    [BatchGUI] 1000 iterations done in 13.576 s ( 73.6594 FPS).
 LEVEL   START    NUM      MIN     MAX   MEAN     DEV    TOTAL  PERCENT ID
   6       0.84    1       9.59   24.93   11.24    2.22   11.24   88.66 ......projectMappedMatrices

MatrixProjectionMethod + areJacobiansConstant=True

[INFO]    [BatchGUI] 1000 iterations done in 8.1806 s ( 122.24 FPS).
 LEVEL   START    NUM      MIN     MAX   MEAN     DEV    TOTAL  PERCENT ID
   6       0.75    1       5.53   17.84    6.32    0.88    6.32   83.28 ......projectMappedMatrices

ConstantSparsityProjectionMethod + areJacobiansConstant=True + parallelProduct=False

[INFO]    [BatchGUI] 1000 iterations done in 11.3896 s ( 87.799 FPS).
 LEVEL   START    NUM      MIN     MAX   MEAN     DEV    TOTAL  PERCENT ID
   6       0.82    1       7.71  510.45    9.73   15.92    9.73   87.39 ......projectMappedMatrices

Note that the timer includes the first iteration which is very very slow. It alters the average.

ConstantSparsityProjectionMethod + areJacobiansConstant=True + parallelProduct=True

[INFO]    [BatchGUI] 1000 iterations done in 4.48981 s ( 222.726 FPS).
 LEVEL   START    NUM      MIN     MAX   MEAN     DEV    TOTAL  PERCENT ID
  6       0.75    1       2.31  522.09    3.32   16.42    3.32   72.50 ......projectMappedMatrices

Note that the timer includes the first iteration which is very very slow. It alters the average.

Conclusion

We can observe that the parallelism is necessary to take advantage of the constant sparsity pattern. The fastest configuration is now ConstantSparsityProjectionMethod + areJacobiansConstant=True + parallelProduct=True compared to MatrixProjectionMethod + areJacobiansConstant=True before this PR. It's a speed up of x1.8.

For the records, at the beginning of this series of enhancement (https://github.com/sofa-framework/sofa/pull/4443), the reduced diamond run at 44 FPS. Now it is 222 FPS = speed up x5.

By submitting this pull request, I acknowledge that
I have read, understand, and agree SOFA Developer Certificate of Origin (DCO).

Reviewers will merge this pull-request only if

alxbilger commented 2 months ago

[ci-build][with-all-tests]