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
 
                #ifndef __ARM_ARCH
                // 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);
                #endif
 
#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.

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

void	decompose ()
	Create the decomposition.

void	refine ()
	Refine current decomposition.

void	redecompose ()
	Redecompose current decomposition.

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

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

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

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

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

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

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

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

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

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

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

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

void	destroy_internal_graph ()
	In case we do not do Dynamic load balancing this this data-structure it is safe to eliminate the full internal graph.

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

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

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

void	getSubSubDomainPos (size_t j, Point< dim, T > &p)
	return the the position of the sub-sub-domain

size_t	get_ndec ()
	Get the decomposition counter.

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

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

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

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

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

void	initLocalToGlobalMap ()
	operator to init ids vector

void	postDecomposition ()
	It update the full decomposition.

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, size_t tag, void *ptr)
	Callback of the sendrecv to set the size of the array received.

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< dim >, nm_e >	gp
	Global sub-sub-domain graph.

Parmetis< Graph_CSR< nm_v< dim >, 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

◆ ParMetisDistribution() [1/3]

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 287 of file ParMetisDistribution.hpp.

◆ ParMetisDistribution() [2/3]

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 297 of file ParMetisDistribution.hpp.

◆ ParMetisDistribution() [3/3]

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 308 of file ParMetisDistribution.hpp.

Member Function Documentation

◆ createCartGraph()

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 319 of file ParMetisDistribution.hpp.

◆ decompose()

template<unsigned int dim, typename T >

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

inline

Create the decomposition.

Decompose

Definition at line 378 of file ParMetisDistribution.hpp.

◆ destroy_internal_graph()

template<unsigned int dim, typename T >

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

inline

In case we do not do Dynamic load balancing this this data-structure it is safe to eliminate the full internal graph.

Definition at line 626 of file ParMetisDistribution.hpp.

◆ get_ndec()

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 699 of file ParMetisDistribution.hpp.

◆ getGraph()

template<unsigned int dim, typename T >

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

inline

Get the current graph (main)

Definition at line 370 of file ParMetisDistribution.hpp.

◆ getNOwnerSubSubDomains()

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 587 of file ParMetisDistribution.hpp.

◆ getNSubSubDomainNeighbors()

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 611 of file ParMetisDistribution.hpp.

◆ getNSubSubDomains()

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 577 of file ParMetisDistribution.hpp.

◆ getOwnerSubSubDomain()

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 599 of file ParMetisDistribution.hpp.

◆ getProcessorLoad()

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 523 of file ParMetisDistribution.hpp.

◆ getSubSubDomainComputationCost()

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 509 of file ParMetisDistribution.hpp.

◆ getSubSubDomainPos()

template<unsigned int dim, typename T >

void ParMetisDistribution< dim, T >::getSubSubDomainPos	(	size_t	j,
		Point< dim, T > &	p
	)

inline

return the the position of the sub-sub-domain

Parameters

i	sub-sub-domain id
p	point

Definition at line 688 of file ParMetisDistribution.hpp.

◆ getSubSubDomainPosition()

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 461 of file ParMetisDistribution.hpp.

◆ getUnbalance()

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 432 of file ParMetisDistribution.hpp.

◆ getVertexGlobalId()

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.

◆ initLocalToGlobalMap()

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.

◆ message_receive()

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,
		size_t	tag,
		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.

◆ operator=() [1/2]

template<unsigned int dim, typename T >

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

inline

Definition at line 648 of file ParMetisDistribution.hpp.

◆ operator=() [2/2]

template<unsigned int dim, typename T >

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

inline

Definition at line 665 of file ParMetisDistribution.hpp.

◆ postDecomposition()

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.

◆ redecompose()

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 417 of file ParMetisDistribution.hpp.

◆ refine()

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 400 of file ParMetisDistribution.hpp.

◆ setCommunicationCost()

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 559 of file ParMetisDistribution.hpp.

◆ setComputationCost()

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 481 of file ParMetisDistribution.hpp.

◆ setDistTol()

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 709 of file ParMetisDistribution.hpp.

◆ setMapId()

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.

◆ setMigrationCost()

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 543 of file ParMetisDistribution.hpp.

◆ updateGraphs()

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.

◆ vertexByMapId()

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.

◆ weightsAreUsed()

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 499 of file ParMetisDistribution.hpp.

◆ write()

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 642 of file ParMetisDistribution.hpp.

Field Documentation

◆ domain

template<unsigned int dim, typename T >

Box<dim, T> ParMetisDistribution< dim, T >::domain

private

rectangular domain to decompose

Definition at line 48 of file ParMetisDistribution.hpp.

◆ gp

template<unsigned int dim, typename T >

Graph_CSR<nm_v<dim>, nm_e> ParMetisDistribution< dim, T >::gp

private

Global sub-sub-domain graph.

Definition at line 51 of file ParMetisDistribution.hpp.

◆ gr

template<unsigned int dim, typename T >

grid_sm<dim, void> ParMetisDistribution< dim, T >::gr

private

Structure that store the cartesian grid information.

Definition at line 45 of file ParMetisDistribution.hpp.

◆ is_distributed

template<unsigned int dim, typename T >

bool ParMetisDistribution< dim, T >::is_distributed = false

private

Is distributed.

Definition at line 39 of file ParMetisDistribution.hpp.

◆ m2g

template<unsigned int dim, typename T >

std::unordered_map<rid, gid> ParMetisDistribution< dim, T >::m2g

private

Hashmap to access to the global position given the re-mapped one (needed for access the map)

Definition at line 83 of file ParMetisDistribution.hpp.

◆ parmetis_graph

template<unsigned int dim, typename T >

Parmetis<Graph_CSR<nm_v<dim>, nm_e> > ParMetisDistribution< dim, T >::parmetis_graph

private

Convert the graph to parmetis format.

Definition at line 54 of file ParMetisDistribution.hpp.

◆ partitions

template<unsigned int dim, typename T >

openfpm::vector<openfpm::vector<idx_t> > ParMetisDistribution< dim, T >::partitions

private

partitions

Definition at line 77 of file ParMetisDistribution.hpp.

◆ sub_sub_owner

template<unsigned int dim, typename T >

openfpm::vector<size_t> ParMetisDistribution< dim, T >::sub_sub_owner

private

Id of the sub-sub-domain where we set the costs.

Definition at line 57 of file ParMetisDistribution.hpp.

◆ v_cl

template<unsigned int dim, typename T >

Vcluster& ParMetisDistribution< dim, T >::v_cl

private

Vcluster.

Definition at line 42 of file ParMetisDistribution.hpp.

◆ v_per_proc

template<unsigned int dim, typename T >

openfpm::vector<openfpm::vector<gid> > ParMetisDistribution< dim, T >::v_per_proc

private

Init data structure to keep trace of new vertices distribution in processors (needed to update main graph)

Definition at line 80 of file ParMetisDistribution.hpp.

◆ verticesGotWeights

template<unsigned int dim, typename T >

bool ParMetisDistribution< dim, T >::verticesGotWeights = false

private

Flag to check if weights are used on vertices.

Definition at line 86 of file ParMetisDistribution.hpp.

◆ vtxdist

template<unsigned int dim, typename T >

openfpm::vector<rid> ParMetisDistribution< dim, T >::vtxdist

private

Init vtxdist needed for Parmetis.

Definition at line 74 of file ParMetisDistribution.hpp.

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

src/Decomposition/Distribution/ParMetisDistribution.hpp

Detailed Description

Initialize a Cartesian graph and decompose

Refine the decomposition

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Constructor & Destructor Documentation

◆ ParMetisDistribution() [1/3]

◆ ParMetisDistribution() [2/3]

◆ ParMetisDistribution() [3/3]

Member Function Documentation

◆ createCartGraph()

◆ decompose()

◆ destroy_internal_graph()

◆ get_ndec()

◆ getGraph()

◆ getNOwnerSubSubDomains()

◆ getNSubSubDomainNeighbors()

◆ getNSubSubDomains()

◆ getOwnerSubSubDomain()

◆ getProcessorLoad()

◆ getSubSubDomainComputationCost()

◆ getSubSubDomainPos()

◆ getSubSubDomainPosition()

◆ getUnbalance()

◆ getVertexGlobalId()

◆ initLocalToGlobalMap()

◆ message_receive()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ postDecomposition()

◆ redecompose()

◆ refine()

◆ setCommunicationCost()

◆ setComputationCost()

◆ setDistTol()

◆ setMapId()

◆ setMigrationCost()

◆ updateGraphs()

◆ vertexByMapId()

◆ weightsAreUsed()

◆ write()

Field Documentation

◆ domain

◆ gp

◆ gr

◆ is_distributed

◆ m2g

◆ parmetis_graph

◆ partitions

◆ sub_sub_owner

◆ v_cl

◆ v_per_proc

◆ verticesGotWeights

◆ vtxdist