MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0026292Open CASCADE[OCCT] OCCT:Visualizationpublic2015-05-28 18:592016-04-20 15:49
Reporterdbp 
Assigned Tobugmaster 
PrioritynormalSeverityfeature 
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version 
Target Version[OCCT] 7.0.0Fixed in Version[OCCT] 7.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 Filespng file icon BVH_Perf.png (121,960 bytes) 2015-06-23 13:19

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

-  Notes
(0041690)
git (administrator)
2015-05-28 19:00

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.
(0041710)
git (administrator)
2015-05-29 11:46

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.

(0042275)
git (administrator)
2015-06-19 16:00

Branch CR26292 has been updated forcibly by dbp.

SHA-1: 0e6b96e27bc5394258e7bfdec4c3209d2a087f3e
(0042277)
dbp (developer)
2015-06-19 16:02

Dear kgv,

please review the patch in branch CR26292.
(0042318)
kgv (developer)
2015-06-22 16:23

+  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..
(0042325)
msv (developer)
2015-06-23 09:54

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.
(0042340)
git (administrator)
2015-06-23 12:17

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)
(0042342)
dbp (developer)
2015-06-23 12:17
edited on: 2015-06-23 16:26

Dear kgv,

please review updated patch in branch CR26292_2.

(0042372)
git (administrator)
2015-06-23 16:25

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)
(0042373)
git (administrator)
2015-06-23 16:43

Branch CR26292_2 has been updated forcibly by dbp.

SHA-1: 6a78b76c31ec206891d36e6107c21173bc758752
(0042375)
git (administrator)
2015-06-23 17:04

Branch CR26292_2 has been updated forcibly by dbp.

SHA-1: f6aa7ab67d31edbdf84c5cab1d6106d6ee123043
(0042385)
kgv (developer)
2015-06-23 18:27

Please test the patch.
(0042389)
git (administrator)
2015-06-23 18:54

Branch CR26292_2 has been updated forcibly by mkv.

SHA-1: 977c1756043c0bd870bbb6d61dc68b770685d996
(0042412)
mkv (tester)
2015-06-24 14:46

Dear BugMaster,
Branch CR26292_2 was rebased on current master of occt git-repository.
SHA-1: 977c1756043c0bd870bbb6d61dc68b770685d996
(0042413)
mkv (tester)
2015-06-24 14:46

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)
(0042510)
git (administrator)
2015-06-26 18:34

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.

(0042511)
dbp (developer)
2015-06-26 18:34

Dear bugmaster,

please re-test patch in branch CR26292_2.
(0042512)
git (administrator)
2015-06-26 18:46

Branch CR26292_2 has been updated forcibly by mkv.

SHA-1: 3245a3a72e3c1e3fac778831f8800e4cdc32d9d0
(0042523)
mkv (tester)
2015-06-29 11:09

Dear BugMaster,
Branch CR26292_2 was rebased on current master of occt git-repository.
SHA-1: 3245a3a72e3c1e3fac778831f8800e4cdc32d9d0
(0042524)
mkv (tester)
2015-06-29 11:10

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)
(0042905)
git (administrator)
2015-07-10 13:58

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)
(0042906)
dbp (developer)
2015-07-10 13:58

Dear bugmaster,

please re-test the patch in branch CR26292_3.
(0042969)
apv (tester)
2015-07-13 15:34

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%]
(0043158)
git (administrator)
2015-07-17 14:45

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)
(0043159)
kgv (developer)
2015-07-17 14:46

Patch in branch CR26292_4 has been rebased onto current master.
(0043518)
git (administrator)
2015-07-27 13:39

Branch CR26292 has been deleted by kgv.

SHA-1: 0e6b96e27bc5394258e7bfdec4c3209d2a087f3e
(0043519)
git (administrator)
2015-07-27 13:39

Branch CR26292_1 has been deleted by kgv.

SHA-1: d925ad73b6bc3f83e9c080d64d1bbcaf64578cd0
(0043520)
git (administrator)
2015-07-27 13:39

Branch CR26292_2 has been deleted by kgv.

SHA-1: 3245a3a72e3c1e3fac778831f8800e4cdc32d9d0
(0043521)
git (administrator)
2015-07-27 13:39

Branch CR26292_3 has been deleted by kgv.

SHA-1: 0546f30ebe877e5eaef6cd9241ede345413e2fad
(0043522)
git (administrator)
2015-07-27 13:39

Branch CR26292_4 has been deleted by kgv.

SHA-1: 9936af603980577421b728507a47c26ab3af4cdd

- Related Changesets
occt: master 65578e1c
Timestamp: 2015-07-17 11:29:50
Author: dbp
Committer: bugmaster
Details ] Diff ]
0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder)
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 View Revisions
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 View Revisions
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 View Revisions
2016-04-20 15:43 aiv Fixed in Version => 7.0.0
2016-04-20 15:49 aiv Status verified => closed


Copyright © 2000 - 2020 MantisBT Team
Powered by Mantis Bugtracker