| 1 |
/*! \file BisectionTree.hpp |
| 2 |
\brief ordeing by graph decomposer, SCOTCH or METIS |
| 3 |
\author Xavier Juvigny, ONERA |
| 4 |
\date Jul. 2nd 2012 |
| 5 |
\date Nov. 30th 2016 |
| 6 |
*/ |
| 7 |
|
| 8 |
// This file is part of Dissection |
| 9 |
// |
| 10 |
// Dissection is free software: you can redistribute it and/or modify |
| 11 |
// it under the terms of the GNU General Public License as published by |
| 12 |
// the Free Software Foundation, either version 3 of the License, or |
| 13 |
// (at your option) any later version. |
| 14 |
// |
| 15 |
// Linking Dissection statically or dynamically with other modules is making |
| 16 |
// a combined work based on Disssection. Thus, the terms and conditions of |
| 17 |
// the GNU General Public License cover the whole combination. |
| 18 |
// |
| 19 |
// As a special exception, the copyright holders of Dissection give you |
| 20 |
// permission to combine Dissection program with free software programs or |
| 21 |
// libraries that are released under the GNU LGPL and with independent modules |
| 22 |
// that communicate with Dissection solely through the Dissection-fortran |
| 23 |
// interface. You may copy and distribute such a system following the terms of |
| 24 |
// the GNU GPL for Dissection and the licenses of the other code concerned, |
| 25 |
// provided that you include the source code of that other code when and as |
| 26 |
// the GNU GPL requires distribution of source code and provided that you do |
| 27 |
// not modify the Dissection-fortran interface. |
| 28 |
// |
| 29 |
// Note that people who make modified versions of Dissection are not obligated |
| 30 |
// to grant this special exception for their modified versions; it is their |
| 31 |
// choice whether to do so. The GNU General Public License gives permission to |
| 32 |
// release a modified version without this exception; this exception also makes |
| 33 |
// it possible to release a modified version which carries forward this |
| 34 |
// exception. If you modify the Dissection-fortran interface, this exception |
| 35 |
// does not apply to your modified version of Dissection, and you must remove |
| 36 |
// this exception when you distribute your modified version. |
| 37 |
// |
| 38 |
// This exception is an additional permission under section 7 of the GNU |
| 39 |
// General Public License, version 3 ("GPLv3") |
| 40 |
// |
| 41 |
// Dissection is distributed in the hope that it will be useful, |
| 42 |
// but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 43 |
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 44 |
// GNU General Public License for more details. |
| 45 |
// |
| 46 |
// You should have received a copy of the GNU General Public License |
| 47 |
// along with Dissection. If not, see <http://www.gnu.org/licenses/>. |
| 48 |
// |
| 49 |
|
| 50 |
// ============================================================== |
| 51 |
// == Bisection tree : stored by components in 1D arrays == |
| 52 |
// ============================================================== |
| 53 |
#ifndef _DISSECTION_SPLITTERS_BISECTIONTREE_HPP_ |
| 54 |
#define _DISSECTION_SPLITTERS_BISECTIONTREE_HPP_ |
| 55 |
#include <cstdio> |
| 56 |
#include "Splitters/BitManipulations.hpp" |
| 57 |
#include "Splitters/BisectionInterConnection.hpp" |
| 58 |
#include "Splitters/Splitter.hpp" |
| 59 |
#include "Algebra/CSR_matrix.hpp" |
| 60 |
|
| 61 |
namespace Dissection |
| 62 |
{ |
| 63 |
/** @brief Nested Bisection tree |
| 64 |
|
| 65 |
The nested bisection tree is the core of the |
| 66 |
symbolic factorization. |
| 67 |
Nodes are numbered from root,starting at 1, |
| 68 |
to leaves by layer order. |
| 69 |
|
| 70 |
By example : (layer level) |
| 71 |
----------- 1 0 |
| 72 |
/ \ |
| 73 |
2 3 1 |
| 74 |
/\ /\ |
| 75 |
4 5 6 7 2 |
| 76 |
|
| 77 |
Data are stored components by components, ordered as above : |
| 78 |
[D1,D2,D3,D4,D5,D6,D7] |
| 79 |
|
| 80 |
Each layer l data begin at 2^l (0 <= l < number of layers) |
| 81 |
|
| 82 |
A node n is in layer highest_one_idx(n) |
| 83 |
|
| 84 |
The brother of a node n (node sharing same father) is n^1 |
| 85 |
(^ means xor operation as C convention). |
| 86 |
|
| 87 |
Ancestors are n>>p where |
| 88 |
0 < p < number of layers - level of domain |
| 89 |
*/ |
| 90 |
class Tree |
| 91 |
{ |
| 92 |
public: |
| 93 |
/**@name Constructors and destructor */ |
| 94 |
//@{ |
| 95 |
/** @brief Build bisection tree |
| 96 |
|
| 97 |
From the sparse matrix CSR structure, |
| 98 |
build the bisection tree for symbolic factorization |
| 99 |
computing some block permutations to speed-up data |
| 100 |
transfert between blocks. |
| 101 |
|
| 102 |
@param dim Dimension of the sparse matrix |
| 103 |
@param ptRows Indices pointing on the beginning of |
| 104 |
each row of the sparse matrix. |
| 105 |
The last value ptRows[dim] provides the |
| 106 |
number of non zero coefficients of the |
| 107 |
sparse matrix. |
| 108 |
@param indCols Column indice of each non zero coefficients |
| 109 |
of the sparse matrix. Values must be stored |
| 110 |
and sorted (increasing) by row |
| 111 |
@param nbMaxLevel Maximal number of iteration for the |
| 112 |
bisection method. |
| 113 |
@param minSize Minimal number of nodes per subdomains |
| 114 |
in the leaves of the tree. |
| 115 |
@param spltFct The nested bisection library function to use |
| 116 |
By default, Scotch is used to do nested |
| 117 |
bisection |
| 118 |
@param checkData If true, verify some consistencies in the given sparse |
| 119 |
matrix structure. If false, assume than |
| 120 |
provided sparse matrix structure is |
| 121 |
consistency. |
| 122 |
*/ |
| 123 |
Tree(FILE *fp, bool &berr, unsigned dim, |
| 124 |
const CSR_indirect *csr, |
| 125 |
const bool isSym, //const bool isLower, |
| 126 |
const int *remap_eqn, //const int *remap_indcols, |
| 127 |
unsigned nbMaxLevel=8, unsigned minSize = 120, |
| 128 |
splitter spltFct = NULL, |
| 129 |
bool checkData = false, bool verbose = true); |
| 130 |
|
| 131 |
/** @brief Destructor |
| 132 |
*/ |
| 133 |
~Tree(); |
| 134 |
//@} |
| 135 |
|
| 136 |
/** @name Getters and setters */ |
| 137 |
//@{ |
| 138 |
/// Return index of the brother (i.e having same father) node |
| 139 |
/// of a node nd. |
| 140 |
static int selfIndex(unsigned nd) { |
| 141 |
return (int)(nd - 1); |
| 142 |
} |
| 143 |
static int Index2Node(unsigned nd) { |
| 144 |
return (int)(nd + 1); |
| 145 |
} |
| 146 |
static unsigned brotherIndex(unsigned nd) { |
| 147 |
return (nd ^ 1); |
| 148 |
} |
| 149 |
/// Return index of the father node index of a node nd |
| 150 |
static unsigned fatherIndex(unsigned nd) { |
| 151 |
return (nd / 2); |
| 152 |
} |
| 153 |
/// Return index of nth forerunner of domain nd : |
| 154 |
static unsigned nthfatherIndex(unsigned nd, unsigned nth) { |
| 155 |
return (nd >> nth); |
| 156 |
} |
| 157 |
/// Return index of the first child index for node nd : |
| 158 |
static unsigned childIndex(unsigned nd) { |
| 159 |
return (nd * 2); |
| 160 |
} |
| 161 |
/// Return layer number where lies the domain nd : |
| 162 |
static unsigned nodeLayer(unsigned nd) { |
| 163 |
return highest_one_idx(nd); |
| 164 |
} |
| 165 |
/// Return |
| 166 |
unsigned NumberOfLevels() { |
| 167 |
return _nbLevels; |
| 168 |
} |
| 169 |
unsigned NumberOfSubdomains() { |
| 170 |
return _nbDoms; |
| 171 |
} |
| 172 |
// |
| 173 |
unsigned NumberOfSubdomains(unsigned level) { |
| 174 |
// (_sbLevels - 1) == (void) |
| 175 |
if (level < _nbLevels) { |
| 176 |
return ((1 << (level + 1)) - 1); // including own level |
| 177 |
} |
| 178 |
else { |
| 179 |
return 0U; |
| 180 |
} |
| 181 |
} |
| 182 |
|
| 183 |
/// Return number of internal nodes of a domain nd (>=1) |
| 184 |
unsigned sizeOfDomain(unsigned nd) const { |
| 185 |
return _sizeOfDomains[selfIndex(nd)]; |
| 186 |
} |
| 187 |
|
| 188 |
unsigned sizeOfFathersStrips(unsigned nd) const { |
| 189 |
return _sizeOfFathersStrips[selfIndex(nd)]; |
| 190 |
} |
| 191 |
|
| 192 |
/// Return connection between a domain nd (nd >= 1) and his ancestors |
| 193 |
const FathersStrips& getFathersStrips(unsigned nd) { |
| 194 |
return _interco[selfIndex(nd)]; |
| 195 |
} |
| 196 |
const CSR_indirect& getDiagCSR(unsigned nd) { |
| 197 |
return _csr_diag[selfIndex(nd)]; |
| 198 |
} |
| 199 |
const CSR_indirect& getOffdiagCSR(unsigned nd) { |
| 200 |
return _csr_offdiag[selfIndex(nd)]; |
| 201 |
} |
| 202 |
int *getDiagLoc2Glob(unsigned nd) { |
| 203 |
return _loc2glob_diag[selfIndex(nd)]; |
| 204 |
} |
| 205 |
int *getOffdiagLoc2Glob(unsigned nd) { |
| 206 |
return _loc2glob_offdiag[selfIndex(nd)]; |
| 207 |
} |
| 208 |
|
| 209 |
bool save(FILE* stream) const; |
| 210 |
/** @brief Load bisection tree contents */ |
| 211 |
bool load(FILE* stream) ; |
| 212 |
/** @brief Print information on bisection tree |
| 213 |
|
| 214 |
A verbose level can be provided. Depending of |
| 215 |
his value, informations printed are : |
| 216 |
|
| 217 |
>=1 : Some statistics data (number of domains, |
| 218 |
mean number of nodes per domains per layer, |
| 219 |
variance of number of nodes per domains,...) |
| 220 |
>=2 : Global indices of nodes contained per domains |
| 221 |
|
| 222 |
>=3 : Block permutation from a domain and his forerunnings |
| 223 |
|
| 224 |
@param verboseLevel Choose the level of verbose |
| 225 |
to print some information for |
| 226 |
dissection tree. |
| 227 |
*/ |
| 228 |
void printInfo(FILE* stream, |
| 229 |
unsigned verboseLevel = 1) const; |
| 230 |
|
| 231 |
//@} |
| 232 |
private: |
| 233 |
bool _verbose; |
| 234 |
/* Allocate and fill an array with indices of domain |
| 235 |
containing each local index. |
| 236 |
The caller of this method must free the returned array. |
| 237 |
*/ |
| 238 |
unsigned* compLoc2Dom(unsigned dim) const; |
| 239 |
/* Remove self references from the skeleton graph of the sparse matrix |
| 240 |
provided to the splitter |
| 241 |
*/ |
| 242 |
void removeLoops(int dim, |
| 243 |
const int* ptRows, const int* indCols, |
| 244 |
int*& ptRows2, int*& indCols2); |
| 245 |
/* Do symbolic factorization */ |
| 246 |
FathersStrips* symbolicFactorization(SetOfStrips** connections); |
| 247 |
/* Renumbering interfaces to optimize number of strips */ |
| 248 |
void renumberingInterface(unsigned nperm, unsigned* perm, |
| 249 |
const SetOfStrips& paral, |
| 250 |
const SetOfStrips& parar, |
| 251 |
const SetOfStrips& seq, |
| 252 |
unsigned layer, unsigned iDom) const; |
| 253 |
void draw_csr(char *filename, |
| 254 |
int dim, |
| 255 |
const int *ptRows, |
| 256 |
const int *indCols, |
| 257 |
const int *ptRow_diag, |
| 258 |
const int *indVals, |
| 259 |
const unsigned *l2d); |
| 260 |
|
| 261 |
/// Number of levels done in nested bisection algorithm |
| 262 |
|
| 263 |
unsigned _nbDoms; |
| 264 |
unsigned _nbLevels; |
| 265 |
/// Number of nodes (internal only for each leaf) |
| 266 |
int *_sizeOfDomains; |
| 267 |
int *_sizeOfFathersStrips; |
| 268 |
/// Indice (starting at 0) of the beginning of each domain |
| 269 |
/// in local 2 global correspondance. |
| 270 |
int *_ptOnDomains; |
| 271 |
/// Local 2 global array for each subdomain (partition) |
| 272 |
int *_local2global; |
| 273 |
/// global 2 local array (partition) |
| 274 |
int *_global2local; |
| 275 |
/// |
| 276 |
FathersStrips* _interco; |
| 277 |
/// For global indices, store the domain containing it : |
| 278 |
int* _glob2dom; |
| 279 |
int **_loc2glob_diag; |
| 280 |
int **_loc2glob_offdiag; |
| 281 |
bool _isSym; |
| 282 |
CSR_indirect *_csr_diag; |
| 283 |
CSR_indirect *_csr_offdiag; |
| 284 |
}; |
| 285 |
} |
| 286 |
|
| 287 |
#endif |