Debian Codegraph @

3rdparty/dissection/src/Splitters/ScotchSplitter.cpp

raw
1 /*! \file ScotchSplitter.cpp
2 \brief to call grpah decomposer : SCOTCH
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 // == Implementation of splitter using Scotch library ==
52 // ==============================================================
53 #include <stdexcept>
54 #include <cstdio>
55 #include <cstring>
56 #include <algorithm>
57 extern"C" {
58 #include <scotch.h>
59 }
60
61 #include "Compiler/DebugUtils.hpp"
62 #include "Compiler/arithmetic.hpp"
63 #include "Splitters/BitManipulations.hpp"
64 #include "Splitters/ScotchSplitter.hpp"
65 #include "Compiler/DissectionIO.hpp"
66
67 #define TOO_SMALL 16
68
69 static unsigned
70 compLevelOfDoms(int nbDoms, int maxLevels,
71 const int* treetab, int* levels,
72 int*& nbDomsPerLevel)
73 {
74 int iDebScan, iEndScan, iCurScan;
75 // DBG_PRINT("Number of levels : %d\n",maxLevels);
76 // DBG_PRINT("Number of doms : %d\n",nbDoms );
77 // Search the effective number of levels given by Scotch :
78 int nbLvls = 0;
79 for (unsigned i = 0; i < nbDoms; i++) {
80 int locLvl = 1;
81 int indDom = i;
82 while (indDom != nbDoms-1) {
83 locLvl ++;
84 indDom = treetab[indDom];
85 }
86 nbLvls = std::max(nbLvls, locLvl);
87 }
88 // DBG_PRINT("Effective level : %d\n",nbLvls);
89 nbDomsPerLevel = new int[nbLvls];
90 for (int i = 0; i < nbDoms-1; i++)
91 levels[i] = -1;
92 assert(treetab[nbDoms-1]==-1);
93 levels[nbDoms-1] = 0;
94 iDebScan = 0;
95 while (iDebScan < nbDoms) {
96 // Search next domains without level of bissection computation :
97 for ( ;(iDebScan<nbDoms)&&(levels[iDebScan] != -1);iDebScan++);
98 if (iDebScan<nbDoms) {
99 assert(iDebScan < nbDoms);
100 assert(iDebScan >=0);
101 // Run child to father into the tree to set levels on some domains :
102 // We assume than this domain is on a leaf of the tree (uppest layer)
103 levels[iDebScan] = nbLvls-1;//maxLevels-1;
104 // From this domain, we go through all ancestors until
105 // we find a ancestor with defined level (we known here than
106 // the root interface has his level defined at 0)
107 iCurScan = iDebScan;
108 iEndScan = treetab[iDebScan];
109 while (-1==levels[iEndScan]) {
110 assert(iEndScan<nbDoms);
111 levels[iEndScan] = levels[iCurScan]-1;
112 iCurScan = iEndScan;// Current is current ancestor now
113 iEndScan = treetab[iCurScan];// <-- next ancestor
114 }
115 if (levels[iCurScan]!=levels[iEndScan]+1) { // Ooops, wrong level for the first domain
116 int diff = levels[iCurScan]-levels[iEndScan]-1;// Correction to do
117 assert(diff > 0);
118 iCurScan = iDebScan;
119 while (iCurScan != iEndScan) {
120 levels[iCurScan] -= diff;
121 iCurScan = treetab[iCurScan];
122 }
123 }
124 }// if iDebScan<nbDoms
125 // ok, next domain, please ?
126 }
127 // Count number of domains per levels :
128 memset(nbDomsPerLevel,0,nbLvls*sizeof(int));
129 for (int i = 0; i < nbDoms; i++) {
130 assert(levels[i] >= 0);
131 CHECK((levels[i]<nbLvls),"Wrong levels value ?");
132 CHECK((i<nbDoms), "Wrong value for i");
133 nbDomsPerLevel[levels[i]] += 1;
134 }
135 return nbLvls;
136 }
137
138 bool
139 ScotchSplitter(unsigned dim,
140 const int* ptRows, const int* indCols,
141 unsigned& nbMaxLevels, unsigned minSize,
142 int* loc2glob, int* glob2loc, int& nbDoms,
143 int*& ptOnDomains, int*& sizeOfDomains,
144 bool checkData, const bool verbose, FILE *fp)
145 {
146 int ierr;
147 // check consistency between Scotch and Dissection library
148 CHECK(sizeof(int) == sizeof(SCOTCH_Num),
149 "Incompatible integer representation between Scotch and Dissection");
150 if (verbose) {
151 int vers, rela, patc;
152 SCOTCH_version(&vers, &rela, &patc);
153 diss_printf(verbose, fp, "%s %d : Soctch version : %d.%d.%d\n",
154 __FILE__, __LINE__, vers, rela, patc);
155 }
156 // Allocate and initialize the Scotch graph
157 SCOTCH_Graph ptGraph;
158 ierr = SCOTCH_graphInit(&ptGraph);
159 CHECK(ierr==0,"Fail initializing Scotch graph");
160 // TRACE("Building Scotch graph\n");
161 ierr = SCOTCH_graphBuild(&ptGraph,
162 (SCOTCH_Num)0, // offset,
163 (SCOTCH_Num)dim,
164 (const SCOTCH_Num*)ptRows,
165 (const SCOTCH_Num*)ptRows+1,
166 NULL, NULL, (SCOTCH_Num)ptRows[dim],
167 (const SCOTCH_Num*)indCols, NULL);
168 // if (verbose) {
169 // fprintf(fp, "%s %d : 1 : ptRows = %p indCols = %p\n",
170 // __FILE__, __LINE__, (void *)ptRows, (void *)indCols);
171 // }
172 CHECK(ierr==0,"Scotch graph building failed !");
173 if (checkData) {
174 //TRACE("Check Scotch graph\n");
175 ierr = SCOTCH_graphCheck(&ptGraph);
176 if (ierr) {
177 diss_printf(verbose, fp,
178 "Failed the checking of the graph : bad data ?\n");
179 SCOTCH_graphFree(&ptGraph);
180 return false;
181 }
182 }
183 // Allocate and initialize the strategy wanted for Scotch
184 // TRACE("Initialize strategy for splitting\n");
185 SCOTCH_Strat ptStrat;
186 ierr = SCOTCH_stratInit(&ptStrat);
187 CHECK(ierr==0,
188 "Failed initializing Scotch strategy structure");
189
190 char *str_Strat = new char[1024];
191 int nbLvls = std::min(unsigned(nbMaxLevels),
192 highestbit(unsigned(dim/minSize)));
193 diss_printf(verbose, fp, "nbLevels = %d\n", nbLvls);
194 sprintf(str_Strat,"c{rat=0.7,cpr=n{sep=/((levl<%d)|(vert>%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}}",
195 nbLvls-1,2*minSize-1,minSize,dim,nbLvls-1,minSize,dim);
196 // DBG_PRINT("Strategy string : %s\n", str_Strat);
197 ierr = SCOTCH_stratGraphOrder(&ptStrat, str_Strat);
198 delete [] str_Strat;
199 CHECK(ierr==0,
200 "Failed build graph ordering strategy for Scotch");
201 // Ordering with nested bisection :
202 // TRACE("Split the graph\n");
203 int* rangtab = new int[dim+1];
204 int* treetab = new int[dim];
205 int nbSplitDoms;
206 bool repeat = true;
207 int lastCompleteLevel;
208 int *levels, *nbDomsPerLevels;
209 SCOTCH_randomReset();
210 while (repeat) {
211 ierr = SCOTCH_graphOrder(&ptGraph, &ptStrat,
212 (SCOTCH_Num*)loc2glob,
213 (SCOTCH_Num*)glob2loc,
214 (SCOTCH_Num*)&nbSplitDoms,
215 (SCOTCH_Num*)rangtab,
216 (SCOTCH_Num*)treetab);
217 if (ierr) {
218 diss_printf(verbose, fp, "Failed reordering sparse matrix graph !\n");
219 SCOTCH_stratExit(&ptStrat);
220 SCOTCH_graphFree(&ptGraph);
221 return false;
222 }
223
224 levels = new int[nbSplitDoms];
225 // int *nbDomsPerLevels;// = new int[nbLvls];
226 unsigned nbLvlsScotch= compLevelOfDoms(nbSplitDoms, nbLvls, treetab, levels,
227 nbDomsPerLevels);
228 /** Search last level where number of domains is a power of two
229 */
230 lastCompleteLevel = 0;
231 while ((lastCompleteLevel<nbLvlsScotch) &&
232 ((1<<lastCompleteLevel) == nbDomsPerLevels[lastCompleteLevel]) ) {
233 lastCompleteLevel ++;
234 }
235 lastCompleteLevel = std::min(lastCompleteLevel, nbLvls);
236
237 nbDoms = (1<<lastCompleteLevel)-1;
238
239 // Search where start each domain per bisection level
240 // and compute the size of each subdomain :
241 // int indDom = 0;
242 bool flag_size_check = false;
243 for (int i = 0; i < nbSplitDoms; i++) {
244 int sz = 0;
245 while (levels[i]>=lastCompleteLevel) {
246 sz += rangtab[i+1]-rangtab[i];
247 i++;
248 }
249 if (sz+rangtab[i+1]-rangtab[i] <= TOO_SMALL) {
250 flag_size_check = true;
251 break;
252 }
253 //DBG_PRINT("Domain %d begin at %d\n",indDom+1,begDom);
254 } // loop : i
255 if (!flag_size_check) {
256 repeat = false;
257 break;
258 }
259 else {
260 delete [] levels;
261 delete [] nbDomsPerLevels;
262 }
263 } // while (repeat)
264 ptOnDomains = new int[nbDoms+1];
265 sizeOfDomains = new int[nbDoms];
266 memset(sizeOfDomains, 0, nbDoms*sizeof(int));
267 int* indDomPerLevel = new int[lastCompleteLevel+1];
268 memset(indDomPerLevel,0,(lastCompleteLevel+1)*sizeof(int));
269 int begDom = 0;
270 for (int i = 0; i < nbSplitDoms; i++) {
271 int sz = 0;
272 while (levels[i]>=lastCompleteLevel) {
273 sz += rangtab[i+1]-rangtab[i];
274 i++;
275 }
276 int indDom = (1<<levels[i])-1+indDomPerLevel[levels[i]];
277 // DBG_PRINT("level %d : current dom = %d\n", levels[i],indDom+1);
278 ptOnDomains[indDom] = begDom;
279 //DBG_PRINT("Domain %d begin at %d\n",indDom+1,begDom);
280 sizeOfDomains[indDom] = sz+rangtab[i+1]-rangtab[i];
281 //DBG_PRINT("Domain %d size of %d\n",indDom+1,sizeOfDomains[indDom]);
282 begDom += sizeOfDomains[indDom];
283 indDomPerLevel[levels[i]] += 1;
284 }
285 diss_printf(verbose, fp, "%s %d : indDomPerlevel[lastCompleteLevel] = %d\n",
286 __FILE__, __LINE__, indDomPerLevel[lastCompleteLevel]);
287 ptOnDomains[nbDoms] = dim;
288 nbMaxLevels = lastCompleteLevel;
289 delete [] indDomPerLevel;
290 delete [] nbDomsPerLevels;
291 delete [] levels;
292 delete [] treetab;
293 delete [] rangtab;
294 // Cleaning all Scotch structures :
295 SCOTCH_stratExit(&ptStrat);
296 SCOTCH_graphFree(&ptGraph);
297 return true;
298 }