Class that distribute sub-sub-domains across processors using ParMetis Library. More...

Detailed Description

template<unsigned int dim, typename T>
class ParMetisDistribution< dim, T >

Class that distribute sub-sub-domains across processors using ParMetis Library.

Given a graph and setting Computational cost, Communication cost (on the edge) and Migration cost or total Communication costs, it produce the optimal balanced distribution

In addition to Metis it provide the functionality to refine the previously computed decomposition

Initialize a Cartesian graph and decompose

    ParMetisDistribution<3, float> pmet_dist(v_cl);
    // Physical domain
    Box<3, float> box( { 0.0, 0.0, 0.0 }, { 10.0, 10.0, 10.0 });
    // Grid info
    grid_sm<3, void> info( { GS_SIZE, GS_SIZE, GS_SIZE });
    // Initialize Cart graph and decompose
    pmet_dist.createCartGraph(info,box);
    // First create the center of the weights distribution, check it is coherent to the size of the domain
    Point<3, float> center( { 2.0, 2.0, 2.0 });
    // It produces a sphere of radius 2.0
    // with high computation cost (5) inside the sphere and (1) outside
    setSphereComputationCosts(pmet_dist, info, center, 2.0f, 5ul, 1ul);
    // first decomposition
    pmet_dist.decompose();
    BOOST_REQUIRE_EQUAL(pmet_dist.get_ndec(),1ul);

Refine the decomposition

    float stime = 0.0, etime = 10.0, tstep = 0.1;
    // Shift of the sphere at each iteration
    Point<3, float> shift( { tstep, tstep, tstep });
    size_t iter = 1;
    size_t n_dec = 1;
    for(float t = stime; t < etime; t = t + tstep, iter++)
    {
        if(t < etime/2)
        center += shift;
        else
        center -= shift;
        setSphereComputationCosts(pmet_dist, info, center, 2.0f, 5, 1);
        // With some regularity refine and write the parmetis distribution
        if ((size_t)iter % 10 == 0)
        {
            pmet_dist.refine();
            n_dec++;
            BOOST_REQUIRE_EQUAL(pmet_dist.get_ndec(),n_dec);
            if (v_cl.getProcessUnitID() == 0)
            {
                std::stringstream str;
                str << "vtk_parmetis_distribution_" << iter;
                pmet_dist.write(str.str());
#ifdef HAVE_OSX
                // Check
                bool test = compare(std::to_string(v_cl.getProcessUnitID()) + "_" + str.str() + ".vtk", "src/Decomposition/Distribution/test_data/" + std::to_string(v_cl.getProcessUnitID()) + "_" + str.str() + "_osx_test.vtk");
                BOOST_REQUIRE_EQUAL(true,test);
#else
                // Check
                bool test = compare(std::to_string(v_cl.getProcessUnitID()) + "_" + str.str() + ".vtk", "src/Decomposition/Distribution/test_data/" + std::to_string(v_cl.getProcessUnitID()) + "_" + str.str() + "_test.vtk");
                BOOST_REQUIRE_EQUAL(true,test);
#endif
            }
        }
    }

Definition at line 36 of file ParMetisDistribution.hpp.

#include <ParMetisDistribution.hpp>

Public Member Functions
	ParMetisDistribution (Vcluster &v_cl)

	ParMetisDistribution (const ParMetisDistribution< dim, T > &pm)

	ParMetisDistribution (ParMetisDistribution< dim, T > &&pm)

void	createCartGraph (grid_sm< dim, void > &grid, Box< dim, T > dom)
	Create the Cartesian graph. More...

Graph_CSR< nm_v, nm_e > &	getGraph ()
	Get the current graph (main) More...

void	decompose ()
	Create the decomposition. More...

void	refine ()
	Refine current decomposition. More...

void	redecompose ()
	Redecompose current decomposition. More...

float	getUnbalance ()
	Compute the unbalance of the processor compared to the optimal balance. More...

void	getSubSubDomainPosition (size_t id, T(&pos)[dim])
	function that return the position of the vertex in the space More...

void	setComputationCost (size_t id, size_t weight)
	Function that set the weight of the vertex. More...

bool	weightsAreUsed ()
	Checks if weights are used on the vertices. More...

size_t	getSubSubDomainComputationCost (size_t id)
	function that get the weight of the vertex More...

size_t	getProcessorLoad ()
	Compute the processor load counting the total weights of its vertices. More...

void	setMigrationCost (size_t id, size_t migration)
	Set migration cost of the vertex id. More...

void	setCommunicationCost (size_t v_id, size_t e, size_t communication)
	Set communication cost of the edge id. More...

size_t	getNSubSubDomains () const
	Returns total number of sub-sub-domains in the distribution graph. More...

size_t	getNOwnerSubSubDomains () const
	Return the total number of sub-sub-domains this processor own. More...

size_t	getOwnerSubSubDomain (size_t id) const
	Return the global id of the owned sub-sub-domain. More...

size_t	getNSubSubDomainNeighbors (size_t id)
	Returns total number of neighbors of the sub-sub-domain id. More...

void	write (const std::string &file)
	Print the current distribution and save it to VTK file. More...

const ParMetisDistribution < dim, T > &	operator= (const ParMetisDistribution< dim, T > &dist)

const ParMetisDistribution < dim, T > &	operator= (ParMetisDistribution< dim, T > &&dist)

size_t	get_ndec ()
	Get the decomposition counter. More...

void	setDistTol (double tol)
	Set the tolerance for each partition. More...

Private Member Functions
void	updateGraphs ()
	Update main graph ad subgraph with the received data of the partitions from the other processors. More...

auto	vertexByMapId (rid id) -> decltype(gp.vertex(m2g.find(id) ->second.id))
	operator to access the vertex by mapped position More...

void	setMapId (rid n, gid g)
	operator to remap vertex to a new position More...

gid	getVertexGlobalId (rid n)
	Get the global id of the vertex given the re-mapped one. More...

void	initLocalToGlobalMap ()
	operator to init ids vector More...

void	postDecomposition ()
	It update the full decomposition. More...

Static Private Member Functions
static void *	message_receive (size_t msg_i, size_t total_msg, size_t total_p, size_t i, size_t ri, void *ptr)
	Callback of the sendrecv to set the size of the array received. More...

Private Attributes
bool	is_distributed = false
	Is distributed.

Vcluster &	v_cl
	Vcluster.

grid_sm< dim, void >	gr
	Structure that store the cartesian grid information.

Box< dim, T >	domain
	rectangular domain to decompose

Graph_CSR< nm_v, nm_e >	gp
	Global sub-sub-domain graph.

Parmetis< Graph_CSR< nm_v, nm_e > >	parmetis_graph
	Convert the graph to parmetis format.

openfpm::vector< size_t >	sub_sub_owner
	Id of the sub-sub-domain where we set the costs.

openfpm::vector< rid >	vtxdist
	Init vtxdist needed for Parmetis.

openfpm::vector < openfpm::vector< idx_t > >	partitions
	partitions

openfpm::vector < openfpm::vector< gid > >	v_per_proc
	Init data structure to keep trace of new vertices distribution in processors (needed to update main graph)

std::unordered_map< rid, gid >	m2g
	Hashmap to access to the global position given the re-mapped one (needed for access the map)

bool	verticesGotWeights = false
	Flag to check if weights are used on vertices.

Constructor & Destructor Documentation

template<unsigned int dim, typename T>

ParMetisDistribution< dim, T >::ParMetisDistribution ( Vcluster & v_cl )

inline

Constructor for the ParMetis class

Parameters

v_cl	Vcluster to use as communication object in this class

Definition at line 286 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

ParMetisDistribution< dim, T >::ParMetisDistribution ( const ParMetisDistribution< dim, T > & pm )

inline

Copy constructor

Parameters

pm	Distribution to copy

Definition at line 296 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

ParMetisDistribution< dim, T >::ParMetisDistribution ( ParMetisDistribution< dim, T > && pm )

inline

Copy constructor

Parameters

pm	Distribution to copy

Definition at line 307 of file ParMetisDistribution.hpp.

Member Function Documentation

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::createCartGraph	(	grid_sm< dim, void > &	grid,
		Box< dim, T >	dom
	)

inline

Create the Cartesian graph.

Parameters

grid	info
dom	domain

Get the number of processing units

Division of vertices in Np graphs Put (div+1) vertices in mod graphs Put div vertices in the rest of the graphs

Definition at line 318 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::decompose ( )

inline

Create the decomposition.

Decompose

Definition at line 377 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

size_t ParMetisDistribution< dim, T >::get_ndec ( )

inline

Get the decomposition counter.

Returns: the decomposition counter

Definition at line 671 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

Graph_CSR<nm_v, nm_e>& ParMetisDistribution< dim, T >::getGraph ( )

inline

Get the current graph (main)

Definition at line 369 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

size_t ParMetisDistribution< dim, T >::getNOwnerSubSubDomains ( ) const

inline

Return the total number of sub-sub-domains this processor own.

Returns: the total number of sub-sub-domains owned by this processor

Definition at line 586 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

size_t ParMetisDistribution< dim, T >::getNSubSubDomainNeighbors ( size_t id )

inline

Returns total number of neighbors of the sub-sub-domain id.

Parameters

id	id of the sub-sub-domain

Returns: the number of neighborhood sub-sub-domains for each sub-domain

Definition at line 610 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

size_t ParMetisDistribution< dim, T >::getNSubSubDomains ( ) const

inline

Returns total number of sub-sub-domains in the distribution graph.

Returns: the total number of sub-sub-domains

Definition at line 576 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

size_t ParMetisDistribution< dim, T >::getOwnerSubSubDomain ( size_t id ) const

inline

Return the global id of the owned sub-sub-domain.

Parameters

id	in the list of owned sub-sub-domains

Returns: the global id

Definition at line 598 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

size_t ParMetisDistribution< dim, T >::getProcessorLoad ( )

inline

Compute the processor load counting the total weights of its vertices.

Returns: the computational load of the processor graph

Definition at line 522 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

size_t ParMetisDistribution< dim, T >::getSubSubDomainComputationCost ( size_t id )

inline

function that get the weight of the vertex

Parameters

id vertex id

Definition at line 508 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::getSubSubDomainPosition	(	size_t	id,
		T(&)	pos[dim]
	)

inline

function that return the position of the vertex in the space

Parameters

id	vertex id
pos	vector that will contain x, y, z

Definition at line 460 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

float ParMetisDistribution< dim, T >::getUnbalance ( )

inline

Compute the unbalance of the processor compared to the optimal balance.

Returns: the unbalance from the optimal one 0.01 mean 1%

Definition at line 431 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

gid ParMetisDistribution< dim, T >::getVertexGlobalId ( rid n )

inlineprivate

Get the global id of the vertex given the re-mapped one.

Parameters

remapped id

Returns: global id

Definition at line 182 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::initLocalToGlobalMap ( )

inlineprivate

operator to init ids vector

Definition at line 192 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

static void* ParMetisDistribution< dim, T >::message_receive	(	size_t	msg_i,
		size_t	total_msg,
		size_t	total_p,
		size_t	i,
		size_t	ri,
		void *	ptr
	)

inlinestaticprivate

Callback of the sendrecv to set the size of the array received.

Parameters

msg_i	Index of the message
total_msg	Total numeber of messages
total_p	Total number of processors to comunicate with
i	Processor id
ri	Request id
ptr	Void pointer parameter for additional data to pass to the call-back

Definition at line 216 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::postDecomposition ( )

inlineprivate

It update the full decomposition.

Get the processor id

Get the number of processing units

Get result partition for this processors

Prepare vector of arrays to contain all partitions

Definition at line 229 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::redecompose ( )

inline

Redecompose current decomposition.

It makes a redecomposition using Parmetis taking into consideration also migration cost

Definition at line 416 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::refine ( )

inline

Refine current decomposition.

It makes a refinement of the current decomposition using Parmetis function RefineKWay After that it also does the remapping of the graph

Definition at line 399 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::setCommunicationCost	(	size_t	v_id,
		size_t	e,
		size_t	communication
	)

inline

Set communication cost of the edge id.

Parameters

v_id	Id of the source vertex of the edge
e	i child of the vertex
communication	Communication value

Definition at line 558 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::setComputationCost	(	size_t	id,
		size_t	weight
	)

inline

Function that set the weight of the vertex.

Parameters

id	vertex id
weight	to give to the vertex

Definition at line 480 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::setDistTol ( double tol )

inline

Set the tolerance for each partition.

Parameters

tol tolerance

Definition at line 681 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::setMapId	(	rid	n,
		gid	g
	)

inlineprivate

operator to remap vertex to a new position

Parameters

n	re-mapped position
g	global position

Definition at line 171 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::setMigrationCost	(	size_t	id,
		size_t	migration
	)

inline

Set migration cost of the vertex id.

Parameters

id	of the vertex to update
migration	cost of the migration

Definition at line 542 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::updateGraphs ( )

inlineprivate

Update main graph ad subgraph with the received data of the partitions from the other processors.

Definition at line 91 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

auto ParMetisDistribution< dim, T >::vertexByMapId ( rid id ) -> decltype( gp.vertex(m2g.find(id)->second.id) )

inlineprivate

operator to access the vertex by mapped position

operator to access the vertex

Parameters

id	re-mapped id of the vertex to access

Definition at line 160 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

bool ParMetisDistribution< dim, T >::weightsAreUsed ( )

inline

Checks if weights are used on the vertices.

Returns: true if weights are used in the decomposition

Definition at line 498 of file ParMetisDistribution.hpp.

template<unsigned int dim, typename T>

void ParMetisDistribution< dim, T >::write ( const std::string & file )

inline

Print the current distribution and save it to VTK file.

Parameters

file filename

Definition at line 625 of file ParMetisDistribution.hpp.

The documentation for this class was generated from the following file:

src/Decomposition/Distribution/ParMetisDistribution.hpp

Detailed Description

template<unsigned int dim, typename T> class ParMetisDistribution< dim, T >

Initialize a Cartesian graph and decompose

Refine the decomposition

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

template<unsigned int dim, typename T>
class ParMetisDistribution< dim, T >