<div dir="ltr"><div>Hi,<br><br><a href="https://github.com/postgis/postgis/pull/592">https://github.com/postgis/postgis/pull/592</a> in principle brings all needed infrastructure for useful OpenMP-based parallel kmeans:<br><br> - recursive divide-and-conquer mode can be implemented via xmeans' improve_structure. <br> - copy-on-split is there to accomodate NUMA (job goes to another node and takes the data to their own memory segment if allocator is smart).<br> - all data structures are swapped to raw vectors of POINT4D, so you can swap allocator from palloc to malloc just in lwkmeans.c.<br><br>So generally there should be just a swap of palloc->malloc and a pragma inside improve_structure for nicely balanced parallel xmeans. For parallel kmeans, hack it to start with less clusters than requested and ramp it back up via xmeans splits.<br><br>Paralleling the update_r makes not much sense: better strategy is to replace it with rtree to go from O(KN) to O(KlogN). A properly implemented rtree will also improve the update_means step changing it from O(N) to O(logN).<br><br><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">вт, 27 июл. 2021 г. в 23:59, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca">pramsey@cleverelephant.ca</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Sidebar on multi-threading, you stripped the multi-threading (pthreads) out of the kmeans for various (good) reasons at the time, but it always seemed to me that kmeans was a perfect target for multi-threading, lots of very straight-forward looping and so on. Any thoughts on whether it is worth spending time trying to bring it back?<br>
<br>
P<br>
<br>
> On Jul 27, 2021, at 1:53 PM, Дорофей Пролесковский <<a href="mailto:me@komzpa.net" target="_blank">me@komzpa.net</a>> wrote:<br>
> <br>
> OpenMP is cool.<br>
> <br>
> I'd say the "take all cores" compile time switch will be a good start for pure analytical workloads like mine. Machine is oversaturated anyways, if it can return back to shell some minutes faster that would be great already.<br>
> <br>
> My previous experiments with instrumenting PostGIS for that exploded on the fact that palloc is not openmp-safe.<br>
> <br>
> <br>
> <br>
> вт, 27 июл. 2021 г. в 23:18, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>>:<br>
> Interested in knowing what people's general reaction to OpenMP work is. <br>
> <br>
> <a href="https://github.com/libgeos/geos/pull/468" rel="noreferrer" target="_blank">https://github.com/libgeos/geos/pull/468</a><br>
> <br>
> Going from PoC to something committable will involve a reasonable amount of CMake twiddling to detect support on multiple platforms and get the right linking info and so on. It can be flipped off as necessary. The biggest implementation thing missing is some kind of run-time API to signal to OpenMP the maximum number of cores to commit, since we'll want to at least wave our hands at trying to avoid capping out server resources.<br>
> <br>
> On the one hand it's kind of cool. On the other there's limited places to put it to work, and it adds complexity for certain.<br>
> <br>
> P.<br>
> _______________________________________________<br>
> geos-devel mailing list<br>
> <a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
> <a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
> _______________________________________________<br>
> geos-devel mailing list<br>
> <a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
> <a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
<br>
_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>
</blockquote></div></div>