View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0026292Open CASCADEOCCT:Visualizationpublic2015-05-28 18:592016-04-20 15:49
ReporterdbpAssigned Tobugmaster  
PrioritynormalSeverityfeature 
Status closedResolutionfixed 
Target Version7.0.0Fixed in Version7.0.0 
Summary0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
DescriptionBinned 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 ReproduceN/A
Additional information
and documentation updates		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%.
TagsNo tags attached.
Test case numberNot needed

Attached Files

  • BVH_Perf.png (121,960 bytes)

Relationships

has duplicate 0025274 closedbugmaster Visualization - Parallelizing BVH binned builder 
related to 0026364 closedbugmaster Foundation Classes, TKMath - Optimize BVH binned algorithm 

Activities

git

2015-05-28 19:00

administrator   ~0041690

Branch CR26292 has been created by dbp.

SHA-1: 0d9cbd54cabe50c0448dab572291c073a566f43b


Detailed log of new commits:

Author: dbp
Date: Thu May 28 19:00:24 2015 +0300

    Initial version.

git

2015-05-29 11:46

administrator   ~0041710

Branch CR26292 has been updated by dbp.

SHA-1: a0edf9d595cddc10fa0263467edeb93a25cf900d


Detailed log of new commits:

Author: dbp
Date: Fri May 29 11:45:20 2015 +0300

    Update.

git

2015-06-19 16:00

administrator   ~0042275

Branch CR26292 has been updated forcibly by dbp.

SHA-1: 0e6b96e27bc5394258e7bfdec4c3209d2a087f3e

dbp

2015-06-19 16:02

developer   ~0042277

Dear kgv,

please review the patch in branch CR26292.

kgv

2015-06-22 16:23

developer   ~0042318 

+  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..

msv

2015-06-23 09:54

developer   ~0042325

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.

git

2015-06-23 12:17

administrator   ~0042340

Branch CR26292_1 has been created by dbp.

SHA-1: d925ad73b6bc3f83e9c080d64d1bbcaf64578cd0


Detailed log of new commits:

Author: dbp
Date: Fri Jun 19 10:24:04 2015 +0300

    0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)

dbp

2015-06-23 12:17

developer   ~0042342

Last edited: 2015-06-23 16:26

 Dear kgv,

please review updated patch in branch CR26292_2.

dbp

2015-06-23 13:19

developer  

BVH_Perf.png (121,960 bytes)

git

2015-06-23 16:25

administrator   ~0042372

Branch CR26292_2 has been created by dbp.

SHA-1: f8264deb9c9d6004a39d53f5055c7f993f4f9e54


Detailed log of new commits:

Author: dbp
Date: Fri Jun 19 10:24:04 2015 +0300

    0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)

git

2015-06-23 16:43

administrator   ~0042373

Branch CR26292_2 has been updated forcibly by dbp.

SHA-1: 6a78b76c31ec206891d36e6107c21173bc758752

git

2015-06-23 17:04

administrator   ~0042375

Branch CR26292_2 has been updated forcibly by dbp.

SHA-1: f6aa7ab67d31edbdf84c5cab1d6106d6ee123043

kgv

2015-06-23 18:27

developer   ~0042385

Please test the patch.

git

2015-06-23 18:54

administrator   ~0042389

Branch CR26292_2 has been updated forcibly by mkv.

SHA-1: 977c1756043c0bd870bbb6d61dc68b770685d996

mkv

2015-06-24 14:46

tester   ~0042412

Dear BugMaster,
Branch CR26292_2 was rebased on current master of occt git-repository.
SHA-1: 977c1756043c0bd870bbb6d61dc68b770685d996

mkv

2015-06-24 14:46

tester   ~0042413

Dear BugMaster,
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.
SHA-1: 977c1756043c0bd870bbb6d61dc68b770685d996

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 /Users/mnt/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_BinnedBuilder.hxx:79:
/Users/mnt/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 /Users/mnt/tools/WOK680/wok_entities/LOC/dev/CR26292-2-master-occt/inc/BVH_SweepPlaneBuilder.hxx:44:
/Users/mnt/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)

git

2015-06-26 18:34

administrator   ~0042510

Branch CR26292_2 has been updated by dbp.

SHA-1: 247cb5aafe79e3c4fe0f98e0329396d07bde6add


Detailed log of new commits:

Author: dbp
Date: Fri Jun 26 18:33:45 2015 +0300

    Fixes for GCC compiler.

dbp

2015-06-26 18:34

developer   ~0042511

Dear bugmaster,

please re-test patch in branch CR26292_2.

git

2015-06-26 18:46

administrator   ~0042512

Branch CR26292_2 has been updated forcibly by mkv.

SHA-1: 3245a3a72e3c1e3fac778831f8800e4cdc32d9d0

mkv

2015-06-29 11:09

tester   ~0042523

Dear BugMaster,
Branch CR26292_2 was rebased on current master of occt git-repository.
SHA-1: 3245a3a72e3c1e3fac778831f8800e4cdc32d9d0

mkv

2015-06-29 11:10

tester   ~0042524

Dear BugMaster,
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.
SHA-1: 3245a3a72e3c1e3fac778831f8800e4cdc32d9d0

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 /Users/mnt/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)

git

2015-07-10 13:58

administrator   ~0042905

Branch CR26292_3 has been created by dbp.

SHA-1: 0546f30ebe877e5eaef6cd9241ede345413e2fad


Detailed log of new commits:

Author: dbp
Date: Fri Jul 10 13:57:55 2015 +0300

    0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)

dbp

2015-07-10 13:58

developer   ~0042906

Dear bugmaster,

please re-test the patch in branch CR26292_3.

apv

2015-07-13 15:34

tester   ~0042969

Dear BugMaster,

Branch CR26292_3 from occt git-repository (and master from products git-repository) was compiled on Linux and Windows platforms and tested.
SHA-1: 0546f30ebe877e5eaef6cd9241ede345413e2fad

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%]

git

2015-07-17 14:45

administrator   ~0043158

Branch CR26292_4 has been created by kgv.

SHA-1: 9936af603980577421b728507a47c26ab3af4cdd


Detailed log of new commits:

Author: dbp
Date: Fri Jul 17 14:29:50 2015 +0300

    0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)

kgv

2015-07-17 14:46

developer   ~0043159

Patch in branch CR26292_4 has been rebased onto current master.

git

2015-07-27 13:39

administrator   ~0043518

Branch CR26292 has been deleted by kgv.

SHA-1: 0e6b96e27bc5394258e7bfdec4c3209d2a087f3e

git

2015-07-27 13:39

administrator   ~0043519

Branch CR26292_1 has been deleted by kgv.

SHA-1: d925ad73b6bc3f83e9c080d64d1bbcaf64578cd0

git

2015-07-27 13:39

administrator   ~0043520

Branch CR26292_2 has been deleted by kgv.

SHA-1: 3245a3a72e3c1e3fac778831f8800e4cdc32d9d0

git

2015-07-27 13:39

administrator   ~0043521

Branch CR26292_3 has been deleted by kgv.

SHA-1: 0546f30ebe877e5eaef6cd9241ede345413e2fad

git

2015-07-27 13:39

administrator   ~0043522

Branch CR26292_4 has been deleted by kgv.

SHA-1: 9936af603980577421b728507a47c26ab3af4cdd

Related Changesets

occt: master 65578e1c

2015-07-17 11:29:50

dbp


Committer: bugmaster Details Diff		 0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder) Affected Issues
0026292
mod - src/BVH/BVH_BinnedBuilder.hxx Diff File
mod - src/BVH/BVH_BinnedBuilder.lxx Diff File
add - src/BVH/BVH_BuildQueue.cxx Diff File
add - src/BVH/BVH_BuildQueue.hxx Diff File
add - src/BVH/BVH_BuildThread.cxx Diff File
add - src/BVH/BVH_BuildThread.hxx Diff File
mod - src/BVH/BVH_DistanceField.lxx Diff File
mod - src/BVH/BVH_QueueBuilder.hxx Diff File
mod - src/BVH/BVH_QueueBuilder.lxx Diff File
mod - src/BVH/BVH_SweepPlaneBuilder.hxx Diff File
mod - src/BVH/BVH_SweepPlaneBuilder.lxx Diff File
mod - src/BVH/BVH_Tree.hxx Diff File
mod - src/BVH/BVH_Tree.lxx Diff File
mod - src/BVH/BVH_Types.hxx Diff File
mod - src/BVH/FILES Diff File
mod - src/OpenGl/OpenGl_SceneGeometry.cxx Diff File
mod - src/OpenGl/OpenGl_SceneGeometry.hxx Diff File

Issue History

Date Modified Username Field Change
2015-05-28 18:59 dbp New Issue
2015-05-28 18:59 dbp Assigned To => dbp
2015-05-28 19:00 git Note Added: 0041690
2015-05-29 09:58 dbp Relationship added has duplicate 0025274
2015-05-29 11:46 git Note Added: 0041710
2015-06-02 16:32 kgv Summary Visualization - Parallelize queue-based BVH bilders (subclasses of BVH_QueueBuilder) => Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
2015-06-19 16:00 git Note Added: 0042275
2015-06-19 16:02 dbp Note Added: 0042277
2015-06-19 16:02 dbp Assigned To dbp => kgv
2015-06-19 16:02 dbp Status new => resolved
2015-06-19 16:02 dbp Steps to Reproduce Updated
2015-06-22 16:23 kgv Note Added: 0042318
2015-06-22 16:23 kgv Assigned To kgv => msv
2015-06-23 09:54 msv Note Added: 0042325
2015-06-23 09:54 msv Assigned To msv => dbp
2015-06-23 09:54 msv Status resolved => assigned
2015-06-23 12:17 git Note Added: 0042340
2015-06-23 12:17 dbp Note Added: 0042342
2015-06-23 12:17 dbp Assigned To dbp => kgv
2015-06-23 12:17 dbp Status assigned => resolved
2015-06-23 12:24 dbp Relationship added related to 0026364
2015-06-23 13:19 dbp File Added: BVH_Perf.png
2015-06-23 16:25 git Note Added: 0042372
2015-06-23 16:26 dbp Note Edited: 0042342
2015-06-23 16:43 git Note Added: 0042373
2015-06-23 17:04 git Note Added: 0042375
2015-06-23 18:27 kgv Note Added: 0042385
2015-06-23 18:27 kgv Assigned To kgv => bugmaster
2015-06-23 18:27 kgv Severity minor => feature
2015-06-23 18:27 kgv Status resolved => reviewed
2015-06-23 18:38 mkv Assigned To bugmaster => mkv
2015-06-23 18:54 git Note Added: 0042389
2015-06-24 14:46 mkv Note Added: 0042412
2015-06-24 14:46 mkv Note Added: 0042413
2015-06-24 14:46 mkv Assigned To mkv => dbp
2015-06-24 14:46 mkv Status reviewed => assigned
2015-06-24 14:47 mkv Test case number => Not needed
2015-06-26 18:34 git Note Added: 0042510
2015-06-26 18:34 dbp Status assigned => resolved
2015-06-26 18:34 dbp Note Added: 0042511
2015-06-26 18:34 dbp Assigned To dbp => bugmaster
2015-06-26 18:34 dbp Status resolved => reviewed
2015-06-26 18:46 git Note Added: 0042512
2015-06-26 18:51 mkv Assigned To bugmaster => mkv
2015-06-29 11:09 mkv Note Added: 0042523
2015-06-29 11:10 mkv Note Added: 0042524
2015-06-29 11:10 mkv Assigned To mkv => dbp
2015-06-29 11:10 mkv Status reviewed => assigned
2015-07-10 13:58 git Note Added: 0042905
2015-07-10 13:58 dbp Status assigned => resolved
2015-07-10 13:58 dbp Note Added: 0042906
2015-07-10 13:58 dbp Assigned To dbp => bugmaster
2015-07-10 13:58 dbp Status resolved => reviewed
2015-07-10 16:03 apv Assigned To bugmaster => apv
2015-07-13 15:34 apv Note Added: 0042969
2015-07-13 15:34 apv Assigned To apv => bugmaster
2015-07-13 15:34 apv Status reviewed => tested
2015-07-17 14:45 git Note Added: 0043158
2015-07-17 14:46 kgv Note Added: 0043159
2015-07-23 11:55 bugmaster Changeset attached => occt master 65578e1c
2015-07-23 11:55 bugmaster Status tested => verified
2015-07-23 11:55 bugmaster Resolution open => fixed
2015-07-27 13:39 git Note Added: 0043518
2015-07-27 13:39 git Note Added: 0043519
2015-07-27 13:39 git Note Added: 0043520
2015-07-27 13:39 git Note Added: 0043521
2015-07-27 13:39 git Note Added: 0043522
2015-12-24 10:55 dbp Additional Information Updated
2016-04-20 15:43 aiv Fixed in Version => 7.0.0
2016-04-20 15:49 aiv Status verified => closed