// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- // vi: set et ts=4 sw=2 sts=2: #ifndef DUNE_ISTL_REPARTITION_HH #define DUNE_ISTL_REPARTITION_HH #include #include #include #include #if HAVE_PARMETIS // Explicitly use C linkage as scotch does not extern "C" in its headers. // Works because ParMETIS/METIS checks whether compiler is C++ and otherwise // does not use extern "C". Therefore no nested extern "C" will be created. extern "C" { #include } #endif #include #include #include #include #include #include #include #include #include #include #include /** * @file * @brief Functionality for redistributing a parallel index set using graph partitioning. * * Refactored version of an intern. * @author Markus Blatt */ namespace Dune { namespace Metis { // Explicitly specify a real_t and idx_t for older (Par)METIS versions that do not // provide these typedefs #if HAVE_PARMETIS && defined(REALTYPEWIDTH) using real_t = ::real_t; #else using real_t = float; #endif #if HAVE_PARMETIS && defined(IDXTYPEWIDTH) using idx_t = ::idx_t; #elif HAVE_PARMETIS && defined(HAVE_SCOTCH_NUM_TYPE) using idx_t = SCOTCH_Num; #elif HAVE_PARMETIS using idx_t = int; #else using idx_t = std::size_t; #endif } #if HAVE_MPI /** * @brief Fills the holes in an index set. * * In general the index set only needs to know those indices * where communication my occur. In usual FE computations these * are just those near the processor boundaries. * * For the repartitioning we need to know all all indices for which data is stored. * The missing indices will be created in this method. * * @param graph The graph to reparition. * @param oocomm The communication information. */ template void fillIndexSetHoles(const G& graph, Dune::OwnerOverlapCopyCommunication& oocomm) { typedef typename Dune::OwnerOverlapCopyCommunication::ParallelIndexSet IndexSet; typedef typename IndexSet::LocalIndex::Attribute Attribute; IndexSet& indexSet = oocomm.indexSet(); const typename Dune::OwnerOverlapCopyCommunication::GlobalLookupIndexSet& lookup =oocomm.globalLookup(); std::size_t sum=0, needed = graph.noVertices()-indexSet.size(); std::vector neededall(oocomm.communicator().size(), 0); MPI_Allgather(&needed, 1, MPITraits::getType() , &(neededall[0]), 1, MPITraits::getType(), oocomm.communicator()); for(int i=0; iglobal()); //Process p creates global indices consecutively //starting atmaxgi+\sum_{i=1}^p neededall[i] // All created indices are owned by the process maxgi=oocomm.communicator().max(maxgi); ++maxgi; // Start with the next free index. for(int i=0; i > > globalIndices; storeGlobalIndicesOfRemoteIndices(globalIndices, oocomm.remoteIndices()); indexSet.beginResize(); for(auto vertex = graph.begin(), vend=graph.end(); vertex != vend; ++vertex) { const typename IndexSet::IndexPair* pair=lookup.pair(*vertex); if(pair==0) { // No index yet, add new one indexSet.add(maxgi, typename IndexSet::LocalIndex(*vertex, OwnerOverlapCopyAttributeSet::owner, false)); ++maxgi; } } indexSet.endResize(); repairLocalIndexPointers(globalIndices, oocomm.remoteIndices(), indexSet); oocomm.freeGlobalLookup(); oocomm.buildGlobalLookup(); #ifdef DEBUG_REPART std::cout<<"Holes are filled!"< ParmetisDuneIndexMap(const Graph& graph, const OOComm& com); int toParmetis(int i) const { return duneToParmetis[i]; } int toLocalParmetis(int i) const { return duneToParmetis[i]-base_; } int operator[](int i) const { return duneToParmetis[i]; } int toDune(int i) const { return parmetisToDune[i]; } std::vector::size_type numOfOwnVtx() const { return parmetisToDune.size(); } Metis::idx_t* vtxDist() { return &vtxDist_[0]; } int globalOwnerVertices; private: int base_; std::vector duneToParmetis; std::vector parmetisToDune; // range of vertices for processor i: vtxdist[i] to vtxdist[i+1] (parmetis global) std::vector vtxDist_; }; template ParmetisDuneIndexMap::ParmetisDuneIndexMap(const G& graph, const OOComm& oocomm) : duneToParmetis(graph.noVertices(), -1), vtxDist_(oocomm.communicator().size()+1) { int npes=oocomm.communicator().size(), mype=oocomm.communicator().rank(); typedef typename OOComm::OwnerSet OwnerSet; int numOfOwnVtx=0; auto end = oocomm.indexSet().end(); for(auto index = oocomm.indexSet().begin(); index != end; ++index) { if (OwnerSet::contains(index->local().attribute())) { numOfOwnVtx++; } } parmetisToDune.resize(numOfOwnVtx); std::vector globalNumOfVtx(npes); // make this number available to all processes MPI_Allgather(&numOfOwnVtx, 1, MPI_INT, &(globalNumOfVtx[0]), 1, MPI_INT, oocomm.communicator()); int base=0; vtxDist_[0] = 0; for(int i=0; ilocal().attribute())) { // assign and count the index parmetisToDune[base-base_]=index->local(); duneToParmetis[index->local()] = base++; } } // At this point, every process knows the ParMETIS global index // of it's owner vertices. The next step is to get the // ParMETIS global index of the overlap vertices from the // associated processes. To do this, the Dune::Interface class // is used. #ifdef DEBUG_REPART std::cout < void buildSendInterface(const std::vector& toPart, const IS& idxset) { std::map sizes; for(auto i=idxset.begin(), end=idxset.end(); i!=end; ++i) if(Flags::contains(i->local().attribute())) ++sizes[toPart[i->local()]]; // Allocate the necessary space for(auto i=sizes.begin(), end=sizes.end(); i!=end; ++i) interfaces()[i->first].first.reserve(i->second); //Insert the interface information for(auto i=idxset.begin(), end=idxset.end(); i!=end; ++i) if(Flags::contains(i->local().attribute())) interfaces()[toPart[i->local()]].first.add(i->local()); } void reserveSpaceForReceiveInterface(int proc, int size) { interfaces()[proc].second.reserve(size); } void addReceiveIndex(int proc, std::size_t idx) { interfaces()[proc].second.add(idx); } template void buildReceiveInterface(std::vector >& indices) { std::size_t i=0; for(auto idx=indices.begin(); idx!= indices.end(); ++idx) { interfaces()[idx->second].second.add(i++); } } }; namespace { /** * @brief Fills send buffer with global indices. * * @param ownerVec the owner vertices to send * @param overlapSet the overlap vertices to send * @param sendBuf the send buffer * @param buffersize The size of the send buffer * @param comm Communicator for the send. */ template void createSendBuf(std::vector& ownerVec, std::set& overlapVec, std::set& neighbors, char *sendBuf, int buffersize, MPI_Comm comm) { // Pack owner vertices std::size_t s=ownerVec.size(); int pos=0; if(s==0) ownerVec.resize(1); // otherwise would read beyond the memory bound MPI_Pack(&s, 1, MPITraits::getType(), sendBuf, buffersize, &pos, comm); MPI_Pack(&(ownerVec[0]), s, MPITraits::getType(), sendBuf, buffersize, &pos, comm); s = overlapVec.size(); MPI_Pack(&s, 1, MPITraits::getType(), sendBuf, buffersize, &pos, comm); for(auto i=overlapVec.begin(), end= overlapVec.end(); i != end; ++i) MPI_Pack(const_cast(&(*i)), 1, MPITraits::getType(), sendBuf, buffersize, &pos, comm); s=neighbors.size(); MPI_Pack(&s, 1, MPITraits::getType(), sendBuf, buffersize, &pos, comm); for(auto i=neighbors.begin(), end= neighbors.end(); i != end; ++i) MPI_Pack(const_cast(&(*i)), 1, MPI_INT, sendBuf, buffersize, &pos, comm); } /** * @brief save the values of the received MPI buffer to the owner/overlap vectors * * @param recvBuf the receive buffer. * @param ownerVec the vector to store the owner indices in. * @param overlapVec the set to store the overlap indices in. * @param comm The communicator used in the receive. */ template void saveRecvBuf(char *recvBuf, int bufferSize, std::vector >& ownerVec, std::set& overlapVec, std::set& neighbors, RedistributeInterface& inf, int from, MPI_Comm comm) { std::size_t size; int pos=0; // unpack owner vertices MPI_Unpack(recvBuf, bufferSize, &pos, &size, 1, MPITraits::getType(), comm); inf.reserveSpaceForReceiveInterface(from, size); ownerVec.reserve(ownerVec.size()+size); for(; size!=0; --size) { GI gi; MPI_Unpack(recvBuf, bufferSize, &pos, &gi, 1, MPITraits::getType(), comm); ownerVec.push_back(std::make_pair(gi,from)); } // unpack overlap vertices MPI_Unpack(recvBuf, bufferSize, &pos, &size, 1, MPITraits::getType(), comm); typename std::set::iterator ipos = overlapVec.begin(); Dune::dverb << "unpacking "<::getType(), comm); ipos=overlapVec.insert(ipos, gi); } //unpack neighbors MPI_Unpack(recvBuf, bufferSize, &pos, &size, 1, MPITraits::getType(), comm); Dune::dverb << "unpacking "<::iterator npos = neighbors.begin(); for(; size!=0; --size) { int n; MPI_Unpack(recvBuf, bufferSize, &pos, &n, 1, MPI_INT, comm); npos=neighbors.insert(npos, n); } } /** * @brief Find the optimal domain number for a given process * * The estimation is necessary because the result of ParMETIS for * the new partition is only a domain/set number and not a process number. * * @param comm the MPI communicator * @param *part the result array of the ParMETIS repartition * @param numOfOwnVtx the number of owner vertices * @param nparts the number of target partitions/processes * @param *myDomain the optimal output domain number * @param domainMapping[] the array of output domain mapping */ template void getDomain(const MPI_Comm& comm, T *part, int numOfOwnVtx, int nparts, int *myDomain, std::vector &domainMapping) { int npes, mype; MPI_Comm_size(comm, &npes); MPI_Comm_rank(comm, &mype); MPI_Status status; *myDomain = -1; std::vector domain(nparts, 0); std::vector assigned(npes, 0); // init domain Mapping domainMapping.assign(domainMapping.size(), -1); // count the occurrence of domains for (int i = 0; i < numOfOwnVtx; i++) { domain[part[i]]++; } std::vector domainMatrix(npes * nparts, -1); // init buffer with the own domain int *buf = new int[nparts]; for (int i = 0; i < nparts; i++) { buf[i] = domain[i]; domainMatrix[mype*nparts+i] = domain[i]; } int pe=0; int src = (mype-1+npes)%npes; int dest = (mype+1)%npes; // ring communication, we need n-1 communications for n processors for (int i = 0; i < npes-1; i++) { MPI_Sendrecv_replace(buf, nparts, MPI_INT, dest, 0, src, 0, comm, &status); // pe is the process of the actual received buffer pe = ((mype-1-i)+npes)%npes; for(int j = 0; j < nparts; j++) { // save the values to the domain matrix domainMatrix[pe*nparts+j] = buf[j]; } } delete[] buf; // Start the domain calculation. // The process which contains the maximum number of vertices of a // particular domain is selected to choose it's favorate domain int maxOccurance = 0; pe = -1; std::set unassigned; for (int i = 0; i < nparts; i++) { for (int j = 0; j < npes; j++) { // process has no domain assigned if (assigned[j]==0) { if (maxOccurance < domainMatrix[j*nparts+i]) { maxOccurance = domainMatrix[j*nparts+i]; pe = j; } } } if (pe!=-1) { // process got a domain, ... domainMapping[i] = pe; // ...mark as assigned assigned[pe] = 1; if (pe==mype) { *myDomain = i; } pe = -1; } else { unassigned.insert(i); } maxOccurance = 0; } typename std::vector::iterator next_free = assigned.begin(); for(auto udomain = unassigned.begin(), end = unassigned.end(); udomain != end; ++udomain) { next_free = std::find_if(next_free, assigned.end(), std::bind(std::less(), std::placeholders::_1, 1)); assert(next_free != assigned.end()); domainMapping[*udomain] = next_free-assigned.begin(); *next_free = 1; } } struct SortFirst { template bool operator()(const T& t1, const T& t2) const { return t1 void mergeVec(std::vector >& ownerVec, std::set& overlapSet) { #ifdef DEBUG_REPART // Safety check for duplicates. if(ownerVec.size()>0) { auto old=ownerVec.begin(); for(auto i=old+1, end=ownerVec.end(); i != end; old=i++) { if(i->first==old->first) { std::cerr<<"Value at index "<first<<","<second<<"]==[" <first<<","<second<<"]"<first<*s) ++v; if(v!=vend && v->first==*s) { // Move to the next element before erasing // thus s stays valid! auto tmp=s; ++s; overlapSet.erase(tmp); }else ++s; } } /** * @brief get the non-owner neighbors of a given vertex * * For a given vertex, get the index of all non-owner neighbor vertices are * computed. * * @param g the local graph * @param part Where the vertices become owner * @param vtx the given vertex * @param parmetisVtxMapping mapping between Dune and ParMETIS vertices * @param indexSet the indexSet * @param neighbor the output set to store the neighbor indices in. */ template void getNeighbor(const Graph& g, std::vector& part, typename Graph::VertexDescriptor vtx, const IS& indexSet, int toPe, std::set& neighbor, std::set& neighborProcs) { for(auto edge=g.beginEdges(vtx), end=g.endEdges(vtx); edge!=end; ++edge) { const typename IS::IndexPair* pindex = indexSet.pair(edge.target()); assert(pindex); if(part[pindex->local()]!=toPe || !OwnerSet::contains(pindex->local().attribute())) { // is sent to another process and therefore becomes overlap neighbor.insert(pindex->global()); neighborProcs.insert(part[pindex->local()]); } } } template void my_push_back(std::vector& ownerVec, const I& index, [[maybe_unused]] int proc) { ownerVec.push_back(index); } template void my_push_back(std::vector >& ownerVec, const I& index, int proc) { ownerVec.push_back(std::make_pair(index,proc)); } template void reserve(std::vector&, RedistributeInterface&, int) {} template void reserve(std::vector >& ownerVec, RedistributeInterface& redist, int proc) { redist.reserveSpaceForReceiveInterface(proc, ownerVec.size()); } /** * @brief get the owner- and overlap vertices for giving source and destination processes. * * The estimation is based on the vtxdist and the global PARMETIS mapping * generated before. The owner- and overlap vertices are stored in two * separate vectors * * @param graph The local graph. * @param part The target domain of the local vertices (result of PARMETIS). * @param indexSet The indexSet of the given graph. * @param parmetisVtxMapping The mapping between PARMETIS index * and DUNE global index. * @param myPe The source process number. * @param toPe The target process number. * @param ownerVec The output vector containing all owner vertices. * @param overlapSet The output vector containing all overlap vertices. */ template void getOwnerOverlapVec(const G& graph, std::vector& part, IS& indexSet, [[maybe_unused]] int myPe, int toPe, std::vector& ownerVec, std::set& overlapSet, RedistributeInterface& redist, std::set& neighborProcs) { for(auto index = indexSet.begin(); index != indexSet.end(); ++index) { // Only Process owner vertices, the others are not in the parmetis graph. if(OwnerSet::contains(index->local().attribute())) { if(part[index->local()]==toPe) { getNeighbor(graph, part, index->local(), indexSet, toPe, overlapSet, neighborProcs); my_push_back(ownerVec, index->global(), toPe); } } } reserve(ownerVec, redist, toPe); } /** * @brief check if the given vertex is a owner vertex * * @param indexSet the indexSet * @param index the given vertex index */ template inline bool isOwner(IS& indexSet, int index) { const typename IS::IndexPair* pindex=indexSet.pair(index); assert(pindex); return F::contains(pindex->local().attribute()); } class BaseEdgeFunctor { public: BaseEdgeFunctor(Metis::idx_t* adj,const ParmetisDuneIndexMap& data) : i_(), adj_(adj), data_(data) {} template void operator()(const T& edge) { // Get the edge weight // const Weight& weight=edge.weight(); adj_[i_] = data_.toParmetis(edge.target()); i_++; } std::size_t index() { return i_; } private: std::size_t i_; Metis::idx_t* adj_; const ParmetisDuneIndexMap& data_; }; template struct EdgeFunctor : public BaseEdgeFunctor { EdgeFunctor(Metis::idx_t* adj, const ParmetisDuneIndexMap& data, std::size_t) : BaseEdgeFunctor(adj, data) {} Metis::idx_t* getWeights() { return NULL; } void free(){} }; template class EdgeFunctor > : public BaseEdgeFunctor { public: EdgeFunctor(Metis::idx_t* adj, const ParmetisDuneIndexMap& data, std::size_t s) : BaseEdgeFunctor(adj, data) { weight_=new Metis::idx_t[s]; } template void operator()(const T& edge) { weight_[index()]=edge.properties().depends() ? 3 : 1; BaseEdgeFunctor::operator()(edge); } Metis::idx_t* getWeights() { return weight_; } void free(){ delete[] weight_; weight_ = nullptr; } private: Metis::idx_t* weight_; }; /** * @brief Create the "adjncy" and "xadj" arrays for using ParMETIS * * This function builds the ParMETIS "adjncy" and "xadj" array according * to the ParMETIS documentation. These arrays are generated by * traversing the graph object. The assigned index to the * "adjncy" array is the ParMETIS global index calculated before. * * @param graph the local graph. * @param indexSet the local indexSet. * @param &xadj the ParMETIS xadj array * @param ew Funcot to setup adjacency info. */ template void getAdjArrays(G& graph, IS& indexSet, Metis::idx_t *xadj, EW& ew) { int j=0; auto vend = graph.end(); for(auto vertex = graph.begin(); vertex != vend; ++vertex) { if (isOwner(indexSet,*vertex)) { // The type of const edge iterator. auto eend = vertex.end(); xadj[j] = ew.index(); j++; for(auto edge = vertex.begin(); edge != eend; ++edge) { ew(edge); } } } xadj[j] = ew.index(); } } // end anonymous namespace template bool buildCommunication(const G& graph, std::vector& realparts, Dune::OwnerOverlapCopyCommunication& oocomm, std::shared_ptr>& outcomm, RedistributeInterface& redistInf, bool verbose=false); #if HAVE_PARMETIS #ifndef METIS_VER_MAJOR extern "C" { // backwards compatibility to parmetis < 4.0.0 void METIS_PartGraphKway(int *nvtxs, Metis::idx_t *xadj, Metis::idx_t *adjncy, Metis::idx_t *vwgt, Metis::idx_t *adjwgt, int *wgtflag, int *numflag, int *nparts, int *options, int *edgecut, Metis::idx_t *part); void METIS_PartGraphRecursive(int *nvtxs, Metis::idx_t *xadj, Metis::idx_t *adjncy, Metis::idx_t *vwgt, Metis::idx_t *adjwgt, int *wgtflag, int *numflag, int *nparts, int *options, int *edgecut, Metis::idx_t *part); } #endif #endif // HAVE_PARMETIS template inline void print_carray(S& os, T* array, std::size_t l) { for(T *cur=array, *end=array+l; cur!=end; ++cur) os<<*cur<<" "; } template inline bool isValidGraph(std::size_t noVtx, std::size_t gnoVtx, S noEdges, T* xadj, T* adjncy, bool checkSymmetry) { bool correct=true; using std::signbit; for(Metis::idx_t vtx=0; vtx<(Metis::idx_t)noVtx; ++vtx) { if(static_cast(xadj[vtx])>noEdges || signbit(xadj[vtx])) { std::cerr <<"Check graph: xadj["<" <(xadj[vtx+1])>noEdges || signbit(xadj[vtx+1])) { std::cerr <<"Check graph: xadj["<" <gnoVtx) { std::cerr<<" Edge "< bool commGraphRepartition(const M& mat, Dune::OwnerOverlapCopyCommunication& oocomm, Metis::idx_t nparts, std::shared_ptr>& outcomm, RedistributeInterface& redistInf, bool verbose=false) { if(verbose && oocomm.communicator().rank()==0) std::cout<<"Repartitioning from "<1) { part[0]=rank; { // sublock for automatic memory deletion // Build the graph of the communication scheme and create an appropriate indexset. // calculate the neighbour vertices int noNeighbours = oocomm.remoteIndices().neighbours(); for(auto n= oocomm.remoteIndices().begin(); n != oocomm.remoteIndices().end(); ++n) if(n->first==rank) { //do not include ourselves. --noNeighbours; break; } // A parmetis graph representing the communication graph. // The diagonal entries are the number of nodes on the process. // The offdiagonal entries are the number of edges leading to other processes. Metis::idx_t *xadj=new Metis::idx_t[2]; Metis::idx_t *vtxdist=new Metis::idx_t[oocomm.communicator().size()+1]; Metis::idx_t *adjncy=new Metis::idx_t[noNeighbours]; #ifdef USE_WEIGHTS Metis::idx_t *vwgt = 0; Metis::idx_t *adjwgt = 0; #endif // each process has exactly one vertex! for(int i=0; i owner(mat.N(), oocomm.communicator().rank()); // for(NeighbourIterator n= oocomm.remoteIndices().begin(); n != oocomm.remoteIndices().end(); // ++n) // { // if(n->first!=oocomm.communicator().rank()){ // typedef typename RemoteIndices::RemoteIndexList RIList; // const RIList& rlist = *(n->second.first); // typedef typename RIList::const_iterator LIter; // for(LIter entry=rlist.begin(); entry!=rlist.end(); ++entry){ // if(entry->attribute()==OwnerOverlapCopyAttributeSet::owner) // owner[entry->localIndexPair().local()] = n->first; // } // } // } // std::map edgecount; // edges to other processors // typedef typename M::ConstRowIterator RIter; // typedef typename M::ConstColIterator CIter; // // calculate edge count // for(RIter row=mat.begin(), endr=mat.end(); row != endr; ++row) // if(owner[row.index()]==OwnerOverlapCopyAttributeSet::owner) // for(CIter entry= row->begin(), end = row->end(); entry != end; ++entry) // ++edgecount[owner[entry.index()]]; // setup edge and weight pattern Metis::idx_t* adjp=adjncy; #ifdef USE_WEIGHTS vwgt = new Metis::idx_t[1]; vwgt[0]= mat.N(); // weight is number of rows TODO: Should actually be the nonzeros. adjwgt = new Metis::idx_t[noNeighbours]; Metis::idx_t* adjwp=adjwgt; #endif for(auto n= oocomm.remoteIndices().begin(); n != oocomm.remoteIndices().end(); ++n) if(n->first != rank) { *adjp=n->first; ++adjp; #ifdef USE_WEIGHTS *adjwp=1; //edgecount[n->first]; ++adjwp; #endif } assert(isValidGraph(vtxdist[rank+1]-vtxdist[rank], vtxdist[oocomm.communicator().size()], noNeighbours, xadj, adjncy, false)); [[maybe_unused]] Metis::idx_t wgtflag=0; Metis::idx_t numflag=0; Metis::idx_t edgecut; #ifdef USE_WEIGHTS wgtflag=3; #endif Metis::real_t *tpwgts = new Metis::real_t[nparts]; for(int i=0; i::getType(), gxadj,noxs,xdispl,MPITraits::getType(), comm); MPI_Allgatherv(adjncy,noNeighbours,MPITraits::getType(), gadjncy,noedges,displ,MPITraits::getType(), comm); #ifdef USE_WEIGHTS MPI_Allgatherv(adjwgt,noNeighbours,MPITraits::getType(), gadjwgt,noedges,displ,MPITraits::getType(), comm); MPI_Allgatherv(vwgt,localNoVtx,MPITraits::getType(), gvwgt,novs,vdispl,MPITraits::getType(), comm); #endif if(verbose && oocomm.communicator().rank()==0) std::cout<<"Gathering global graph data took "<(gxadjlen)); increment = *(start-1); std::transform(start+offset, start+l+offset, start, std::bind(std::plus(), std::placeholders::_1, increment)); } Dune::dinfo<= 5 Metis::idx_t ncon = 1; Metis::idx_t moptions[METIS_NOPTIONS]; METIS_SetDefaultOptions(moptions); moptions[METIS_OPTION_NUMBERING] = numflag; METIS_PartGraphRecursive(&noVertices, &ncon, gxadj, gadjncy, gvwgt, NULL, gadjwgt, &nparts, NULL, NULL, moptions, &edgecut, gpart); #else int options[5] = {0, 1, 1, 3, 3}; // Call metis METIS_PartGraphRecursive(&noVertices, gxadj, gadjncy, gvwgt, gadjwgt, &wgtflag, &numflag, &nparts, options, &edgecut, gpart); #endif if(verbose && oocomm.communicator().rank()==0) std::cout<<"METIS took "<::getType(), part, 1, MPITraits::getType(), 0, comm); { // release remaining memory delete[] gpart; delete[] noedges; delete[] displ; } #endif delete[] xadj; delete[] vtxdist; delete[] adjncy; #ifdef USE_WEIGHTS delete[] vwgt; delete[] adjwgt; #endif delete[] tpwgts; } }else{ part[0]=0; } #endif Dune::dinfo<<" repart "< "<< part[0]< realpart(mat.N(), part[0]); delete[] part; oocomm.copyOwnerToAll(realpart, realpart); if(verbose && oocomm.communicator().rank()==0) std::cout<<"Scattering repartitioning took "< graph(const_cast(mat)); fillIndexSetHoles(graph, oocomm); if(verbose && oocomm.communicator().rank()==0) std::cout<<"Filling index set took "< bool graphRepartition(const G& graph, Dune::OwnerOverlapCopyCommunication& oocomm, Metis::idx_t nparts, std::shared_ptr>& outcomm, RedistributeInterface& redistInf, bool verbose=false) { Timer time; MPI_Comm comm=oocomm.communicator(); oocomm.buildGlobalLookup(graph.noVertices()); fillIndexSetHoles(graph, oocomm); if(verbose && oocomm.communicator().rank()==0) std::cout<<"Filling holes took "<(oocomm.communicator().size())); int myDomain = -1; // // 1) Prepare the required parameters for using ParMETIS // Especially the arrays that represent the graph must be // generated by the DUNE Graph and IndexSet input variables. // These are the arrays: // - vtxdist // - xadj // - adjncy // // #ifdef PERF_REPART // reset timer for step 1) t1=MPI_Wtime(); #endif typedef typename Dune::OwnerOverlapCopyCommunication OOComm; typedef typename OOComm::OwnerSet OwnerSet; // Create the vtxdist array and parmetisVtxMapping. // Global communications are necessary // The parmetis global identifiers for the owner vertices. ParmetisDuneIndexMap indexMap(graph,oocomm); Metis::idx_t *part = new Metis::idx_t[indexMap.numOfOwnVtx()]; for(std::size_t i=0; i < indexMap.numOfOwnVtx(); ++i) part[i]=mype; #if !HAVE_PARMETIS if(oocomm.communicator().rank()==0 && nparts>1) std::cerr<<"ParMETIS not activated. Will repartition to 1 domain instead of requested " <1) { // Create the xadj and adjncy arrays Metis::idx_t *xadj = new Metis::idx_t[indexMap.numOfOwnVtx()+1]; Metis::idx_t *adjncy = new Metis::idx_t[graph.noEdges()]; EdgeFunctor ef(adjncy, indexMap, graph.noEdges()); getAdjArrays(graph, oocomm.globalLookup(), xadj, ef); // // 2) Call ParMETIS // // Metis::idx_t numflag=0, wgtflag=0, options[3], edgecut=0, ncon=1; //float *tpwgts = NULL; Metis::real_t *tpwgts = new Metis::real_t[nparts]; for(int i=0; i(comm)); delete[] xadj; delete[] adjncy; delete[] tpwgts; ef.free(); #ifdef DEBUG_REPART if (mype == 0) { std::cout< domainMapping(nparts); if(nparts>1) getDomain(comm, part, indexMap.numOfOwnVtx(), nparts, &myDomain, domainMapping); else domainMapping[0]=0; #ifdef DEBUG_REPART std::cout< setPartition(oocomm.indexSet().size(), -1); std::size_t i=0; // parmetis index for(auto index = oocomm.indexSet().begin(); index != oocomm.indexSet().end(); ++index) if(OwnerSet::contains(index->local().attribute())) { setPartition[index->local()]=domainMapping[part[i++]]; } delete[] part; oocomm.copyOwnerToAll(setPartition, setPartition); // communication only needed for ALU // (ghosts with same global id as owners on the same process) if (SolverCategory::category(oocomm) == static_cast(SolverCategory::nonoverlapping)) oocomm.copyCopyToAll(setPartition, setPartition); bool ret = buildCommunication(graph, setPartition, oocomm, outcomm, redistInf, verbose); if(verbose) { oocomm.communicator().barrier(); if(oocomm.communicator().rank()==0) std::cout<<"Creating indexsets took "< bool buildCommunication(const G& graph, std::vector& setPartition, Dune::OwnerOverlapCopyCommunication& oocomm, std::shared_ptr>& outcomm, RedistributeInterface& redistInf, bool verbose) { typedef typename Dune::OwnerOverlapCopyCommunication OOComm; typedef typename OOComm::OwnerSet OwnerSet; Timer time; // Build the send interface redistInf.buildSendInterface(setPartition, oocomm.indexSet()); #ifdef PERF_REPART // stop the time for step 3) t3=MPI_Wtime()-t3; // reset timer for step 4) t4=MPI_Wtime(); #endif // // 4) Create the output IndexSet and RemoteIndices // 4.1) Determine the "send to" and "receive from" relation // according to the new partition using a MPI ring // communication. // // 4.2) Depends on the "send to" and "receive from" vector, // the processes will exchange the vertices each other // // 4.3) Create the IndexSet, RemoteIndices and the new MPI // communicator // // // 4.1) Let's start... // int npes = oocomm.communicator().size(); int *sendTo = 0; int noSendTo = 0; std::set recvFrom; // the max number of vertices is stored in the sendTo buffer, // not the number of vertices to send! Because the max number of Vtx // is used as the fixed buffer size by the MPI send/receive calls int mype = oocomm.communicator().rank(); { std::set tsendTo; for(auto i=setPartition.begin(), iend = setPartition.end(); i!=iend; ++i) tsendTo.insert(*i); noSendTo = tsendTo.size(); sendTo = new int[noSendTo]; int idx=0; for(auto i=tsendTo.begin(); i != tsendTo.end(); ++i, ++idx) sendTo[idx]=*i; } // int* gnoSend= new int[oocomm.communicator().size()]; int* gsendToDispl = new int[oocomm.communicator().size()+1]; MPI_Allgather(&noSendTo, 1, MPI_INT, gnoSend, 1, MPI_INT, oocomm.communicator()); // calculate total receive message size int totalNoRecv = 0; for(int i=0; i0; // Delete memory delete[] gnoSend; delete[] gsendToDispl; delete[] gsendTo; #ifdef DEBUG_REPART if(recvFrom.size()) { std::cout< GlobalVector; std::vector > myOwnerVec; std::set myOverlapSet; GlobalVector sendOwnerVec; std::set sendOverlapSet; std::set myNeighbors; // getOwnerOverlapVec(graph, setPartition, oocomm.globalLookup(), // mype, mype, myOwnerVec, myOverlapSet, redistInf, myNeighbors); char **sendBuffers=new char*[noSendTo]; MPI_Request *requests = new MPI_Request[noSendTo]; // Create all messages to be sent for(int i=0; i < noSendTo; ++i) { // clear the vector for sending sendOwnerVec.clear(); sendOverlapSet.clear(); // get all owner and overlap vertices for process j and save these // in the vectors sendOwnerVec and sendOverlapSet std::set neighbors; getOwnerOverlapVec(graph, setPartition, oocomm.globalLookup(), mype, sendTo[i], sendOwnerVec, sendOverlapSet, redistInf, neighbors); // +2, we need 2 integer more for the length of each part // (owner/overlap) of the array int buffersize=0; int tsize; MPI_Pack_size(1, MPITraits::getType(), oocomm.communicator(), &buffersize); MPI_Pack_size(sendOwnerVec.size(), MPITraits::getType(), oocomm.communicator(), &tsize); buffersize +=tsize; MPI_Pack_size(1, MPITraits::getType(), oocomm.communicator(), &tsize); buffersize +=tsize; MPI_Pack_size(sendOverlapSet.size(), MPITraits::getType(), oocomm.communicator(), &tsize); buffersize += tsize; MPI_Pack_size(1, MPITraits::getType(), oocomm.communicator(), &tsize); buffersize += tsize; MPI_Pack_size(neighbors.size(), MPI_INT, oocomm.communicator(), &tsize); buffersize += tsize; sendBuffers[i] = new char[buffersize]; #ifdef DEBUG_REPART std::cout<0) { // probe for an incoming message MPI_Status stat; MPI_Probe(MPI_ANY_SOURCE, 99, oocomm.communicator(), &stat); int buffersize; MPI_Get_count(&stat, MPI_PACKED, &buffersize); if(oldbuffersize(outputComm,SolverCategory::category(oocomm),true); // translate neighbor ranks. int newrank=outcomm->communicator().rank(); int *newranks=new int[oocomm.communicator().size()]; std::vector tneighbors; tneighbors.reserve(myNeighbors.size()); typename OOComm::ParallelIndexSet& outputIndexSet = outcomm->indexSet(); MPI_Allgather(&newrank, 1, MPI_INT, newranks, 1, MPI_INT, oocomm.communicator()); #ifdef DEBUG_REPART std::cout<=0); std::cout<<*i<<"->"<first,LocalIndexT(i, OwnerOverlapCopyAttributeSet::owner, true)); redistInf.addReceiveIndex(g->second, i); } if(verbose) { oocomm.communicator().barrier(); if(oocomm.communicator().rank()==0) std::cout<<" Adding owner indices took "<< time.elapsed()<local().attribute())) { numOfOwnVtx++; } } numOfOwnVtx = oocomm.communicator().sum(numOfOwnVtx); // if(numOfOwnVtx!=indexMap.globalOwnerVertices) // { // std::cerr<remoteIndices().setNeighbours(tneighbors); outcomm->remoteIndices().template rebuild(); } // release the memory delete[] sendTo; if(verbose) { oocomm.communicator().barrier(); if(oocomm.communicator().rank()==0) std::cout<<" Storing indexsets took "<< time.elapsed()< bool graphRepartition(const G& graph, P& oocomm, int nparts, std::shared_ptr

& outcomm, R& redistInf, bool v=false) { if(nparts!=oocomm.size()) DUNE_THROW(NotImplemented, "only available for MPI programs"); } template bool commGraphRepartition(const G& graph, P& oocomm, int nparts, std::shared_ptr

& outcomm, R& redistInf, bool v=false) { if(nparts!=oocomm.size()) DUNE_THROW(NotImplemented, "only available for MPI programs"); } #endif // HAVE_MPI } // end of namespace Dune #endif