<br><br><div class="gmail_quote"><br><br>I sent a previous mail but it did not go through, so sending it again:<br><br>The base concept is that if we are going to parallelize, then the parallelization can be of two types,<br>
keeping the current algorithm and tweaking it to become more parallel.<br>
Here, a method will be to run the r.cost of two entities in the store(heap I assume), to a certain depth, and then collecting their values.<br><br>Another method is to partition the dataspace into large chunks, and perform operations on them.<br>
Here the method is to divide the space into say 8 blocks, such that each block divides the map into 3 entities and any path from block 1 and 3 pass through block2. Then run the algorithm for each boundary element such that the cost of each pixel pair on (boundary12 and boundary23) and (boundary12,12) and (boundary 23,23) cost is known.<br>
<br>The given map is just too big for the second operation, the size of temporary store being arnd 40 gb.<br>For smaller image sizes, the method would have worked just fine.<br>The reference paper for the second method <br>
A simple parallel algorithm for the single source shortest path problem on planar digraphs.<br><br>The assumption I am making is that the algorithm for r.cost is closely related to dijkstra's algorithm.<div><div></div>
<div class="h5"><br><br><br><br>
<div class="gmail_quote">On Fri, Apr 10, 2009 at 6:02 PM, Glynn Clements <span dir="ltr"><<a href="mailto:glynn@gclements.plus.com" target="_blank">glynn@gclements.plus.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div><br>
Colin Nielsen wrote:<br>
<br>
> In my experience, the main drain in computation time is the IO not the<br>
> actual calculation of the btree. Is there any way to parallelize the<br>
> IO by passing rows to different cores or something like that ie. "for<br>
> (row = 0; row < nrows; row++) {"?<br>
<br>
</div>That's feasible, but r.cost and r.walk aren't row-by-row algorithms.<br>
<br>
With a row-by-row algorithm, you still have the issue that you can't<br>
have multiple concurrent invocations of G_get_raster_row() etc on a<br>
single map (in 6.x, you simply can't have multiple concurrent<br>
invocations, even on different maps).<br>
<br>
But you can have one thread which reads rows, multiple threads which<br>
each process a particular row, and one thread which writes rows. The<br>
number of useful intermediate threads is limited by the I/O rate.<br>
<div><br>
> Or a more efficient segment library sounds good as well. Is there a<br>
> way to estimate how much more efficient would it be<br>
<br>
</div>Hard to say. The main inefficiencies with the current implementation<br>
are:<br>
<br>
1. The tile size isn't restricted to a power of two (so it uses<br>
division/remainder rather than shift/mask).<br>
<br>
2. The tile size is set at run-time rather than compile-time.<br>
<br>
3. Acess is via function calls rather than macros or inline functions.<br>
<br>
The version in r.proj[.seg] doesn't have these issues, although it's<br>
currently read-only.<br>
<div><br>
> and would it make use of multiple cores?<br>
<br>
</div>Using multiple threads for segment I/O would probably be a net loss,<br>
as you would need to perform locking for every access.<br>
<br>
Multi-threading is most effective if you can partition the data such<br>
that you don't need to perform locking.<br>
<div><br>
--<br>
Glynn Clements <<a href="mailto:glynn@gclements.plus.com" target="_blank">glynn@gclements.plus.com</a>><br>
_______________________________________________<br>
</div><div><div></div><div>grass-dev mailing list<br>
<a href="mailto:grass-dev@lists.osgeo.org" target="_blank">grass-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/grass-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/grass-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><br></div></div>-- <br><div><div></div><div class="h5">JYOTHISH SOMAN<br>MS-2008-CS<br>Center for Security, Theory And Algorithm Research (CSTAR)<br>International Institute of Information Technology<br>
Hyderabad<br>
India<br>Phone:+91-9966222626<br><a href="http://www.iiit.ac.in/" target="_blank">http://www.iiit.ac.in/</a><br>--------------------------------------------------------------<br>The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.<br>
George Bernard Shaw<br>--------------------------------------------------------<br><br>
</div></div></div><br><br clear="all"><br>-- <br>JYOTHISH SOMAN<br>MS-2008-CS<br>Center for Security, Theory And Algorithm Research (CSTAR)<br>International Institute of Information Technology<br>Hyderabad<br>India<br>Phone:+91-9966222626<br>
<a href="http://www.iiit.ac.in/">http://www.iiit.ac.in/</a><br>--------------------------------------------------------------<br>The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.<br>
George Bernard Shaw<br>--------------------------------------------------------<br><br>