1 /* 2 * Copyright 2001, Regents of the University of Minnesota 3 * 4 * struct.h 5 * 6 * This file contains data structures. 7 * 8 * George Irene 9 */ 10 11 /* Indexes are as long as integers for now */ 12 #ifdef IDXTYPE_INT 13 #define IDX_DATATYPE MPI_INT 14 #else 15 #define IDX_DATATYPE MPI_SHORT 16 #endif 17 18 /* floats for now */ 19 #ifdef TYPE_REAL 20 #define REAL_DATATYPE MPI_FLOAT 21 #else 22 #define REAL_DATATYPE MPI_DOUBLE 23 #endif 24 25 26 /************************************************************************* 27 * The following data structure stores key-value pair 28 **************************************************************************/ 29 struct KeyValueType { 30 idxtype key; 31 idxtype val; 32 }; 33 34 typedef struct KeyValueType KeyValueType; 35 36 37 /************************************************************************* 38 * The following data structure is used to store the buckets for the 39 * refinment algorithms 40 **************************************************************************/ 41 struct PQueueType { 42 int nnodes; 43 int maxnnodes; 44 idxtype *perm, *iperm, *values; 45 /* iperm[i] stores where the ith entry is located 46 perm[i] stores the entry that is located in the ith position */ 47 }; 48 49 typedef struct PQueueType PQueueType; 50 51 52 /************************************************************************* 53 * The following data structure stores an edge 54 **************************************************************************/ 55 struct edgedef { 56 realtype ewgt; 57 idxtype edge; 58 }; 59 typedef struct edgedef EdgeType; 60 61 62 /************************************************************************* 63 * This data structure holds various working space data 64 **************************************************************************/ 65 struct workspacedef { 66 idxtype *core; /* Where pairs, indices, and degrees are coming from */ 67 int maxcore; 68 69 int nlarge; /* The size of 'Large' */ 70 71 KeyValueType *pairs; /* Large pair array used during setup */ 72 idxtype *indices; /* Large array of indxtype used for various purposes */ 73 74 /* Auxiliary parameters */ 75 idxtype *pv1, *pv2, *pv4; /* Vectors of npes+1 size used in various places */ 76 KeyValueType *pepairs1, *pepairs2; 77 78 EdgeType *degrees; 79 }; 80 81 typedef struct workspacedef MGridWorkSpaceType; 82 83 84 /************************************************************************* 85 * The following data structure holds information on degrees for k-way 86 * partition 87 **************************************************************************/ 88 struct rinfodef { 89 realtype id, ed; /* ID/ED of edges */ 90 int ndegrees; /* The number of different ext-degrees */ 91 EdgeType *degrees; /* List of edges */ 92 }; 93 94 typedef struct rinfodef RInfoType; 95 96 97 /************************************************************************* 98 * The following data structure holds information on degrees for k-way 99 * partition 100 **************************************************************************/ 101 struct nrinfodef { 102 int edegrees[2]; 103 }; 104 105 typedef struct nrinfodef NRInfoType; 106 107 108 /************************************************************************* 109 * This data structure holds the input graph 110 **************************************************************************/ 111 struct graphdef { 112 int gnvtxs, nvtxs, nedges; 113 idxtype *xadj; /* Pointers to the locally stored vertices */ 114 idxtype *vwgt; /* Vertex weights */ 115 realtype *vvol; /* The volume of the vertex */ 116 realtype *vsurf; /* The surface of the vertex (applicable only to boundary elements) */ 117 idxtype *vsize; /* Vertex size */ 118 idxtype *adjncy; /* Array that stores the adjacency lists of nvtxs */ 119 realtype *adjwgt; /* Array that stores the weights of the adjacency lists */ 120 realtype *adjwgtsum; /* The sum of the adjacent weights (surace volume) */ 121 idxtype *vtxdist; /* Distribution of vertices */ 122 123 idxtype *match; 124 idxtype *cmap; 125 126 /* Communication/Setup parameters */ 127 int nnbrs, nrecv, nsend; /* The number of neighboring processors */ 128 idxtype *peind; /* Array of size nnbrs storing the neighboring PEs */ 129 idxtype *sendptr, *sendind; /* CSR format of the vertices that are sent */ 130 idxtype *recvptr, *recvind; /* CSR format of the vertices that are received */ 131 idxtype *imap; /* The inverse map of local to global indices */ 132 idxtype *pexadj, *peadjncy, 133 *peadjloc; /* CSR format of the PEs each vertex is adjancent to */ 134 135 int nlocal; /* Number of interior vertices */ 136 idxtype *lperm; /* lperm[0:nlocal] points to interior vertices, the rest are interface */ 137 138 /* Communication parameters for projecting the partition. 139 * These are computed during CreateCoarseGraph and used during projection 140 * Note that during projection, the meaning of received and sent is reversed! */ 141 idxtype *rlens, *slens; /* Arrays of size nnbrs of how many vertices you are sending and receiving */ 142 KeyValueType *rcand; 143 144 145 /* Partition parameters */ 146 idxtype *where; /* processor where vtx resides */ 147 idxtype *fusedinfo; /* fused element vtx belongs to */ 148 idxtype *glblvtxid; 149 idxtype *lpwgts, *gpwgts; 150 realtype *lpvol, *gpvol; /* The volume of the partitions */ 151 realtype *lpsurf, *gpsurf; /* The surface area of the partitions */ 152 153 realtype lminratio, gminratio; /* The value of the objective function */ 154 155 RInfoType *rinfo; 156 157 /* Node refinement information */ 158 NRInfoType *nrinfo; 159 160 realtype lmincut, mincut; 161 }; 162 163 typedef struct graphdef MGridGraphType; 164 165 166 /************************************************************************* 167 * The following data type implements a timer 168 **************************************************************************/ 169 typedef double timer; 170 171 172 /************************************************************************* 173 * The following structure stores information used by parallel kmetis 174 **************************************************************************/ 175 struct controldef { 176 int mype, npes; /* Info about the parallel system */ 177 int dbglvl; /* Controls the debuging output of the program */ 178 int nparts; /* The number of partitions */ 179 180 int CType; /* The type of coarsening */ 181 int RType; /* The type of refinement */ 182 183 int minsize; /* The bounds on the number of elements per parti 184 tion */ 185 int maxsize; 186 187 188 MPI_Comm gcomm; 189 MPI_Comm comm; /* MPI Communicator */ 190 MPI_Request sreq[MAX_PES], 191 rreq[MAX_PES]; /* MPI send and receive requests */ 192 MPI_Status statuses[MAX_PES]; 193 MPI_Status status; 194 195 /* Various Timers */ 196 timer TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, RefTmr, 197 SetupTmr, ColorTmr, ProjectTmr, KWayInitTmr, KWayTmr, MoveTmr, 198 RemapTmr, AuxTmr1, AuxTmr2, AuxTmr3, AuxTmr4, AuxTmr5, AuxTmr6; 199 }; 200 201 typedef struct controldef MGridCtrlType; 202 203 204 /************************************************************************* 205 * The following data structure stores a sparse matrix in CSR format 206 * The diagonal entry is in the first position of each row. 207 **************************************************************************/ 208 struct matrixdef { 209 int nrows; /* Number of rows in the matrix */ 210 idxtype *rowptr; 211 idxtype *colind; 212 float *values; 213 idxtype *transfer; 214 }; 215 216 typedef struct matrixdef MatrixType; 217