50 #ifndef _ZOLTAN2_PARTITIONINGSOLUTION_HPP_ 51 #define _ZOLTAN2_PARTITIONINGSOLUTION_HPP_ 54 template <
typename Adapter>
90 template <
typename Adapter>
95 #ifndef DOXYGEN_SHOULD_SKIP_THIS 96 typedef typename Adapter::gno_t gno_t;
97 typedef typename Adapter::scalar_t scalar_t;
98 typedef typename Adapter::lno_t lno_t;
99 typedef typename Adapter::part_t part_t;
100 typedef typename Adapter::user_t user_t;
121 RCP<
const Comm<int> > &comm,
155 RCP<
const Comm<int> > &comm,
156 int nUserWeights, ArrayView<ArrayRCP<part_t> > reqPartIds,
157 ArrayView<ArrayRCP<scalar_t> > reqPartSizes,
215 if (partDist_.size() > 0)
return &partDist_[0];
236 if (procDist_.size() > 0)
return &procDist_[0];
267 if (pSizeUniform_[idx])
268 return 1.0 / nGlobalParts_;
269 else if (pCompactIndex_[idx].size())
270 return pSize_[idx][pCompactIndex_[idx][part]];
272 return pSize_[idx][part];
319 void setParts(ArrayRCP<part_t> &partList);
341 part_t nrhs, part_t nlhs)
344 for (part_t i = 0; i < nrhs; i++) {
345 part_t k = (remap ? remap[i] : i);
346 for (part_t j = idx[k]; j < idx[k+1]; j++) {
347 if (i == (adj[j]-nlhs)) {
373 if (parts_.size() > 0)
return parts_.getRawPtr();
382 if (procs_.size() > 0)
return procs_.getRawPtr();
389 std::vector<Zoltan2::coordinateModelPartBox<scalar_t, part_t> > &
392 return this->algorithm_->getPartBoxesView();
408 if (this->algorithm_ == Teuchos::null)
409 throw std::logic_error(
"no partitioning algorithm has been run yet");
411 p = this->algorithm_->pointAssign(dim, point);
429 void boxAssign(
int dim, scalar_t *lower, scalar_t *upper,
430 size_t &nPartsFound, part_t **partsFound)
const 433 if (this->algorithm_ == Teuchos::null)
434 throw std::logic_error(
"no partitioning algorithm has been run yet");
436 this->algorithm_->boxAssign(dim, lower, upper, nPartsFound, partsFound);
445 ArrayRCP <part_t> &comAdj)
const 448 if (this->algorithm_ == Teuchos::null)
449 throw std::logic_error(
"no partitioning algorithm has been run yet");
451 this->algorithm_->getCommunicationGraph(
this, comXAdj, comAdj);
474 part_t &partMax)
const 476 env_->localInputAssertion(__FILE__, __LINE__,
"invalid process id",
479 procToPartsMap(procId, numParts, partMin, partMax);
495 env_->localInputAssertion(__FILE__, __LINE__,
"invalid part id",
498 partToProcsMap(partId, procMin, procMax);
502 void partToProc(
bool doCheck,
bool haveNumLocalParts,
bool haveNumGlobalParts,
503 int numLocalParts,
int numGlobalParts);
505 void procToPartsMap(
int procId,
double &numParts, part_t &partMin,
506 part_t &partMax)
const;
508 void partToProcsMap(part_t partId,
int &procMin,
int &procMax)
const;
510 void setPartDistribution();
512 void setPartSizes(ArrayView<ArrayRCP<part_t> > reqPartIds,
513 ArrayView<ArrayRCP<scalar_t> > reqPartSizes);
515 void computePartSizes(
int widx, ArrayView<part_t> ids,
516 ArrayView<scalar_t> sizes);
518 void broadcastPartSizes(
int widx);
521 RCP<const Environment> env_;
522 RCP<const Comm<int> > comm_;
525 RCP < std::vector <Zoltan2::coordinateModelPartBox <scalar_t, part_t> > > partBoxes;
527 part_t nGlobalParts_;
530 scalar_t localFraction_;
562 bool onePartPerProc_;
563 std::vector<int> partDist_;
564 std::vector<part_t> procDist_;
565 bool procDistEquallySpread_;
601 ArrayRCP<bool> pSizeUniform_;
602 ArrayRCP<ArrayRCP<unsigned char> > pCompactIndex_;
603 ArrayRCP<ArrayRCP<scalar_t> > pSize_;
608 ArrayRCP<part_t> parts_;
612 part_t nGlobalPartsSolution_;
618 ArrayRCP<int> procs_;
623 const RCP<Algorithm<Adapter> > algorithm_;
630 template <
typename Adapter>
632 const RCP<const Environment> &env,
633 RCP<
const Comm<int> > &comm,
636 : env_(env), comm_(comm),
638 nGlobalParts_(0), nLocalParts_(0),
639 localFraction_(0), nWeightsPerObj_(),
640 onePartPerProc_(false), partDist_(), procDist_(),
641 procDistEquallySpread_(false),
642 pSizeUniform_(), pCompactIndex_(), pSize_(),
643 parts_(), haveSolution_(false), nGlobalPartsSolution_(0),
644 procs_(), algorithm_(algorithm)
646 nWeightsPerObj_ = (nUserWeights ? nUserWeights : 1);
648 setPartDistribution();
653 ArrayRCP<part_t> *noIds =
new ArrayRCP<part_t> [nWeightsPerObj_];
654 ArrayRCP<scalar_t> *noSizes =
new ArrayRCP<scalar_t> [nWeightsPerObj_];
655 ArrayRCP<ArrayRCP<part_t> > ids(noIds, 0, nWeightsPerObj_,
true);
656 ArrayRCP<ArrayRCP<scalar_t> > sizes(noSizes, 0, nWeightsPerObj_,
true);
658 setPartSizes(ids.view(0, nWeightsPerObj_), sizes.view(0, nWeightsPerObj_));
660 env_->memory(
"After construction of solution");
663 template <
typename Adapter>
665 const RCP<const Environment> &env,
666 RCP<
const Comm<int> > &comm,
668 ArrayView<ArrayRCP<part_t> > reqPartIds,
669 ArrayView<ArrayRCP<scalar_t> > reqPartSizes,
671 : env_(env), comm_(comm),
673 nGlobalParts_(0), nLocalParts_(0),
674 localFraction_(0), nWeightsPerObj_(),
675 onePartPerProc_(false), partDist_(), procDist_(),
676 procDistEquallySpread_(false),
677 pSizeUniform_(), pCompactIndex_(), pSize_(),
678 parts_(), haveSolution_(false), nGlobalPartsSolution_(0),
679 procs_(), algorithm_(algorithm)
681 nWeightsPerObj_ = (nUserWeights ? nUserWeights : 1);
683 setPartDistribution();
685 setPartSizes(reqPartIds, reqPartSizes);
687 env_->memory(
"After construction of solution");
690 template <
typename Adapter>
695 const ParameterList &pl = env_->getParameters();
696 size_t haveGlobalNumParts=0, haveLocalNumParts=0;
697 int numLocal=0, numGlobal=0;
700 const Teuchos::ParameterEntry *pe = pl.getEntryPtr(
"num_global_parts");
703 val = pe->getValue<
double>(&val);
704 haveGlobalNumParts = 1;
705 numGlobal =
static_cast<int>(val);
706 nGlobalParts_ = part_t(numGlobal);
709 pe = pl.getEntryPtr(
"num_local_parts");
712 val = pe->getValue<
double>(&val);
713 haveLocalNumParts = 1;
714 numLocal =
static_cast<int>(val);
715 nLocalParts_ = part_t(numLocal);
721 partToProc(
true, haveLocalNumParts, haveGlobalNumParts,
722 numLocal, numGlobal);
726 int nprocs = comm_->getSize();
727 int rank = comm_->getRank();
729 if (onePartPerProc_){
730 nGlobalParts_ = nprocs;
733 else if (partDist_.size() > 0){
734 nGlobalParts_ = partDist_.size() - 1;
735 int pstart = partDist_[0];
736 for (part_t i=1; i <= nGlobalParts_; i++){
737 int pend = partDist_[i];
738 if (rank >= pstart && rank < pend){
739 int numOwners = pend - pstart;
741 localFraction_ = 1.0 / numOwners;
747 else if (procDist_.size() > 0){
748 nGlobalParts_ = procDist_[nprocs];
749 nLocalParts_ = procDist_[rank+1] - procDist_[rank];
752 throw std::logic_error(
"partToProc error");
757 template <
typename Adapter>
759 ArrayView<ArrayRCP<part_t> > ids, ArrayView<ArrayRCP<scalar_t> > sizes)
761 int widx = nWeightsPerObj_;
764 size_t *countBuf =
new size_t [widx*2];
765 ArrayRCP<size_t> counts(countBuf, 0, widx*2,
true);
767 fail = ((ids.size() != widx) || (sizes.size() != widx));
769 for (
int w=0; !fail && w < widx; w++){
770 counts[w] = ids[w].size();
771 if (ids[w].size() != sizes[w].size()) fail=
true;
774 env_->globalBugAssertion(__FILE__, __LINE__,
"bad argument arrays", fail==0,
779 ArrayRCP<scalar_t> *emptySizes=
new ArrayRCP<scalar_t> [widx];
780 pSize_ = arcp(emptySizes, 0, widx);
782 ArrayRCP<unsigned char> *emptyIndices=
new ArrayRCP<unsigned char> [widx];
783 pCompactIndex_ = arcp(emptyIndices, 0, widx);
785 bool *info =
new bool [widx];
786 pSizeUniform_ = arcp(info, 0, widx);
787 for (
int w=0; w < widx; w++)
788 pSizeUniform_[w] =
true;
790 if (nGlobalParts_ == 1){
794 size_t *ptr1 = counts.getRawPtr();
795 size_t *ptr2 = counts.getRawPtr() + widx;
798 reduceAll<int, size_t>(*comm_, Teuchos::REDUCE_MAX, widx, ptr1, ptr2);
804 for (
int w=0; w < widx; w++)
805 if (counts[widx+w] > 0){
807 pSizeUniform_[w] =
false;
816 int nprocs = comm_->getSize();
817 int rank = comm_->getRank();
819 for (
int w=0; w < widx; w++){
820 if (pSizeUniform_[w])
continue;
825 part_t length = ids[w].size();
826 part_t *allLength =
new part_t [nprocs];
827 Teuchos::gatherAll<int, part_t>(*comm_, 1, &length,
832 for (
int i=0; i < nprocs; i++)
833 total += allLength[i];
835 part_t *partNums =
new part_t [total];
836 scalar_t *partSizes =
new scalar_t [total];
838 ArrayView<part_t> idArray(partNums, total);
839 ArrayView<scalar_t> sizeArray(partSizes, total);
842 for (
int i=0; i < length; i++){
843 *partNums++ = ids[w][i];
844 *partSizes++ = sizes[w][i];
848 for (
int p=1; p < nprocs; p++){
849 if (allLength[p] > 0){
850 Teuchos::receive<int, part_t>(*comm_, p,
851 allLength[p], partNums);
852 Teuchos::receive<int, scalar_t>(*comm_, p,
853 allLength[p], partSizes);
854 partNums += allLength[p];
855 partSizes += allLength[p];
862 computePartSizes(w, idArray, sizeArray);
866 delete [] idArray.getRawPtr();
867 delete [] sizeArray.getRawPtr();
872 Teuchos::send<int, part_t>(*comm_, length, ids[w].getRawPtr(), 0);
873 Teuchos::send<int, scalar_t>(*comm_, length, sizes[w].getRawPtr(), 0);
877 broadcastPartSizes(w);
881 template <
typename Adapter>
884 env_->localBugAssertion(__FILE__, __LINE__,
"preallocations",
885 pSize_.size()>widx &&
886 pSizeUniform_.size()>widx && pCompactIndex_.size()>widx,
889 int rank = comm_->getRank();
890 int nprocs = comm_->getSize();
891 part_t nparts = nGlobalParts_;
899 if (pSizeUniform_[widx] ==
true)
901 else if (pCompactIndex_[widx].size() > 0)
908 Teuchos::broadcast<int, char>(*comm_, 0, 1, &flag);
914 pSizeUniform_[widx] =
true;
923 unsigned char *idxbuf = NULL;
926 idxbuf =
new unsigned char [nparts];
927 env_->localMemoryAssertion(__FILE__, __LINE__, nparts, idxbuf);
930 env_->localBugAssertion(__FILE__, __LINE__,
"index list size",
932 idxbuf = pCompactIndex_[widx].getRawPtr();
937 Teuchos::broadcast<int, char>(*comm_, 0, nparts,
938 reinterpret_cast<char *
>(idxbuf));
943 pCompactIndex_[widx] = arcp(idxbuf, 0, nparts,
true);
947 unsigned char maxIdx=0;
948 for (part_t p=0; p < nparts; p++)
949 if (idxbuf[p] > maxIdx) maxIdx = idxbuf[p];
951 int numSizes = maxIdx + 1;
953 scalar_t *sizeList = NULL;
956 sizeList =
new scalar_t [numSizes];
957 env_->localMemoryAssertion(__FILE__, __LINE__, numSizes, sizeList);
960 env_->localBugAssertion(__FILE__, __LINE__,
"wrong number of sizes",
963 sizeList = pSize_[widx].getRawPtr();
967 Teuchos::broadcast<int, scalar_t>(*comm_, 0, numSizes, sizeList);
972 pSize_[widx] = arcp(sizeList, 0, numSizes,
true);
981 scalar_t *sizeList = NULL;
984 sizeList =
new scalar_t [nparts];
985 env_->localMemoryAssertion(__FILE__, __LINE__, nparts, sizeList);
988 env_->localBugAssertion(__FILE__, __LINE__,
"wrong number of sizes",
991 sizeList = pSize_[widx].getRawPtr();
995 Teuchos::broadcast<int, scalar_t >(*comm_, 0, nparts, sizeList);
1000 pSize_[widx] = arcp(sizeList, 0, nparts);
1006 template <
typename Adapter>
1008 ArrayView<part_t> ids, ArrayView<scalar_t> sizes)
1010 int len = ids.size();
1013 pSizeUniform_[widx] =
true;
1017 env_->localBugAssertion(__FILE__, __LINE__,
"bad array sizes",
1020 env_->localBugAssertion(__FILE__, __LINE__,
"bad index",
1023 env_->localBugAssertion(__FILE__, __LINE__,
"preallocations",
1024 pSize_.size()>widx &&
1025 pSizeUniform_.size()>widx && pCompactIndex_.size()>widx,
1031 part_t nparts = nGlobalParts_;
1032 unsigned char *buf =
new unsigned char [nparts];
1033 env_->localMemoryAssertion(__FILE__, __LINE__, nparts, buf);
1034 memset(buf, 0, nparts);
1035 ArrayRCP<unsigned char> partIdx(buf, 0, nparts,
true);
1037 scalar_t
epsilon = 10e-5 / nparts;
1038 scalar_t min=sizes[0], max=sizes[0], sum=0;
1040 for (
int i=0; i < len; i++){
1042 scalar_t size = sizes[i];
1044 env_->localInputAssertion(__FILE__, __LINE__,
"invalid part id",
1047 env_->localInputAssertion(__FILE__, __LINE__,
"invalid part size", size>=0,
1054 env_->localInputAssertion(__FILE__, __LINE__,
1055 "multiple sizes provided for one part", partIdx[
id]==0,
BASIC_ASSERTION);
1059 if (size < min) min = size;
1060 if (size > max) max = size;
1069 scalar_t *allSizes =
new scalar_t [2];
1070 env_->localMemoryAssertion(__FILE__, __LINE__, 2, allSizes);
1072 ArrayRCP<scalar_t> sizeArray(allSizes, 0, 2,
true);
1074 int numNonZero = nparts - len;
1077 allSizes[1] = 1.0 / numNonZero;
1079 for (part_t p=0; p < nparts; p++)
1082 for (
int i=0; i < len; i++)
1085 pSize_[widx] = sizeArray;
1086 pCompactIndex_[widx] = partIdx;
1091 if (max - min <= epsilon){
1092 pSizeUniform_[widx] =
true;
1097 scalar_t avg = sum / nparts;
1104 scalar_t *tmp =
new scalar_t [len];
1105 env_->localMemoryAssertion(__FILE__, __LINE__, len, tmp);
1106 memcpy(tmp, sizes.getRawPtr(),
sizeof(scalar_t) * len);
1107 ArrayRCP<scalar_t> partSizes(tmp, 0, len,
true);
1109 std::sort(partSizes.begin(), partSizes.end());
1113 Array<scalar_t> nextUniqueSize;
1114 nextUniqueSize.push_back(partSizes[len-1]);
1115 scalar_t curr = partSizes[len-1];
1117 bool haveAvg =
false;
1118 if (curr - avg <= epsilon)
1121 for (
int i=len-2; i >= 0; i--){
1122 scalar_t val = partSizes[i];
1123 if (curr - val > epsilon){
1124 nextUniqueSize.push_back(val);
1126 if (avgIndex==len && val > avg && val - avg <= epsilon){
1128 avgIndex = nextUniqueSize.size() - 1;
1136 size_t numSizes = nextUniqueSize.size();
1137 int sizeArrayLen = numSizes;
1144 if (!haveAvg) sizeArrayLen++;
1146 scalar_t *allSizes =
new scalar_t [sizeArrayLen];
1147 env_->localMemoryAssertion(__FILE__, __LINE__, sizeArrayLen, allSizes);
1148 ArrayRCP<scalar_t> sizeArray(allSizes, 0, sizeArrayLen,
true);
1150 int newAvgIndex = sizeArrayLen;
1152 for (
int i=numSizes-1, idx=0; i >= 0; i--){
1154 if (newAvgIndex == sizeArrayLen){
1156 if (haveAvg && i==avgIndex)
1159 else if (!haveAvg && avg < nextUniqueSize[i]){
1161 allSizes[idx++] = avg;
1165 allSizes[idx++] = nextUniqueSize[i];
1168 env_->localBugAssertion(__FILE__, __LINE__,
"finding average in list",
1171 for (
int i=0; i < nparts; i++){
1172 buf[i] = newAvgIndex;
1175 sum = (nparts - len) * allSizes[newAvgIndex];
1177 for (
int i=0; i < len; i++){
1179 scalar_t size = sizes[i];
1184 if (size < avg && avg - size <= epsilon)
1185 index = newAvgIndex;
1187 typename ArrayRCP<scalar_t>::iterator found =
1188 std::lower_bound(sizeArray.begin(), sizeArray.end(), size);
1190 env_->localBugAssertion(__FILE__, __LINE__,
"size array",
1193 index = found - sizeArray.begin();
1197 sum += allSizes[index];
1200 for (
int i=0; i < sizeArrayLen; i++){
1201 sizeArray[i] /= sum;
1204 pCompactIndex_[widx] = partIdx;
1205 pSize_[widx] = sizeArray;
1211 tmp =
new scalar_t [nparts];
1212 env_->localMemoryAssertion(__FILE__, __LINE__, nparts, tmp);
1214 sum += ((nparts - len) * avg);
1216 for (
int i=0; i < nparts; i++){
1220 for (
int i=0; i < len; i++){
1221 tmp[ids[i]] = sizes[i]/sum;
1224 pSize_[widx] = arcp(tmp, 0, nparts);
1228 template <
typename Adapter>
1233 size_t len = partList.size();
1241 part_t lMax = std::numeric_limits<part_t>::min();
1242 part_t lMin = std::numeric_limits<part_t>::max();
1245 for (
size_t i = 0; i < len; i++) {
1246 if (partList[i] < lMin) lMin = partList[i];
1247 if (partList[i] > lMax) lMax = partList[i];
1249 Teuchos::reduceAll<int, part_t>(*comm_, Teuchos::REDUCE_MIN, 1, &lMin, &gMin);
1250 Teuchos::reduceAll<int, part_t>(*comm_, Teuchos::REDUCE_MAX, 1, &lMax, &gMax);
1252 nGlobalPartsSolution_ = gMax - gMin + 1;
1257 if (!onePartPerProc_){
1259 int *procs =
new int [len];
1260 env_->localMemoryAssertion(__FILE__, __LINE__, len, procs);
1261 procs_ = arcp<int>(procs, 0, len);
1263 part_t *parts = partList.getRawPtr();
1265 if (procDist_.size() > 0){
1268 for (
size_t i=0; i < len; i++){
1269 partToProcsMap(parts[i], procs[i], procId);
1274 lno_t *partCounter =
new lno_t [nGlobalPartsSolution_];
1275 env_->localMemoryAssertion(__FILE__, __LINE__, nGlobalPartsSolution_,
1278 int numProcs = comm_->getSize();
1282 memset(partCounter, 0,
sizeof(lno_t) * nGlobalPartsSolution_);
1284 for (
typename ArrayRCP<part_t>::size_type i=0; i < partList.size(); i++)
1285 partCounter[parts[i]]++;
1287 lno_t *procCounter =
new lno_t [numProcs];
1288 env_->localMemoryAssertion(__FILE__, __LINE__, numProcs, procCounter);
1291 int proc2 = partDist_[0];
1293 for (part_t part=1; part < nGlobalParts_; part++){
1295 proc2 = partDist_[part+1];
1296 int numprocs = proc2 - proc1;
1298 double dNum = partCounter[part];
1299 double dProcs = numprocs;
1302 double each = floor(dNum/dProcs);
1303 double extra = fmod(dNum,dProcs);
1305 for (
int proc=proc1, i=0; proc<proc2; proc++, i++){
1307 procCounter[proc] = lno_t(each) + 1;
1309 procCounter[proc] = lno_t(each);
1313 delete [] partCounter;
1315 for (
typename ArrayRCP<part_t>::size_type i=0; i < partList.size(); i++){
1316 if (partList[i] >= nGlobalParts_){
1319 procs[i] = comm_->getRank();
1322 part_t partNum = parts[i];
1323 proc1 = partDist_[partNum];
1324 proc2 = partDist_[partNum + 1];
1327 for (proc=proc1; proc < proc2; proc++){
1328 if (procCounter[proc] > 0){
1330 procCounter[proc]--;
1334 env_->localBugAssertion(__FILE__, __LINE__,
"part to proc",
1338 delete [] procCounter;
1348 const Teuchos::ParameterEntry *pe =
1349 env_->getParameters().getEntryPtr(
"remap_parts");
1350 if (pe) doRemap = pe->getValue(&doRemap);
1353 haveSolution_ =
true;
1355 env_->memory(
"After Solution has processed algorithm's answer");
1360 template <
typename Adapter>
1362 double &numParts, part_t &partMin, part_t &partMax)
const 1364 if (onePartPerProc_){
1366 partMin = partMax = procId;
1368 else if (procDist_.size() > 0){
1369 partMin = procDist_[procId];
1370 partMax = procDist_[procId+1] - 1;
1371 numParts = procDist_[procId+1] - partMin;
1376 std::vector<int>::const_iterator entry;
1377 entry = std::upper_bound(partDist_.begin(), partDist_.end(), procId);
1379 size_t partIdx = entry - partDist_.begin();
1380 int numProcs = partDist_[partIdx] - partDist_[partIdx-1];
1381 partMin = partMax = int(partIdx) - 1;
1382 numParts = 1.0 / numProcs;
1386 template <
typename Adapter>
1388 int &procMin,
int &procMax)
const 1390 if (partId >= nGlobalParts_){
1394 procMin = procMax = comm_->getRank();
1396 else if (onePartPerProc_){
1397 procMin = procMax = int(partId);
1399 else if (procDist_.size() > 0){
1400 if (procDistEquallySpread_) {
1402 double fProcs = comm_->getSize();
1403 double fParts = nGlobalParts_;
1404 double each = fParts / fProcs;
1405 procMin = int(partId / each);
1406 while (procDist_[procMin] > partId) procMin--;
1407 while (procDist_[procMin+1] <= partId) procMin++;
1414 typename std::vector<part_t>::const_iterator entry;
1415 entry = std::upper_bound(procDist_.begin(), procDist_.end(), partId);
1417 size_t procIdx = entry - procDist_.begin();
1418 procMin = procMax = int(procIdx) - 1;
1422 procMin = partDist_[partId];
1423 procMax = partDist_[partId+1] - 1;
1427 template <
typename Adapter>
1429 int c1,
int c2)
const 1431 if (c1 < 0 || c1 >= nWeightsPerObj_ || c2 < 0 || c2 >= nWeightsPerObj_ )
1432 throw std::logic_error(
"criteriaHaveSamePartSizes error");
1434 bool theSame =
false;
1439 else if (pSizeUniform_[c1] ==
true && pSizeUniform_[c2] ==
true)
1442 else if (pCompactIndex_[c1].size() == pCompactIndex_[c2].size()){
1444 bool useIndex = pCompactIndex_[c1].size() > 0;
1446 for (part_t p=0; theSame && p < nGlobalParts_; p++)
1447 if (pSize_[c1][pCompactIndex_[c1][p]] !=
1448 pSize_[c2][pCompactIndex_[c2][p]])
1452 for (part_t p=0; theSame && p < nGlobalParts_; p++)
1453 if (pSize_[c1][p] != pSize_[c2][p])
1476 template <
typename Adapter>
1478 bool doCheck,
bool haveNumLocalParts,
bool haveNumGlobalParts,
1479 int numLocalParts,
int numGlobalParts)
1482 typedef SSIZE_T ssize_t;
1484 int nprocs = comm_->getSize();
1485 ssize_t reducevals[4];
1486 ssize_t sumHaveGlobal=0, sumHaveLocal=0;
1487 ssize_t sumGlobal=0, sumLocal=0;
1488 ssize_t maxGlobal=0, maxLocal=0;
1489 ssize_t
vals[4] = {haveNumGlobalParts, haveNumLocalParts,
1490 numGlobalParts, numLocalParts};
1498 reduceAll<int, ssize_t>(*comm_, Teuchos::REDUCE_SUM, 4,
vals, reducevals);
1502 sumHaveGlobal = reducevals[0];
1503 sumHaveLocal = reducevals[1];
1504 sumGlobal = reducevals[2];
1505 sumLocal = reducevals[3];
1507 env_->localInputAssertion(__FILE__, __LINE__,
1508 "Either all procs specify num_global/local_parts or none do",
1509 (sumHaveGlobal == 0 || sumHaveGlobal == nprocs) &&
1510 (sumHaveLocal == 0 || sumHaveLocal == nprocs),
1514 if (haveNumLocalParts)
1515 sumLocal = numLocalParts * nprocs;
1516 if (haveNumGlobalParts)
1517 sumGlobal = numGlobalParts * nprocs;
1519 sumHaveGlobal = haveNumGlobalParts ? nprocs : 0;
1520 sumHaveLocal = haveNumLocalParts ? nprocs : 0;
1522 maxLocal = numLocalParts;
1523 maxGlobal = numGlobalParts;
1526 if (!haveNumLocalParts && !haveNumGlobalParts){
1527 onePartPerProc_ =
true;
1531 if (haveNumGlobalParts){
1533 vals[0] = numGlobalParts;
1534 vals[1] = numLocalParts;
1536 reduceAll<int, ssize_t>(
1537 *comm_, Teuchos::REDUCE_MAX, 2,
vals, reducevals);
1541 maxGlobal = reducevals[0];
1542 maxLocal = reducevals[1];
1544 env_->localInputAssertion(__FILE__, __LINE__,
1545 "Value for num_global_parts is different on different processes.",
1550 env_->localInputAssertion(__FILE__, __LINE__,
1551 "Sum of num_local_parts does not equal requested num_global_parts",
1554 if (sumLocal == nprocs && maxLocal == 1){
1555 onePartPerProc_ =
true;
1560 if (maxGlobal == nprocs){
1561 onePartPerProc_ =
true;
1569 if (sumHaveLocal == nprocs){
1575 procDist_.resize(nprocs+1);
1577 catch (std::exception &e){
1578 throw(std::bad_alloc());
1581 part_t *procArray = &procDist_[0];
1584 part_t tmp = part_t(numLocalParts);
1585 gatherAll<int, part_t>(*comm_, 1, &tmp, nprocs, procArray + 1);
1591 for (
int proc=0; proc < nprocs; proc++)
1592 procArray[proc+1] += procArray[proc];
1598 double fParts = numGlobalParts;
1599 double fProcs = nprocs;
1601 if (fParts < fProcs){
1604 partDist_.resize(
size_t(fParts+1));
1606 catch (std::exception &e){
1607 throw(std::bad_alloc());
1610 int *partArray = &partDist_[0];
1612 double each = floor(fProcs / fParts);
1613 double extra = fmod(fProcs, fParts);
1616 for (part_t part=0; part < numGlobalParts; part++){
1617 int numOwners = int(each + ((part<extra) ? 1 : 0));
1618 partArray[part+1] = partArray[part] + numOwners;
1621 env_->globalBugAssertion(__FILE__, __LINE__,
"#parts != #procs",
1624 else if (fParts > fProcs){
1629 procDistEquallySpread_ =
true;
1632 procDist_.resize(
size_t(fProcs+1));
1634 catch (std::exception &e){
1635 throw(std::bad_alloc());
1638 part_t *procArray = &procDist_[0];
1640 double each = floor(fParts / fProcs);
1641 double extra = fmod(fParts, fProcs);
1644 for (
int proc=0; proc < nprocs; proc++){
1645 part_t numParts = part_t(each + ((proc<extra) ? 1 : 0));
1646 procArray[proc+1] = procArray[proc] + numParts;
1649 env_->globalBugAssertion(__FILE__, __LINE__,
"#parts != #procs",
1653 env_->globalBugAssertion(__FILE__, __LINE__,
1671 template <
typename Adapter>
1674 size_t len = parts_.size();
1676 part_t me = comm_->getRank();
1677 int np = comm_->getSize();
1679 if (np < nGlobalParts_) {
1681 std::cout <<
"Remapping not yet supported for " 1682 <<
"num_global_parts " << nGlobalParts_
1683 <<
" > num procs " << np << std::endl;
1696 std::map<part_t, long> edges;
1701 for (
size_t i = 0; i < len; i++) {
1703 if (parts_[i] == me) lstaying++;
1706 Teuchos::reduceAll<int, long>(*comm_, Teuchos::REDUCE_SUM, 1,
1707 &lstaying, &gstaying);
1710 part_t *remap = NULL;
1712 int nedges = edges.size();
1715 part_t tnVtx = np + nGlobalParts_;
1719 idx =
new int[tnVtx+1];
1720 sizes =
new int[np];
1724 Teuchos::gather<int, int>(&nedges, 1, sizes, 1, 0, *comm_);
1729 for (
int i = 0; i < np; i++)
1730 idx[i+1] = idx[i] + sizes[i];
1735 part_t *bufv = NULL;
1738 bufv =
new part_t[nedges];
1739 bufw =
new long[nedges];
1741 for (
typename std::map<part_t, long>::iterator it = edges.begin();
1742 it != edges.end(); it++) {
1743 bufv[cnt] = it->first;
1744 bufw[cnt] = it->second;
1755 adj =
new part_t[idx[np]];
1756 wgt =
new long[idx[np]];
1759 Teuchos::gatherv<int, part_t>(bufv, cnt, adj, sizes, idx, 0, *comm_);
1760 Teuchos::gatherv<int, long>(bufw, cnt, wgt, sizes, idx, 0, *comm_);
1771 for (
int i = 0; i < idx[np]; i++) {
1776 for (part_t i = np; i < tnVtx; i++) {
1782 for (part_t i = 0; i <= tnVtx; i++) std::cout << idx[i] <<
" ";
1783 std::cout << std::endl;
1785 std::cout <<
"ADJ ";
1786 for (part_t i = 0; i < idx[tnVtx]; i++) std::cout << adj[i] <<
" ";
1787 std::cout << std::endl;
1789 std::cout <<
"WGT ";
1790 for (part_t i = 0; i < idx[tnVtx]; i++) std::cout << wgt[i] <<
" ";
1791 std::cout << std::endl;
1795 part_t *match =
new part_t[tnVtx];
1796 for (part_t i = 0; i < tnVtx; i++) match[i] = i;
1798 Zoltan2::GreedyMWM<part_t, long>(idx, adj, wgt, tnVtx, match);
1801 std::cout <<
"After matching: " << nmatches <<
" found" << std::endl;
1802 for (part_t i = 0; i < tnVtx; i++)
1803 std::cout <<
"match[" << i <<
"] = " << match[i]
1804 << ((match[i] != i &&
1805 (i < np && match[i] != i+np))
1811 bool nontrivial =
false;
1813 for (part_t i = 0; i < np; i++) {
1814 if ((match[i] != i) && (match[i] != (i+np))) {
1823 remap =
new part_t[nGlobalParts_];
1824 for (part_t i = 0; i < nGlobalParts_; i++) remap[i] = -1;
1826 bool *used =
new bool[np];
1827 for (part_t i = 0; i < np; i++) used[i] =
false;
1830 for (part_t i = 0; i < nGlobalParts_; i++) {
1831 part_t tmp = i + np;
1832 if (match[tmp] != tmp) {
1833 remap[i] = match[tmp];
1834 used[match[tmp]] =
true;
1839 for (part_t i = 0; i < nGlobalParts_; i++) {
1840 if (remap[i] > -1)
continue;
1848 for (part_t i = 0, uidx = 0; i < nGlobalParts_; i++) {
1849 if (remap[i] > -1)
continue;
1850 while (used[uidx]) uidx++;
1859 cout <<
"Remap vector: ";
1860 for (part_t i = 0; i < nGlobalParts_; i++) cout << remap[i] <<
" ";
1861 std::cout << std::endl;
1866 doRemap = (newgstaying > gstaying);
1867 std::cout <<
"gstaying " << gstaying <<
" measure(input) " 1869 <<
" newgstaying " << newgstaying
1870 <<
" nontrivial " << nontrivial
1871 <<
" doRemap " << doRemap << std::endl;
1878 Teuchos::broadcast<int, int>(*comm_, 0, 1, &doRemap);
1881 if (me != 0) remap =
new part_t[nGlobalParts_];
1882 Teuchos::broadcast<int, part_t>(*comm_, 0, nGlobalParts_, remap);
1883 for (
size_t i = 0; i < len; i++) {
1884 parts_[i] = remap[parts_[i]];
const int * getProcListView() const
Returns the process list corresponding to the global ID list.
scalar_t getCriteriaPartSize(int idx, part_t part) const
Get the size for a given weight index and a given part.
Defines the Solution base class.
fast typical checks for valid arguments
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
part_t pointAssign(int dim, scalar_t *point) const
Return the part overlapping a given point in space;.
void RemapParts()
Remap a new partition for maximum overlap with an input partition.
Just a placeholder for now.
PartitioningSolution(const RCP< const Environment > &env, RCP< const Comm< int > > &comm, int nUserWeights, const RCP< Algorithm< Adapter > > &algorithm=Teuchos::null)
Constructor when part sizes are not supplied.
more involved, like validate a graph
size_t getLocalNumberOfParts() const
Returns the number of parts to be assigned to this process.
void getPartsForProc(int procId, double &numParts, part_t &partMin, part_t &partMax) const
Get the parts belonging to a process.
void getProcsForPart(part_t partId, part_t &procMin, part_t &procMax) const
Get the processes containing a part.
sub-steps, each method's entry and exit
std::vector< Zoltan2::coordinateModelPartBox< scalar_t, part_t > > & getPartBoxesView() const
returns the part box boundary list.
bool oneToOnePartDistribution() const
Is the part-to-process distribution is one-to-one.
long measure_stays(part_t *remap, int *idx, part_t *adj, long *wgt, part_t nrhs, part_t nlhs)
scalar_t getLocalFractionOfPart() const
If parts are divided across processes, return the fraction of a part on this process.
A PartitioningSolution is a solution to a partitioning problem.
const RCP< const Comm< int > > & getCommunicator() const
Return the communicator associated with the solution.
void boxAssign(int dim, scalar_t *lower, scalar_t *upper, size_t &nPartsFound, part_t **partsFound) const
Return an array of all parts overlapping a given box in space.
const part_t * getPartListView() const
Returns the part list corresponding to the global ID list.
Algorithm defines the base class for all algorithms.
Greedy Maximal Weight Matching.
static const std::string fail
void setParts(ArrayRCP< part_t > &partList)
The algorithm uses setParts to set the solution.
Defines the Environment class.
const part_t * getProcDistribution() const
Return a distribution by process.
void getCommunicationGraph(ArrayRCP< part_t > &comXAdj, ArrayRCP< part_t > &comAdj) const
returns communication graph resulting from geometric partitioning.
int getNumberOfCriteria() const
Get the number of criteria (object weights)
const int * getPartDistribution() const
Return a distribution by part.
#define Z2_THROW_OUTSIDE_ERROR(env)
Throw an error returned from outside the Zoltan2 library.
size_t getActualGlobalNumberOfParts() const
Returns the actual global number of parts provided in setParts().
bool criteriaHasUniformPartSizes(int idx) const
Determine if balancing criteria has uniform part sizes. (User can specify differing part sizes...
bool criteriaHaveSamePartSizes(int c1, int c2) const
Return true if the two weight indices have the same part size information.
size_t getTargetGlobalNumberOfParts() const
Returns the global number of parts desired in the solution.
const RCP< const Environment > & getEnvironment() const
Return the environment associated with the solution.