“Another operation which uses a recursive tree structure is
CascadedPolygonUnion. This should be fairly easy to make parallel, I think”
Exactly the same one I was thinking of! (and just started to look at). The new
concurrent classes in JDK 8 look promising, in particular the RecursiveTask and
ForkJoinPool.
Jim
From: Martin Davis [mailto:[email protected]]
Sent: 30 November 2015 17:41
To: Kay, Jim
Cc: [email protected]
Subject: Re: [Jts-topo-suite-user] JTS and Parallel Computing
I've given parallel computation with JTS only some casual thought, but one
thing that occurred to me is that there's two ways to parallelize geometry
computation with JTS. The first is what I'll call *external* parallelism. In
this scenario JTS itself runs sequentially, but the invoking process is
parallelized. In many cases the client process is easily parallelizable, so
this provides improved throughput for low effort.
The other approach is *internal* parallelism, in which JTS algorithms are
reworked to offer some degree of multi-execution. This sounds like what you're
thinking of. Is it the case that the frameworks mentioned can only improve
performance for internal parallelism? (In which case I'm curious to know why
this is - and to what extent it's in fact possible.)
For internal parallelism, the obvious place to look is at the major loops in
the processes. In the case of overlay operations, this would be the noding
phase. Ironically, the algorithms which provide best performance in the
sequential case often are not ones which parallelize. For instance, currently
overlay uses a sweepline algorithm for noding (SimpleMCSweepLineIntersector),
which is inherently sequential. To parallelize this it would be better to use
something like MCIndexNoder, which iterates over a set of unordered chains.
In the case of distance, the current (inefficient) algorithm iterates over a
set of unordered geometry "facets", so this should be easily parallelized.
However, there's a much more efficient approach which is to use a
Branch-and-Bound algorithm over two spatial indexes. Perhaps this would be
harder to parallelize?
Another operation which uses a recursive tree structure is
CascadedPolygonUnion. This should be fairly easy to make parallel, I think.
One worthy goal would be to generalize the code so that it is easy to switch
between parallel and sequential execution modes. How hard would this be?
On Mon, Nov 30, 2015 at 12:44 AM, Kay, Jim
<[email protected]<mailto:[email protected]>> wrote:
I am starting to think about dipping my toe in the water of Java parallel
computing; possibly using JCuda for gpu calculations, or PJ2 for everything, or
possibly MPJ-Express.
Has anybody got any experience or advice of using JTS in a parallel Java world?
Our application principally uses a lot of basic Polygon operations (union,
intersection, distance between geometries).
Can anybody provide any useful pointers as to which core Geometry routines
might benefit from speedup by being rewritten to use parallel methods?
Thanks.
Jim
Jim Kay
Principal Engineer
Tel: +44 (0) 1332 223229<tel:%2B44%20%280%29%201332%20223229>
Mob: +44 (0) 7715 536828<tel:%2B44%20%280%29%207715%20536828>
Email: [email protected]<mailto:[email protected]>
[cid:[email protected]]
interfleetgroup.com<http://www.interfleetgroup.com/> |
snclavalin.com<http://snclavalin.com>
------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]<mailto:[email protected]>
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
------------------------------------------------------------------------------
Go from Idea to Many App Stores Faster with Intel(R) XDK
Give your users amazing mobile app experiences with Intel(R) XDK.
Use one codebase in this all-in-one HTML5 development environment.
Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs.
http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
