parmetis_util.hpp 12.2 KB
Newer Older
tonynsyde's avatar
tonynsyde committed
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 <iostream>
#include "parmetis.h"
13
#include "VTKWriter/VTKWriter.hpp"
incardon's avatar
incardon committed
14
#include "VCluster/VCluster.hpp"
15
#include "Graph/ids.hpp"
tonynsyde's avatar
tonynsyde committed
16

incardon's avatar
incardon committed
17 18 19
#define PARMETSI_ERROR_OBJECT std::runtime_error("Runtime Parmetis error");


tonynsyde's avatar
tonynsyde committed
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
/*! \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
 *
 * \tparam graph structure that store the graph
 *
 */
template<typename Graph>
class Parmetis
{
incardon's avatar
incardon committed
101
	//! Graph in metis reppresentation
tonynsyde's avatar
tonynsyde committed
102 103 104 105 106
	Parmetis_graph Mg;

	// Original graph
	//	Graph & g;

incardon's avatar
incardon committed
107
	//! Communticator for OpenMPI
108
	MPI_Comm comm = (MPI_Comm)NULL;
tonynsyde's avatar
tonynsyde committed
109

incardon's avatar
incardon committed
110
	//! VCluster
tonynsyde's avatar
tonynsyde committed
111 112
	Vcluster & v_cl;

incardon's avatar
incardon committed
113
	//! Process rank information
tonynsyde's avatar
tonynsyde committed
114 115
	int p_id = 0;

incardon's avatar
incardon committed
116
	//! nc Number of partition
tonynsyde's avatar
tonynsyde committed
117 118
	size_t nc = 0;

incardon's avatar
incardon committed
119
	//! first re-mapped id
120
	rid first;
121

incardon's avatar
incardon committed
122
	//! last re-mapped id
123
	rid last;
124

incardon's avatar
incardon committed
125
	//! number of vertices that the processor has
126 127
	size_t nvertex;

incardon's avatar
incardon committed
128 129 130
	//! indicate how many time decompose/refine/re-decompose has been called
	size_t n_dec;

incardon's avatar
incardon committed
131 132 133
	//! Distribution tolerance
	real_t dist_tol = 1.05;

tonynsyde's avatar
tonynsyde committed
134 135
	/*! \brief Construct Adjacency list
	 *
136
	 * \param g Global graph
incardon's avatar
incardon committed
137
	 * \param m2g map from local index to global index
tonynsyde's avatar
tonynsyde committed
138 139
	 *
	 */
140
	void constructAdjList(Graph &g, const std::unordered_map<rid, gid> & m2g)
tonynsyde's avatar
tonynsyde committed
141 142 143 144
	{
		// init basic graph informations and part vector
		// Put the total communication size to NULL

145 146 147 148
		Mg.nvtxs[0] = nvertex;
		Mg.part = new idx_t[nvertex];

		size_t nedge = 0;
149
		size_t i = 0;
150
		for (rid j = first; i < nvertex; i++, ++j)
151
		{
tonynsyde's avatar
tonynsyde committed
152
			Mg.part[i] = p_id;
153
			nedge += g.getNChilds(m2g.find(j)->second.id);
154
		}
tonynsyde's avatar
tonynsyde committed
155 156

		// create xadj, adjlist, vwgt, adjwgt and vsize
157 158 159 160 161
		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's avatar
tonynsyde committed
162 163 164 165 166 167 168

		//! starting point in the adjacency list
		size_t prev = 0;

		// actual position
		size_t id = 0;

169 170
		size_t j = 0;

tonynsyde's avatar
tonynsyde committed
171
		// for each vertex calculate the position of the starting point in the adjacency list
172
		for (rid i = first; i <= last; ++i, j++)
tonynsyde's avatar
tonynsyde committed
173
		{
174
			gid idx = m2g.find(i)->second;
tonynsyde's avatar
tonynsyde committed
175 176

			// Add weight to vertex and migration cost
177
			Mg.vwgt[j] = g.vertex(idx.id).template get<nm_v::computation>();
178
			Mg.vsize[j] = g.vertex(idx.id).template get<nm_v::migration>();
tonynsyde's avatar
tonynsyde committed
179 180 181 182 183

			// Calculate the starting point in the adjacency list
			Mg.xadj[id] = prev;

			// Create the adjacency list and the weights for edges
184
			for (size_t s = 0; s < g.getNChilds(idx.id); s++)
tonynsyde's avatar
tonynsyde committed
185 186
			{

187
				size_t child = g.getChild(idx.id, s);
tonynsyde's avatar
tonynsyde committed
188

189
				Mg.adjncy[prev + s] = g.vertex(child).template get<nm_v::id>();
190
				Mg.adjwgt[prev + s] = g.getChildEdge(idx.id, s).template get<nm_e::communication>();
tonynsyde's avatar
tonynsyde committed
191 192 193
			}

			// update the position for the next vertex
194
			prev += g.getNChilds(idx.id);
tonynsyde's avatar
tonynsyde committed
195 196 197 198 199 200 201 202 203 204 205 206 207 208

			id++;
		}

		// Fill the last point
		Mg.xadj[id] = prev;
	}

public:

	/*! \brief Constructor
	 *
	 * Construct a metis graph from Graph_CSR
	 *
incardon's avatar
incardon committed
209
	 * \param v_cl Vcluster object
tonynsyde's avatar
tonynsyde committed
210 211 212
	 * \param nc number of partitions
	 *
	 */
213
	Parmetis(Vcluster & v_cl, size_t nc)
incardon's avatar
incardon committed
214
	:v_cl(v_cl), nc(nc),n_dec(0)
tonynsyde's avatar
tonynsyde committed
215 216 217
	{
		// TODO Move into VCluster
		MPI_Comm_dup(MPI_COMM_WORLD, &comm);
Pietro Incardona's avatar
Pietro Incardona committed
218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236

		// Nullify Mg
		Mg.nvtxs = NULL;
		Mg.ncon = NULL;
		Mg.xadj = NULL;
		Mg.adjncy = NULL;
		Mg.vwgt = NULL;
		Mg.vsize = NULL;
		Mg.adjwgt = NULL;
		Mg.nparts = NULL;
		Mg.tpwgts = NULL;
		Mg.ubvec = NULL;
		Mg.options = NULL;
		Mg.objval = NULL;
		Mg.part = NULL;
		Mg.edgecut = NULL;
		Mg.itr = NULL;
		Mg.numflag = NULL;
		Mg.wgtflag = NULL;
Pietro Incardona's avatar
Pietro Incardona committed
237 238 239
		first.id = 0;
		last.id = 0;
		nvertex = 0;
tonynsyde's avatar
tonynsyde committed
240 241 242 243 244 245 246 247 248
	}

	/*! \brief destructor
	 *
	 * Destructor, It destroy all the memory allocated
	 *
	 */
	~Parmetis()
	{
incardon's avatar
incardon committed
249 250 251 252 253 254 255 256 257 258
#ifdef SE_CLASS1

		if (sizeof(idx_t) != 8)
		{
			std::cerr << __FILE__ << ":" << __LINE__ << " Error detected invalid installation of Parmetis. OpenFPM support Parmetis/Metis version with 64 bit idx_t" << std::endl;
			ACTION_ON_ERROR(PARMETIS_ERROR_OBJECT);
		}

#endif

tonynsyde's avatar
tonynsyde committed
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 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328
		// 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;
		}
329

330
		if (is_openfpm_init() == true)
incardon's avatar
incardon committed
331
		{MPI_Comm_free(&comm);}
tonynsyde's avatar
tonynsyde committed
332 333 334 335
	}

	/*! \brief Set the Sub-graph
	 *
336
	 * \param g Global graph to set
incardon's avatar
incardon committed
337 338 339
	 * \param vtxdist indicate how the vertex of the graph are distrubuted across
	 *        processors.
	 * \param m2g map the local ids of the vertex into global-ids
340
	 * \param w true if vertices have weights
tonynsyde's avatar
tonynsyde committed
341
	 */
incardon's avatar
incardon committed
342 343 344 345
	void initSubGraph(Graph & g,
			          const openfpm::vector<rid> & vtxdist,
					  const std::unordered_map<rid, gid> & m2g,
					  bool w)
tonynsyde's avatar
tonynsyde committed
346 347 348
	{
		p_id = v_cl.getProcessUnitID();

349
		first = vtxdist.get(p_id);
350
		last = vtxdist.get(p_id + 1) - 1;
351
		nvertex = last.id - first.id + 1;
352

Pietro Incardona's avatar
Pietro Incardona committed
353
		setDefaultParameters(w);
tonynsyde's avatar
tonynsyde committed
354 355

		// construct the adjacency list
356
		constructAdjList(g, m2g);
357 358

		//reset(g, vtxdist, m2g, w);
tonynsyde's avatar
tonynsyde committed
359 360 361 362 363 364 365
	}

	/*! \brief Decompose the graph
	 *
	 * \tparam i which property store the decomposition
	 *
	 */
366
	void decompose(const openfpm::vector<rid> & vtxdist)
tonynsyde's avatar
tonynsyde committed
367 368
	{
		// Decompose
369

370
		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);
incardon's avatar
incardon committed
371 372

		n_dec++;
tonynsyde's avatar
tonynsyde committed
373 374 375 376 377 378 379
	}

	/*! \brief Refine the graph
	 *
	 * \tparam i which property store the refined decomposition
	 *
	 */
380
	void refine(openfpm::vector<rid> & vtxdist)
tonynsyde's avatar
tonynsyde committed
381 382 383
	{
		// Refine

384
		ParMETIS_V3_RefineKway((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);
incardon's avatar
incardon committed
385 386 387 388 389 390 391 392 393 394 395 396 397 398

		n_dec++;
	}

	/*! \brief Redecompose the graph
	 *
	 * \tparam i which property
	 *
	 */
	void redecompose(openfpm::vector<rid> & vtxdist)
	{
		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);

		n_dec++;
tonynsyde's avatar
tonynsyde committed
399 400 401 402 403 404 405 406 407 408 409
	}

	/*! \brief Get graph partition vector
	 *
	 */
	idx_t* getPartition()
	{
		return Mg.part;
	}

	/*! \brief Reset graph and reconstruct it
410
	 *
411 412 413 414
	 * \param g Global graph
	 * \param vtxdist Distribution vector
	 * \param m2g Mapped id to global id map
	 * \param vgw Using weights on vertices
tonynsyde's avatar
tonynsyde committed
415
	 */
416
	void reset(Graph & g, const openfpm::vector<rid> & vtxdist, const std::unordered_map<rid, gid> & m2g, bool vgw)
tonynsyde's avatar
tonynsyde committed
417
	{
418
		first = vtxdist.get(p_id);
419
		last = vtxdist.get(p_id + 1) - 1;
420
		nvertex = last.id - first.id + 1;
421

tonynsyde's avatar
tonynsyde committed
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448
		// 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;
		}

449 450
		setDefaultParameters(vgw);

tonynsyde's avatar
tonynsyde committed
451
		// construct the adjacency list
452
		constructAdjList(g, m2g);
tonynsyde's avatar
tonynsyde committed
453 454
	}

Pietro Incardona's avatar
Pietro Incardona committed
455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490
	/*! \brief Seth the default parameters for parmetis
	 *
	 *
	 */
	void setDefaultParameters(bool w)
	{
		Mg.nvtxs = new idx_t[1];

		// 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;

		// 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;

tonynsyde's avatar
tonynsyde committed
491 492
		Mg.objval = new idx_t[1];

Pietro Incardona's avatar
Pietro Incardona committed
493 494 495 496 497
		//! init tpwgts to have balanced vertices and ubvec

		Mg.tpwgts = new real_t[Mg.nparts[0]];
		Mg.ubvec = new real_t[Mg.nparts[0]];

498
		for (size_t s = 0; s < (size_t) Mg.nparts[0]; s++)
Pietro Incardona's avatar
Pietro Incardona committed
499 500
		{
			Mg.tpwgts[s] = 1.0 / Mg.nparts[0];
incardon's avatar
incardon committed
501
			Mg.ubvec[s] = dist_tol;
Pietro Incardona's avatar
Pietro Incardona committed
502 503 504 505 506 507 508 509 510 511 512 513
		}

		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];

514
		if (w)
Pietro Incardona's avatar
Pietro Incardona committed
515 516 517 518 519
			Mg.wgtflag[0] = 3;
		else
			Mg.wgtflag[0] = 0;
	}

incardon's avatar
incardon committed
520 521
	/*! \brief Copy the object
	 *
522 523 524
	 * \param pm object to copy
	 *
	 * \return itself
incardon's avatar
incardon committed
525 526
	 *
	 */
Pietro Incardona's avatar
Pietro Incardona committed
527 528
	const Parmetis<Graph> & operator=(const Parmetis<Graph> & pm)
	{
incardon's avatar
incardon committed
529
		MPI_Comm_dup(pm.comm, &comm);
Pietro Incardona's avatar
Pietro Incardona committed
530 531 532 533 534 535 536 537
		p_id = pm.p_id;
		nc = pm.nc;

		setDefaultParameters(pm.Mg.wgtflag[0] == 3);

		return *this;
	}

incardon's avatar
incardon committed
538 539
	/*! \brief Copy the object
	 *
540 541 542
	 * \param pm object to copy
	 *
	 * \return itself
incardon's avatar
incardon committed
543 544
	 *
	 */
Pietro Incardona's avatar
Pietro Incardona committed
545 546
	const Parmetis<Graph> & operator=(Parmetis<Graph> && pm)
	{
incardon's avatar
incardon committed
547
		MPI_Comm_dup(pm.comm, &comm);
Pietro Incardona's avatar
Pietro Incardona committed
548 549 550 551 552 553 554 555
		p_id = pm.p_id;
		nc = pm.nc;

		setDefaultParameters(pm.Mg.wgtflag[0] == 3);

		return *this;
	}

incardon's avatar
incardon committed
556 557 558 559 560 561 562 563 564
	/*! \brief Get the decomposition counter
	 *
	 * \return the decomposition counter
	 *
	 */
	size_t get_ndec()
	{
		return n_dec;
	}
565 566 567

	/*! \brief Distribution tolerance
	 *
incardon's avatar
incardon committed
568
	 * \param tol tolerance
569 570
	 *
	 */
incardon's avatar
incardon committed
571
	void setDistTol(real_t tol)
572
	{
incardon's avatar
incardon committed
573
		dist_tol = tol;
574
	}
tonynsyde's avatar
tonynsyde committed
575 576 577
};

#endif