[GRASS-dev] Interested in parallelization of GRASS

[Markus Metz]

Glynn Clements wrote:
>
> Markus Metz wrote:
>
>> The segment lib implementation in trunk is considerably faster than in
>> 6.x, but not as efficient as the caching method of r.proj. Some
>> reasons why the segment library is slower than the caching code in
>> r.proj are 1) write support in the segment lib, 2) flexible data
>> storage size in the segment lib, 3) flexible tile size in the segment
>> lib, 4) bad abuse of the segment library, e.g. in r.los.
>
> The main factors for performance are whether the tile size is fixed at
> compile time and whether it's known (at compile time) to be a power of
> two.
>
> It wouldn't be particularly hard to structure the r.proj tile cache
> code such that the tile size can be set by the module, so long as it's
> set at compile time. Allowing the tile size to be set at run time
> incurs an inevitable performance penalty.
>
That means that the r.proj tile cache can not go into a library
function because libraries are compiled before modules, i.e. tile size
and data structure size are no known to the library at compile time,
correct? Thus the r.proj tile cache code would need to be duplicated
for each module, making maintenance more tedious. See e.g. the
different versions of crs.[c|h] floating around in the imagery
modules.

> The power-of-two constraint needn't be enforced by the code. The
> shifts and masks could be replaced by multiplication, division and
> modulo; any modern compiler will optimise these back to shifts and
> masks if the tile size is a compile-time constant which is a power of
> two.
>
The segment library in G7 figures out during setup of the segment
structure if bit operations can be used. That gave me a good speed-up.

> OTOH, I'm not sure there's any benefit to relaxing the requirement.
> Some modules may be less efficient if the tile size is significantly
> too small or too large, but being off by a factor of sqrt(2) shouldn't
> be an issue.
>
The tile size used by r.cost, r.walk, r.watershed in G7 is 64x64
throughout, as for the r.proj tile cache. That size seems to be good
for various different region sizes. With the exception of r.watershed
where a sorted array is stored in a segmented structure, i.e. only one
row, many columns.

I have optimized the segment library a bit more (using an idea from
the r.poj tile cache). For a region with 66 million cells, r.watershed
in segmented mode with memory=2000 needs 66 minutes in 6.4 and 7m30s
in 7.0. The all-in-memory mode finishes in about 4m30s. That includes
optimizations of r.watershed.seg in 7, though. Anyway, the time
penalty by using the grass 7 segment library seems to be no longer
that serious.

I am not against a replacement of the segment library, but I would
like to keep any tile cache code as a library for easy code
maintenance. And I would like to have some flexibility, at least
support for tiles and arrays as well as custom data sizes beyond CELL,
FCELL, DCELL.

Markus M