Nektar::SpatialDomains::MeshPartitionScotch Class Reference

#include <MeshPartitionScotch.h>

Inheritance diagram for Nektar::SpatialDomains::MeshPartitionScotch:

Static Public Member Functions
static MeshPartitionSharedPtr	create (const LibUtilities::SessionReaderSharedPtr session, LibUtilities::CommSharedPtr comm, int meshDim, std::map< int, MeshEntity > element, CompositeDescriptor compMap)
	Creates an instance of this class.

Static Public Attributes
static std::string	className
	Name of class.
static std::string	cmdSwitch

Protected Member Functions
	MeshPartitionScotch (const LibUtilities::SessionReaderSharedPtr session, LibUtilities::CommSharedPtr comm, int meshDim, std::map< int, MeshEntity > element, CompositeDescriptor compMap)
	~MeshPartitionScotch () override=default
void	v_PartitionGraphImpl (int &nVerts, int &nVertConds, Nektar::Array< Nektar::OneD, int > &xadj, Nektar::Array< Nektar::OneD, int > &adjcy, Nektar::Array< Nektar::OneD, int > &vertWgt, Nektar::Array< Nektar::OneD, int > &vertSize, Nektar::Array< Nektar::OneD, int > &edgeWgt, int &nparts, int &volume, Nektar::Array< Nektar::OneD, int > &part) final
Protected Member Functions inherited from Nektar::SpatialDomains::MeshPartition
	MeshPartition (const LibUtilities::SessionReaderSharedPtr session, LibUtilities::CommSharedPtr comm, int meshDim, std::map< int, MeshEntity > element, CompositeDescriptor compMap)
virtual	~MeshPartition ()=default
void	ReadExpansions ()
void	ReadConditions ()
void	WeightElements ()
void	CreateGraph ()
void	PartitionGraph (int nParts, bool overlapping=false)
	Partition the graph.
void	CheckPartitions (int nParts, Array< OneD, int > &pPart)
int	CalculateElementWeight (LibUtilities::ShapeType elmtType, bool bndWeight, int na, int nb, int nc)
int	CalculateEdgeWeight (LibUtilities::ShapeType elmtType, int na, int nb, int nc)

Private Member Functions
void	PartGraphVKway (const SCOTCH_Num *const n, const SCOTCH_Num *const xadj, const SCOTCH_Num *const adjncy, const SCOTCH_Num *const vwgt, const SCOTCH_Num *const vsize, const SCOTCH_Num *const wgtflag, const SCOTCH_Num *const numflag, const SCOTCH_Num *const nparts, SCOTCH_Num *const volume, SCOTCH_Num *const part)
int	PartGraph2 (const SCOTCH_Num *const n, const SCOTCH_Num *const xadj, const SCOTCH_Num *const adjncy, const SCOTCH_Num *const vwgt, const SCOTCH_Num *const adjwgt, const SCOTCH_Num *const numflag, const SCOTCH_Num *const nparts, SCOTCH_Num *const part, SCOTCH_Num flagval, double kbalval)

Friends
class	MemoryManager< MeshPartitionScotch >

Additional Inherited Members
Public Member Functions inherited from Nektar::SpatialDomains::MeshPartition
void	PartitionMesh (int nParts, bool shared=false, bool overlapping=false, int nLocal=0)
void	PrintPartInfo (std::ostream &out)
void	GetElementIDs (const int procid, std::vector< unsigned int > &tmp)
Protected Types inherited from Nektar::SpatialDomains::MeshPartition
typedef std::vector< unsigned int >	MultiWeight
typedef boost::adjacency_list< boost::setS, boost::vecS, boost::undirectedS, GraphVertexProperties, boost::property< boost::edge_index_t, unsigned int, GraphEdgeProperties > >	BoostGraph
typedef boost::graph_traits< BoostGraph >::vertex_descriptor	BoostVertex
typedef boost::graph_traits< BoostGraph >::edge_descriptor	BoostEdge
typedef boost::graph_traits< BoostGraph >::edge_iterator	BoostEdgeIterator
typedef boost::graph_traits< BoostGraph >::vertex_iterator	BoostVertexIterator
typedef boost::graph_traits< BoostGraph >::adjacency_iterator	BoostAdjacencyIterator
typedef std::vector< unsigned int >	NumModes
typedef std::map< std::string, NumModes >	NummodesPerField
Protected Attributes inherited from Nektar::SpatialDomains::MeshPartition
LibUtilities::SessionReaderSharedPtr	m_session
LibUtilities::CommSharedPtr	m_comm
int	m_dim
int	m_numFields
std::map< int, MeshEntity >	m_elements
std::map< int, MeshEntity >	m_ghostElmts
CompositeDescriptor	m_compMap
std::map< int, NummodesPerField >	m_expansions
std::map< int, LibUtilities::ShapeType >	m_shape
std::map< std::string, int >	m_fieldNameToId
std::map< int, MultiWeight >	m_vertWeights
std::map< int, MultiWeight >	m_vertBndWeights
std::map< int, MultiWeight >	m_edgeWeights
BoostGraph	m_graph
std::map< int, std::vector< unsigned int > >	m_localPartition
bool	m_weightingRequired
bool	m_weightBnd
bool	m_weightDofs
bool	m_shared
bool	m_parallel

Detailed Description

Definition at line 49 of file MeshPartitionScotch.h.

Constructor & Destructor Documentation

MeshPartitionScotch()

Nektar::SpatialDomains::MeshPartitionScotch::MeshPartitionScotch ( const LibUtilities::SessionReaderSharedPtr  session, LibUtilities::CommSharedPtr  comm, int  meshDim, std::map< int, MeshEntity >  element, CompositeDescriptor  compMap  )

protected

Definition at line 50 of file MeshPartitionScotch.cpp.

    : MeshPartition(session, comm, meshDim, element, compMap)
{
}

~MeshPartitionScotch()

Nektar::SpatialDomains::MeshPartitionScotch::~MeshPartitionScotch ( )

overrideprotecteddefault

Member Function Documentation

create()

static MeshPartitionSharedPtr Nektar::SpatialDomains::MeshPartitionScotch::create ( const LibUtilities::SessionReaderSharedPtr  session, LibUtilities::CommSharedPtr  comm, int  meshDim, std::map< int, MeshEntity >  element, CompositeDescriptor  compMap  )

inlinestatic

Creates an instance of this class.

Definition at line 55 of file MeshPartitionScotch.h.

    {
        return MemoryManager<MeshPartitionScotch>::AllocateSharedPtr(
            session, comm, meshDim, element, compMap);
    }

References Nektar::MemoryManager< DataType >::AllocateSharedPtr().

PartGraph2()

int Nektar::SpatialDomains::MeshPartitionScotch::PartGraph2 ( const SCOTCH_Num *const  n, const SCOTCH_Num *const  xadj, const SCOTCH_Num *const  adjncy, const SCOTCH_Num *const  vwgt, const SCOTCH_Num *const  adjwgt, const SCOTCH_Num *const  numflag, const SCOTCH_Num *const  nparts, SCOTCH_Num *const  part, SCOTCH_Num  flagval, double  kbalval  )

private

Definition at line 258 of file MeshPartitionScotch.cpp.

{
    // Scotch graph object to interface with libScotch
    SCOTCH_Graph *grafdat = SCOTCH_graphAlloc();
    ASSERTL0(grafdat != nullptr,
             "Failed to allocate Scotch graph for partitioning.");
 
    SCOTCH_Strat stradat;
    SCOTCH_Num baseval;
    SCOTCH_Num vertnbr;
    int o;
 
    ASSERTL0(SCOTCH_graphInit(grafdat) == 0,
             "Failed to initialise Scotch graph for partitioning.");
 
    baseval = *numflag;
    vertnbr = *n;
 
    o = 1; // Assume something will go wrong
    if (SCOTCH_graphBuild(grafdat, baseval, vertnbr, xadj, xadj + 1, vwgt,
                          nullptr, xadj[vertnbr] - baseval, adjncy,
                          adjwgt) == 0)
    {
        SCOTCH_stratInit(&stradat);
        SCOTCH_stratGraphMapBuild(&stradat, flagval, *nparts, kbalval);
#ifdef SCOTCH_DEBUG_ALL
        // TRICK: next instruction called only if graph is consistent
        if (SCOTCH_graphCheck(grafdat) == 0)
#endif /* SCOTCH_DEBUG_ALL */
            o = SCOTCH_graphPart(grafdat, *nparts, &stradat, part);
        SCOTCH_stratExit(&stradat);
    }
    SCOTCH_graphExit(grafdat);
 
    if (o != 0)
    {
        return (1);
    }
 
    if (baseval != 0)
    { // MeTiS part array is based, Scotch is not
        SCOTCH_Num vertnum;
 
        for (vertnum = 0; vertnum < vertnbr; vertnum++)
        {
            part[vertnum] += baseval;
        }
    }
 
    return (0);
}

References ASSERTL0.

Referenced by PartGraphVKway().

PartGraphVKway()

void Nektar::SpatialDomains::MeshPartitionScotch::PartGraphVKway ( const SCOTCH_Num *const  n, const SCOTCH_Num *const  xadj, const SCOTCH_Num *const  adjncy, const SCOTCH_Num *const  vwgt, const SCOTCH_Num *const  vsize, const SCOTCH_Num *const  wgtflag, const SCOTCH_Num *const  numflag, const SCOTCH_Num *const  nparts, SCOTCH_Num *const  volume, SCOTCH_Num *const  part  )

private

Communication volume of current vertex

Definition at line 128 of file MeshPartitionScotch.cpp.

{
    SCOTCH_Num baseval;
    const SCOTCH_Num *vwgt2;
    const SCOTCH_Num *vsize2;
    SCOTCH_Num vsizval; /// Communication volume of current vertex
    SCOTCH_Num vertnbr;
    SCOTCH_Num vertnum;
    SCOTCH_Num edgenum;
    const SCOTCH_Num *edgetax;
    const SCOTCH_Num *parttax;
    SCOTCH_Num *nghbtab;
    SCOTCH_Num commvol;
 
    vsize2  = ((*wgtflag & 1) != 0) ? vsize : nullptr;
    vwgt2   = ((*wgtflag & 2) != 0) ? vwgt : nullptr;
    baseval = *numflag;
    vertnbr = *n;
    edgetax = adjncy - baseval;
 
    // If no communication load   data provided
    if (vsize2 == nullptr)
    {
        if (PartGraph2(n, xadj, adjncy, vwgt2, nullptr, numflag, nparts, part,
                       SCOTCH_STRATQUALITY, 0.01) != 0)
        {
            return;
        }
    }
 
    // Will have to turn communication volumes into edge loads
    else
    {
        const SCOTCH_Num *vsiztax;
        SCOTCH_Num edgenbr;
        SCOTCH_Num *edlotax;
        int o;
 
        edgenbr = xadj[vertnbr] - baseval;
        if ((edlotax = (SCOTCH_Num *)malloc(edgenbr * sizeof(SCOTCH_Num))) ==
            nullptr)
        {
            return;
        }
 
        edlotax -= baseval; // Base access to edlotax
        vsiztax = vsize2 - baseval;
 
        // Un-based scan of vertex array xadj
        for (vertnum = 0, edgenum = baseval; vertnum < vertnbr; vertnum++)
        {
            SCOTCH_Num vsizval; // Communication size of current vertex
            SCOTCH_Num edgennd;
 
            vsizval = vsize2[vertnum];
            // Based traversal of edge array adjncy
            for (edgennd = xadj[vertnum + 1]; edgenum < edgennd; edgenum++)
            {
 
                SCOTCH_Num vertend; // Based end vertex number
 
                vertend          = edgetax[edgenum];
                edlotax[edgenum] = vsizval + vsiztax[vertend];
            }
        }
 
        o = PartGraph2(n, xadj, adjncy, vwgt2, edlotax + baseval, numflag,
                       nparts, part, SCOTCH_STRATQUALITY, 0.01);
 
        free(edlotax + baseval);
 
        if (o != 0)
        {
            return;
        }
    }
 
    if ((nghbtab = (SCOTCH_Num *)malloc(*nparts * sizeof(SCOTCH_Num))) ==
        nullptr)
    {
        return;
    }
 
    memset(nghbtab, ~0, *nparts * sizeof(SCOTCH_Num));
 
    parttax = part - baseval;
    vsizval = 1; // Assume no vertex communication sizes
 
    // Un-based scan of vertex array xadj
    for (vertnum = 0, edgenum = baseval, commvol = 0; vertnum < vertnbr;
         vertnum++)
    {
        SCOTCH_Num partval;
        SCOTCH_Num edgennd;
 
        partval          = part[vertnum];
        nghbtab[partval] = vertnum; // Do not count local neighbors in
                                    // communication volume
        if (vsize2 != nullptr)
        {
            vsizval = vsize2[vertnum];
        }
 
        // Based traversal of edge array adjncy
        for (edgennd = xadj[vertnum + 1]; edgenum < edgennd; edgenum++)
        {
            SCOTCH_Num vertend; // Based end vertex number
            SCOTCH_Num partend;
 
            vertend = edgetax[edgenum];
            partend = parttax[vertend];
 
            // If first neighbor in this part set part as accounted for
            if (nghbtab[partend] != vertnum)
            {
                nghbtab[partend] = vertnum;
                commvol += vsizval;
            }
        }
    }
    *volume = commvol;
 
    free(nghbtab);
}

References PartGraph2().

Referenced by v_PartitionGraphImpl().

v_PartitionGraphImpl()

void Nektar::SpatialDomains::MeshPartitionScotch::v_PartitionGraphImpl ( int &  nVerts, int &  nVertConds, Nektar::Array< Nektar::OneD, int > &  xadj, Nektar::Array< Nektar::OneD, int > &  adjcy, Nektar::Array< Nektar::OneD, int > &  vertWgt, Nektar::Array< Nektar::OneD, int > &  vertSize, Nektar::Array< Nektar::OneD, int > &  edgeWgt, int &  nparts, int &  volume, Nektar::Array< Nektar::OneD, int > &  part  )

finalprotectedvirtual

Implements Nektar::SpatialDomains::MeshPartition.

Definition at line 58 of file MeshPartitionScotch.cpp.

{
 
    // This method seems to fail if we have elements in the graph that
    // are isolated from others can happen when post-processing (i.e. mesh on a
    // surface). So remove these elementsand add in at the end
    std::set<unsigned> isolated;
    for (int i = 0; i < nVerts; ++i)
    {
        if (xadj[i] == xadj[i + 1])
        {
            isolated.insert(i);
        }
    }
 
    if (isolated.size())
    {
        Nektar::Array<Nektar::OneD, int> tmp;
        for (auto i : isolated)
        {
            // contract xadjacent list
            Vmath::Vcopy(nVerts - i, xadj + i + 1, 1, tmp = xadj + i, 1);
            nVerts--;
        }
    }
 
    int wgtflag = 0;
    int *vwgt   = nullptr;
    int *vsize  = nullptr;
    if (vertWgt.size() > 0)
    {
        wgtflag += 1;
        vwgt = &vertWgt[0];
    }
    if (vertSize.size() > 0)
    {
        wgtflag += 2;
        vsize = &vertSize[0];
    }
    int numflag = 0;
 
    PartGraphVKway(&nVerts, &xadj[0], &adjcy[0], vwgt, vsize, &wgtflag,
                   &numflag, &nparts, &volume, &part[0]);
 
    // distribute isolated elements to each partition in order.
    if (isolated.size())
    {
        Nektar::Array<Nektar::OneD, int> tmp;
        unsigned topart = 0;
        for (auto i : isolated)
        {
            // contract xadjacent list
            if (nVerts - i)
            {
                Vmath::Vcopy(nVerts - i, part + i, 1, tmp = part + i + 1, 1);
            }
            part[i] = topart % nparts;
            nVerts++;
            topart++;
        }
    }
}

References PartGraphVKway(), and Vmath::Vcopy().

Friends And Related Symbol Documentation

MemoryManager< MeshPartitionScotch >

friend class MemoryManager< MeshPartitionScotch >

friend

Definition at line 1 of file MeshPartitionScotch.h.

Member Data Documentation

className

std::string Nektar::SpatialDomains::MeshPartitionScotch::className

static

Initial value:

=
    GetMeshPartitionFactory().RegisterCreatorFunction(
        "Scotch", MeshPartitionScotch::create,
        "Partitioning using the Scotch library.")

Name of class.

Definition at line 65 of file MeshPartitionScotch.h.

cmdSwitch

std::string Nektar::SpatialDomains::MeshPartitionScotch::cmdSwitch

static

Initial value:

=
    LibUtilities::SessionReader::RegisterCmdLineFlag(
        "use-scotch", "", "Use Scotch for mesh partitioning.")

Definition at line 66 of file MeshPartitionScotch.h.