/*! \file ScotchSplitter.cpp
\brief to call grpah decomposer : SCOTCH
\author Xavier Juvigny, ONERA
\date Jul. 2nd 2012
\date Nov. 30th 2016
*/
// This file is part of Dissection
//
// Dissection is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Linking Dissection statically or dynamically with other modules is making
// a combined work based on Disssection. Thus, the terms and conditions of
// the GNU General Public License cover the whole combination.
//
// As a special exception, the copyright holders of Dissection give you
// permission to combine Dissection program with free software programs or
// libraries that are released under the GNU LGPL and with independent modules
// that communicate with Dissection solely through the Dissection-fortran
// interface. You may copy and distribute such a system following the terms of
// the GNU GPL for Dissection and the licenses of the other code concerned,
// provided that you include the source code of that other code when and as
// the GNU GPL requires distribution of source code and provided that you do
// not modify the Dissection-fortran interface.
//
// Note that people who make modified versions of Dissection are not obligated
// to grant this special exception for their modified versions; it is their
// choice whether to do so. The GNU General Public License gives permission to
// release a modified version without this exception; this exception also makes
// it possible to release a modified version which carries forward this
// exception. If you modify the Dissection-fortran interface, this exception
// does not apply to your modified version of Dissection, and you must remove
// this exception when you distribute your modified version.
//
// This exception is an additional permission under section 7 of the GNU
// General Public License, version 3 ("GPLv3")
//
// Dissection is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Dissection. If not, see .
//
// ==============================================================
// == Implementation of splitter using Scotch library ==
// ==============================================================
#include
#include
#include
#include
extern"C" {
#include
}
#include "Compiler/DebugUtils.hpp"
#include "Compiler/arithmetic.hpp"
#include "Splitters/BitManipulations.hpp"
#include "Splitters/ScotchSplitter.hpp"
#include "Compiler/DissectionIO.hpp"
#define TOO_SMALL 16
static unsigned
compLevelOfDoms(int nbDoms, int maxLevels,
const int* treetab, int* levels,
int*& nbDomsPerLevel)
{
int iDebScan, iEndScan, iCurScan;
// DBG_PRINT("Number of levels : %d\n",maxLevels);
// DBG_PRINT("Number of doms : %d\n",nbDoms );
// Search the effective number of levels given by Scotch :
int nbLvls = 0;
for (unsigned i = 0; i < nbDoms; i++) {
int locLvl = 1;
int indDom = i;
while (indDom != nbDoms-1) {
locLvl ++;
indDom = treetab[indDom];
}
nbLvls = std::max(nbLvls, locLvl);
}
// DBG_PRINT("Effective level : %d\n",nbLvls);
nbDomsPerLevel = new int[nbLvls];
for (int i = 0; i < nbDoms-1; i++)
levels[i] = -1;
assert(treetab[nbDoms-1]==-1);
levels[nbDoms-1] = 0;
iDebScan = 0;
while (iDebScan < nbDoms) {
// Search next domains without level of bissection computation :
for ( ;(iDebScan=0);
// Run child to father into the tree to set levels on some domains :
// We assume than this domain is on a leaf of the tree (uppest layer)
levels[iDebScan] = nbLvls-1;//maxLevels-1;
// From this domain, we go through all ancestors until
// we find a ancestor with defined level (we known here than
// the root interface has his level defined at 0)
iCurScan = iDebScan;
iEndScan = treetab[iDebScan];
while (-1==levels[iEndScan]) {
assert(iEndScan 0);
iCurScan = iDebScan;
while (iCurScan != iEndScan) {
levels[iCurScan] -= diff;
iCurScan = treetab[iCurScan];
}
}
}// if iDebScan= 0);
CHECK((levels[i]%d))?m{type=h,rat=0.7,vert=100,low=h{pass=10},asc=b{width=3,bnd=f{bal=0.2},org=h{pass=10}f{bal=0.2}}}|m{type=h,rat=0.7,vert=100,low=h{pass=10},asc=b{width=3,bnd=f{bal=0.2},org=h{pass=10}f{bal=0.2}}};,ole=f{cmin=%d,cmax=%d,frat=0.05},ose=s},unc=n{sep=/(levl<%d)?(m{type=h,rat=0.7,vert=100,low=h{pass=10},asc=b{width=3,bnd=f{bal=0.2},org=h{pass=10}f{bal=0.2}}})|m{type=h,rat=0.7,vert=100,low=h{pass=10},asc=b{width=3,bnd=f{bal=0.2},org=h{pass=10}f{bal=0.2}}};,ole=f{cmin=%d,cmax=%d,frat=0.05},ose=s}}",
nbLvls-1,2*minSize-1,minSize,dim,nbLvls-1,minSize,dim);
// DBG_PRINT("Strategy string : %s\n", str_Strat);
ierr = SCOTCH_stratGraphOrder(&ptStrat, str_Strat);
delete [] str_Strat;
CHECK(ierr==0,
"Failed build graph ordering strategy for Scotch");
// Ordering with nested bisection :
// TRACE("Split the graph\n");
int* rangtab = new int[dim+1];
int* treetab = new int[dim];
int nbSplitDoms;
bool repeat = true;
int lastCompleteLevel;
int *levels, *nbDomsPerLevels;
SCOTCH_randomReset();
while (repeat) {
ierr = SCOTCH_graphOrder(&ptGraph, &ptStrat,
(SCOTCH_Num*)loc2glob,
(SCOTCH_Num*)glob2loc,
(SCOTCH_Num*)&nbSplitDoms,
(SCOTCH_Num*)rangtab,
(SCOTCH_Num*)treetab);
if (ierr) {
diss_printf(verbose, fp, "Failed reordering sparse matrix graph !\n");
SCOTCH_stratExit(&ptStrat);
SCOTCH_graphFree(&ptGraph);
return false;
}
levels = new int[nbSplitDoms];
// int *nbDomsPerLevels;// = new int[nbLvls];
unsigned nbLvlsScotch= compLevelOfDoms(nbSplitDoms, nbLvls, treetab, levels,
nbDomsPerLevels);
/** Search last level where number of domains is a power of two
*/
lastCompleteLevel = 0;
while ((lastCompleteLevel=lastCompleteLevel) {
sz += rangtab[i+1]-rangtab[i];
i++;
}
if (sz+rangtab[i+1]-rangtab[i] <= TOO_SMALL) {
flag_size_check = true;
break;
}
//DBG_PRINT("Domain %d begin at %d\n",indDom+1,begDom);
} // loop : i
if (!flag_size_check) {
repeat = false;
break;
}
else {
delete [] levels;
delete [] nbDomsPerLevels;
}
} // while (repeat)
ptOnDomains = new int[nbDoms+1];
sizeOfDomains = new int[nbDoms];
memset(sizeOfDomains, 0, nbDoms*sizeof(int));
int* indDomPerLevel = new int[lastCompleteLevel+1];
memset(indDomPerLevel,0,(lastCompleteLevel+1)*sizeof(int));
int begDom = 0;
for (int i = 0; i < nbSplitDoms; i++) {
int sz = 0;
while (levels[i]>=lastCompleteLevel) {
sz += rangtab[i+1]-rangtab[i];
i++;
}
int indDom = (1<