parmetis_util.hpp 9.64 KB
 tonynsyde committed Nov 19, 2015 1 2 3 4 5 6 7 8 9 10 11 12 ``````/* * parmetis_util.hpp * * Created on: Oct 07, 2015 * Author: Antonio Leo */ #ifndef PARMETIS_UTIL_HPP #define PARMETIS_UTIL_HPP #include #include "parmetis.h" `````` Pietro Incardona committed Feb 26, 2016 13 ``````#include "VTKWriter/VTKWriter.hpp" `````` tonynsyde committed Nov 19, 2015 14 ``````#include "VCluster.hpp" `````` Pietro Incardona committed Mar 01, 2016 15 ``````#include "Graph/ids.hpp" `````` tonynsyde committed Nov 19, 2015 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 `````` /*! \brief Metis graph structure * * Metis graph structure * */ struct Parmetis_graph { //! The number of vertices in the graph idx_t * nvtxs; //! number of balancing constrains //! more practical, are the number of weights for each vertex //! PS even we you specify vwgt == NULL ncon must be set at leat to //! one idx_t * ncon; //! For each vertex it store the adjacency lost start for the vertex i idx_t * xadj; //! For each vertex it store a list of all neighborhood vertex idx_t * adjncy; //! Array that store the weight for each vertex idx_t * vwgt; //! Array of the vertex size, basically is the total communication amount idx_t * vsize; //! The weight of the edge idx_t * adjwgt; //! number of part to partition the graph idx_t * nparts; //! Desired weight for each partition (one for each constrain) real_t * tpwgts; //! For each partition load imbalance tollerated real_t * ubvec; //! Additional option for the graph partitioning idx_t * options; //! return the total comunication cost for each partition idx_t * objval; //! Is a output vector containing the partition for each vertex idx_t * part; //! Upon successful completion, the number of edges that are cut by the partitioning is written to this parameter. idx_t * edgecut; //! This parameter describes the ratio of inter-processor communication time compared to data redistri- bution time. It should be set between 0.000001 and 1000000.0. If ITR is set high, a repartitioning with a low edge-cut will be computed. If it is set low, a repartitioning that requires little data redistri- bution will be computed. Good values for this parameter can be obtained by dividing inter-processor communication time by data redistribution time. Otherwise, a value of 1000.0 is recommended. real_t * itr; //! This is used to indicate the numbering scheme that is used for the vtxdist, xadj, adjncy, and part arrays. (0 for C-style, start from 0 index) idx_t * numflag; //! This is used to indicate if the graph is weighted. wgtflag can take one of four values: // 0 No weights (vwgt and adjwgt are both NULL). // 1 Weights on the edges only (vwgt is NULL). // 2 Weights on the vertices only (adjwgt is NULL). // 3 Weights on both the vertices and edges. idx_t * wgtflag; }; //! Balance communication and computation #define BALANCE_CC 1 //! Balance communication computation and memory #define BALANCE_CCM 2 //! Balance computation and comunication and others #define BALANCE_CC_O(c) c+1 /*! \brief Helper class to define Metis graph * * TODO Transform pointer to openfpm vector * * \tparam graph structure that store the graph * */ template class Parmetis { // Graph in metis reppresentation Parmetis_graph Mg; // Original graph // Graph & g; // Communticator for OpenMPI MPI_Comm comm = NULL; // VCluster Vcluster & v_cl; // Process rank information int p_id = 0; // nc Number of partition size_t nc = 0; `````` Pietro Incardona committed Mar 01, 2016 118 `````` // first re-mapped id `````` Pietro Incardona committed Mar 01, 2016 119 `````` rid first; `````` Pietro Incardona committed Mar 01, 2016 120 121 `````` // last re-mapped id `````` Pietro Incardona committed Mar 01, 2016 122 `````` rid last; `````` Pietro Incardona committed Mar 01, 2016 123 124 125 126 `````` // number of vertices that the processor has size_t nvertex; `````` tonynsyde committed Nov 19, 2015 127 128 `````` /*! \brief Construct Adjacency list * `````` Pietro Incardona committed Mar 01, 2016 129 `````` * \param g Global graph `````` tonynsyde committed Nov 19, 2015 130 131 `````` * */ `````` Pietro Incardona committed Mar 01, 2016 132 `````` void constructAdjList(Graph &g, const std::unordered_map & m2g) `````` tonynsyde committed Nov 19, 2015 133 134 135 136 `````` { // init basic graph informations and part vector // Put the total communication size to NULL `````` Pietro Incardona committed Mar 01, 2016 137 138 139 140 `````` Mg.nvtxs[0] = nvertex; Mg.part = new idx_t[nvertex]; size_t nedge = 0; `````` Pietro Incardona committed Mar 01, 2016 141 142 `````` size_t i = 0; for (rid j = first; i < nvertex ; i++, ++j) `````` Pietro Incardona committed Mar 01, 2016 143 `````` { `````` tonynsyde committed Nov 19, 2015 144 `````` Mg.part[i] = p_id; `````` Pietro Incardona committed Mar 01, 2016 145 `````` nedge += g.getNChilds(m2g.find(j)->second.id); `````` Pietro Incardona committed Mar 01, 2016 146 `````` } `````` tonynsyde committed Nov 19, 2015 147 148 `````` // create xadj, adjlist, vwgt, adjwgt and vsize `````` Pietro Incardona committed Mar 01, 2016 149 150 151 152 153 `````` Mg.xadj = new idx_t[nvertex + 1]; Mg.adjncy = new idx_t[nedge]; Mg.vwgt = new idx_t[nvertex]; Mg.adjwgt = new idx_t[nedge]; Mg.vsize = new idx_t[nvertex]; `````` tonynsyde committed Nov 19, 2015 154 155 156 157 158 159 160 `````` //! starting point in the adjacency list size_t prev = 0; // actual position size_t id = 0; `````` Pietro Incardona committed Mar 01, 2016 161 162 `````` size_t j = 0; `````` tonynsyde committed Nov 19, 2015 163 `````` // for each vertex calculate the position of the starting point in the adjacency list `````` Pietro Incardona committed Mar 01, 2016 164 `````` for (rid i = first ; i <= last; ++i, j++) `````` tonynsyde committed Nov 19, 2015 165 `````` { `````` Pietro Incardona committed Mar 01, 2016 166 `````` gid idx = m2g.find(i)->second; `````` tonynsyde committed Nov 19, 2015 167 168 `````` // Add weight to vertex and migration cost `````` Pietro Incardona committed Mar 01, 2016 169 170 `````` Mg.vwgt[j] = g.vertex(idx.id).template get(); Mg.vsize[j] = g.vertex(idx.id).template get();; `````` tonynsyde committed Nov 19, 2015 171 172 173 174 175 `````` // Calculate the starting point in the adjacency list Mg.xadj[id] = prev; // Create the adjacency list and the weights for edges `````` Pietro Incardona committed Mar 01, 2016 176 `````` for (size_t s = 0; s < g.getNChilds(idx.id); s++) `````` tonynsyde committed Nov 19, 2015 177 178 `````` { `````` Pietro Incardona committed Mar 01, 2016 179 `````` size_t child = g.getChild(idx.id, s); `````` tonynsyde committed Nov 19, 2015 180 `````` `````` Pietro Incardona committed Mar 01, 2016 181 `````` Mg.adjncy[prev + s] = g.vertex(child).template get(); `````` Pietro Incardona committed Mar 01, 2016 182 `````` Mg.adjwgt[prev + s] = g.getChildEdge(idx.id,s).template get(); `````` tonynsyde committed Nov 19, 2015 183 184 185 `````` } // update the position for the next vertex `````` Pietro Incardona committed Mar 01, 2016 186 `````` prev += g.getNChilds(idx.id); `````` tonynsyde committed Nov 19, 2015 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 `````` id++; } // Fill the last point Mg.xadj[id] = prev; } public: /*! \brief Constructor * * Construct a metis graph from Graph_CSR * * \param g Graph we want to convert to decompose * \param nc number of partitions * */ `````` Pietro Incardona committed Mar 01, 2016 205 206 `````` Parmetis(Vcluster & v_cl, size_t nc) :v_cl(v_cl), nc(nc) `````` tonynsyde committed Nov 19, 2015 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 `````` { // TODO Move into VCluster MPI_Comm_dup(MPI_COMM_WORLD, &comm); } //TODO deconstruct new variables /*! \brief destructor * * Destructor, It destroy all the memory allocated * */ ~Parmetis() { // Deallocate the Mg structure if (Mg.nvtxs != NULL) { delete[] Mg.nvtxs; } if (Mg.ncon != NULL) { delete[] Mg.ncon; } if (Mg.xadj != NULL) { delete[] Mg.xadj; } if (Mg.adjncy != NULL) { delete[] Mg.adjncy; } if (Mg.vwgt != NULL) { delete[] Mg.vwgt; } if (Mg.adjwgt != NULL) { delete[] Mg.adjwgt; } if (Mg.nparts != NULL) { delete[] Mg.nparts; } if (Mg.tpwgts != NULL) { delete[] Mg.tpwgts; } if (Mg.ubvec != NULL) { delete[] Mg.ubvec; } if (Mg.options != NULL) { delete[] Mg.options; } if (Mg.part != NULL) { delete[] Mg.part; } if (Mg.edgecut != NULL) { delete[] Mg.edgecut; } if (Mg.numflag != NULL) { delete[] Mg.numflag; } if (Mg.wgtflag != NULL) { delete[] Mg.wgtflag; } } /*! \brief Set the Sub-graph * `````` Pietro Incardona committed Mar 01, 2016 294 `````` * \param g Global graph to set `````` tonynsyde committed Feb 25, 2016 295 `````` * \param w true if vertices have weights `````` tonynsyde committed Nov 19, 2015 296 `````` */ `````` Pietro Incardona committed Mar 01, 2016 297 `````` void initSubGraph(Graph & g, const openfpm::vector & vtxdist, const std::unordered_map & m2g, bool w) `````` tonynsyde committed Nov 19, 2015 298 299 300 `````` { p_id = v_cl.getProcessUnitID(); `````` Pietro Incardona committed Mar 01, 2016 301 302 `````` first = vtxdist.get(p_id); last = vtxdist.get(p_id+1)-1; `````` Pietro Incardona committed Mar 01, 2016 303 `````` nvertex = last.id - first.id + 1; `````` Pietro Incardona committed Mar 01, 2016 304 `````` `````` tonynsyde committed Nov 19, 2015 305 306 `````` // Get the number of vertex Mg.nvtxs = new idx_t[1]; `````` Pietro Incardona committed Mar 01, 2016 307 `````` Mg.nvtxs[0] = nvertex; `````` tonynsyde committed Nov 19, 2015 308 309 310 311 312 313 314 315 316 317 318 319 `````` // Set the number of constrains Mg.ncon = new idx_t[1]; Mg.ncon[0] = 1; // Set to null the weight of the vertex (init after in constructAdjList) (can be removed) Mg.vwgt = NULL; // Set to null the weight of the edge (init after in constructAdjList) (can be removed) Mg.adjwgt = NULL; // construct the adjacency list `````` Pietro Incardona committed Mar 01, 2016 320 `````` constructAdjList(g, m2g); `````` tonynsyde committed Nov 19, 2015 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 `````` // Set the total number of partitions Mg.nparts = new idx_t[1]; Mg.nparts[0] = nc; //! Set option for the graph partitioning (set as default) Mg.options = new idx_t[4]; Mg.options[0] = 0; Mg.options[1] = 0; Mg.options[2] = 0; Mg.options[3] = 0; //! is an output vector containing the partition for each vertex //! adaptiveRepart itr value Mg.itr = new real_t[1]; Mg.itr[0] = 1000.0; //! init tpwgts to have balanced vertices and ubvec Mg.tpwgts = new real_t[Mg.nparts[0]]; Mg.ubvec = new real_t[Mg.nparts[0]]; `````` Pietro Incardona committed Feb 26, 2016 345 `````` for (size_t s = 0; s < (size_t)Mg.nparts[0]; s++) `````` tonynsyde committed Nov 19, 2015 346 347 348 349 350 351 352 353 354 355 356 357 358 359 `````` { Mg.tpwgts[s] = 1.0 / Mg.nparts[0]; Mg.ubvec[s] = 1.05; } Mg.edgecut = new idx_t[1]; Mg.edgecut[0] = 0; //! This is used to indicate the numbering scheme that is used for the vtxdist, xadj, adjncy, and part arrays. (0 for C-style, start from 0 index) Mg.numflag = new idx_t[1]; Mg.numflag[0] = 0; //! This is used to indicate if the graph is weighted. wgtflag can take one of four values: Mg.wgtflag = new idx_t[1]; `````` tonynsyde committed Feb 25, 2016 360 361 362 363 364 `````` if(w) Mg.wgtflag[0] = 3; else Mg.wgtflag[0] = 0; `````` tonynsyde committed Nov 19, 2015 365 366 367 368 369 370 371 372 `````` } /*! \brief Decompose the graph * * \tparam i which property store the decomposition * */ template `````` Pietro Incardona committed Mar 01, 2016 373 `````` void decompose(const openfpm::vector & vtxdist) `````` tonynsyde committed Nov 19, 2015 374 375 `````` { // Decompose `````` tonynsyde committed Jan 29, 2016 376 `````` `````` tonynsyde committed Nov 19, 2015 377 378 379 380 381 382 383 384 385 386 387 `````` ParMETIS_V3_PartKway((idx_t *) vtxdist.getPointer(), Mg.xadj, Mg.adjncy, Mg.vwgt, Mg.adjwgt, Mg.wgtflag, Mg.numflag, Mg.ncon, Mg.nparts, Mg.tpwgts, Mg.ubvec, Mg.options, Mg.edgecut, Mg.part, &comm); } /*! \brief Refine the graph * * \tparam i which property store the refined decomposition * */ template `````` Pietro Incardona committed Mar 01, 2016 388 `````` void refine(openfpm::vector & vtxdist) `````` tonynsyde committed Nov 19, 2015 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 `````` { // Refine ParMETIS_V3_AdaptiveRepart((idx_t *) vtxdist.getPointer(), Mg.xadj, Mg.adjncy, Mg.vwgt, Mg.vsize, Mg.adjwgt, Mg.wgtflag, Mg.numflag, Mg.ncon, Mg.nparts, Mg.tpwgts, Mg.ubvec, Mg.itr, Mg.options, Mg.edgecut, Mg.part, &comm); } /*! \brief Get graph partition vector * */ idx_t* getPartition() { return Mg.part; } /*! \brief Reset graph and reconstruct it `````` Pietro Incardona committed Mar 01, 2016 406 407 `````` * * \param Global graph `````` tonynsyde committed Nov 19, 2015 408 409 `````` * */ `````` Pietro Incardona committed Mar 01, 2016 410 `````` void reset(Graph & g,const openfpm::vector & vtxdist, const std::unordered_map & m2g) `````` tonynsyde committed Nov 19, 2015 411 `````` { `````` Pietro Incardona committed Mar 01, 2016 412 413 `````` first = vtxdist.get(p_id); last = vtxdist.get(p_id+1)-1; `````` Pietro Incardona committed Mar 01, 2016 414 `````` nvertex = last.id - first.id + 1; `````` Pietro Incardona committed Mar 01, 2016 415 `````` `````` tonynsyde committed Nov 19, 2015 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 `````` // Deallocate the graph structures if (Mg.xadj != NULL) { delete[] Mg.xadj; } if (Mg.adjncy != NULL) { delete[] Mg.adjncy; } if (Mg.vwgt != NULL) { delete[] Mg.vwgt; } if (Mg.adjwgt != NULL) { delete[] Mg.adjwgt; } if (Mg.part != NULL) { delete[] Mg.part; } // construct the adjacency list `````` Pietro Incardona committed Mar 01, 2016 444 `````` constructAdjList(g,m2g); `````` tonynsyde committed Nov 19, 2015 445 446 447 448 449 `````` } }; #endif``````