Archived issue #0026292
Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
Description
Binned BVH is used extensively in OCCT, and its performance has become critical. One of the major resources of increasing building performance is to parallelize all queue-based BVH builders.
Steps to reproduce
N/A
Additional information
In the frames of this patch the BVH queue-based builders (classes derived from BVH_QueueBuilder such as BVH_BinnedBuilder, BVH_SpatialMedianBuilder, and BVH_SweepPlaneBuilder) were parallelized. Note that parallelization is disabled by default (1 thread is used for building) and can be configured using last argument in BVH_QueueBuilder constructor:
//! Creates new BVH queue based builder.
BVH_QueueBuilder (const Standard_Integer theLeafNodeSize,
const Standard_Integer theMaxTreeDepth,
const Standard_Integer theNumOfThreads = 1);
In order to support parallel mode, a corresponding BVH primitive set should provide thread safe implementations of BVH_PrimitiveSet interface (such methods as Swap, Box, and Center). Otherwise, the results will be undefined (for that reason, parallelization is disabled by default). To the moment, parallel BVH construction is used in OCCT ray-tracing core. On quad-core CPU the speed-up is about 300%.
//! Creates new BVH queue based builder.
BVH_QueueBuilder (const Standard_Integer theLeafNodeSize,
const Standard_Integer theMaxTreeDepth,
const Standard_Integer theNumOfThreads = 1);
In order to support parallel mode, a corresponding BVH primitive set should provide thread safe implementations of BVH_PrimitiveSet interface (such methods as Swap, Box, and Center). Otherwise, the results will be undefined (for that reason, parallelization is disabled by default). To the moment, parallel BVH construction is used in OCCT ray-tracing core. On quad-core CPU the speed-up is about 300%.
Public activity
30 archived notes
Participants are labeled by their role within this record.
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu May 28 19:00:24 2015 +0300
Initial version.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu May 28 19:00:24 2015 +0300
Initial version.
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri May 29 11:45:20 2015 +0300
Update.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri May 29 11:45:20 2015 +0300
Update.
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Dear kgv,
please review the patch in branch CR26292.
please review the patch in branch CR26292.
+ Standard_Integer getNbOfCores()
+ {
+#ifdef WIN32
why there is code duplicating OSD_Parallel::NbLogicalProcessors()?
-// #define RAY_TRACE_PRINT_INFO +#define RAY_TRACE_PRINT_INFO
as usual..
Remarks.
It is needed to take into account HAVE_TBB macro. When it is defined then TBB threading mechanism should be used instead of OSD_Thread. Consider using tbb::parallel_invoke method (see http://scc.ustc.edu.cn/zlsc/sugon/intel/tbb/Design_Patterns.pdf, 7. Divide and Conquer).
Taking into account the bug "0024826: Wrapping of parallelisation algorithms", it would be worth to think about adding "divide and conquer" pattern in OSD_Parallel framework.
Use OSD_Parallel::NbLogicalProcessors() instead of adding new method getNbOfCores().
Disable debug macro RAY_TRACE_PRINT_INFO.
It is needed to take into account HAVE_TBB macro. When it is defined then TBB threading mechanism should be used instead of OSD_Thread. Consider using tbb::parallel_invoke method (see http://scc.ustc.edu.cn/zlsc/sugon/intel/tbb/Design_Patterns.pdf, 7. Divide and Conquer).
Taking into account the bug "0024826: Wrapping of parallelisation algorithms", it would be worth to think about adding "divide and conquer" pattern in OSD_Parallel framework.
Use OSD_Parallel::NbLogicalProcessors() instead of adding new method getNbOfCores().
Disable debug macro RAY_TRACE_PRINT_INFO.
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jun 19 10:24:04 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jun 19 10:24:04 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
Dear kgv,
please review updated patch in branch CR26292_2.
please review updated patch in branch CR26292_2.
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jun 19 10:24:04 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jun 19 10:24:04 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Please test the patch.
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Dear Commenter 1,
Branch CR26292_2 was rebased on current master of occt git-repository.
[revision removed]
Branch CR26292_2 was rebased on current master of occt git-repository.
[revision removed]
Dear Commenter 1,
Branch CR26292_2 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
[revision removed]
There are following compilation errors:
Linux:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_build_occt_linux/1/parsed_console/
../../../../inc/BVH_BinnedBuilder.lxx: In member function 'typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_BinnedBuilder<T, N, Bins>::BuildNode(BVH_Set<T, N>*, BVH_Tree<T, N>*, Standard_Integer)':
../../../../inc/BVH_BinnedBuilder.lxx:297:109: error: there are no arguments to 'BVH_PrimitiveRange' that depend on a template parameter, so a declaration of 'BVH_PrimitiveRange' must be available [-fpermissive]
...
MacOS:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_prepare_build_occt_MacOS/1/parsed_console/
...
In file included from [user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_BinnedBuilder.hxx:79:
[user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_BinnedBuilder.lxx:297:59: error: use of undeclared identifier 'BVH_PrimitiveRange'
BVH_PrimitiveRange (aNodeBegPrimitive, aMiddle - 1),
^
...
In file included from [user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_SweepPlaneBuilder.hxx:44:
[user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_SweepPlaneBuilder.lxx:151:59: error: use of undeclared identifier 'BVH_PrimitiveRange'
BVH_PrimitiveRange (aNodeBegPrimitive, aMiddle - 1),
^
2 errors generated.
....
Number of compiler warnings:
occt component :
Windows: 0 (0 on master)
products component :
Windows: 0 (0 on master)
Branch CR26292_2 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
[revision removed]
There are following compilation errors:
Linux:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_build_occt_linux/1/parsed_console/
../../../../inc/BVH_BinnedBuilder.lxx: In member function 'typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_BinnedBuilder<T, N, Bins>::BuildNode(BVH_Set<T, N>*, BVH_Tree<T, N>*, Standard_Integer)':
../../../../inc/BVH_BinnedBuilder.lxx:297:109: error: there are no arguments to 'BVH_PrimitiveRange' that depend on a template parameter, so a declaration of 'BVH_PrimitiveRange' must be available [-fpermissive]
...
MacOS:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_prepare_build_occt_MacOS/1/parsed_console/
...
In file included from [user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_BinnedBuilder.hxx:79:
[user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_BinnedBuilder.lxx:297:59: error: use of undeclared identifier 'BVH_PrimitiveRange'
BVH_PrimitiveRange (aNodeBegPrimitive, aMiddle - 1),
^
...
In file included from [user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_SweepPlaneBuilder.hxx:44:
[user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_SweepPlaneBuilder.lxx:151:59: error: use of undeclared identifier 'BVH_PrimitiveRange'
BVH_PrimitiveRange (aNodeBegPrimitive, aMiddle - 1),
^
2 errors generated.
....
Number of compiler warnings:
occt component :
Windows: 0 (0 on master)
products component :
Windows: 0 (0 on master)
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jun 26 18:33:45 2015 +0300
Fixes for GCC compiler.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jun 26 18:33:45 2015 +0300
Fixes for GCC compiler.
Dear Commenter 1,
please re-test patch in branch CR26292_2.
please re-test patch in branch CR26292_2.
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Dear Commenter 1,
Branch CR26292_2 was rebased on current master of occt git-repository.
[revision removed]
Branch CR26292_2 was rebased on current master of occt git-repository.
[revision removed]
Dear Commenter 1,
Branch CR26292_2 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
[revision removed]
There are following compilation errors:
Linux:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_build_occt_linux/1/parsed_console/
...
../../../../inc/BVH_Types.hxx:255:9: error: 'BVH::Array<double, 2>::BVH_ArrayNt' has no member named 'shrink_to_fit'
...
MacOS:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_prepare_build_occt_MacOS/1/parsed_console/
...
In file included from [user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_BuildQueue.hxx:19:
fatal error: 'features.h' file not found
#include <features.h>
^
....
Number of compiler warnings:
occt component :
Windows: 0 (0 on master)
products component :
Windows: 0 (0 on master)
Branch CR26292_2 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
[revision removed]
There are following compilation errors:
Linux:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_build_occt_linux/1/parsed_console/
...
../../../../inc/BVH_Types.hxx:255:9: error: 'BVH::Array<double, 2>::BVH_ArrayNt' has no member named 'shrink_to_fit'
...
MacOS:
http://jenkins-test-01.nnov.opencascade.com:8080/view/CR26292-2-master/job/CR26292-2-master_prepare_build_occt_MacOS/1/parsed_console/
...
In file included from [user path removed]/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_BuildQueue.hxx:19:
fatal error: 'features.h' file not found
#include <features.h>
^
....
Number of compiler warnings:
occt component :
Windows: 0 (0 on master)
products component :
Windows: 0 (0 on master)
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jul 10 13:57:55 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jul 10 13:57:55 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
Dear Commenter 1,
please re-test the patch in branch CR26292_3.
please re-test the patch in branch CR26292_3.
Dear Commenter 1,
Branch CR26292_3 from occt git-repository (and master from products git-repository) was compiled on Linux and Windows platforms and tested.
[revision removed]
Number of compiler warnings:
occt component:
Linux: 24 (24 on master)
Windows: 0 (0 on master)
products component:
Linux: 37 (37 on master)
Windows: 0 (0 on master)
Regressions/Differences:
Not detected
Testing cases:
Not needed
Testing on Linux:
Total MEMORY difference: 97239481 / 96647056 [+0.61%]
Total CPU difference: 17642.489999999914 / 17411.409999999752 [+1.33%]
Testing on Windows:
Total MEMORY difference: 57134686 / 56554589 [+1.03%]
Total CPU difference: 16380.214200698889 / 15993.00411859893 [+2.42%]
Branch CR26292_3 from occt git-repository (and master from products git-repository) was compiled on Linux and Windows platforms and tested.
[revision removed]
Number of compiler warnings:
occt component:
Linux: 24 (24 on master)
Windows: 0 (0 on master)
products component:
Linux: 37 (37 on master)
Windows: 0 (0 on master)
Regressions/Differences:
Not detected
Testing cases:
Not needed
Testing on Linux:
Total MEMORY difference: 97239481 / 96647056 [+0.61%]
Total CPU difference: 17642.489999999914 / 17411.409999999752 [+1.33%]
Testing on Windows:
Total MEMORY difference: 57134686 / 56554589 [+1.03%]
Total CPU difference: 16380.214200698889 / 15993.00411859893 [+2.42%]
Branch [archived branch] has been created by Commenter 3.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jul 17 14:29:50 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Jul 17 14:29:50 2015 +0300
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
Patch in Branch [archived branch] has been rebased onto current master.
Branch [archived branch] has been deleted by Commenter 3.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Commenter 3.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Commenter 3.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Commenter 3.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Commenter 3.
[revision removed]
[revision removed]
Related records