ScalES-PPM: Issueshttps://swprojects.dkrz.de/redmine/https://swprojects.dkrz.de/redmine/redmine/favicon.ico?17095821032017-09-26T01:13:39ZDKRZ projects
Redmine Feature #347 (Feedback): Add support for METIS v4-5 and ParMETIS v3-4https://swprojects.dkrz.de/redmine/issues/3472017-09-26T01:13:39ZMatthew Krupcale
<a name="Introduction"></a>
<h2 >Introduction<a href="#Introduction" class="wiki-anchor">¶</a></h2>
<p>The current ScalES-PPM API appears to be designed around the METIS v4 and ParMETIS v3 APIs. The attached patch aims to add support for both METIS v4 and v5 as well as ParMETIS v3 and v4.</p>
<a name="Summary-of-the-patched-files"></a>
<h2 >Summary of the patched files<a href="#Summary-of-the-patched-files" class="wiki-anchor">¶</a></h2>
<ul>
<li><code>configure.ac</code>: detect METIS and ParMETIS version; check <code>idxtype</code>/<code>idx_t</code> compatibility; check <code>real_t</code> compatibility</li>
<li><code>include/f77/ppm.inc.in</code>: define parameter <code>PPM_REAL</code> to be the width of <code>real_t</code></li>
<li><code>ppm.settings.in</code>: define ParMETIS/METIS <code>fcrealkind</code> to be the width of <code>real_t</code></li>
<li><code>src/Makefile.am</code>: define HAVE_METIS_V4 and HAVE_PARMETIS_V3 compiler preprocessor macros as needed; only in ParMETIS v3 include <code>src/ppm/parmetis_wrap.c</code> in <code>libscalesppm</code></li>
<li><code>src/ppm/ppm_graph_partition_mpi.f90</code>: adjust <code>INTERFACE SUBROUTINE parmetis_v3_partkway</code> C-binding for particular version of ParMETIS; use <code>c_null_ptr</code> instead of all combinations of <code>dummy_{balance,weights}</code></li>
<li><code>ppm_graph_partition_serial.f90</code>: define <code>INTERFACE SUBROUTINE metis_mcpartgraphkway</code>, <code>INTERFACE SUBROUTINE metis_setdefaultoptions</code>, and <code>INTERFACE SUBROUTINE metis_partgraphkway</code> C-bindings for particular version of METIS; use <code>c_null_ptr</code> instead of all combinations of <code>{v,e}w_dummy</code></li>
</ul>
<a name="Detailed-changes"></a>
<h2 >Detailed changes<a href="#Detailed-changes" class="wiki-anchor">¶</a></h2>
<a name="configureac"></a>
<h3 ><code>configure.ac</code><a href="#configureac" class="wiki-anchor">¶</a></h3>
<p>There have been several changes made between METIS v4 and v5 in particular, making <code>configure.ac</code> and <code>ppm/ppm_graph_partition_serial.f90</code> inoperable with METIS v5. Some of the particular changes between METIS v4 and v5 are:</p>
<ul>
<li>Changed <code>idxtype</code> -> <code>idx_t</code></li>
<li>Unified routines (<code>METIS_PartGraphKway</code>, <code>METIS_mCPartGraphKway</code>, <code>METIS_WPartGraphKway</code>, <code>METIS_PartGraphVKway</code>, <code>METIS_WPartGraphVKway</code>) -> <code>METIS_PartGraphKway</code> (with a change in API)</li>
</ul>
<p>ParMETIS v4 now also directly relies on METIS v5 and thus should not in principle have a different <code>idx_t</code> than METIS, unless the user explicitly builds METIS with <code>IDXTYPEWIDTH 32</code> and <code>IDXTYPEWIDTH 64</code>, then builds a modified version of ParMETIS v4. This would have to be a modified ParMETIS v4 because it directly includes the <code>metis.h</code>, where <code>idx_t</code> is <code>typedef</code>'d. Obviously this is not a supported configuration, and I would hope that the user would not attempt this. Nevertheless, if the user does this, the patched <code>configure.ac</code> still checks both <code>parmetis.h</code> and <code>metis.h</code> for the <code>idxtype</code>/<code>idx_t</code> and ensures that they are compatible.</p>
<p>Similarly to <code>idx_t</code>, METIS v5 now defines <code>real_t</code> rather than <code>float</code> for some of the balancing constraints. Thus, the patched <code>configure.ac</code> also checks for <code>real_t</code> (again in both <code>parmetis.h</code> and <code>metis.h</code>, in case the user tries to do something strange) and makes sure they are compatible. Note that this relies on the patch in <a class="issue tracker-1 status-5 priority-4 priority-default closed" title="Bug: ACX_FORTRAN_RUN_CHECK_SIZEOF in acx_fc_real_size.m4 does not check size of its argument (Closed)" href="https://swprojects.dkrz.de/redmine/issues/343">#343</a>.</p>
<p>These are the major changes to <code>configure.ac</code>. In addition to the above changes, <code>METIS_HEADER='metis/metis.h'</code> was removed because I could find no reference to such a file in any of the METIS installations and assumed this must be some custom installation location. In this case, the <code>metis.h</code> header location should be specified in the <code>configure</code> <code>CFLAGS</code> instead. If desired I can break this change out into a separate bug/patch, but it was causing issues when configuring my METIS/ParMETIS setups.</p>
<a name="srcMakefileam"></a>
<h3 ><code>src/Makefile.am</code><a href="#srcMakefileam" class="wiki-anchor">¶</a></h3>
<p>A Fortran to C wrapper for <code>ParMETIS_V3_PartKway</code> is included in <code>src/ppm/parmetis_wrap.c</code> since the ParMETIS v3 Fortran wrapper does not include the conversion from Fortran MPI communicator to C MPI communicator, while the v4 API does this properly (see macro <code>FRENAME</code> in <code>parmetis-4.0.3/libparmetis/frename.c</code>), so this wrapper is only included in <code>libscalesppm</code> when using ParMETIS v3.</p>
<a name="srcppmppm_graph_partition_mpif90"></a>
<h3 ><code>src/ppm/ppm_graph_partition_mpi.f90</code><a href="#srcppmppm_graph_partition_mpif90" class="wiki-anchor">¶</a></h3>
<p><code>ParMETIS_V3_PartKway</code> function has the following prototypes in v 3.2.0 and v 4.0.3, respectively:</p>
<pre>
// ParMETIS v 3.2.0
void __cdecl ParMETIS_V3_PartKway(
idxtype *vtxdist, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
idxtype *adjwgt, int *wgtflag, int *numflag, int *ncon, int *nparts,
float *tpwgts, float *ubvec, int *options, int *edgecut, idxtype *part,
MPI_Comm *comm);
// ParMETIS v 4.0.3
int __cdecl ParMETIS_V3_PartKway(
idx_t *vtxdist, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
idx_t *adjwgt, idx_t *wgtflag, idx_t *numflag, idx_t *ncon, idx_t *nparts,
real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *edgecut, idx_t *part,
MPI_Comm *comm);
</pre>
<p>Thus, the types defined in the <code>INTERFACE SUBROUTINE parmetis_v3_partkway</code> had to be adjusted depending on the version of the library used.</p>
<p>The method for invoking <code>parmetis_v3_partkway</code> was also modified to require only one <code>CALL</code> site with the arguments passed depending on the presence of the <code>OPTIONAL</code> arguments to <code>graph_partition_parmetis</code>. In particular, several <code>TYPE(c_ptr)</code> were used and passed (by value) to the <code>parmetis_v3_partkway</code> Fortran C-binding rather than using an uninitialized dummy array. This scales much better with the number of optional arguments: for <em>N</em> optional arguments, there are 2^N combinations, while defining a pointer to either <code>NULL</code> or the location of the argument when present scales linearly in <em>N</em>.</p>
<p>Although <code>balance</code> is an <code>OPTIONAL</code> argument, <code>tpwgts</code> appears to be required in the ParMETIS v4 API (see <code>parmetis-4.0.3/libparmetis/weird.c:CheckInputsPartKway</code>), and thus <code>balance</code> is constructed with equal weights for each sub-domain/partition when it is not present.</p>
<a name="ppm_graph_partition_serialf90"></a>
<h3 ><code>ppm_graph_partition_serial.f90</code><a href="#ppm_graph_partition_serialf90" class="wiki-anchor">¶</a></h3>
<p>METIS v4 has separate routines for multi-constraint partitioning (<code>METIS_mCPartGraphKway</code>) and single-constraint partitioning (<code>METIS_PartGraphKway</code>); in METIS v5, these two partitioning methods are unified into <code>METIS_PartGraphKway</code> (albeit with different API than in v4). METIS v5 also has a larger set of <code>options</code> and a corresponding function <code>METIS_SetDefaultOptions</code> to initialize it with defaults. Only <code>METIS_OPTION_NUMBERING</code> is set (corresponding to <code>numflag</code> in the v4 API) to indicate Fortran-style numbering.</p>
<p>The <code>METIS_PartGraphKway</code> function has the following prototypes in v 4.0.3 and v 5.1.1, respectively:</p>
<pre>
// METIS v 4.0.3
void METIS_PartGraphKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,
int *options, int *edgecut, idxtype *part);
// METIS v 5.1.0
METIS_API(int) METIS_PartGraphKway(idx_t *nvtxs, idx_t *ncon, idx_t *xadj,
idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt,
idx_t *nparts, real_t *tpwgts, real_t *ubvec, idx_t *options,
idx_t *edgecut, idx_t *part);
</pre>
<p>Thus, similar to in <code>src/ppm/ppm_graph_partition_mpi.f90</code>, the types and parameters defined in the <code>INTERFACE SUBROUTINE metis_partgraphkway</code> had to be adjusted depending on the version of the library used. Additionally, like in <code>src/ppm/ppm_graph_partition_mpi.f90</code>, <code>c_null_ptr</code> was used to indicate the absence of <code>OPTIONAL</code> arguments, and a single <code>CALL</code> site was used for all combinations of <code>OPTIONAL</code> arguments.</p>
<a name="Supported-combinations-of-METIS-and-ParMETIS"></a>
<h2 >Supported combinations of METIS and ParMETIS<a href="#Supported-combinations-of-METIS-and-ParMETIS" class="wiki-anchor">¶</a></h2>
<p>While this patch is designed for use with arbitrary combinations of METIS v4/v5 and ParMETIS v3/v4, in practice, when using ParMETIS, I expect this to only work when building ParMETIS with the internally-bundled version of METIS or with ParMETIS v4.0.3 and an internal or external METIS v5.</p>
<p>By default, it is not possible to build binaries linked against ParMETIS v3+ and external METIS v4 package because the ParMETIS v3 version of <code>parmetis.c</code> (modified from the METIS version) defines functions <code>METIS_NodeRefine</code> (needed by ParMETIS v3.2+) and/or <code>METIS_mCPartGraphRecursive2</code> (needed by ParMETIS v3). So in order to use an external METIS v4 with ParMETIS v3, the METIS v4 <code>parmetis.c</code> would have to be similarly modified to define these functions. However, it is possible to build binaries linked against ParMETIS v4 and external METIS v5 since it defines <code>METIS_NodeRefine</code>. This should also be clear from the fact that ParMETIS v4 now uses and bundles METIS v5 directly.</p>
<p>In spite of still technically supporting METIS v4 and ParMETIS v3, the only combination really recommended is METIS v5 and ParMETIS v4. In testing (using <code>example/graph_partition</code>), METIS v4 seems to be unreliable, returning <code>SIGABRT</code> double free or corrupted double-linked list or <code>SIGSEGV</code> segmentation fault errors within <code>METIS_mCPartGraphKway</code>. Thus, the multi-constraint procedure in METIS v4 seems altogether un-usable. These errors do not appear in the METIS v5 version. Both of these codes are more than 5 years old at this point, so I would hope that this is not much of an issue.</p>
<a name="Testing"></a>
<h2 >Testing<a href="#Testing" class="wiki-anchor">¶</a></h2>
<p>Since my goal is to package ScalES-PPM for Fedora, I am working on this on Fedora, and I have some Bash scripts which setup a mock chroot, build METIS v4 and ParMETIS v3/4, and build ScalES-PPM with various combinations of these. Let me know if you are interested in trying out these tests.</p> Feature #298 (New): Use binary search in sorted_insertionhttps://swprojects.dkrz.de/redmine/issues/2982012-01-18T19:58:06ZThomas Jahnsjahns@dkrz.de
<p>Since the list is already sorted upon sorted insertion, it would be beneficial to use binary search for finding the insertion position.</p> Feature #296 (Assigned): Multi-threaded repartitioning routinehttps://swprojects.dkrz.de/redmine/issues/2962012-01-02T13:20:29ZThomas Jahnsjahns@dkrz.de
<p>The multi-process variants of the repartition-by-swapping routines are a blue-print of how to construct comparable multi-threaded variants.</p>
<p>Additionally in a hybrid environment, it might also help to have a multi-threaded, multi-process variant.</p> Feature #294 (New): Add OpenMP multithreaded index construction routinehttps://swprojects.dkrz.de/redmine/issues/2942012-01-02T13:11:31ZThomas Jahnsjahns@dkrz.de
<p>Index construction can take huge amounts of time where the mask is large and not layed out in unit-step.</p> Feature #265 (New): new prefix for public ScalES-Lib names https://swprojects.dkrz.de/redmine/issues/2652011-04-13T09:38:42ZJoerg Behrensbehrens@dkrz.de
<p>We recently decided to call the ScalES Library "ScalES-Lib". I think we also need to reconsider our choice of name prefix, currently the prefix "ppm_" is used - this does not fit anymore. In my opinion, the purpose of the prefix is global namespace separation and visibility of our work. For practical purposes, the prefix should neither be too long nor too difficult to type or memorize.</p>
<p>Looking at the term "Scales-Lib", several possibilities come to my mind:</p>
<p>scl_<br />sesl_<br />slib_<br />scali_</p>
<p>I don't think this list is already comprehensive enough to start a vote, so I opened this issue in order to have a place for us for further suggestions.</p> Feature #263 (New): Support flushing of all open Fortran file descriptorshttps://swprojects.dkrz.de/redmine/issues/2632011-03-24T17:07:45ZThomas Jahnsjahns@dkrz.de
<p>To ensure legible debug print-outs, it is desirable to have a routine to call <code>flush</code> on all open output handles.</p> Feature #220 (Assigned): Add distributed summation routineshttps://swprojects.dkrz.de/redmine/issues/2202010-12-08T10:52:31ZThomas Jahnsjahns@dkrz.de
<p>Parallel summation of floating-point values is not associative and thus gives different results depending on the execution sequence which changes with MPI implementation and decomposition of the summed array.</p>
<p>Therefore a method to give identical results for any decomposition should be implemented, three alternatives are currently evaluated:</p>
<ol>
<li>summation of double double precision values (fast, but only limited guarantees against cancellation)</li>
<li>summation of wordsize integers derived from scaling of the FP values to a pre-established exponent (slow on some platforms where fp to integer conversion is slow, does not address cancellation or overflow)</li>
<li>summation of bignum integers derived from conversion of the FP values (slow, but addresses both overflow of intermediates and cancellation on any exponent range)</li>
</ol>
<p>The first alternative is already implemented in a prototype and only needs porting to the ScalES-PPM.</p> Feature #211 (New): Add support for rectangular grids in ncdf_dump.https://swprojects.dkrz.de/redmine/issues/2112010-11-15T10:36:37ZThomas Jahnsjahns@dkrz.de
<p>Currently only the general case of curvilinear grids is supported. Regular grid coordinates can be stored more efficiently as one-dimensional arrays for latitude and logitude each. This should be implemented to dump data out of ECHAM and other models with such a coordinate system.</p>