[GRASS-dev] [GRASS GIS] #3104: Parallelize tools like r.cost

#3104: Parallelize tools like r.cost
-------------------------+-------------------------
Reporter: belg4mit | Owner: grass-dev@…
     Type: enhancement | Status: new
Priority: normal | Milestone: 7.0.5
Component: Default | Version: unspecified
Keywords: | CPU: Unspecified
Platform: Unspecified |
-------------------------+-------------------------
Currently QGIS will peg one of my cores while running r.cost. This leaves
the system usable, but it also greatly slows down the execution time.
Traversal of the cost raster should be readily parallelizable, and could
divide the run time by the number of cores allocated.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/3104&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------
Changes (by martinl):

* keywords: => r.cost
* component: Default => Raster
* milestone: 7.0.5 => 7.3.0

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3104#comment:1&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------

Comment (by mmetz):

Replying to [ticket:3104 belg4mit]:
> Currently QGIS will peg one of my cores while running r.cost. This
leaves the system usable, but it also greatly slows down the execution
time. Traversal of the cost raster should be readily parallelizable, and
could divide the run time by the number of cores allocated.

Can you provide hints about how r.cost could be parallelized? That would
help a lot.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3104#comment:2&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------

Comment (by belg4mit):

Hmm, the algorithm used is different than I imagined. However it seems
like one possibility, although it would not necessarily scale easily
beyond two cores, would be to have a pair of threads iterating over the
raster cells: One beginning at the top left and the other working
backwards from the bottom right.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3104#comment:3&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------

Comment (by mmetz):

Replying to [comment:3 belg4mit]:
> Hmm, the algorithm used is different than I imagined. However it seems
like one possibility, although it would not necessarily scale easily
beyond two cores, would be to have a pair of threads iterating over the
raster cells: One beginning at the top left and the other working
backwards from the bottom right.

r.cost, like least cost search path methods in general, do not iterate
over items. Instead, r.cost starts with the start cells, calculates costs
to the neighbors and continues with the cell with the least cost,
calculating the costs to its neighbors, granted that the neighbors have
not yet been processed. It stops when all cells have been processed or if
all stop points have been reached. That means random access to cells, the
order in which cells are processed is determined by the cost to reach a
cell.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3104#comment:4&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------

Comment (by belg4mit):

I understand your point, but that's still a form of iteration, simply over
a continuously updated list rather than pixel indices (which does occur as
well). Regardless, why couldn't the start cells be divided up among
multiple threads? e.g; those on the top of the image for core0, and those
on bottom for core1.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/3104#comment:5&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------

Comment (by mmetz):

Replying to [comment:5 belg4mit]:
> I understand your point, but that's still a form of iteration, simply
over a continuously updated list rather than pixel indices (which does
occur as well). Regardless, why couldn't the start cells be divided up
among multiple threads? e.g; those on the top of the image for core0, and
those on bottom for core1.

The list needs to be updated using the cell with the current lowest cost.
There is always only one such cell, processing the e.g. four cells with
the lowest costs in separate threads would corrupt the result (after one
cell is processed, the list of the smallest four cells might change). In
other words, the order of iteration is not predictable.

You could start a separate thread for each start point separately, but
then you would need to create an individual temporary output for each
start cell and process all cells once for each start cell. At the end, the
different outputs would need to be merged, assigning to each cell the cost
and the path to the closest start cell. In the current single-thread
version, all start cells are loaded at the beginning and processed
together. Each cell needs to be processed only once, regardless of the
number of start cells. Thus with your suggestion, more cores could be
used, but total processing time would be longer.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3104#comment:6&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------

Comment (by belg4mit):

Apparently others have done work on this, however C is not my forte so I'm
not sure about adapting these:

http://calhoun.nps.edu/bitstream/handle/10945/27274/solvingweightedr00garc.pdf
http://www.sciencedirect.com/science/article/pii/092523129400018N

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/3104#comment:7&gt;
GRASS GIS <https://grass.osgeo.org>

#3104: Parallelize tools like r.cost
--------------------------+-------------------------
  Reporter: belg4mit | Owner: grass-dev@…
      Type: enhancement | Status: new
  Priority: normal | Milestone: 7.3.0
Component: Raster | Version: unspecified
Resolution: | Keywords: r.cost
       CPU: Unspecified | Platform: Unspecified
--------------------------+-------------------------

Comment (by mmetz):

Replying to [comment:7 belg4mit]:
> Apparently others have done work on this, however C is not my forte so
I'm not sure about adapting these:
>
>
http://calhoun.nps.edu/bitstream/handle/10945/27274/solvingweightedr00garc.pdf
> http://www.sciencedirect.com/science/article/pii/092523129400018N

Thanks for the references! There are more helpful references in the links
you provided. Parallelizing r.cost according to these references would be
a nice Google Summer of Code project.

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/3104#comment:8&gt;
GRASS GIS <https://grass.osgeo.org>