Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.
2464 Discussions

Parallel implementation for tree traversal as the best practice

Nishikawa__Mitsuru
916 Views

I understand TBB is designed to be composable threading library, which enable parallelism in nested, or recursive, algorithms.

By taking advantage of it, I would like to make tree traversal algorithm parallel for ray tracing, or intersection tests. (needed to query many objects, so queries are made parallel)

As the best knowledge to me, the easiest way to realize it is to nest tbb::parallel_for. But, I am afraid that a lot of creation of tasks, which is produced in tbb::parallel_for in recursive call, degrade the performance.

 

I would appreciate it if you could tell me the best practices, or sample codes, for such a manner, without performance loss.

 

Kind regards

0 Kudos
4 Replies
Nishikawa__Mitsuru
904 Views

I noticed that cutoff, which is limitation number of task, is used to avoid overhead as written in an example of quick sort in "Pro TBB" Chapter 2 PP.41.

<https://link.springer.com/book/10.1007/978-1-4842-4398-5>

 

I also consider such a limit in my tree traversal algorithm.

 

Kind regards

0 Kudos
IntelSupport
Community Manager
893 Views

Hello. I have started an investigation.


0 Kudos
IntelSupport
Community Manager
878 Views

Hello. TBB is composable so it is going to be aware of how many threads it has created. So this should not degrade the performance.


0 Kudos
IntelSupport
Community Manager
771 Views

This issue has been resolved and support will no longer respond to this thread. If you require additional assistance from Intel, please start a new thread. Any further interaction in this thread will be considered community only


0 Kudos
Reply