45 #ifndef _ZOLTAN2_ALGSCOTCH_HPP_ 46 #define _ZOLTAN2_ALGSCOTCH_HPP_ 67 pl.set(
"scotch_verbose",
false,
"verbose output",
70 RCP<Teuchos::EnhancedNumberValidator<int>> scotch_level_Validator =
71 Teuchos::rcp(
new Teuchos::EnhancedNumberValidator<int>(0, 1000, 1, 0) );
72 pl.set(
"scotch_level", 0,
"scotch ordering - Level of the subgraph in the " 73 "separators tree for the initial graph at the root of the tree",
74 scotch_level_Validator);
76 pl.set(
"scotch_imbalance_ratio", 0.2,
"scotch ordering - Dissection " 80 pl.set(
"scotch_ordering_default",
true,
"use default scotch ordering " 83 pl.set(
"scotch_ordering_strategy",
"",
"scotch ordering - Dissection " 89 #ifndef HAVE_ZOLTAN2_SCOTCH 96 template <
typename Adapter>
106 const RCP<
const Comm<int> > &problemComm,
107 const RCP<const base_adapter_t> &adapter
110 throw std::runtime_error(
111 "BUILD ERROR: Scotch requested but not compiled into Zoltan2.\n" 112 "Please set CMake flag Zoltan2_ENABLE_Scotch:BOOL=ON.");
128 #ifdef HAVE_ZOLTAN2_SCOTCH 135 #ifndef HAVE_ZOLTAN2_MPI 138 #include "ptscotch.h" 142 #ifdef SHOW_ZOLTAN2_SCOTCH_MEMORY 155 #ifdef HAVE_SCOTCH_GETMEMORYMAX 157 extern size_t SCOTCH_getMemoryMax();
160 #error "Either turn off ZOLTAN2_ENABLE_SCOTCH_MEMORY_REPORT in cmake configure, or see SHOW_ZOLTAN2_SCOTCH_MEMORY comment in Zoltan2_AlgScotch.hpp" 161 #endif // HAVE_SCOTCH_GETMEMORYMAX 162 #endif // SHOW_ZOLTAN2_SCOTCH_MEMORY 164 template <
typename Adapter>
165 class AlgPTScotch :
public Algorithm<Adapter>
170 typedef GraphModel<typename Adapter::base_adapter_t> graphModel_t;
171 typedef typename Adapter::lno_t
lno_t;
172 typedef typename Adapter::gno_t
gno_t;
173 typedef typename Adapter::scalar_t
scalar_t;
174 typedef typename Adapter::part_t
part_t;
175 typedef typename Adapter::user_t user_t;
176 typedef typename Adapter::userCoord_t userCoord_t;
208 const RCP<
const Comm<int> > &problemComm__,
209 const RCP<
const IdentifierAdapter<user_t> > &adapter__) :
210 env(env__), problemComm(problemComm__),
211 #ifdef HAVE_ZOLTAN2_MPI
212 mpicomm(
Teuchos::getRawMpiComm(*problemComm__)),
216 std::string errStr =
"cannot build GraphModel from IdentifierAdapter, ";
217 errStr +=
"Scotch requires Graph, Matrix, or Mesh Adapter";
218 throw std::runtime_error(errStr);
222 const RCP<
const Comm<int> > &problemComm__,
223 const RCP<
const VectorAdapter<user_t> > &adapter__) :
224 env(env__), problemComm(problemComm__),
225 #ifdef HAVE_ZOLTAN2_MPI
226 mpicomm(
Teuchos::getRawMpiComm(*problemComm__)),
230 std::string errStr =
"cannot build GraphModel from IdentifierAdapter, ";
231 errStr +=
"Scotch requires Graph, Matrix, or Mesh Adapter";
232 throw std::runtime_error(errStr);
236 const RCP<
const Comm<int> > &problemComm__,
237 const RCP<
const GraphAdapter<user_t, userCoord_t> > &adapter__) :
238 env(env__), problemComm(problemComm__),
239 #ifdef HAVE_ZOLTAN2_MPI
240 mpicomm(
Teuchos::getRawMpiComm(*problemComm__)),
242 adapter(adapter__), model_flags()
244 this->model_flags.reset();
248 const RCP<
const Comm<int> > &problemComm__,
249 const RCP<
const MatrixAdapter<user_t, userCoord_t> > &adapter__) :
250 env(env__), problemComm(problemComm__),
251 #ifdef HAVE_ZOLTAN2_MPI
252 mpicomm(
Teuchos::getRawMpiComm(*problemComm__)),
254 adapter(adapter__), model_flags()
256 this->model_flags.reset();
258 const ParameterList &pl = env->getParameters();
259 const Teuchos::ParameterEntry *pe;
261 std::string defString(
"default");
262 std::string objectOfInterest(defString);
263 pe = pl.getEntryPtr(
"objects_to_partition");
265 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
267 if (objectOfInterest == defString ||
268 objectOfInterest == std::string(
"matrix_rows") )
270 else if (objectOfInterest == std::string(
"matrix_columns"))
272 else if (objectOfInterest == std::string(
"matrix_nonzeros"))
277 const RCP<
const Comm<int> > &problemComm__,
278 const RCP<
const MeshAdapter<user_t> > &adapter__) :
279 env(env__), problemComm(problemComm__),
280 #ifdef HAVE_ZOLTAN2_MPI
281 mpicomm(
Teuchos::getRawMpiComm(*problemComm__)),
283 adapter(adapter__), model_flags()
285 this->model_flags.reset();
287 const ParameterList &pl = env->getParameters();
288 const Teuchos::ParameterEntry *pe;
290 std::string defString(
"default");
291 std::string objectOfInterest(defString);
292 pe = pl.getEntryPtr(
"objects_to_partition");
294 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
296 if (objectOfInterest == defString ||
297 objectOfInterest == std::string(
"mesh_nodes") )
299 else if (objectOfInterest == std::string(
"mesh_elements"))
310 void partition(
const RCP<PartitioningSolution<Adapter> > &solution);
317 int order(
const RCP<OrderingSolution<lno_t, gno_t> > &solution);
321 const RCP<const Environment> env;
322 const RCP<const Comm<int> > problemComm;
323 #ifdef HAVE_ZOLTAN2_MPI 324 const MPI_Comm mpicomm;
326 const RCP<const base_adapter_t> adapter;
328 RCP<graphModel_t > model;
330 void buildModel(
bool isLocal);
331 void scale_weights(
size_t n, StridedData<lno_t, scalar_t> &fwgts,
333 static int setStrategy(SCOTCH_Strat * c_strat_ptr,
const ParameterList &pList,
int procRank);
337 template <
typename Adapter>
338 void AlgPTScotch<Adapter>::buildModel(
bool isLocal) {
340 const ParameterList &pl = env->getParameters();
341 const Teuchos::ParameterEntry *pe;
343 std::string defString(
"default");
344 std::string symParameter(defString);
345 pe = pl.getEntryPtr(
"symmetrize_graph");
347 symParameter = pe->getValue<std::string>(&symParameter);
348 if (symParameter == std::string(
"transpose"))
350 else if (symParameter == std::string(
"bipartite"))
353 bool sgParameter =
false;
354 pe = pl.getEntryPtr(
"subset_graph");
356 sgParameter = pe->getValue(&sgParameter);
368 this->model = rcp(
new graphModel_t(this->adapter,
375 template <
typename Adapter>
377 const RCP<PartitioningSolution<Adapter> > &solution
381 this->buildModel(
false);
383 size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
385 SCOTCH_Num partnbr=0;
388 #ifdef HAVE_ZOLTAN2_MPI 390 int me = problemComm->getRank();
392 const SCOTCH_Num baseval = 0;
395 SCOTCH_Strat stratstr;
397 SCOTCH_stratInit(&stratstr);
400 SCOTCH_Dgraph *gr = SCOTCH_dgraphAlloc();
401 ierr = SCOTCH_dgraphInit(gr, mpicomm);
403 env->globalInputAssertion(__FILE__, __LINE__,
"SCOTCH_dgraphInit",
407 ArrayView<const gno_t> vtxID;
408 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
409 size_t nVtx = model->getVertexList(vtxID, vwgts);
410 SCOTCH_Num vertlocnbr=0;
412 SCOTCH_Num vertlocmax = vertlocnbr;
415 ArrayView<const gno_t> edgeIds;
416 ArrayView<const lno_t> offsets;
417 ArrayView<StridedData<lno_t, scalar_t> > ewgts;
419 size_t nEdge = model->getEdgeList(edgeIds, offsets, ewgts);
421 SCOTCH_Num edgelocnbr=0;
423 const SCOTCH_Num edgelocsize = edgelocnbr;
425 SCOTCH_Num *vertloctab;
428 SCOTCH_Num *edgeloctab;
432 SCOTCH_Num *vendloctab = NULL;
433 SCOTCH_Num *vlblloctab = NULL;
434 SCOTCH_Num *edgegsttab = NULL;
437 SCOTCH_Num *velotab = NULL;
438 SCOTCH_Num *edlotab = NULL;
440 int nVwgts = model->getNumWeightsPerVertex();
441 int nEwgts = model->getNumWeightsPerEdge();
442 if (nVwgts > 1 && me == 0) {
443 std::cerr <<
"Warning: NumWeightsPerVertex is " << nVwgts
444 <<
" but Scotch allows only one weight. " 445 <<
" Zoltan2 will use only the first weight per vertex." 448 if (nEwgts > 1 && me == 0) {
449 std::cerr <<
"Warning: NumWeightsPerEdge is " << nEwgts
450 <<
" but Scotch allows only one weight. " 451 <<
" Zoltan2 will use only the first weight per edge." 456 velotab =
new SCOTCH_Num[nVtx+1];
458 scale_weights(nVtx, vwgts[0], velotab);
462 edlotab =
new SCOTCH_Num[nEdge+1];
464 scale_weights(nEdge, ewgts[0], edlotab);
468 ierr = SCOTCH_dgraphBuild(gr, baseval, vertlocnbr, vertlocmax,
469 vertloctab, vendloctab, velotab, vlblloctab,
470 edgelocnbr, edgelocsize,
471 edgeloctab, edgegsttab, edlotab);
473 env->globalInputAssertion(__FILE__, __LINE__,
"SCOTCH_dgraphBuild",
477 SCOTCH_Num *partloctab =
new SCOTCH_Num[nVtx+1];
482 float *partsizes =
new float[numGlobalParts];
483 if (!solution->criteriaHasUniformPartSizes(0))
484 for (
size_t i=0; i<numGlobalParts; i++)
485 partsizes[i] = solution->getCriteriaPartSize(0, i);
487 for (
size_t i=0; i<numGlobalParts; i++)
488 partsizes[i] = 1.0 /
float(numGlobalParts);
492 SCOTCH_archInit(&archdat);
494 SCOTCH_Num velosum = 0;
495 SCOTCH_dgraphSize (gr, &velosum, NULL, NULL, NULL);
496 SCOTCH_Num *goalsizes =
new SCOTCH_Num[partnbr];
502 for (SCOTCH_Num i = 0; i < partnbr; i++)
503 goalsizes[i] = SCOTCH_Num(ceil(velosum * partsizes[i]));
506 SCOTCH_archCmpltw(&archdat, partnbr, goalsizes);
509 ierr = SCOTCH_dgraphMap(gr, &archdat, &stratstr, partloctab);
511 env->globalInputAssertion(__FILE__, __LINE__,
"SCOTCH_dgraphMap",
514 SCOTCH_archExit(&archdat);
519 #ifdef SHOW_ZOLTAN2_SCOTCH_MEMORY 520 int me = env->comm_->getRank();
523 #ifdef HAVE_SCOTCH_ZOLTAN2_GETMEMORYMAX 525 size_t scotchBytes = SCOTCH_getMemoryMax();
526 std::cout <<
"Rank " << me <<
": Maximum bytes used by Scotch: ";
527 std::cout << scotchBytes << std::endl;
532 SCOTCH_dgraphExit(gr);
534 SCOTCH_stratExit(&stratstr);
538 ArrayRCP<part_t> partList;
543 solution->setParts(partList);
545 env->memory(
"Zoltan2-Scotch: After creating solution");
551 if (nVwgts)
delete [] velotab;
552 if (nEwgts)
delete [] edlotab;
554 #else // DO NOT HAVE MPI 562 ArrayView<const gno_t> vtxID;
563 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
564 size_t nVtx = model->getVertexList(vtxID, vwgts);
566 ArrayRCP<part_t> partList(
new part_t[nVtx], 0, nVtx,
true);
567 for (
size_t i = 0; i < nVtx; i++) partList[i] = 0;
569 solution->setParts(partList);
571 #endif // DO NOT HAVE MPI 584 template <
typename Adapter>
585 void AlgPTScotch<Adapter>::scale_weights(
587 StridedData<typename Adapter::lno_t, typename Adapter::scalar_t> &fwgts,
591 const double INT_EPSILON = 1e-5;
593 SCOTCH_Num nonint, nonint_local = 0;
594 double sum_wgt, sum_wgt_local = 0.;
595 double max_wgt, max_wgt_local = 0.;
599 for (
size_t i = 0; i < n; i++) {
600 double fw = double(fwgts[i]);
602 SCOTCH_Num tmp = (SCOTCH_Num) floor(fw + .5);
603 if (fabs((
double)tmp-fw) > INT_EPSILON) {
608 if (fw > max_wgt_local) max_wgt_local = fw;
611 Teuchos::reduceAll<int,SCOTCH_Num>(*problemComm, Teuchos::REDUCE_MAX, 1,
612 &nonint_local, &nonint);
613 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_SUM, 1,
614 &sum_wgt_local, &sum_wgt);
615 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_MAX, 1,
616 &max_wgt_local, &max_wgt);
619 const double max_wgt_sum = double(SCOTCH_NUMMAX/8);
623 if (nonint || (max_wgt <= INT_EPSILON) || (sum_wgt > max_wgt_sum)) {
625 if (sum_wgt != 0.) scale = max_wgt_sum/sum_wgt;
629 for (
size_t i = 0; i < n; i++)
630 iwgts[i] = (SCOTCH_Num) ceil(
double(fwgts[i])*scale);
634 template <
typename Adapter>
635 int AlgPTScotch<Adapter>::setStrategy(SCOTCH_Strat * c_strat_ptr,
const ParameterList &pList,
int procRank) {
638 const Teuchos::ParameterEntry *pe;
639 bool isVerbose =
false;
640 pe = pList.getEntryPtr(
"scotch_verbose");
642 isVerbose = pe->getValue(&isVerbose);
644 bool use_default =
true;
645 std::string strat_string(
"");
647 pe = pList.getEntryPtr(
"scotch_ordering_default");
649 use_default = pe->getValue(&use_default);
651 pe = pList.getEntryPtr(
"scotch_ordering_strategy");
653 strat_string = pe->getValue<std::string>(&strat_string);
656 if (!use_default && strat_string.size() > 0) {
658 if (isVerbose && procRank == 0) {
659 std::cout <<
"Ordering strategy string: " << strat_string << std::endl;
661 SCOTCH_stratInit(c_strat_ptr);
662 ierr = SCOTCH_stratGraphOrder( c_strat_ptr, strat_string.c_str());
669 pe = pList.getEntryPtr(
"scotch_level");
671 levels = pe->getValue<
int>(&levels);
673 pe = pList.getEntryPtr(
"scotch_imbalance_ratio");
675 balrat = pe->getValue<
double>(&balrat);
677 if (isVerbose && procRank == 0) {
678 std::cout <<
"Ordering level: " << levels << std::endl;
679 std::cout <<
"Ordering dissection imbalance ratio: " << balrat << std::endl;
682 SCOTCH_stratInit(c_strat_ptr);
683 ierr = SCOTCH_stratGraphOrderBuild( c_strat_ptr,
684 SCOTCH_STRATLEVELMAX | SCOTCH_STRATLEVELMIN | SCOTCH_STRATLEAFSIMPLE | SCOTCH_STRATSEPASIMPLE,
691 template <
typename Adapter>
693 const RCP<OrderingSolution<lno_t, gno_t> > &solution) {
700 int me = problemComm->getRank();
701 const ParameterList &pl = env->getParameters();
702 const Teuchos::ParameterEntry *pe;
704 bool isVerbose =
false;
705 pe = pl.getEntryPtr(
"scotch_verbose");
707 isVerbose = pe->getValue(&isVerbose);
710 this->buildModel(
true);
711 if (isVerbose && me== 0) {
712 std::cout <<
"Built local graph model." << std::endl;
716 SCOTCH_Strat c_strat_ptr;
717 SCOTCH_Graph c_graph_ptr;
720 ierr = SCOTCH_graphInit( &c_graph_ptr);
722 throw std::runtime_error(
"Failed to initialize Scotch graph!");
723 }
else if (isVerbose && me == 0) {
724 std::cout <<
"Initialized Scotch graph." << std::endl;
728 ArrayView<const gno_t> vtxID;
729 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
730 size_t nVtx = model->getVertexList(vtxID, vwgts);
731 SCOTCH_Num vertnbr=0;
735 ArrayView<const gno_t> edgeIds;
736 ArrayView<const lno_t> offsets;
737 ArrayView<StridedData<lno_t, scalar_t> > ewgts;
739 size_t nEdge = model->getEdgeList(edgeIds, offsets, ewgts);
740 SCOTCH_Num edgenbr=0;
750 SCOTCH_Num *vendtab = NULL;
753 SCOTCH_Num *velotab = NULL;
754 SCOTCH_Num *vlbltab = NULL;
755 SCOTCH_Num *edlotab = NULL;
757 int nVwgts = model->getNumWeightsPerVertex();
758 int nEwgts = model->getNumWeightsPerEdge();
759 if (nVwgts > 1 && me == 0) {
760 std::cerr <<
"Warning: NumWeightsPerVertex is " << nVwgts
761 <<
" but Scotch allows only one weight. " 762 <<
" Zoltan2 will use only the first weight per vertex." 765 if (nEwgts > 1 && me == 0) {
766 std::cerr <<
"Warning: NumWeightsPerEdge is " << nEwgts
767 <<
" but Scotch allows only one weight. " 768 <<
" Zoltan2 will use only the first weight per edge." 773 velotab =
new SCOTCH_Num[nVtx+1];
775 scale_weights(nVtx, vwgts[0], velotab);
779 edlotab =
new SCOTCH_Num[nEdge+1];
781 scale_weights(nEdge, ewgts[0], edlotab);
787 ierr = SCOTCH_graphBuild( &c_graph_ptr, baseval,
788 vertnbr, verttab, vendtab, velotab, vlbltab,
789 edgenbr, edgetab, edlotab);
791 throw std::runtime_error(
"Failed to build Scotch graph!");
792 }
else if (isVerbose && me == 0) {
793 std::cout <<
"Built Scotch graph." << std::endl;
796 ierr = SCOTCH_graphCheck(&c_graph_ptr);
798 throw std::runtime_error(
"Graph is inconsistent!");
799 }
else if (isVerbose && me == 0) {
800 std::cout <<
"Graph is consistent." << std::endl;
804 ierr = AlgPTScotch<Adapter>::setStrategy(&c_strat_ptr, pl, me);
807 throw std::runtime_error(
"Can't build strategy!");
808 }
else if (isVerbose && me == 0) {
809 std::cout <<
"Graphing strategy built.." << std::endl;
816 SCOTCH_Num *rangetab;
820 permtab =
reinterpret_cast<SCOTCH_Num*
>(solution->getPermutationView(
false));
821 peritab =
reinterpret_cast<SCOTCH_Num*
>(solution->getPermutationView(
true));
822 rangetab =
reinterpret_cast<SCOTCH_Num*
>(solution->getSeparatorRangeView());
823 treetab =
reinterpret_cast<SCOTCH_Num*
>(solution->getSeparatorTreeView());
826 permtab =
new SCOTCH_Num[nVtx];
827 peritab =
new SCOTCH_Num[nVtx];
828 rangetab =
new SCOTCH_Num[nVtx+1];
829 treetab =
new SCOTCH_Num[nVtx];
832 ierr = SCOTCH_graphOrder(&c_graph_ptr, &c_strat_ptr, permtab, peritab,
833 &cblk, rangetab, treetab);
835 throw std::runtime_error(
"Could not compute ordering!!");
836 }
else if(isVerbose && me == 0) {
837 std::cout <<
"Ordering computed." << std::endl;
842 solution->setNumSeparatorBlocks(nSepBlocks);
846 const ArrayRCP<lno_t> arv_perm = solution->getPermutationRCP(
false);
847 for (
size_t i = 0; i < nVtx; i++)
851 const ArrayRCP<lno_t> arv_peri = solution->getPermutationRCP(
true);
852 for (
size_t i = 0; i < nVtx; i++)
856 const ArrayRCP<lno_t> arv_range = solution->getSeparatorRangeRCP();
857 for (
size_t i = 0; i <= nVtx; i++)
861 const ArrayRCP<lno_t> arv_tree = solution->getSeparatorTreeRCP();
862 for (
size_t i = 0; i < nVtx; i++)
867 solution->setHaveSeparator(
true);
874 if (nVwgts)
delete [] velotab;
875 if (nEwgts)
delete [] edlotab;
877 SCOTCH_stratExit(&c_strat_ptr);
878 SCOTCH_graphFree(&c_graph_ptr);
880 if (isVerbose && problemComm->getRank() == 0) {
881 std::cout <<
"Freed Scotch graph!" << std::endl;
888 #endif // HAVE_ZOLTAN2_SCOTCH use columns as graph vertices
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
Adapter::base_adapter_t base_adapter_t
use mesh nodes as vertices
fast typical checks for valid arguments
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
algorithm requires consecutive ids
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
model must symmetrize input
Defines the OrderingSolution class.
model must symmetrize input
Defines the PartitioningSolution class.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyDoubleValidator()
Exists to make setting up validators less cluttered.
static void SAVE_ARRAYRCP(ArrayRCP< first_t > *a, second_t *b, size_t size)
sub-steps, each method's entry and exit
use matrix rows as graph vertices
algorithm requires no self edges
static void getScotchParameters(Teuchos::ParameterList &pl)
Adapter::scalar_t scalar_t
use nonzeros as graph vertices
Algorithm defines the base class for all algorithms.
virtual int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
static void ASSIGN(first_t &a, second_t b)
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
virtual void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t...
use mesh elements as vertices
static void ASSIGN_ARRAY(first_t **a, ArrayView< second_t > &b)
AlgPTScotch(const RCP< const Environment > &env, const RCP< const Comm< int > > &problemComm, const RCP< const base_adapter_t > &adapter)
Defines the GraphModel interface.
A gathering of useful namespace methods.
static void DELETE_ARRAY(first_t **a)
model represents graph within only one rank