Multifrontal TODOs

[dellaert]

Context:

We created a new class MultiFrontalSolver designed to

• solve the same system multiple times - as is common in a nonlinear optimization loop. Other than the legacy GaussianFactorGraph pipeline, this allocates all the memory in advance and is optimized for cache performance and avoiding mallocs.
• deal with changing damping parameter lambda without as little overhead as possible
• when TBB is not installed, it uses a newly created TaskScheduler which provides parallel processing for the multifrontal elimination (bottom-up) and solve (top-down).

Dirty secret: Frank pinned the number of threads to be 0.75 * nr cores, for both TBB and Mixin. This is super-important for the TaskScheduler, as I think because Eigen also tries threads and get starved. This might make TBB look worse (as it might do that again).

Goal:

• Mixin (name for using TaskScheduler/ForestTraversal) beats TBB every time. Then we can eradicate TBB. This though means that the legacy GTSAM also has to use ForestTraversal. That would be awesome!

What's left:

• Have a proper SymbolicAnalysis class that bundles the merging code, use payload in SymbolicFactor
• If MULTIFRONTAL_SOLVER is selected, throw if conditions not met - don't fail silently.
• merged leaves should be parallel in the eliminate step
• problemSize tuning and max (branch by Frank)
• pinning of threads
• in MFC, line 381, just add to the queue in the TaskScheduler - will also share the threadpool if multiple parallel updates are happening
• threads = cores - 1 ?
• add datasets in-between BAL and chain: SLAm, sparser SFM
• Profile @tzvist approach to parallelizing parent updates rather than per-thread storage
• See whether we can do same linear graph with different lambda, even after eliminate. Probably not.

[ProfFan]

Also #2275

[tzvist]

Context:

We created a new class MultiFrontalSolver designed to solve the same system multiple times - as is common in a nonlinear optimization loop. Other than the legacy GaussianFactorGraph pipeline, this allocates all the memory in advance and is optimized for cache performance and avoiding mallocs. In addition, when TBB is not installed, it uses a newly created TaskScheduler which provides parallel processing for the multifrontal elimination (bottom-up) and solve (top-down).

Dirty secret: Frank pinned the number of threads to be 0.75 * nr cores, for both TBB and Mixin. This is super-important for the TaskScheduler, as I think because Eigen also tries threads and get starved. This might make TBB look worse (as it might do that again).

Goal:

• Mixin (name for using TaskScheduler/ForestTraversal) beats TBB every time. Then we can eradicate TBB. This though means that the legacy GTSAM also has to use ForestTraversal. That would be awesome!

What's left:

• merged leaves should be parallel in the eliminate step[ ] problemSize tuning and max (branch by Frank)[ ] pinning of threads[ ] in MFC, line 381, just add to the queue in the TaskScheduler - will also share the threadpool if multiple parallel updates are happening[ ] threads = cores - 1 ?[ ] add datasets in-between BAL and chain: SLAm, sparser SFM[ ] Profile @tzvist approach to parallelizing parent updates rather than per-thread storage

A) I did not benchmark enough but from what i saw cores - 1 worked the best, what I saw Tbb seems to keep its threads still spinning with some kind of busy wait and that causes Eigen to work slower, this also makes the timing profiler not accurate when looking at CPU because it show the busy wait as work.

B) I did not manage to get any performance improvements when trying to get Eigen to be Multi-thread to use MKL or OMP.

C) I don't know if this is the general use case, but for our use case memory usage is critical, currently when using TBB tree-traverse it jumps (in my test case from ~4GB to ~12 GB).

[dellaert]

Yeah, so the PR I just pushed can be parallel without TBB - And should in theory create much less memory over here. Do you want to try and see whether memory usage is still crazy when using the new solver? In that branch it's enabled by default (MULTIFRONTAL_SOLVER), although it could be silently flipping back to the old one if there are null noise models - or even segfault :-) (because it asks dim() from a nullptr). It would also be nice to see how much faster it is on your problem - if it is faster.

[dellaert]

@tzvist I merged the nonlinear optimizer. I'd be interested in hearing whether you can use it without any problems, and what the memory and runtime performance is for your use case. Note if you use HessianFactors and/or general constraints, the optimizer will throw a helpful exception, telling you to switch back to the legacy solver :-).

[ProfFan]

Also note that modern allocators usually prefer to over allocate and only release memory when absolutely needed, for performance. It would be great to know what's your exact configuration before we come to any conclusion :)

[ProfFan]

On the dim part @dellaert , I'll continue working on #2275 which should allow getting the dim of non-dynamic-shaped factors without the noise model, which should save some memory and improve speed a bit

[tzvist]

@tzvist I merged the nonlinear optimizer. I'd be interested in hearing whether you can use it without any problems, and what the memory and runtime performance is for your use case. Note if you use HessianFactors and/or general constraints, the optimizer will throw a helpful exception, telling you to switch back to the legacy solver :-).

@shteren1 created a use case representing our data https://github.com/tzvist/gtsam/tree/tzvist/benchmark
(see commit message explaining how to run it)
On this test case MULTIFRONTAL_SOLVER yields a ~3× slowdown vs MULTIFRONTAL_CHOLESKY (342 s vs 109 s).:

MULTIFRONTAL_SOLVER

./build_RelWithDebInfo/simple_gtsam_deserialize
simple_gtsam_deserialize2.cpp
Reading values file took 0.0158 seconds
Reading graph file took 0.2655 seconds
   6     80079.51         1.85       0.00      1      18.97
Processing factor lines took 3.0308 seconds
Processing values lines took 0.1080 seconds
Setting up optimizer took 8.9294 seconds
   7     80078.27         1.25       0.00      1      18.44
Initial error: 83467.7055, values: 65796
   8     80077.21         1.05       0.00      1      18.75
iter      cost      cost_change    lambda  success iter_time
   0   80521.8653      2945.84       0.00      1      19.40
   9     80076.12         1.10       0.00      1      19.12
   1     80158.71       363.15       0.00      1      18.87
  10     80075.23         0.88       0.00      1      18.76
   2     80240.30       -81.59       0.00      1      18.83
  11     80073.29         1.94       0.00      1      18.53
   2     80109.06        49.65       0.00      1      19.31
  12     80071.41         1.88       0.00      1      19.11
   3     80091.18        17.89       0.00      1      19.07
  13     80070.16         1.26       0.00      1      18.34
   4     80084.62         6.55       0.00      1      18.34
  14     80069.22         0.93       0.00      1      19.05
   5     80081.36         3.26       0.00      1      18.84
  15     80068.53         0.69       0.00      1      19.11
Running gtsam optimizer took 351.2945 seconds
   6     80079.51         1.85       0.00      1      18.41
   7     80078.27         1.25       0.00      1      20.55
   8     80077.21         1.05       0.00      1      18.54
   9     80076.12         1.10       0.00      1      18.51
  10     80075.23         0.88       0.00      1      18.25
  11     80073.29         1.94       0.00      1      18.96
  12     80071.41         1.88       0.00      1      18.18
  13     80070.16         1.26       0.00      1      18.54
  14     80069.22         0.93       0.00      1      18.48
  15     80068.53         0.69       0.00      1      18.47
Running gtsam optimizer took 342.3837 seconds 

MULTIFRONTAL_CHOLESKY

/homes/tzvichaims/work/ba/gtsam9/build_RelWithDebInfo/simple_gtsam_deserialize
simple_gtsam_deserialize2.cpp
Reading values file took 0.0154 seconds
Reading graph file took 0.1866 seconds
Processing factor lines took 2.8288 seconds
Processing values lines took 0.1021 seconds
Setting up optimizer took 9.0484 seconds
Initial error: 83467.7055, values: 65796
iter      cost      cost_change    lambda  success iter_time
   0          inf         0.00       0.00      0       1.54
iter      cost      cost_change    lambda  success iter_time
   0     80421.88      3045.82       0.00      1       7.38
   1          inf         0.00       0.00      0       0.91
   1     80163.07       258.81       0.00      1       4.78
   2          inf         0.00       0.00      0       0.96
   2     80113.89        49.18       0.00      1       4.90
   3          inf         0.00       0.00      0       0.93
   3     80096.39        17.50       0.00      1       4.97
   4          inf         0.00       0.00      0       0.95
   4     80089.79         6.60       0.00      1       4.90
   5          inf         0.00       0.00      0       0.94
   5     80086.41         3.38       0.00      1       5.01
   6          inf         0.00       0.00      0       0.93
   6     80084.44         1.98       0.00      1       4.81
   7          inf         0.00       0.00      0       0.89
   7     80083.05         1.39       0.00      1       4.96
   8          inf         0.00       0.00      0       0.91
   8     80081.84         1.21       0.00      1       4.95
   9          inf         0.00       0.00      0       0.94
   9     80080.52         1.32       0.00      1       4.90
  10          inf         0.00       0.00      0       0.95
  10     80078.92         1.60       0.00      1       4.73
  11          inf         0.00       0.00      0       0.92
  11     80076.99         1.93       0.00      1       4.86
  12          inf         0.00       0.00      0       0.98
  12     80074.94         2.05       0.00      1       4.97
  13          inf         0.00       0.00      0       1.00
  13     80073.22         1.72       0.00      1       4.90
  14          inf         0.00       0.00      0       0.96
  14     80071.87         1.34       0.00      1       4.80
  15          inf         0.00       0.00      0       0.94
  15     80071.04         0.83       0.00      1       4.82
  16          inf         0.00       0.00      0       1.00
  16     80070.76         0.28       0.00      1       5.60
Running gtsam optimizer took 109.2203 seconds

[dellaert]

Wow, yeah. That’s surprising. I won’t have time until the weekend to actually look at. But if you figure out what the big bottleneck is then maybe we can learn from that. note that the constructor of the solverr takes an output stream and will print out statistics on the graphs.

[dellaert]

BTW I am a bit puzzled about the lambda values and the iteration numbers that are printed out above. But that doesn’t undo the fact that the iteration time is so much larger for the new solver. Puzzling!

[tzvist]

BTW I am a bit puzzled about the lambda values and the iteration numbers that are printed out above. But that doesn’t undo the fact that the iteration time is so much larger for the new solver. Puzzling!

i added some precision to the printing of lambda

added statistics and made more permissions for lambda:

 ./build_RelWithDebInfo/simple_gtsam_deserialize
simple_gtsam_deserialize2.cpp
Reading values file took 0.0153 seconds
Reading graph file took 0.2010 seconds
Processing factor lines took 2.8240 seconds
Processing values lines took 0.1065 seconds
Setting up optimizer took 8.9750 seconds
Symbolic cluster structure
  cliques:    65316
  frontals:   max=924 avg=3.0475
  separators: max=1794 avg=102.6310
  total dim:  max=1824 avg=105.6785
  children:   max=14580 avg=1.0000
Clique structure after leaf merge
  cliques:    40964
  frontals:   max=924 avg=4.8592
  separators: max=1794 avg=135.8419
  total dim:  max=1824 avg=140.7011
  children:   max=10526 avg=1.0000
Clique structure after merge
  cliques:    40964
  frontals:   max=924 avg=4.8592
  separators: max=1794 avg=135.8419
  total dim:  max=1824 avg=140.7011
  children:   max=10526 avg=1.0000
Initial error: 83467.7055, values: 65796
iter      cost      cost_change    lambda  success iter_time
   0   80521.8653      2945.84   0.000010      1      18.66
   1     80158.71       363.15   0.000001      1      19.01
   2     80240.30       -81.59   0.000000      1      18.15
   2     80109.06        49.65   0.000001      1      17.95
   3     80091.18        17.89   0.000000      1      18.58
   4     80084.62         6.55   0.000000      1      18.50
   5     80081.36         3.26   0.000000      1      18.48
   6     80079.51         1.85   0.000000      1      17.84

[dellaert]

I just merged #2365 to switch back default until we get to the bottom of this.