00001 /* 00002 * Copyright 1997, Regents of the University of Minnesota 00003 * 00004 * struct.h 00005 * 00006 * This file contains data structures for ILU routines. 00007 * 00008 * Started 9/26/95 00009 * George 00010 * 00011 * $Id$ 00012 */ 00013 00014 /* Indexes are as long as integers for now */ 00015 #ifdef IDXTYPE_INT 00016 #define IDX_DATATYPE MPI_INT 00017 #define MAX_INT INT_MAX 00018 #define MIN_INT INT_MIN 00019 #else 00020 #define IDX_DATATYPE MPI_SHORT 00021 #define MAX_INT SHRT_MAX 00022 #define MIN_INT SHRT_MIN 00023 #endif 00024 00025 00026 /************************************************************************* 00027 * The following data structure stores key-value pair 00028 **************************************************************************/ 00029 struct KeyValueType { 00030 idxtype key; 00031 idxtype val; 00032 }; 00033 00034 typedef struct KeyValueType KeyValueType; 00035 00036 /************************************************************************* 00037 * The following data structure stores key-value pair 00038 **************************************************************************/ 00039 struct KVType { 00040 int key; 00041 floattype val; 00042 }; 00043 00044 typedef struct KVType KVType; 00045 00046 00047 /************************************************************************* 00048 * The following data structure stores key-value pair 00049 **************************************************************************/ 00050 struct FKeyValueType { 00051 floattype key; 00052 idxtype val; 00053 }; 00054 00055 typedef struct FKeyValueType FKeyValueType; 00056 00057 /************************************************************************* 00058 * The following data structure stores key-key-value triplets 00059 **************************************************************************/ 00060 struct KeyKeyValueType { 00061 idxtype key1, key2; 00062 idxtype val; 00063 }; 00064 00065 typedef struct KeyKeyValueType KeyKeyValueType; 00066 00067 /************************************************************************* 00068 * The following data structure is used to store the buckets for the 00069 * refinment algorithms 00070 **************************************************************************/ 00071 struct PQueueType { 00072 int nnodes; 00073 int maxnnodes; 00074 idxtype *perm, *iperm, *values; 00075 /* iperm[i] stores where the ith entry is located 00076 perm[i] stores the entry that is located in the ith position */ 00077 }; 00078 00079 typedef struct PQueueType PQueueType; 00080 00081 00082 /************************************************************************* 00083 * The following data structure is used to store the buckets for the 00084 * refinment algorithms 00085 **************************************************************************/ 00086 struct FPQueueType { 00087 int type; /* The type of the representation used */ 00088 int nnodes; 00089 int maxnodes; 00090 00091 /* Heap version of the data structure */ 00092 FKeyValueType *heap; 00093 idxtype *locator; 00094 }; 00095 00096 typedef struct FPQueueType FPQueueType; 00097 00098 /************************************************************************* 00099 * The following data structure stores an edge 00100 **************************************************************************/ 00101 struct edgedef { 00102 idxtype edge; 00103 idxtype ewgt; 00104 }; 00105 typedef struct edgedef EdgeType; 00106 00107 00108 /************************************************************************* 00109 * This data structure holds various working space data 00110 **************************************************************************/ 00111 struct workspacedef { 00112 idxtype *core; /* Where pairs, indices, and degrees are coming from */ 00113 int maxcore; 00114 00115 int nlarge; /* The size of 'Large' */ 00116 00117 KeyValueType *pairs; /* Large pair array used during setup */ 00118 idxtype *indices; /* Large array of indxtype used for various purposes */ 00119 00120 /* Auxiliary parameters */ 00121 idxtype *pv1, *pv2, *pv3, *pv4; /* Vectors of npes+1 size used in various places */ 00122 KeyValueType *pepairs1, *pepairs2; 00123 00124 EdgeType *degrees; 00125 }; 00126 00127 typedef struct workspacedef WorkSpaceType; 00128 00129 00130 /************************************************************************* 00131 * The following data structure holds information on degrees for k-way 00132 * partition 00133 **************************************************************************/ 00134 struct rinfodef { 00135 int id, ed; /* ID/ED of edges */ 00136 int ndegrees; /* The number of different ext-degrees */ 00137 EdgeType *degrees; /* List of edges */ 00138 }; 00139 00140 typedef struct rinfodef RInfoType; 00141 00142 00143 /************************************************************************* 00144 * The following data structure holds information on degrees for k-way 00145 * partition 00146 **************************************************************************/ 00147 struct nrinfodef { 00148 int edegrees[2]; 00149 }; 00150 00151 typedef struct nrinfodef NRInfoType; 00152 00153 00154 /************************************************************************* 00155 * The following data structure stores a sparse matrix in CSR format 00156 * The diagonal entry is in the first position of each row. 00157 **************************************************************************/ 00158 struct matrixdef { 00159 int nrows, nnzs; /* Number of rows and nonzeros in the matrix */ 00160 idxtype *rowptr; 00161 idxtype *colind; 00162 floattype *values; 00163 floattype *transfer; 00164 }; 00165 00166 typedef struct matrixdef MatrixType; 00167 00168 00169 /************************************************************************* 00170 * This data structure holds the input graph 00171 **************************************************************************/ 00172 struct graphdef { 00173 int gnvtxs, nvtxs, nedges, ncon, nobj; 00174 idxtype *xadj; /* Pointers to the locally stored vertices */ 00175 idxtype *vwgt; /* Vertex weights */ 00176 floattype *nvwgt; /* Vertex weights */ 00177 idxtype *vsize; /* Vertex size */ 00178 idxtype *adjncy; /* Array that stores the adjacency lists of nvtxs */ 00179 idxtype *adjwgt; /* Array that stores the weights of the adjacency lists */ 00180 idxtype *vtxdist; /* Distribution of vertices */ 00181 00182 idxtype *match; 00183 idxtype *cmap; 00184 00185 idxtype *label; 00186 00187 /* Communication/Setup parameters */ 00188 int nnbrs, nrecv, nsend; /* The number of neighboring processors */ 00189 idxtype *peind; /* Array of size nnbrs storing the neighboring PEs */ 00190 idxtype *sendptr, *sendind; /* CSR format of the vertices that are sent */ 00191 idxtype *recvptr, *recvind; /* CSR format of the vertices that are received */ 00192 idxtype *imap; /* The inverse map of local to global indices */ 00193 idxtype *pexadj, *peadjncy, 00194 *peadjloc; /* CSR format of the PEs each vertex is adjancent to */ 00195 00196 int nlocal; /* Number of interior vertices */ 00197 idxtype *lperm; /* lperm[0:nlocal] points to interior vertices, the rest are interface */ 00198 00199 /* Communication parameters for projecting the partition. 00200 * These are computed during CreateCoarseGraph and used during projection 00201 * Note that during projection, the meaning of received and sent is reversed! */ 00202 idxtype *rlens, *slens; /* Arrays of size nnbrs of how many vertices you are sending and receiving */ 00203 KeyValueType *rcand; 00204 00205 00206 /* Partition parameters */ 00207 idxtype *where, *home; 00208 idxtype *lpwgts, *gpwgts; 00209 floattype *lnpwgts, *gnpwgts; 00210 RInfoType *rinfo; 00211 00212 /* Node refinement information */ 00213 NRInfoType *nrinfo; 00214 int nsep; /* The number of vertices in the separator */ 00215 idxtype *sepind; /* The indices of the vertices in the separator */ 00216 00217 int lmincut, mincut; 00218 00219 int level; 00220 int match_type; 00221 int edgewgt_type; 00222 00223 struct graphdef *coarser, *finer; 00224 }; 00225 00226 typedef struct graphdef GraphType; 00227 00228 00229 /************************************************************************* 00230 * The following data type implements a timer 00231 **************************************************************************/ 00232 typedef double timer; 00233 00234 00235 /************************************************************************* 00236 * The following structure stores information used by parallel kmetis 00237 **************************************************************************/ 00238 struct controldef { 00239 int mype, npes; /* Info about the parallel system */ 00240 int CoarsenTo; /* The # of vertices in the coarsest graph */ 00241 int dbglvl; /* Controls the debuging output of the program */ 00242 int nparts; /* The number of partitions */ 00243 int foldf; /* What is the folding factor */ 00244 int ipart; /* The type of initial partitioning */ 00245 int xyztype; /* The type of coordinate indexing */ 00246 int seed; /* Random number seed */ 00247 int sync; /* Random number seed */ 00248 floattype *tpwgts; /* Target subdomain weights */ 00249 int tvwgts[MAXNCON]; 00250 floattype ubvec[MAXNCON]; 00251 int partType; 00252 int ps_relation; 00253 00254 floattype redist_factor, redist_base, ipc_factor; 00255 floattype edge_size_ratio; 00256 MatrixType *matrix; 00257 00258 MPI_Comm gcomm; 00259 MPI_Comm comm; /* MPI Communicator */ 00260 MPI_Request sreq[MAX_PES], 00261 rreq[MAX_PES]; /* MPI send and receive requests */ 00262 MPI_Status statuses[MAX_PES]; 00263 MPI_Status status; 00264 00265 /* Various Timers */ 00266 timer TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, RefTmr, 00267 SetupTmr, ColorTmr, ProjectTmr, KWayInitTmr, KWayTmr, MoveTmr, 00268 RemapTmr, AuxTmr1, AuxTmr2, AuxTmr3, AuxTmr4, AuxTmr5, AuxTmr6; 00269 }; 00270 00271 typedef struct controldef CtrlType; 00272 00273 00274 00275 /************************************************************************* 00276 * The following data structure stores a mesh. 00277 **************************************************************************/ 00278 struct meshdef { 00279 int etype; 00280 int gnelms, gnns; 00281 int nelms, nns; 00282 int ncon; 00283 int esize, gminnode; 00284 idxtype *elmdist; 00285 idxtype *elements; 00286 idxtype *elmwgt; 00287 }; 00288 00289 typedef struct meshdef MeshType; 00290
1.5.5