You wouldn't necessarily need parallel processing to get more than an order of
magnitude performance improvement, but why not right? :)
The main trick with parallel processing is just managing access to data. If
multiple threads are reading/writing the same data, you have to make sure only
one thread at a time is accessing the data. It's even better when you can have
independent threads reading/writing data without the need for acquiring a lock
(WAY faster).
Our BU library makes parallel processing crazy simple no-frills so the app is
structured around the number crunching it might need. You call bu_parallel()
telling it how many threads to create, what function they should all call, and
a data pointer for stashing results.
Skriptkid's GCI patch is actually a really nice simple example of it in action:
http://www.google-melange.com/gci/task/view/google/gci2012/8086204
On top of that, I just added a new memory allocation interface, bu_heap_get(),
that will give you thread-safe memory. Used together, you have the basics in
place.
To get started, I'd suggest just creating a little test command to be run
within mged. A "fastecize" command (pun intended) copying
src/libged/facetize.c to src/libged/fastecize.c, updating the internal names to
match and adding a hook to your new command in src/mged/setup.c (look for
facetize). Add it to the src/libged/CMakeLists.txt file, make sure it
compiles, and check that it runs. You should have the essentials in place to
gut the function with your own parallel-processing creation. [1]
Maybe start by having a main thread serialize the hierarchy into a list of
objects, invoke threads to facetize each object and tabulate the polygons, then
have the main thread print out the total result. All that'd be left after that
performing the boolean evaluation instead of counting polygons.
Cheers!
Sean
[1] The ged_fastecize() function should eventually just be a wrapper around
some other function that lives down in librt (or libnmg), so we can call it
from all of our converters.
On Apr 9, 2013, at 7:29 PM, Matt Shepit wrote:
> A piece of me wants to take this on, as it would be a good opportunity to
> learn some parallel processing skills, which has been on my todo list for a
> while now. Might go well, might not...
>
> Any pointers as to where a good starting point might be?
>
> On 10/04/2013 9:04 AM, "Christopher Sean Morrison" <[email protected]> wrote:
> Anyone care to give this optimization a try? The solution is to use some
> spatial partitioning (e.g., a kd-tree) during the processing. Data coherence
> would be another. Both would be pure gravy.
>
> For tools like g-stl where we know we're going to triangles, it might make
> sense to triangulate right away (instead of processing as polygons and then
> to triangles) so we could use TIE's kd-tree during triangle comparisons.
> Another approach would be to try using something like
> http://code.google.com/p/kdtree/ or generalizing TIE's kd-tree. Or using a
> different BVH altogether. Either way, we just shouldn't end up with two
> implementations of the same algorithm in our tree (even for "just a little
> while"). Any takers?
>
> Cheers!
> Sean
>
>
> Begin forwarded message:
>
>> From: Christopher Sean Morrison <[email protected]>
>> Date: April 9, 2013 6:42:20 PM EDT
>> To: BRL-CAD Users Mailing List <[email protected]>
>> Subject: Re: [brlcad-users] Parallel g-stl conversion?
>> Reply-To: BRL-CAD Users Mailing List <[email protected]>
>>
>>
>> On Apr 9, 2013, at 5:24 PM, Joshua Stults wrote:
>>
>>> I think you are right; this scripting approach is probably what I'll end up
>>> doing. Right now I'm unioning a bunch of right circular cylinder
>>> primatives into a region, and then converting to stl with g-stl (I've found
>>> the time scaling for that to be quadratic in the number of cylinders [1]).
>>
>> Ouch! 8 hours for 500 cells... that's just awful. A recent change I've
>> been working on and was planning for public unveiling in a couple months
>> will probably cut a couple hours off that time but the conversion is still
>> way too slow.
>>
>> The reason it slows down so fast is due to the simple algorithm (which is
>> O(N^2) complexity at best with large overhead constants). As it unions in
>> each new object, it has to compare all the triangles being added against the
>> set so it knows how and where to stitch them together.
>>
>> The fix needed is a change to be spatially aware so that it doesn't have to
>> perform so many comparisons (O(N*log(N)). The next piece being added very
>> likely only intersects a few polygons. It should only compare against those
>> near it. Nothing at all hard, just not an optimization that's been
>> performed yet (we tend to abhor polygonal formats for their terrible
>> analysis and processing properites).
>>
>> Done right, it'd probably only take a few seconds.
>>
>>> An alternative approach would be to facetize the cylinders (maybe at really
>>> low resolution) and perform Boolean ops on those BoTs (perhaps
>>> incrementally rather than all n cylinders at once?). Would you expect
>>> unioning BoTs to be faster than unioning rcc primitives?
>>
>> It should be identical. Under the hood, it first turns all of the
>> primitives into polygons (which takes no time whatsoever) and then starts
>> splicing them together.
>>
>>> I'm happy to report back with timing results for any other approaches folks
>>> on the list recommend.
>>
>> Depending on how you combined the truss elements together, you may be able
>> to get a drastic reduction by changing your boolean recipe. For example,
>> say you had OBJ = A u B u C u D u E u F
>>
>> Changing that to spatially (and logically) group them first can cut down on
>> the number of comparisons:
>> OBJ = G1 u G2 u G3
>> G1 = A u B
>> G2 = C u D
>> G3 = E u F
>>
>> Worth a try if you basically built up a massive union. Most of the devs are
>> knee deep in the middle of projects at the moment to try the optimization,
>> but I'll add it to our TODO.
>>
>> Cheers!
>> Sean
>>
>>
>> ------------------------------------------------------------------------------
>> Precog is a next-generation analytics platform capable of advanced
>> analytics on semi-structured data. The platform includes APIs for building
>> apps and a phenomenal toolset for data science. Developers can use
>> our toolset for easy data analysis & visualization. Get a free account!
>> http://www2.precog.com/precogplatform/slashdotnewsletter
>> _______________________________________________
>> BRL-CAD Users mailing list
>> [email protected]
>> https://lists.sourceforge.net/lists/listinfo/brlcad-users
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> BRL-CAD Developer mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/brlcad-devel
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter_______________________________________________
> BRL-CAD Developer mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/brlcad-devel
------------------------------------------------------------------------------
Precog is a next-generation analytics platform capable of advanced
analytics on semi-structured data. The platform includes APIs for building
apps and a phenomenal toolset for data science. Developers can use
our toolset for easy data analysis & visualization. Get a free account!
http://www2.precog.com/precogplatform/slashdotnewsletter
_______________________________________________
BRL-CAD Developer mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-devel
