Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Parallelization of KDTree construction #92

Open
dokempf opened this issue Nov 30, 2021 · 1 comment
Open

Parallelization of KDTree construction #92

dokempf opened this issue Nov 30, 2021 · 1 comment
Labels
enhancement New feature or request performance Performance Optimization related improvement or experiment

Comments

@dokempf
Copy link
Collaborator

dokempf commented Nov 30, 2021

Performance benchmarking shows that as is, the KDTree construction is the bottleneck of the entire algorithm. A naive approach to parallelization could be to distribute the subtree construction to threads. The very coarse levels do not parallelize well in this algorithm, but a sufficiently deep tree mitigates this disadvantage.

Implementation includes two non-trivial aspects:

  • Review nanoflann's internal data structures w.r.t. thread safety as we are operating outside of nanoflann's communicated thread safetly guarantee. However, we are only using the static version of nanoflann (the dynamic would definitely not be thread-safe).
  • Add a task-based OpenMP parallelization to the recursive construction algorithm.
@dokempf dokempf added enhancement New feature or request performance Performance Optimization related improvement or experiment labels Nov 30, 2021
@dokempf
Copy link
Collaborator Author

dokempf commented Jun 22, 2023

Nanoflann v1.5.0 added parallel construction support: https://github.com/jlblancoc/nanoflann/releases/tag/v1.5.0

However, my initial testing was far off the advocated speedup of 3. I got around 20% for medium core counts and the code got slower for large core counts. I am currently hesitant to include that in the code base, at least not without a user interface to control.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request performance Performance Optimization related improvement or experiment
Projects
None yet
Development

No branches or pull requests

1 participant