metis_util.hpp 9.13 KB
Newer Older
incardon's avatar
incardon committed
1 2 3 4 5 6 7 8 9 10 11 12
/*
 * metis_util.hpp
 *
 *  Created on: Nov 21, 2014
 *      Author: Pietro Incardona
 */

#ifndef METIS_UTIL_HPP
#define METIS_UTIL_HPP

#include <iostream>
#include "metis.h"
13
#include "SubdomainGraphNodes.hpp"
14
#include "VTKWriter/VTKWriter.hpp"
incardon's avatar
incardon committed
15 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

/*! \brief Metis graph structure
 *
 * Metis graph structure
 *
 */
struct Metis_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;
};

//! 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 Metis
{
incardon's avatar
incardon committed
75
	//! Graph in metis reppresentation
incardon's avatar
incardon committed
76 77
	Metis_graph Mg;

incardon's avatar
incardon committed
78
	//! Original graph
incardon's avatar
incardon committed
79 80
	Graph & g;

81
	//Check if weights are available
incardon's avatar
incardon committed
82 83 84 85
//	bool useWeights = false;

	//! Distribution tolerance
	real_t dist_tol = 1.05;
86

incardon's avatar
incardon committed
87 88 89 90 91 92 93 94 95
	/*! \brief Construct Adjacency list
	 *
	 * \param g Graph
	 *
	 */
	void constructAdjList(Graph & g)
	{
		// create xadj and adjlist

96 97
		// create xadj, adjlist, vwgt, adjwgt and vsize
		Mg.xadj = new idx_t[g.getNVertex() + 1];
incardon's avatar
incardon committed
98 99
		Mg.adjncy = new idx_t[g.getNEdge()];

100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
		//! starting point in the adjacency list
		size_t prev = 0;

		// actual position
		size_t id = 0;

		// for each vertex calculate the position of the starting point in the adjacency list
		for (size_t i = 0; i < g.getNVertex(); i++)
		{
			// Calculate the starting point in the adjacency list
			Mg.xadj[id] = prev;

			// Create the adjacency list
			for (size_t s = 0; s < g.getNChilds(i); s++)
			{
				Mg.adjncy[prev + s] = g.getChild(i, s);
			}

			// update the position for the next vertex
			prev += g.getNChilds(i);

			id++;
		}

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

	/*! \brief Construct Adjacency list
	 *
	 * \param g Graph
	 *
	 */
	void constructAdjListWithWeights(Graph & g)
	{
		// create xadj, adjlist, vwgt, adjwgt and vsize
		Mg.xadj = new idx_t[g.getNVertex() + 1];
		Mg.adjncy = new idx_t[g.getNEdge()];
		Mg.vwgt = new idx_t[g.getNVertex()];
		Mg.adjwgt = new idx_t[g.getNEdge()];
		Mg.vsize = new idx_t[g.getNVertex()];
incardon's avatar
incardon committed
141 142 143 144 145 146 147 148

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

		// actual position
		size_t id = 0;

		// for each vertex calculate the position of the starting point in the adjacency list
149
		for (size_t i = 0; i < g.getNVertex(); i++)
incardon's avatar
incardon committed
150
		{
151 152
			// Add weight to vertex and migration cost
			Mg.vwgt[i] = g.vertex(i).template get<nm_v::computation>();
incardon's avatar
incardon committed
153
			Mg.vwgt[i] = (Mg.vwgt[i] == 0)?1:Mg.vwgt[i];
154
			Mg.vsize[i] = g.vertex(i).template get<nm_v::migration>();
155
			Mg.vsize[i] = (Mg.vsize[i] == 0)?1:Mg.vsize[i];
156

incardon's avatar
incardon committed
157 158 159 160
			// Calculate the starting point in the adjacency list
			Mg.xadj[id] = prev;

			// Create the adjacency list
161 162 163 164
			for (size_t s = 0; s < g.getNChilds(i); s++)
			{
				Mg.adjncy[prev + s] = g.getChild(i, s);

165
				// zero values on Metis are dangerous
tonynsyde's avatar
tonynsyde committed
166
				Mg.adjwgt[prev + s] = g.getChildEdge(i, s).template get<nm_e::communication>();
167
				Mg.adjwgt[prev + s] = (Mg.adjwgt[prev + s] == 0)?1:Mg.adjwgt[prev + s];
168
			}
incardon's avatar
incardon committed
169 170

			// update the position for the next vertex
171
			prev += g.getNChilds(i);
incardon's avatar
incardon committed
172 173 174 175 176 177 178 179 180 181

			id++;
		}

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

public:

182 183 184 185 186 187 188 189 190
	/*! \brief Constructor
	 *
	 * Construct a metis graph from Graph_CSR
	 *
	 * \param g Graph we want to convert to decompose
	 * \param nc number of partitions
	 * \param useWeights tells if weights are used or not
	 *
	 */
incardon's avatar
incardon committed
191 192
	Metis(Graph & g, size_t nc, bool useWeights)
	:g(g)
193
	{
incardon's avatar
incardon committed
194
		initMetisGraph(nc,useWeights);
195 196
	}

incardon's avatar
incardon committed
197 198 199 200 201 202 203 204
	/*! \brief Constructor
	 *
	 * Construct a metis graph from Graph_CSR
	 *
	 * \param g Graph we want to convert to decompose
	 * \param nc number of partitions
	 *
	 */
205 206
	Metis(Graph & g, size_t nc) :
			g(g)
incardon's avatar
incardon committed
207
	{
incardon's avatar
incardon committed
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
		initMetisGraph(nc,false);
	}

	/*! \brief Constructor
	 *
	 * This constructor does not initialize the internal metis graph
	 * you have to use initMetisGraph to initialize
	 *
	 * \param g Graph we want to convert to decompose
	 *
	 */
	Metis(Graph & g)
	:g(g)
	{
		Mg.nvtxs = NULL;
		Mg.ncon = NULL;
		Mg.xadj = NULL;
		Mg.adjncy = NULL;
		Mg.vwgt = NULL;
		Mg.adjwgt = NULL;
		Mg.nparts = NULL;
		Mg.tpwgts = NULL;
		Mg.ubvec = NULL;
		Mg.options = NULL;
		Mg.objval = NULL;
		Mg.part = NULL;
234 235
	}

incardon's avatar
incardon committed
236 237 238 239 240 241 242 243

	/*! \brief Initialize the METIS graph
	 *
	 * \param nc number of partitions
	 * \param useWeights use the weights on the graph
	 *
	 */
	void initMetisGraph(int nc, bool useWeights)
244 245
	{

incardon's avatar
incardon committed
246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267
		// Get the number of vertex

		Mg.nvtxs = new idx_t[1];
		Mg.nvtxs[0] = g.getNVertex();

		// Set the number of constrains

		Mg.ncon = new idx_t[1];
		Mg.ncon[0] = 1;

		// Set to null the weight of the vertex

		Mg.vwgt = NULL;

		// Put the total communication size to NULL

		Mg.vsize = NULL;

		// Set to null the weight of the edge

		Mg.adjwgt = NULL;

268 269 270 271 272 273
		// construct the adjacency list
		if (useWeights)
			constructAdjListWithWeights(g);
		else
			constructAdjList(g);

incardon's avatar
incardon committed
274 275 276 277 278 279 280 281 282
		// Set the total number of partitions

		Mg.nparts = new idx_t[1];
		Mg.nparts[0] = nc;

		// Set to null the desired weight for each partition (one for each constrain)

		Mg.tpwgts = NULL;

283
		//! Set to null the partition load imbalance tolerance
incardon's avatar
incardon committed
284 285 286 287 288 289 290 291 292 293 294 295

		Mg.ubvec = NULL;

		//! Set tp null additional option for the graph partitioning

		Mg.options = NULL;

		//! set the objective value
		Mg.objval = new idx_t[1];

		//! Is an output vector containing the partition for each vertex
		Mg.part = new idx_t[g.getNVertex()];
tonynsyde's avatar
tonynsyde committed
296

297
		for (size_t i = 0; i < g.getNVertex(); i++)
tonynsyde's avatar
tonynsyde committed
298
			Mg.part[i] = 0;
incardon's avatar
incardon committed
299 300 301 302 303 304 305 306 307 308 309 310
	}

	/*! \brief destructor
	 *
	 * Destructor, It destroy all the memory allocated
	 *
	 */
	~Metis()
	{
		// Deallocate the Mg structure
		if (Mg.nvtxs != NULL)
		{
311
			delete[] Mg.nvtxs;
incardon's avatar
incardon committed
312 313 314 315
		}

		if (Mg.ncon != NULL)
		{
316
			delete[] Mg.ncon;
incardon's avatar
incardon committed
317 318 319 320
		}

		if (Mg.xadj != NULL)
		{
321
			delete[] Mg.xadj;
incardon's avatar
incardon committed
322 323 324 325
		}

		if (Mg.adjncy != NULL)
		{
326
			delete[] Mg.adjncy;
incardon's avatar
incardon committed
327 328 329
		}
		if (Mg.vwgt != NULL)
		{
330
			delete[] Mg.vwgt;
incardon's avatar
incardon committed
331 332 333
		}
		if (Mg.adjwgt != NULL)
		{
334
			delete[] Mg.adjwgt;
incardon's avatar
incardon committed
335 336 337
		}
		if (Mg.nparts != NULL)
		{
338
			delete[] Mg.nparts;
incardon's avatar
incardon committed
339 340 341
		}
		if (Mg.tpwgts != NULL)
		{
342
			delete[] Mg.tpwgts;
incardon's avatar
incardon committed
343 344 345
		}
		if (Mg.ubvec != NULL)
		{
346
			delete[] Mg.ubvec;
incardon's avatar
incardon committed
347 348 349
		}
		if (Mg.options != NULL)
		{
350
			delete[] Mg.options;
incardon's avatar
incardon committed
351 352 353
		}
		if (Mg.objval != NULL)
		{
354
			delete[] Mg.objval;
incardon's avatar
incardon committed
355 356 357
		}
		if (Mg.part != NULL)
		{
358
			delete[] Mg.part;
incardon's avatar
incardon committed
359 360 361 362 363 364 365 366 367 368 369 370
		}
	}

	/*! \brief Decompose the graph
	 *
	 * \tparam i which property store the decomposition
	 *
	 */

	template<unsigned int i>
	void decompose()
	{
incardon's avatar
incardon committed
371 372 373
		if (Mg.nparts[0] != 1)
		{
			// Decompose
374
			METIS_PartGraphRecursive(Mg.nvtxs, Mg.ncon, Mg.xadj, Mg.adjncy, Mg.vwgt, Mg.vsize, Mg.adjwgt, Mg.nparts, Mg.tpwgts, Mg.ubvec, Mg.options, Mg.objval, Mg.part);
incardon's avatar
incardon committed
375

incardon's avatar
incardon committed
376
			// vertex id
incardon's avatar
incardon committed
377

incardon's avatar
incardon committed
378
			size_t id = 0;
incardon's avatar
incardon committed
379

incardon's avatar
incardon committed
380
			// For each vertex store the processor that contain the data
incardon's avatar
incardon committed
381

incardon's avatar
incardon committed
382
			auto it = g.getVertexIterator();
incardon's avatar
incardon committed
383

incardon's avatar
incardon committed
384 385 386 387 388 389 390 391 392
			while (it.isNext())
			{
				g.vertex(it).template get<i>() = Mg.part[id];

				++id;
				++it;
			}
		}
		else
incardon's avatar
incardon committed
393
		{
incardon's avatar
incardon committed
394
			// Trivially assign all the domains to the processor 0
incardon's avatar
incardon committed
395

incardon's avatar
incardon committed
396 397 398 399 400 401 402 403
			auto it = g.getVertexIterator();

			while (it.isNext())
			{
				g.vertex(it).template get<i>() = 0;

				++it;
			}
incardon's avatar
incardon committed
404 405 406 407 408 409 410 411 412 413 414 415 416
		}
	}

	/*! \brief Decompose the graph
	 *
	 * \tparam i which property store the decomposition
	 *
	 */

	template<unsigned int i, typename Graph_part>
	void decompose(Graph_part & gp)
	{
		// Decompose
417
		METIS_PartGraphRecursive(Mg.nvtxs, Mg.ncon, Mg.xadj, Mg.adjncy, Mg.vwgt, Mg.vsize, Mg.adjwgt, Mg.nparts, Mg.tpwgts, Mg.ubvec, Mg.options, Mg.objval, Mg.part);
incardon's avatar
incardon committed
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434

		// vertex id

		size_t id = 0;

		// For each vertex store the processor that contain the data

		auto it = gp.getVertexIterator();

		while (it.isNext())
		{
			gp.vertex(it).template get<i>() = Mg.part[id];

			++id;
			++it;
		}
	}
435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459

	/*! \brief It set Metis on test
	 *
	 * \param testing set to true to disable the testing
	 *
	 * At the moment disable the seed randomness to keep the result
	 * reproducible
	 *
	 */
	void onTest(bool testing)
	{
		if (testing == false)
			return;

		if (Mg.options == NULL)
		{
			// allocate
			Mg.options = new idx_t[METIS_NOPTIONS];

			// set default options
			METIS_SetDefaultOptions(Mg.options);
		}

		Mg.options[METIS_OPTION_SEED] = 0;
	}
incardon's avatar
incardon committed
460 461 462 463 464 465 466 467 468 469

	/*! \brief Distribution tolerance
	 *
	 * \param tol tolerance
	 *
	 */
	const void setDistTol(real_t tol)
	{
		dist_tol = tol;
	}
incardon's avatar
incardon committed
470 471 472
};

#endif