PaStiX Handbook  6.3.2
cand_gendot.c
Go to the documentation of this file.
1 /**
2  *
3  * @file cand_gendot.c
4  *
5  * PaStiX analyse routines
6  * PaStiX is a software package provided by Inria Bordeaux - Sud-Ouest,
7  * LaBRI, University of Bordeaux 1 and IPB.
8  *
9  * Contains functions to generate dot files of the elimination tree and the
10  * compressed elimination tree.
11  *
12  * @copyright 2004-2023 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
13  * Univ. Bordeaux. All rights reserved.
14  *
15  * @version 6.3.2
16  * @author Mathieu Faverge
17  * @date 2023-07-21
18  *
19  * @addtogroup blend_dev_elim
20  * @{
21  *
22  **/
23 #include "common.h"
24 #include "symbol/symbol.h"
25 #include "blend/elimintree.h"
26 #include "blend/cost.h"
27 #include "blend/cand.h"
28 
29 /**
30  *******************************************************************************
31  *
32  * @brief Compute the number of nodes in the compressed tree. The compression is
33  * based on identical candidates for computations.
34  *
35  *******************************************************************************
36  *
37  * @param[in] etree
38  * The pointer to the elimination tree.
39  *
40  * @param[in] candtab
41  * The candidate array associated to the elimination tree for
42  * additional information.
43  *
44  * @param[in] rootnum
45  * The root index of the subtree to compress.
46  *
47  *******************************************************************************
48  *
49  * @return The number of nodes of the subtree.
50  *
51  *******************************************************************************/
52 static inline pastix_int_t
54  const Cand *candtab,
55  pastix_int_t rootnum )
56 {
57  pastix_int_t i, merge, fcand, lcand;
58  pastix_int_t sonsnbr, nbnodes;
59 
60  fcand = candtab[rootnum].fcandnum;
61  lcand = candtab[rootnum].lcandnum;
62 
63  sonsnbr = etree->nodetab[rootnum].sonsnbr;
64  merge = 1;
65  nbnodes = 1;
66  for( i=0; i<sonsnbr; i++ )
67  {
68  pastix_int_t son = eTreeSonI(etree, rootnum, i);
69  nbnodes += compress_getNodeNbr( etree, candtab, son );
70 
71  if ( (fcand != candtab[son].fcandnum) ||
72  (lcand != candtab[son].lcandnum) )
73  {
74  merge = 0;
75  }
76  }
77 
78  /* If all sons have the same candidate set, then they will be merged within the current node */
79  if (merge) {
80  nbnodes -= sonsnbr;
81  }
82  return nbnodes;
83 }
84 
85 /**
86  *******************************************************************************
87  *
88  * @brief Compress a subtree. The compression is based on identical candidates
89  * for computations.
90  *
91  *******************************************************************************
92  *
93  * @param[in] etree
94  * The pointer to the elimination tree.
95  *
96  * @param[in] candtab
97  * The candidate array associated to the elimination tree for
98  * additional information. (optionnal)
99  *
100  * @param[in] rootnum
101  * The root index of the subtree to compress.
102  *
103  * @param[inout] ctree
104  * The pointer to the compressed elimination tree.
105  *
106  * @param[inout] ccand
107  * The pointer to the compressed candidate array associated to ctree.
108  *
109  * @param[in] fathnum
110  * The index of the father in the compressed elimination tree.
111  *
112  * @param[inout] cnodeidx
113  * The index of the next available spot in the compressed elimation
114  * tree array to store the nodes.
115  *
116  * @param[inout] tmp
117  * A temporary array of the size of the number of nodes in etree for
118  * the initial root. It is used to store the elements visited in the
119  * tree.
120  *
121  *******************************************************************************/
122 static inline void
124  const Cand *candtab,
125  pastix_int_t rootnum,
126  EliminTree *ctree,
127  Cand *ccand,
128  pastix_int_t fathnum,
129  pastix_int_t *cnodeidx,
130  pastix_int_t *tmp )
131 {
132  eTreeNode_t *cnode;
133  double total;
134  pastix_int_t i, merge, fcand, lcand;
135  pastix_int_t sonsnbr, gdsonsnbr;
136  (*cnodeidx)++;
137  assert( *cnodeidx < ctree->nodenbr );
138 
139  fcand = candtab[rootnum].fcandnum;
140  lcand = candtab[rootnum].lcandnum;
141 
142  /* Copy current node */
143  cnode = ctree->nodetab + (*cnodeidx);
144  cnode->ndecost = etree->nodetab[rootnum].ndecost;
145  cnode->subcost = etree->nodetab[rootnum].subcost;
146  cnode->subpath = etree->nodetab[rootnum].subpath;
147  cnode->fathnum = fathnum;
148 
149  ccand[ *cnodeidx ].fcandnum = fcand;
150  ccand[ *cnodeidx ].lcandnum = lcand;
151 
152  sonsnbr = etree->nodetab[rootnum].sonsnbr;
153  if (sonsnbr == 0) {
154  return;
155  }
156 
157  memcpy( tmp, etree->sonstab + etree->nodetab[rootnum].fsonnum,
158  sonsnbr * sizeof(pastix_int_t) );
159  do {
160  total = 0.;
161  gdsonsnbr = 0;
162  merge = 1;
163  for( i=0; i<sonsnbr; i++ )
164  {
165  pastix_int_t son = tmp[i];
166 
167  /* Backup grandsons after the sons */
168  memcpy( tmp + sonsnbr + gdsonsnbr,
169  etree->sonstab + etree->nodetab[ son ].fsonnum,
170  etree->nodetab[ son ].sonsnbr * sizeof(pastix_int_t) );
171  gdsonsnbr += etree->nodetab[son].sonsnbr;
172  total += etree->nodetab[son].ndecost;
173 
174  if ( (fcand != candtab[son].fcandnum) ||
175  (lcand != candtab[son].lcandnum) )
176  {
177  merge = 0;
178  }
179  }
180 
181  /* If all sons have the same candidate set, then they will be merged within the current node */
182  if ( merge ) {
183  /* Grandsons become sons */
184  for (i=0; i<gdsonsnbr; i++) {
185  tmp[i] = tmp[sonsnbr+i];
186  }
187  sonsnbr = gdsonsnbr;
188  cnode->ndecost += total;
189  }
190  }
191  while( merge && (sonsnbr>0) );
192 
193  /* Recurse on sons */
194  merge = *cnodeidx;
195  for(i=0; i<sonsnbr; i++) {
196  pastix_int_t son = (*cnodeidx) + 1;
197  compress_setSonsNbr( etree, candtab, tmp[i],
198  ctree, ccand,
199  merge, cnodeidx, tmp+sonsnbr );
200  tmp[i] = son;
201  }
202  cnode->sonsnbr = sonsnbr;
203 
204  /* Compress the single candidate nodes */
205  for(i=0; i<sonsnbr; i++) {
206  pastix_int_t j, soni, sonj;
207 
208  soni = tmp[i];
209  if ( ccand[soni].fcandnum != ccand[soni].lcandnum )
210  continue;
211 
212  for( j=i+1; j<sonsnbr; j++ ) {
213  sonj = tmp[j];
214 
215  if ( (ccand[sonj].fcandnum != ccand[soni].fcandnum) ||
216  (ccand[sonj].lcandnum != ccand[soni].lcandnum) )
217  continue;
218 
219  ctree->nodetab[soni].ndecost += ctree->nodetab[sonj].ndecost;
220  ctree->nodetab[soni].subcost += ctree->nodetab[sonj].subcost;
221  assert( ctree->nodetab[sonj].sonsnbr == 0 );
222  assert( ctree->nodetab[sonj].fathnum == ctree->nodetab[soni].fathnum );
223  ctree->nodetab[sonj].fathnum = -2;
224 
225  sonsnbr--;
226  tmp[j] = tmp[sonsnbr]; j--;
227  }
228  }
229  cnode->sonsnbr = sonsnbr;
230 
231  return;
232 }
233 
234 /**
235  *******************************************************************************
236  *
237  * @brief Print the elimination tree in a dot file.
238  *
239  *******************************************************************************
240  *
241  * @param[in] etree
242  * The pointer to the elimination tree.
243  *
244  * @param[in] candtab
245  * The candidate array associated to the elimination tree for
246  * additional information. (optionnal)
247  *
248  * @param[inout] stream
249  * The file to which write the elimination tree in the dot format.
250  *
251  *******************************************************************************/
252 void
253 candGenDot( const EliminTree *etree,
254  const Cand *candtab,
255  FILE *stream )
256 {
257  pastix_int_t i;
258 
259  fprintf(stream,
260  "digraph G {\n"
261  "\tcolor=white\n"
262  "\trankdir=BT;\n");
263 
264  for (i=0; i < etree->nodenbr; i++)
265  {
266  if ((etree->nodetab[i]).fathnum == -2)
267  continue;
268 
269  if ( candtab == NULL ) {
270  fprintf( stream, "\t\"%ld\" [label=\"#%ld\\nNode: %e:%e\\nSubtree: %e:%e\"]\n",
271  (long)i, (long)i,
272  etree->nodetab[i].ndecost,
273  etree->nodetab[i].ndepath,
274  etree->nodetab[i].subcost,
275  etree->nodetab[i].subpath );
276  }
277  else {
278  if ( candtab[i].lcandnum != candtab[i].fcandnum ) {
279  fprintf( stream, "\t\"%ld\" [label=\"#%ld\\nCand: %ld - %ld\\nNode: %e:%e\\nSubtree cost: %e:%e\"]\n",
280  (long)i, (long)i,
281  (long)(candtab[i].fcandnum),
282  (long)(candtab[i].lcandnum),
283  etree->nodetab[i].ndecost,
284  etree->nodetab[i].ndepath,
285  etree->nodetab[i].ndecost,
286  etree->nodetab[i].subpath );
287  }
288  else {
289  fprintf( stream, "\t\"%ld\" [label=\"#%ld\\nCand: %ld\\nNode: %e:%e\\nSubtree cost: %e:%e\" colorscheme=set312 style=filled fillcolor=%ld]\n",
290  (long)i, (long)i,
291  (long)(candtab[i].fcandnum),
292  etree->nodetab[i].ndecost,
293  etree->nodetab[i].ndepath,
294  etree->nodetab[i].ndecost,
295  etree->nodetab[i].subpath,
296  (long)((candtab[i].lcandnum % 12) + 1));
297  }
298  }
299  if ((etree->nodetab[i]).fathnum == -1)
300  continue;
301  fprintf(stream, "\t\"%ld\"->\"%ld\"\n", (long)i, (long)((etree->nodetab[i]).fathnum));
302  }
303  fprintf(stream, "}\n");
304 }
305 
306 /**
307  *******************************************************************************
308  *
309  * @brief Print one level of the elimination subtree in a dot file.
310  *
311  *******************************************************************************
312  *
313  * @param[in] etree
314  * The pointer to the elimination tree.
315  *
316  * @param[in] candtab
317  * The candidate array associated to the elimination tree for
318  * additional information. (optionnal)
319  *
320  * @param[inout] stream
321  * The file to which write the elimination tree in the dot format.
322  *
323  * @param[in] nblevel
324  * The number of level remaining to be printed.
325  *
326  * @param[in] rootnum
327  * The root of the subtree to print.
328  *
329  *******************************************************************************/
330 static inline void
332  const Cand *candtab,
333  FILE *stream,
334  pastix_int_t nblevel,
335  pastix_int_t rootnum )
336 {
337  pastix_int_t i, son;
338 
339  assert( (etree->nodetab[rootnum]).fathnum != -2 );
340 
341  /* Print current node informations */
342  if ( candtab == NULL ) {
343  fprintf( stream, "\t\"%ld\" [label=\"#%ld\\nSubtree cost: %e\\nNode cost: %e\\nNode CP: %e\"]\n",
344  (long)rootnum, (long)rootnum,
345  etree->nodetab[rootnum].subcost,
346  etree->nodetab[rootnum].ndecost,
347  etree->nodetab[rootnum].subpath );
348  }
349  else {
350  if ( candtab[rootnum].lcandnum != candtab[rootnum].fcandnum ) {
351  fprintf( stream, "\t\"%ld\" [label=\"#%ld\\nCand: %ld - %ld\\nSubtree cost: %e\\nNode cost: %e\\nNode CP: %e\"]\n",
352  (long)rootnum, (long)rootnum,
353  (long)(candtab[rootnum].fcandnum),
354  (long)(candtab[rootnum].lcandnum),
355  etree->nodetab[rootnum].subcost,
356  etree->nodetab[rootnum].ndecost,
357  etree->nodetab[rootnum].subpath );
358  }
359  else {
360  fprintf(stream, "\t\"%ld\" [label=\"#%ld\\nCand: %ld\\nSubtree cost: %e\\nNode cost: %e\\nNode CP: %e\" colorscheme=set312 style=filled fillcolor=%ld]\n",
361  (long)rootnum, (long)rootnum,
362  (long)(candtab[rootnum].fcandnum),
363  etree->nodetab[rootnum].subcost,
364  etree->nodetab[rootnum].ndecost,
365  etree->nodetab[rootnum].subpath,
366  (long)((candtab[rootnum].lcandnum % 12) + 1));
367  }
368  }
369 
370  if ( nblevel > 0 ) {
371  nblevel--;
372 
373  for(i=0; i<etree->nodetab[rootnum].sonsnbr; i++)
374  {
375  son = eTreeSonI(etree, rootnum, i);
376  candGenDotLevelSub( etree, candtab, stream, nblevel, son );
377 
378  fprintf(stream, "\t\"%ld\"->\"%ld\"\n", (long)son, (long)rootnum);
379  }
380  }
381 }
382 
383 /**
384  *******************************************************************************
385  *
386  * @brief Print the first levels of the elimination tree in a dot file.
387  *
388  *******************************************************************************
389  *
390  * @param[in] etree
391  * The pointer to the elimination tree.
392  *
393  * @param[in] candtab
394  * The candidate array associated to the elimination tree for
395  * additional information. (optionnal)
396  *
397  * @param[inout] stream
398  * The file to which write the elimination tree in the dot format.
399  *
400  * @param[in] nblevel
401  * The number of levels of the elimination tree to print.
402  *
403  *******************************************************************************/
404 void
406  const Cand *candtab,
407  FILE *stream,
408  pastix_int_t nblevel )
409 {
410  fprintf(stream,
411  "digraph G {\n"
412  "\tcolor=white\n"
413  "\trankdir=BT;\n");
414 
415  candGenDotLevelSub( etree, candtab, stream,
416  nblevel, eTreeRoot( etree ) );
417 
418  fprintf(stream, "}\n");
419 }
420 
421 /**
422  *******************************************************************************
423  *
424  * @brief Print the compressed elimination tree in a dot file, where all nodes
425  * with the same candidates are merged together.
426  *
427  *******************************************************************************
428  *
429  * @param[in] etree
430  * The pointer to the elimination tree.
431  *
432  * @param[in] candtab
433  * The candidate array associated to the elimination tree for
434  * additional information.
435  *
436  * @param[inout] stream
437  * The file to which write the elimination tree in the dot format.
438  *
439  *******************************************************************************/
440 void
442  const Cand *candtab,
443  FILE *stream )
444 {
445  EliminTree *ctree;
446  Cand *ccand;
447  pastix_int_t cnodesnbr, cnodeidx, *tmp;
448 
449  cnodesnbr = compress_getNodeNbr( etree, candtab, eTreeRoot(etree) );
450 
451  /* Let's create a second compressed elimination tree, and the associated candtab */
452  ctree = eTreeInit( cnodesnbr );
453 
454  ccand = candInit( cnodesnbr );
455 
456  MALLOC_INTERN(tmp, etree->nodenbr, pastix_int_t);
457  cnodeidx = -1;
458  compress_setSonsNbr( etree, candtab, eTreeRoot( etree ),
459  ctree, ccand, -1, &cnodeidx, tmp );
460  memFree_null(tmp);
461 
462  /* Write the dot file */
463  candGenDot( ctree, ccand, stream );
464 
465  /* Free temporary ressources */
466  candExit( ccand );
467  eTreeExit( ctree );
468 }
469 
470 /**
471  * @}
472  */
BEGIN_C_DECLS typedef int pastix_int_t
Definition: datatypes.h:51
pastix_int_t lcandnum
Definition: cand.h:32
pastix_int_t fcandnum
Definition: cand.h:31
Cand * candInit(pastix_int_t cblknbr)
Initialize the candtab array with default values.
Definition: cand.c:48
void candExit(Cand *candtab)
Exit and free the candtab structure given.
Definition: cand.c:83
Processor candidate group to own a column blok.
Definition: cand.h:28
double subpath
Definition: elimintree.h:29
double subcost
Definition: elimintree.h:28
double ndepath
Definition: elimintree.h:27
double ndecost
Definition: elimintree.h:26
pastix_int_t fsonnum
Definition: elimintree.h:33
pastix_int_t * sonstab
Definition: elimintree.h:43
pastix_int_t nodenbr
Definition: elimintree.h:41
eTreeNode_t * nodetab
Definition: elimintree.h:42
pastix_int_t fathnum
Definition: elimintree.h:32
static pastix_int_t eTreeRoot(const EliminTree *etree)
Return the root of the elimination tree.
Definition: elimintree.h:126
static pastix_int_t eTreeSonI(const EliminTree *etree, pastix_int_t node, pastix_int_t i)
Return the i^{th} son of a given node.
Definition: elimintree.h:105
EliminTree * eTreeInit(pastix_int_t)
Initialize the elimination tree structure.
Definition: elimintree.c:43
static void candGenDotLevelSub(const EliminTree *etree, const Cand *candtab, FILE *stream, pastix_int_t nblevel, pastix_int_t rootnum)
Print one level of the elimination subtree in a dot file.
Definition: cand_gendot.c:331
void candGenCompressedDot(const EliminTree *etree, const Cand *candtab, FILE *stream)
Print the compressed elimination tree in a dot file, where all nodes with the same candidates are mer...
Definition: cand_gendot.c:441
static pastix_int_t compress_getNodeNbr(const EliminTree *etree, const Cand *candtab, pastix_int_t rootnum)
Compute the number of nodes in the compressed tree. The compression is based on identical candidates ...
Definition: cand_gendot.c:53
void candGenDotLevel(const EliminTree *etree, const Cand *candtab, FILE *stream, pastix_int_t nblevel)
Print the first levels of the elimination tree in a dot file.
Definition: cand_gendot.c:405
static void compress_setSonsNbr(const EliminTree *etree, const Cand *candtab, pastix_int_t rootnum, EliminTree *ctree, Cand *ccand, pastix_int_t fathnum, pastix_int_t *cnodeidx, pastix_int_t *tmp)
Compress a subtree. The compression is based on identical candidates for computations.
Definition: cand_gendot.c:123
void candGenDot(const EliminTree *etree, const Cand *candtab, FILE *stream)
Print the elimination tree in a dot file.
Definition: cand_gendot.c:253
void eTreeExit(EliminTree *)
Free the elimination tree structure.
Definition: elimintree.c:89
Node of the elimination tree.
Definition: elimintree.h:25
Elimination tree.
Definition: elimintree.h:39