nek5000 / parrsb

parallel graph partitioning using recursive spectral bisection (RSB)

parRSB

• Computes high quality partitionings using recursive spectral bisection (RSB)
• Requires MPI and gslib (requires version 1.0.8 or later)

Note, any initial distribution of mesh elements is valid.

Build Instructions

Download gslib from here and follow the build instructions there to build it. Then set the GSLIBPATH variable to point to the gslib build directory.

make CC=mpicc GSLIBPATH=<path to gslib>/build  all

Run Example

You can run both genmap and gencon examples in build/examples directory after building parRSB. Examples invoked with all available options are shown below.

cd build/examples
mpirun -np 4 ./genmap --mesh ethier --nactive=2 --tol=0.2 --test
mpirun -np 4 ./gencon --mesh ethier --tol=0.2 --test

• --mesh (required) is the name of the input mesh (.re2 file) and is required.
• --tol (optional, default = 0.2) is the tolerance used for finding mesh connectivity.
• --test (optional) Run checks in genmap or gencon examples.
• --dump (optional) Dump .co2 and/or .ma2 file after running gencon and/or genmap respectively.
• --nactive (optional, default: INT_MAX) controls how many MPI ranks are active when running genmap.

Please note that all the optional arguments requires a = sign when being specified in the command line.

C Interface

int parrsb_part_mesh(int *part, int *seq, long long *vtx, double *coord,
                     int nel, int nv, parrsb_options opts, MPI_Comm comm)

See example/genmap.c for an example.

Parameters

nel  [in] : Numer of local elements.
nv   [in] : Number of vertices in a single element (has to be same the for all).
vtx  [in] : Vertices of `nel` elements, `nv` entries for each element (dense
            unique IDs, size = nel * nv).
coord[in] : Coordinates of `nel` elements, should be in the same order as vtx
            (size = nel * dimesnion of the mesh).
opts [in] : parRSB configuration options (See below for a detailed explanation).
comm [in] : MPI Communicator (size determines number of partitions).
part [out]: Destination processor number for each element after partition
            (size = nel).
seq  [out]: Order of element `i` in processor `part[i]` after partition
            (size = nel).

opts is a struct of type parrsb_options declared in parRSB.h.

typedef struct {
  // General options
  int partitioner; // Partition algo: 0 - RSB, 1 - RCB, 2 - RIB (Default: 0)
  int tagged;      // Tagged partitioning: 0 - No, 1 - Yes (Default: 0)
  int levels;      // Number of levels: 1, or 2 (Default: 2)
  int find_disconnected_comps; // Find number of components: 0 - No, 1 - Yes
                               // (Default: 1)
  int repair; // Repair disconnected components: 0 - No, 1 - Yes (Default: 0)
  int verbose_level; // Verbose level: 0, 1, 2, .. etc (Default: 1)
  int profile_level; // Profile level: 0, 1, 2, .. etc (Default: 0)
  // RSB common (Lanczos and MG) options
  int rsb_algo; // RSB algo: 0 - Lanczos, 1 - MG (Default: 0)
  int rsb_pre;  // RSB pre-partition : 0 - None, 1 - RCB , 2 - RIB (Default: 1)
  int rsb_max_iter;   // Max iterations in Lanczos / MG (Default: 50)
  int rsb_max_passes; // Max Lanczos restarts / Inverse iterations (Default: 50)
  double rsb_tol;     // Tolerance for Lanczos or RQI (Default: 1e-5)
  int rsb_dump_stats; // Dump partition statistics to a text file.
  // RSB MG specific options
  int rsb_mg_grammian; // MG Grammian: 0 or 1 (Default: 0)
  int rsb_mg_factor;   // MG Coarsening factor (Default: 2, should be > 1)
} parrsb_options;

User can use parrsb_default_options struct instance to pass default options to parrsb_part_mesh routine.

All of these options can be controlled at runtime by setting the relevant environment variable (named PARRSB_<OPT_NAME>) as well. Enviornment variable values will override what is passed to parrsb_part_mesh routine.

Below is a full list of some of environment variables:

PARRSB_PARTITIONER
PARRSB_TAGGED
PARRSB_LEVELS
PARRSB_FIND_DISCONNECTED_COMPONENTS
PARRSB_REPAIR
PARRSB_VERBOSE_LEVEL
PARRSB_PROFILE_LEVEL

PARRSB_RSB_ALGO
PARRSB_RSB_PRE
PARRSB_RSB_MAX_ITER
PARRSB_RSB_MAX_PASSES
PARRSB_RSB_TOL

PARRSB_RSB_MG_GRAMMIAN
PARRSB_RSB_MG_FACTOR

parrsb's Issues

Fix unbalanced sort of Fielder vector

Our current bucket sort of the Fielder vector results in unbalanced bin sizes. Hence, we may run out of memory on some ranks.

Add two level partitioning for RCB/RIB similar to RSB

Refactor Internal structs and memory management

• Remove type from struct rcb_element and struct rsb_element
• Remove globalId0 from struct rsb_element
• Replace GenmapMalloc by tmalloc when allocating structs
• Replace GenmapMalloc by buffer_reserve when allocating arrays
• Replace GenmapFree by free and buffer_free
• Replace GenmapX by gslib types where X is int, long, uint, ulong.

Add more useful error messages for parCon failures

Print level id when printing disconnected components

Detect disconnected sets in quality check

Print warning if there are disconnected subsets

Fix memory issues in RCB, gencon and MG

Currently, the following functions are not valgrind clean:

• rcb_local
• findSegments
• mg_setup

Avoid disconnected subsets

The current implentation do not guarantee that the partitions are contiguous.

Add multi-level partitioning using MPI_COMM_TYPE_HW_GUIDED

Create connectivity online

Add RSB Level to disconnected subset warning

Update README to reflect latest API

Memory Leak

Tested on BGQ using fparRSB_partMesh()

Generate periodic face connectivity automatically

Change gmsh-test to C interface

• Remove gmsh reader from src
• Add gmsh reader to example
• Output results as vtk

Add CI testing

Get rid of identifier and type names with the suffix `_t`

POSIX has reserved these names.

Check if periodic face match can be optimized in parCon

We can get rid of this O(n^2) loop:
https://github.com/Nek5000/parRSB/blob/master/src/con-periodic.c#L188

Connectivity fails when running in serial

Describe the bug
Sometime in the last month, something broke in parSB related to how the connectivity works for serial cases. When I run a case in serial, I get a negative Jacobian error for every element in the mesh, but this error disappears and the case runs as normal if I run in parallel.

The reason I'm sure the error lies somewhere in parSB is because if you pre-generate the .co2 file, there is no error. So something is wrong with the automatic .co2 file generation for serial problems.

To Reproduce
I've attached a few input files that run with nekRS for you to replicate the problem. Download these files and run the following:

This fails with negative Jacobian errors:

nrsmpi pyramid 1 

This works:

nrsmpi pyramid 2

This also works:

gencon
nrsmpi pyramid 1

Expected behavior
Cases should be able to run in serial.

Fix or turn-off failing tests

Remove all implicit type converions

Select `gs_method` automatically in gs_setup

Currently, we have hard coded gs_crystal in genmap-laplacian.c and gs_pairwise in
genmap-quality.c. We should select these method automatically. May be we do this once
at the top level ?

Implement Adaptive Lanczos

Currently we're using a fixed iteration counts which is not robust and efficient.

Add genmap example

Run gencon + parRSB to generate a ma2 file.