PaStiX Handbook  6.3.2
order_apply_level_order.c
Go to the documentation of this file.
1 /**
2  *
3  * @file order_apply_level_order.c
4  *
5  * PaStiX order function that apply reverse level ordering to the elimination
6  * tree.
7  *
8  * @copyright 2004-2023 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
9  * Univ. Bordeaux. All rights reserved.
10  *
11  * @version 6.3.2
12  * @author Gregoire Pichon
13  * @author Mathieu Faverge
14  * @author Pierre Ramet
15  * @date 2023-07-21
16  *
17  **/
18 #include <string.h>
19 #include "common.h"
20 #include "blend/elimintree.h"
21 #include "order/order_internal.h"
22 
23 /**
24  *******************************************************************************
25  *
26  * @ingroup order_dev
27  *
28  * @brief This routine build the elimination tree associated to an ordering.
29  *
30  *******************************************************************************
31  *
32  * @param[in] order
33  * The ordering structure.
34  *
35  *******************************************************************************
36  *
37  * @return the elimination tree structure associated to the ordering.
38  *
39  *******************************************************************************/
40 EliminTree *
42 {
43  EliminTree *etree = NULL;
44  eTreeNode_t *enode;
45  pastix_int_t i, fathnum;
46 
47  etree = eTreeInit( order->cblknbr );
48 
49  /* Compute the fathers and the number of sons */
50  enode = etree->nodetab;
51  for(i=0; i<order->cblknbr; i++, enode++)
52  {
53  fathnum = order->treetab[i];
54  enode->fathnum = fathnum;
55 
56  assert(fathnum < (order->cblknbr+1) );
57  etree->nodetab[ fathnum ].sonsnbr ++;
58  }
59 
60  /* Set the index of the first sons */
61  eTreeSetSons( etree );
62 
63  return etree;
64 }
65 
66 /**
67  *******************************************************************************
68  *
69  * @ingroup pastix_order
70  *
71  * @brief This routine reorder the elimination tree nodes per level.
72  *
73  *******************************************************************************
74  *
75  * @param[in] order
76  * The ordering structure to reorder.
77  *
78  * @param[in] level_tasks2d
79  * Define the ways 2D tasks are decided. If < 0, autolvel will be made
80  * based on all blocks above the minimal width_tasks2d criterion. If 0,
81  * 1D tasks will be used, and if > 0, only the first level_tasks2d lvel
82  * of the elimination tree will be considered as 2D tasks.
83  *
84  * @param[in] width_tasks2d
85  * Define the minimal width for the supernodes that are considered as 2D
86  * blocks if level_tasks2d < 0. Unused otherwise.
87  *
88  *******************************************************************************
89  *
90  * @retval PASTIX_SUCCESS on successful exit,
91  * @retval PASTIX_ERR_BADPARAMETER if the ordering structure is incorrect.
92  *
93  *******************************************************************************/
94 int
96  pastix_int_t level_tasks2d,
97  pastix_int_t width_tasks2d )
98 {
99  pastix_order_t oldorder;
100  EliminTree *etree;
101  pastix_int_t baseval; /* Node base value */
102  pastix_int_t i, s, node, sonsnbr;
103  pastix_int_t nfcol, ofcol, size;
104  int rc;
105 
106  /* Parameter checks */
107  if ( order == NULL ) {
108  pastix_print_error( "orderApplyLevelOrder: invalid order pointer" );
110  }
111 
112  if ( (order->permtab == NULL) && (order->vertnbr > 0) ) {
113  pastix_print_error( "orderApplyLevelOrder: invalid order->permtab pointer" );
115  }
116  if ( order->rangtab == NULL ) {
117  pastix_print_error( "orderApplyLevelOrder: invalid order->rangtab pointer" );
119  }
120  if ( (order->treetab == NULL) && (order->cblknbr > 0) ) {
121  pastix_print_error( "orderApplyLevelOrder: invalid order->treetab pointer" );
123  }
124 
125  if ( order->cblknbr < 0 ) {
126  pastix_print_error( "orderApplyLevelOrder: invalid nunber of column blocks" );
128  }
129  baseval = order->baseval;
130  if ( baseval < 0 ) {
131  pastix_print_error( "orderApplyLevelOrder: invalid vertex node base number" );
133  }
134 
135  /* Quick return */
136  if ( order->cblknbr <= 1 ) {
137  return PASTIX_SUCCESS;
138  }
139 
140  assert( baseval == order->rangtab[0] );
141 
142  memcpy( &oldorder, order, sizeof(pastix_order_t) );
143  rc = pastixOrderAlloc( order,
144  oldorder.vertnbr,
145  oldorder.cblknbr );
146  if ( rc != PASTIX_SUCCESS ) {
147  return rc;
148  }
149 
150  /*
151  * Build the elimination tree from top to bottom
152  */
153  etree = orderBuildEtree( &oldorder );
154 
155  /*
156  * Build the sorted array per level
157  * If autolevel is enabled for 2D, we need to sort the 2D cblks first and
158  * then the 1D.
159  */
160  if ( level_tasks2d < 0 )
161  {
162  pastix_int_t pos_1D, pos_2D;
163  pastix_int_t tot_nb_2D = 0;
164  pastix_int_t fathnum;
165  pastix_int_t *sorted = order->permtab;
166  int8_t *is_2D;
167 
168  MALLOC_INTERN(is_2D, order->cblknbr, int8_t);
169  memset(is_2D, 0, order->cblknbr * sizeof(int8_t));
170 
171 #if defined(PASTIX_BLEND_DEEPEST_DISTRIB)
172  for(node=0; node<order->cblknbr; node++ ){
173  size = oldorder.rangtab[ node+1 ] - oldorder.rangtab[ node ];
174  if (is_2D[node] == 1) {
175  continue;
176  }
177 
178  fathnum = etree->nodetab[node].fathnum;
179 
180  /* Mark as 2D only if the father is a real supernode, otherwise we don't reorder */
181  if ( size >= width_tasks2d )
182  {
183  /* Force all brothers to be considered as 2D */
184  sonsnbr = etree->nodetab[fathnum].sonsnbr;
185  for(i=0; i<sonsnbr; i++) {
186  s = eTreeSonI(etree, fathnum, i);
187  if (is_2D[s] == 0) {
188  is_2D[s] = 1;
189  tot_nb_2D++;
190  }
191  }
192 
193  /* Force parent and thus uncles to be 2D too */
194  while( (fathnum != -1) && (is_2D[fathnum] == 0) ) {
195  fathnum = etree->nodetab[fathnum].fathnum;
196 
197  sonsnbr = etree->nodetab[fathnum].sonsnbr;
198  for(i=0; i<sonsnbr; i++) {
199  s = eTreeSonI(etree, fathnum, i);
200  if (is_2D[s] == 0) {
201  is_2D[s] = 1;
202  tot_nb_2D++;
203  }
204  }
205  }
206  }
207  }
208 
209 #else /* defined(PASTIX_BLEND_DEEPEST_DISTRIB) */
210 
211  /* First pass to choose which nodes are 2D from the top to bottom */
212  for(node=order->cblknbr-1; node>-1; node--) {
213 
214  fathnum = etree->nodetab[node].fathnum;
215  size = oldorder.rangtab[ node+1 ] - oldorder.rangtab[ node ];
216 
217  /* Mark as 2D only if the father is a real supernode, otherwise we don't reorder */
218  if ( (size >= width_tasks2d) &&
219  ((fathnum == -1) ||
220  ((is_2D[fathnum] == 1) && (etree->nodetab[fathnum].sonsnbr == 2))) )
221  {
222  is_2D[node] = 1;
223  tot_nb_2D++;
224  }
225  }
226 #endif
227 
228  /* Lets start by inserting the roots */
229  pos_2D = 0;
230  pos_1D = tot_nb_2D;
231 
232  sonsnbr = etree->nodetab[-1].sonsnbr;
233  assert( etree->nodetab[-1].fsonnum == 0 );
234  for (i=0; i<sonsnbr; i++) {
235  node = etree->sonstab[i];
236  if ( is_2D[node] ) {
237  sorted[pos_2D] = node;
238  pos_2D++;
239  }
240  else {
241  sorted[pos_1D] = node;
242  pos_1D++;
243  }
244  }
245 
246  /* Second pass to sort nodes: firstly by type (1D/2D) and then by levels */
247  for(i=0; i<order->cblknbr; i++) {
248  pastix_int_t current_1D = 0;
249  pastix_int_t current_2D = 0;
250  pastix_int_t sons1D, sons2D;
251 
252  node = sorted[i];
253  sonsnbr = etree->nodetab[node].sonsnbr;
254  sons2D = 0;
255 
256  /* Count the number of 2D sons */
257  for(s=0; s<sonsnbr; s++) {
258  pastix_int_t son = eTreeSonI(etree, node, s);
259  if (is_2D[son]) {
260  sons2D++;
261  }
262  }
263  sons1D = sonsnbr - sons2D;
264 
265  /*
266  * We put the sons in reverse order to keep the original order
267  * betwen the brothers. This matters for the Minimum Degree part of
268  * the ordering algorithm.
269  */
270  for(s=0; s<sonsnbr; s++) {
271  pastix_int_t son = eTreeSonI(etree, node, s);
272  if (is_2D[son]) {
273  sorted[pos_2D + sons2D - current_2D - 1] = son;
274  current_2D++;
275  }
276  else{
277  sorted[pos_1D + sons1D - current_1D - 1] = son;
278  current_1D++;
279  }
280  etree->nodetab[ son ].fathnum = order->cblknbr - i - 1;
281  }
282  pos_2D += sons2D;
283  pos_1D += sons1D;
284  }
285  memFree_null(is_2D);
286  }
287  else
288  {
289  pastix_int_t pos;
290  pastix_int_t *sorted = order->permtab;
291 
292  /* Start with the roots */
293  pos = etree->nodetab[-1].sonsnbr;
294  memcpy( sorted, etree->sonstab, pos * sizeof(pastix_int_t) );
295 
296  for(i=0; i<order->cblknbr; i++) {
297  node = sorted[i];
298  sonsnbr = etree->nodetab[node].sonsnbr;
299  /*
300  * We put the sons in reverse order to keep the original order
301  * betwen the brothers. This matters for the Minimum Degree part of
302  * the ordering algorithm.
303  */
304  for(s=0; s<sonsnbr; s++) {
305  pastix_int_t son = eTreeSonI(etree, node, s);
306  sorted[ pos + sonsnbr-1-s ] = son;
307  etree->nodetab[ son ].fathnum = order->cblknbr - i - 1;
308  }
309  pos += sonsnbr;
310  }
311  assert(pos == order->cblknbr);
312  }
313 
314  /* Let's rebuild peritab, treetab, and rangtab */
315  order->rangtab[0] = 0;
316 
317  for(i=0; i<order->cblknbr; i++ ) {
318  node = order->permtab[order->cblknbr - i - 1];
319  size = oldorder.rangtab[ node+1 ] - oldorder.rangtab[ node ];
320 
321  ofcol = oldorder.rangtab[ node ];
322  nfcol = order->rangtab[ i ];
323  order->rangtab[ i+1 ] = nfcol + size;
324  order->treetab[ i ] = etree->nodetab[ node ].fathnum;
325 
326  memcpy( order->peritab + nfcol, oldorder.peritab + ofcol,
327  size * sizeof( pastix_int_t ) );
328  }
329 
330  /* Update the permutation */
331  for (i=0; i<order->vertnbr; i++) {
332  order->permtab[ order->peritab[i] ] = i;
333  }
334 
335  pastixOrderExit( &oldorder );
336 
337  eTreeExit( etree );
338 
339  return PASTIX_SUCCESS;
340 }
BEGIN_C_DECLS typedef int pastix_int_t
Definition: datatypes.h:51
pastix_int_t fsonnum
Definition: elimintree.h:33
pastix_int_t * sonstab
Definition: elimintree.h:43
eTreeNode_t * nodetab
Definition: elimintree.h:42
pastix_int_t fathnum
Definition: elimintree.h:32
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
void eTreeSetSons(EliminTree *)
Set the fsonnum fields base on the initialized sonsnbr.
Definition: elimintree.c:142
EliminTree * eTreeInit(pastix_int_t)
Initialize the elimination tree structure.
Definition: elimintree.c:43
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
EliminTree * orderBuildEtree(const pastix_order_t *order)
This routine build the elimination tree associated to an ordering.
@ PASTIX_SUCCESS
Definition: api.h:367
@ PASTIX_ERR_BADPARAMETER
Definition: api.h:374
pastix_int_t baseval
Definition: order.h:48
pastix_int_t * treetab
Definition: order.h:54
pastix_int_t * permtab
Definition: order.h:51
pastix_int_t * peritab
Definition: order.h:52
pastix_int_t cblknbr
Definition: order.h:50
pastix_int_t * rangtab
Definition: order.h:53
pastix_int_t vertnbr
Definition: order.h:49
int pastixOrderAlloc(pastix_order_t *ordeptr, pastix_int_t vertnbr, pastix_int_t cblknbr)
Allocate the order structure.
Definition: order.c:55
int orderApplyLevelOrder(pastix_order_t *order, pastix_int_t level_tasks2d, pastix_int_t width_tasks2d)
This routine reorder the elimination tree nodes per level.
void pastixOrderExit(pastix_order_t *ordeptr)
Free the arrays initialized in the order structure.
Definition: order.c:273
Order structure.
Definition: order.h:47