You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
221 lines
9.4 KiB
221 lines
9.4 KiB
2 years ago
|
/*
|
||
|
|
* Copyright 1997, Regents of the University of Minnesota
|
||
|
|
*
|
||
|
|
* struct.h
|
||
|
|
*
|
||
|
|
* This file contains data structures for ILU routines.
|
||
|
|
*
|
||
|
|
* Started 9/26/95
|
||
|
|
* George
|
||
|
|
*
|
||
|
|
* $Id: struct.h 14362 2013-05-21 21:35:23Z karypis $
|
||
|
|
*/
|
||
|
|
|
||
|
|
#ifndef _LIBMETIS_STRUCT_H_
|
||
|
|
#define _LIBMETIS_STRUCT_H_
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! This data structure stores cut-based k-way refinement info about an
|
||
|
|
adjacent subdomain for a given vertex. */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct cnbr_t {
|
||
|
|
idx_t pid; /*!< The partition ID */
|
||
|
|
idx_t ed; /*!< The sum of the weights of the adjacent edges
|
||
|
|
that are incident on pid */
|
||
|
|
} cnbr_t;
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! The following data structure stores holds information on degrees for k-way
|
||
|
|
partition */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct ckrinfo_t {
|
||
|
|
idx_t id; /*!< The internal degree of a vertex (sum of weights) */
|
||
|
|
idx_t ed; /*!< The total external degree of a vertex */
|
||
|
|
idx_t nnbrs; /*!< The number of neighboring subdomains */
|
||
|
|
idx_t inbr; /*!< The index in the cnbr_t array where the nnbrs list
|
||
|
|
of neighbors is stored */
|
||
|
|
} ckrinfo_t;
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! This data structure stores volume-based k-way refinement info about an
|
||
|
|
adjacent subdomain for a given vertex. */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct vnbr_t {
|
||
|
|
idx_t pid; /*!< The partition ID */
|
||
|
|
idx_t ned; /*!< The number of the adjacent edges
|
||
|
|
that are incident on pid */
|
||
|
|
idx_t gv; /*!< The gain in volume achieved by moving the
|
||
|
|
vertex to pid */
|
||
|
|
} vnbr_t;
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! The following data structure holds information on degrees for k-way
|
||
|
|
vol-based partition */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct vkrinfo_t {
|
||
|
|
idx_t nid; /*!< The internal degree of a vertex (count of edges) */
|
||
|
|
idx_t ned; /*!< The total external degree of a vertex (count of edges) */
|
||
|
|
idx_t gv; /*!< The volume gain of moving that vertex */
|
||
|
|
idx_t nnbrs; /*!< The number of neighboring subdomains */
|
||
|
|
idx_t inbr; /*!< The index in the vnbr_t array where the nnbrs list
|
||
|
|
of neighbors is stored */
|
||
|
|
} vkrinfo_t;
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! The following data structure holds information on degrees for k-way
|
||
|
|
partition */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct nrinfo_t {
|
||
|
|
idx_t edegrees[2];
|
||
|
|
} nrinfo_t;
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! This data structure holds a graph */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct graph_t {
|
||
|
|
idx_t nvtxs, nedges; /* The # of vertices and edges in the graph */
|
||
|
|
idx_t ncon; /* The # of constrains */
|
||
|
|
idx_t *xadj; /* Pointers to the locally stored vertices */
|
||
|
|
idx_t *vwgt; /* Vertex weights */
|
||
|
|
idx_t *vsize; /* Vertex sizes for min-volume formulation */
|
||
|
|
idx_t *adjncy; /* Array that stores the adjacency lists of nvtxs */
|
||
|
|
idx_t *adjwgt; /* Array that stores the weights of the adjacency lists */
|
||
|
|
|
||
|
|
idx_t *tvwgt; /* The sum of the vertex weights in the graph */
|
||
|
|
real_t *invtvwgt; /* The inverse of the sum of the vertex weights in the graph */
|
||
|
|
|
||
|
|
|
||
|
|
/* These are to keep track control if the corresponding fields correspond to
|
||
|
|
application or library memory */
|
||
|
|
int free_xadj, free_vwgt, free_vsize, free_adjncy, free_adjwgt;
|
||
|
|
|
||
|
|
idx_t *cmap; /* The contraction/coarsening map */
|
||
|
|
|
||
|
|
idx_t *label; /* The labels of the vertices for recursive bisection (pmetis/ometis) */
|
||
|
|
|
||
|
|
/* Partition parameters */
|
||
|
|
idx_t mincut, minvol;
|
||
|
|
idx_t *where, *pwgts;
|
||
|
|
idx_t nbnd;
|
||
|
|
idx_t *bndptr, *bndind;
|
||
|
|
|
||
|
|
/* Bisection refinement parameters */
|
||
|
|
idx_t *id, *ed;
|
||
|
|
|
||
|
|
/* K-way refinement parameters */
|
||
|
|
ckrinfo_t *ckrinfo; /*!< The per-vertex cut-based refinement info */
|
||
|
|
vkrinfo_t *vkrinfo; /*!< The per-vertex volume-based refinement info */
|
||
|
|
|
||
|
|
/* Node refinement information */
|
||
|
|
nrinfo_t *nrinfo;
|
||
|
|
|
||
|
|
/* various fields for out-of-core processing */
|
||
|
|
int gID;
|
||
|
|
int ondisk;
|
||
|
|
|
||
|
|
/* keep track of the dropped edgewgt */
|
||
|
|
idx_t droppedewgt;
|
||
|
|
|
||
|
|
/* the linked-list structure of the sequence of graphs */
|
||
|
|
struct graph_t *coarser, *finer;
|
||
|
|
|
||
|
|
} graph_t;
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! This data structure holds a mesh */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct mesh_t {
|
||
|
|
idx_t ne, nn; /*!< The # of elements and nodes in the mesh */
|
||
|
|
idx_t ncon; /*!< The number of element balancing constraints (element weights) */
|
||
|
|
|
||
|
|
idx_t *eptr, *eind; /*!< The CSR-structure storing the nodes in the elements */
|
||
|
|
idx_t *ewgt; /*!< The weights of the elements */
|
||
|
|
} mesh_t;
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
/*************************************************************************/
|
||
|
|
/*! The following structure stores information used by Metis */
|
||
|
|
/*************************************************************************/
|
||
|
|
typedef struct ctrl_t {
|
||
|
|
moptype_et optype; /* Type of operation */
|
||
|
|
mobjtype_et objtype; /* Type of refinement objective */
|
||
|
|
mdbglvl_et dbglvl; /* Controls the debugging output of the program */
|
||
|
|
mctype_et ctype; /* The type of coarsening */
|
||
|
|
miptype_et iptype; /* The type of initial partitioning */
|
||
|
|
mrtype_et rtype; /* The type of refinement */
|
||
|
|
|
||
|
|
idx_t CoarsenTo; /* The # of vertices in the coarsest graph */
|
||
|
|
idx_t nIparts; /* The number of initial partitions to compute */
|
||
|
|
idx_t no2hop; /* Indicates if 2-hop matching will be used */
|
||
|
|
idx_t ondisk; /* Indicates out-of-core execution */
|
||
|
|
idx_t minconn; /* Indicates if the subdomain connectivity will be minimized */
|
||
|
|
idx_t contig; /* Indicates if contiguous partitions are required */
|
||
|
|
idx_t nseps; /* The number of separators to be found during multiple bisections */
|
||
|
|
idx_t ufactor; /* The user-supplied load imbalance factor */
|
||
|
|
idx_t compress; /* If the graph will be compressed prior to ordering */
|
||
|
|
idx_t ccorder; /* If connected components will be ordered separately */
|
||
|
|
idx_t seed; /* The seed for the random number generator */
|
||
|
|
idx_t ncuts; /* The number of different partitionings to compute */
|
||
|
|
idx_t niter; /* The number of iterations during each refinement */
|
||
|
|
idx_t numflag; /* The user-supplied numflag for the graph */
|
||
|
|
idx_t dropedges; /* Indicates if edges will be randomly dropped during coarsening */
|
||
|
|
idx_t *maxvwgt; /* The maximum allowed weight for a vertex */
|
||
|
|
|
||
|
|
idx_t ncon; /*!< The number of balancing constraints */
|
||
|
|
idx_t nparts; /*!< The number of partitions */
|
||
|
|
|
||
|
|
real_t pfactor; /* .1*(user-supplied prunning factor) */
|
||
|
|
|
||
|
|
real_t *ubfactors; /*!< The per-constraint ubfactors */
|
||
|
|
|
||
|
|
real_t *tpwgts; /*!< The target partition weights */
|
||
|
|
real_t *pijbm; /*!< The nparts*ncon multiplies for the ith partition
|
||
|
|
and jth constraint for obtaining the balance */
|
||
|
|
|
||
|
|
real_t cfactor; /*!< The achieved compression factor */
|
||
|
|
|
||
|
|
/* Various Timers */
|
||
|
|
double TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, UncoarsenTmr,
|
||
|
|
RefTmr, ProjectTmr, SplitTmr, Aux1Tmr, Aux2Tmr, Aux3Tmr;
|
||
|
|
|
||
|
|
/* Workspace information */
|
||
|
|
gk_mcore_t *mcore; /*!< The persistent memory core for within function
|
||
|
|
mallocs/frees */
|
||
|
|
|
||
|
|
/* These are for use by the k-way refinement routines */
|
||
|
|
size_t nbrpoolsize_max; /*!< The maximum number of {c,v}nbr_t entries that will ever be allocated */
|
||
|
|
size_t nbrpoolsize; /*!< The number of {c,v}nbr_t entries that have been allocated */
|
||
|
|
size_t nbrpoolcpos; /*!< The position of the first free entry in the array */
|
||
|
|
size_t nbrpoolreallocs; /*!< The number of times the pool was resized */
|
||
|
|
|
||
|
|
cnbr_t *cnbrpool; /*!< The pool of cnbr_t entries to be used during refinement.
|
||
|
|
The size and current position of the pool is controlled
|
||
|
|
by nnbrs & cnbrs */
|
||
|
|
vnbr_t *vnbrpool; /*!< The pool of vnbr_t entries to be used during refinement.
|
||
|
|
The size and current position of the pool is controlled
|
||
|
|
by nnbrs & cnbrs */
|
||
|
|
|
||
|
|
/* The subdomain graph, in sparse format */
|
||
|
|
idx_t *maxnads; /* The maximum allocated number of adjacent domains */
|
||
|
|
idx_t *nads; /* The number of adjacent domains */
|
||
|
|
idx_t **adids; /* The IDs of the adjacent domains */
|
||
|
|
idx_t **adwgts; /* The edge-weight to the adjacent domains */
|
||
|
|
idx_t *pvec1, *pvec2; /* Auxiliary nparts-size vectors for efficiency */
|
||
|
|
|
||
|
|
/* ondisk related info */
|
||
|
|
pid_t pid; /*!< The pid of the running process */
|
||
|
|
} ctrl_t;
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
#endif
|