Check which OpenMP for-loops could benefit from dynamic schedule

[mvieth]

          I guess other OMP implementations could use this setting as well, since most of those also require some search for neighbors, which can vary a lot and hence vary the computation between each iteration?

Originally posted by @larshg in #5775 (comment)

Candidates are for-loops where the loop iterations do not take the same time, e.g. when a neighbourhood search is done for each point in a cloud (especially radius search).
Files that contain parallelized for-loops and should be checked:

apps/3d_rec_framework/include/pcl/apps/3d_rec_framework/pipeline/impl/global_nn_recognizer_crh.hpp
apps/3d_rec_framework/include/pcl/apps/3d_rec_framework/pipeline/impl/local_recognizer.hpp
apps/3d_rec_framework/include/pcl/apps/3d_rec_framework/pipeline/impl/global_nn_recognizer_cvfh.hpp
common/src/range_image.cpp
common/src/fft/kiss_fft.c
features/include/pcl/features/impl/fpfh_omp.hpp
features/include/pcl/features/impl/shot_omp.hpp
features/include/pcl/features/impl/normal_3d_omp.hpp
features/include/pcl/features/impl/intensity_gradient.hpp
features/include/pcl/features/impl/shot_lrf_omp.hpp
features/src/range_image_border_extractor.cpp
features/src/narf.cpp
filters/include/pcl/filters/impl/convolution_3d.hpp
filters/include/pcl/filters/impl/convolution.hpp
filters/include/pcl/filters/impl/pyramid.hpp
filters/include/pcl/filters/impl/fast_bilateral_omp.hpp
filters/src/pyramid.cpp
io/include/pcl/io/impl/lzf_image_io.hpp
io/src/real_sense_2_grabber.cpp
keypoints/include/pcl/keypoints/impl/harris_6d.hpp
keypoints/include/pcl/keypoints/impl/trajkovic_3d.hpp
keypoints/include/pcl/keypoints/impl/iss_3d.hpp
keypoints/include/pcl/keypoints/impl/harris_3d.hpp
keypoints/include/pcl/keypoints/impl/harris_2d.hpp
keypoints/include/pcl/keypoints/impl/trajkovic_2d.hpp
keypoints/src/narf_keypoint.cpp
recognition/include/pcl/recognition/impl/hv/hv_go.hpp
registration/include/pcl/registration/impl/ia_fpcs.hpp
segmentation/include/pcl/segmentation/impl/approximate_progressive_morphological_filter.hpp
surface/include/pcl/surface/impl/mls.hpp
tools/fast_bilateral_filter.cpp
tools/normal_estimation.cpp
tracking/include/pcl/tracking/impl/pyramidal_klt.hpp
tracking/include/pcl/tracking/impl/kld_adaptive_particle_filter_omp.hpp
tracking/include/pcl/tracking/impl/particle_filter_omp.hpp

[NemB0t]

Hello @mvieth, I would like to work on this issue. Since this is my first contribution I would like some helpful pointers.

[mvieth]

Hello @mvieth, I would like to work on this issue. Since this is my first contribution I would like some helpful pointers.

@NemB0t Great! Please take a look at #5775 if you haven't already. As a start, please look through the files mentioned above and search for all parallel for loops (pragma omp for). The goal is to categorize them: One category would be "iterates over all input points/input indices and does a neighbourhood search for each one (neighbours within a radius or k-nearest)". The normal estimation from the linked pull request would fall in this category. There are probably more categories which I can't foresee right now.
Based on these, we can then check where the for-loop iterations are unbalanced, that is, the iterations do not all take (roughly) the same time. For these, we would consider switching to a dynamic OpenMP schedule, like we did for the normal estimation, and then we should probably also do one or two benchmarks to verify that the dynamic schedule indeed made the algorithms faster. But we can discuss this part in detail later.
I hope that helps.

[NemB0t]

@mvieth , I went through all the mentioned files and have classified the way parallel loops are used based on my understanding. Could you please check a few of them from each categories and let me know if corrections are needed.

Iterates over a set of indexes or group of points:

apps/3d_rec_framework/include/pcl/apps/3d_rec_framework/pipeline/impl/global_nn_recognizer_crh.hpp
apps/3d_rec_framework/include/pcl/apps/3d_rec_framework/pipeline/impl/local_recognizer.hpp
apps/3d_rec_framework/include/pcl/apps/3d_rec_framework/pipeline/impl/global_nn_recognizer_cvfh.hpp
features/include/pcl/features/impl/fpfh_omp.hpp
features/include/pcl/features/impl/shot_omp.hpp
features/include/pcl/features/impl/normal_3d_omp.hpp
features/include/pcl/features/impl/intensity_gradient.hpp
features/include/pcl/features/impl/shot_lrf_omp.hpp
features/src/narf.cpp
filters/include/pcl/filters/impl/convolution_3d.hpp
filters/include/pcl/filters/impl/fast_bilateral_omp.hpp
io/include/pcl/io/impl/lzf_image_io.hpp
io/src/real_sense_2_grabber.cpp
keypoints/include/pcl/keypoints/impl/harris_6d.hpp
keypoints/include/pcl/keypoints/impl/trajkovic_3d.hpp
keypoints/include/pcl/keypoints/impl/iss_3d.hpp
keypoints/include/pcl/keypoints/impl/harris_3d.hpp
keypoints/include/pcl/keypoints/impl/harris_2d.hpp
keypoints/include/pcl/keypoints/impl/trajkovic_2d.hpp
keypoints/src/narf_keypoint.cpp
segmentation/include/pcl/segmentation/impl/approximate_progressive_morphological_filter.hppsegmentation/include/pcl/segmentation/impl/approximate_progressive_morphological_filter.hpp
surface/include/pcl/surface/impl/mls.hpp
tools/fast_bilateral_filter.cpp
tools/normal_estimation.cpp
tracking/include/pcl/tracking/impl/kld_adaptive_particle_filter_omp.hpp
tracking/include/pcl/tracking/impl/particle_filter_omp.hpp

Iterates over the number of images dimentions:

common/src/range_image.cpp
features/src/range_image_border_extractor.cpp
filters/include/pcl/filters/impl/convolution.hpp
tracking/include/pcl/tracking/impl/pyramidal_klt.hpp

Iterates p number of times (p is the value received from function call):

common/src/fft/kiss_fft.c

Iterates over the number of images dimentions and the number of kernel dimentions:

filters/include/pcl/filters/impl/pyramid.hpp
filters/src/pyramid.cpp

Iterates over a fixed number of iterations:

registration/include/pcl/registration/impl/ia_fpcs.hpp

Could not find parallel for loops:

recognition/include/pcl/recognition/impl/hv/hv_go.hpp

If these are correct, could also provide some guidance on further steps?

[mvieth]

First of all, thank you for the list. In addition to checking what the loop iterates over, it is also imported to check what happens in each iteration. Remember, we want to find loops where the iterations do not take the same amount of time (unbalanced loops). This is for example the case when the computations in each iteration depend a lot on the data used in that iteration (e.g. on the point, when iterating over all points). I imagine that this may be difficult to judge if you don't know the classes so well. Since in the case of normal estimation we have found that the duration of a neighbourhood search can vary a lot from iteration to iteration, I would suggest to concentrate on those. This can be a search for neighbours within a radius (radiusSearch), for the k nearest neighbours (nearestKSearch), or either of these two based on settings made by the user (usually called searchForNeighbors but may have slightly different names). So it would be great if you could go through the loops in the category "Iterates over a set of indexes or group of points" again, and check whether they do a neighborhood search in each iteration, and if yes, with which method.

[russoanto]

Hi, do you still need help with this issue? I’d be glad to contribute.

[mvieth]

Hi, do you still need help with this issue? I’d be glad to contribute.

Hello, that's great! Basically, the task I described in my last comment (from exactly one year ago 😆 ) is still a to-do. You could start there, if you like. I hope the description is clear, otherwise feel free to ask.

[kai-waang]

I was trying to add a dynamic schedule for SHOT estimation, however, benchmark results indicate that this change does not yield a significant performance gain. Given these findings, I’m uncertain whether this worth a PR. What do you think? @mvieth

My code is something like this:

#pragma omp parallel for \
  default(none) \
  shared(output) \
  num_threads(threads_) \
  schedule(dynamic, chunk_size_)
  for (std::ptrdiff_t idx = 0; idx < static_cast<std::ptrdiff_t> (indices_->size ()); ++idx)
  {
    ...
  }

PCL is built in Release mode, all benchmarks are run on my macbook air m4.

Run on (10 X 24 MHz CPU s)
CPU Caches:
  L1 Data 64 KiB
  L1 Instruction 128 KiB
  L2 Unified 4096 KiB (x10)
Load Average: 4.06, 4.45, 4.26

on bun0.pcd

build type: Release, 4 threads

static schedule (original)

------------------------------------------------------------------------
Benchmark                              Time             CPU   Iterations
------------------------------------------------------------------------
BM_SHOT352/iterations:10            2.61 ms         2.40 ms           10
BM_SHOT352_OMP/iterations:10       0.846 ms        0.553 ms           10
BM_SHOT1344/iterations:10           2.97 ms         2.94 ms           10
BM_SHOT1344_OMP/iterations:10      0.854 ms        0.574 ms           10

dynamic schedule

-----------------------------------------------------------------------------
Benchmark                                   Time             CPU   Iterations
-----------------------------------------------------------------------------
BM_SHOT352/iterations:100                2.39 ms         2.37 ms          100
BM_SHOT352_OMP/8/iterations:100         0.741 ms        0.705 ms          100
BM_SHOT352_OMP/16/iterations:100        0.732 ms        0.682 ms          100
BM_SHOT352_OMP/32/iterations:100        0.777 ms        0.711 ms          100
BM_SHOT352_OMP/64/iterations:100        0.822 ms        0.735 ms          100
BM_SHOT352_OMP/128/iterations:100       0.859 ms        0.802 ms          100
BM_SHOT1344/iterations:100               3.13 ms         3.12 ms          100
BM_SHOT1344_OMP/8/iterations:100         1.51 ms         1.18 ms          100
BM_SHOT1344_OMP/16/iterations:100       0.924 ms        0.874 ms          100
BM_SHOT1344_OMP/32/iterations:100       0.932 ms        0.849 ms          100
BM_SHOT1344_OMP/64/iterations:100        1.03 ms        0.835 ms          100
BM_SHOT1344_OMP/128/iterations:100       1.11 ms         1.05 ms          100

on cturtle.pcd

static (original):

------------------------------------------------------------------------
Benchmark                              Time             CPU   Iterations
------------------------------------------------------------------------
BM_SHOT352/iterations:10            2277 ms         2274 ms           10
BM_SHOT352_OMP/iterations:10         434 ms          396 ms           10
BM_SHOT1344/iterations:10           2891 ms         2842 ms           10
BM_SHOT1344_OMP/iterations:10        527 ms          482 ms           10

dynamic:

----------------------------------------------------------------------------
Benchmark                                  Time             CPU   Iterations
----------------------------------------------------------------------------
BM_SHOT352/iterations:10                2348 ms         2323 ms           10
BM_SHOT352_OMP/8/iterations:10           432 ms          418 ms           10
BM_SHOT352_OMP/16/iterations:10          432 ms          429 ms           10
BM_SHOT352_OMP/32/iterations:10          466 ms          442 ms           10
BM_SHOT352_OMP/64/iterations:10          457 ms          441 ms           10
BM_SHOT352_OMP/128/iterations:10         452 ms          446 ms           10
BM_SHOT1344/iterations:10               2990 ms         2924 ms           10
BM_SHOT1344_OMP/8/iterations:10          535 ms          528 ms           10
BM_SHOT1344_OMP/16/iterations:10         560 ms          549 ms           10
BM_SHOT1344_OMP/32/iterations:10         564 ms          553 ms           10
BM_SHOT1344_OMP/64/iterations:10         563 ms          558 ms           10
BM_SHOT1344_OMP/128/iterations:10        565 ms          559 ms           10

[mvieth]

@kai-waang I am not sure how well bun0.pcd and cturtle.pcd work for SHOT estimation benchmarks: bun0.pcd has only very few points which makes time measurements rather noisy, and cturtle.pcd looks artificially generated, basically a part of a sphere with very uniform point densities. In this tutorial, SHOT estimation is also applied, perhaps you could try with the point clouds used there.

[kai-waang]

@mvieth I tried the milk.pcd, and dynamic schdule does help .

Benchmark	Chunk Size	Static Time	Dynamic Time	Speedup (vs Static)	Improvement (%)
BM_SHOT352	64	168 ms	160 ms	1.05x	+4.76%
BM_SHOT1344	64	195 ms	180 ms	1.08x	+7.69%

---

dynamic:

Run on (28 X 3417.6 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB (x14)
  L1 Instruction 32 KiB (x14)
  L2 Unified 2048 KiB (x14)
  L3 Unified 33792 KiB (x1)
Load Average: 2.78, 2.41, 1.09
***WARNING*** Library was built as DEBUG. Timings may be affected.
----------------------------------------------------------------------------
Benchmark                                  Time             CPU   Iterations
----------------------------------------------------------------------------
BM_SHOT352_OMP/64/iterations:100         160 ms          141 ms          100
BM_SHOT1344_OMP/64/iterations:100        180 ms          163 ms          100

static:

Run on (28 X 3417.6 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB (x14)
  L1 Instruction 32 KiB (x14)
  L2 Unified 2048 KiB (x14)
  L3 Unified 33792 KiB (x1)
Load Average: 2.78, 2.41, 1.09
***WARNING*** Library was built as DEBUG. Timings may be affected.
----------------------------------------------------------------------------
Benchmark                                  Time             CPU   Iterations
----------------------------------------------------------------------------
BM_SHOT352_OMP/64/iterations:100         168 ms          112 ms          100
BM_SHOT1344_OMP/64/iterations:100        195 ms          121 ms          100

[larshg]

Looks nice - we have somewhat defaulted to a chunk size of 256 - how does that look?

[kai-waang]

@larshg, we can alse see a improvement. I think it's ok to add dynamic schedule for shot_omp.hpp

Benchmark	Chunk Size	Static Time	Dynamic Time	Speedup
BM_SHOT352	64	155 ms	147 ms	1.05x
	128	154 ms	146 ms	1.05x
	256	157 ms	146 ms	1.08x
BM_SHOT1344	64	187 ms	167 ms	1.12x
	128	181 ms	170 ms	1.06x
	256	180 ms	173 ms	1.04x

---

static:

-----------------------------------------------------------------------------
Benchmark                                   Time             CPU   Iterations
-----------------------------------------------------------------------------
BM_SHOT352_OMP/64/iterations:100          155 ms          111 ms          100
BM_SHOT352_OMP/128/iterations:100         154 ms          111 ms          100
BM_SHOT352_OMP/256/iterations:100         157 ms          112 ms          100
BM_SHOT1344_OMP/64/iterations:100         187 ms          126 ms          100
BM_SHOT1344_OMP/128/iterations:100        181 ms          123 ms          100
BM_SHOT1344_OMP/256/iterations:100        180 ms          123 ms          100

dynamic:

-----------------------------------------------------------------------------
Benchmark                                   Time             CPU   Iterations
-----------------------------------------------------------------------------
BM_SHOT352_OMP/64/iterations:100          147 ms          146 ms          100
BM_SHOT352_OMP/128/iterations:100         146 ms          145 ms          100
BM_SHOT352_OMP/256/iterations:100         146 ms          141 ms          100
BM_SHOT1344_OMP/64/iterations:100         167 ms          164 ms          100
BM_SHOT1344_OMP/128/iterations:100        170 ms          168 ms          100
BM_SHOT1344_OMP/256/iterations:100        173 ms          167 ms          100

[mvieth]

To me it seems like a good idea to change the SHOT estimation to a dynamic schedule. Feel free to open a pull request if you like.