Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.
Announcements
Welcome to the Intel Community. If you get an answer you like, please mark it as an Accepted Solution to help others. Thank you!
2403 Discussions

Parallel implementation for tree traversal as the best practice

Nishikawa__Mitsuru
439 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
427 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

IntelSupport
Community Manager
416 Views

Hello. I have started an investigation.


IntelSupport
Community Manager
401 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.


IntelSupport
Community Manager
294 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


Reply