1 /* Copyright 2004,2007 ENSEIRB, INRIA & CNRS
2 **
3 ** This file is part of the Scotch software package for static mapping,
4 ** graph partitioning and sparse matrix ordering.
5 **
6 ** This software is governed by the CeCILL-C license under French law
7 ** and abiding by the rules of distribution of free software. You can
8 ** use, modify and/or redistribute the software under the terms of the
9 ** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
10 ** URL: "http://www.cecill.info".
11 **
12 ** As a counterpart to the access to the source code and rights to copy,
13 ** modify and redistribute granted by the license, users are provided
14 ** only with a limited warranty and the software's author, the holder of
15 ** the economic rights, and the successive licensors have only limited
16 ** liability.
17 **
18 ** In this respect, the user's attention is drawn to the risks associated
19 ** with loading, using, modifying and/or developing or reproducing the
20 ** software by the user in light of its specific status of free software,
21 ** that may mean that it is complicated to manipulate, and that also
22 ** therefore means that it is reserved for developers and experienced
23 ** professionals having in-depth computer knowledge. Users are therefore
24 ** encouraged to load and test the software's suitability as regards
25 ** their requirements in conditions enabling the security of their
26 ** systems and/or data to be ensured and, more generally, to use and
27 ** operate it in the same conditions as regards security.
28 **
29 ** The fact that you are presently reading this means that you have had
30 ** knowledge of the CeCILL-C license and that you accept its terms.
31 */
32 /************************************************************/
33 /** **/
34 /** NAME : hmesh_order_st.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module is the generic call to the **/
39 /** halo mesh ordering module, using a **/
40 /** given strategy. **/
41 /** **/
42 /** DATES : # Version 4.0 : from : 28 sep 2002 **/
43 /** to 05 jan 2005 **/
44 /** **/
45 /************************************************************/
46
47 /*
48 ** The defines and includes.
49 */
50
51 #define HMESH_ORDER_ST
52
53 #include "module.h"
54 #include "common.h"
55 #include "parser.h"
56 #include "graph.h"
57 #include "hgraph.h"
58 #include "mesh.h"
59 #include "hmesh.h"
60 #include "order.h"
61 #include "hgraph_order_st.h"
62 #include "hmesh_order_bl.h"
63 #include "hmesh_order_cp.h"
64 #include "hmesh_order_gp.h"
65 #include "hmesh_order_gr.h"
66 #include "hmesh_order_hd.h"
67 #include "hmesh_order_hf.h"
68 #include "hmesh_order_nd.h"
69 #include "hmesh_order_si.h"
70 #include "hmesh_order_st.h"
71 #include "vmesh.h"
72 #include "vmesh_separate_st.h"
73
74 /*
75 ** The static and global variables.
76 */
77
78 static Hmesh hmeshorderstmeshdummy; /* Dummy mesh for offset computations */
79
80 static union { /* Default parameters for block splitting method */
81 HmeshOrderBlParam param; /* Parameter zone */
82 StratNodeMethodData padding; /* To avoid reading out of structure */
83 } hmeshorderstdefaultbl = { { &stratdummy, 8 } };
84
85 static union {
86 HmeshOrderCpParam param;
87 StratNodeMethodData padding;
88 } hmeshorderstdefaultcp = { { 0.70L, &stratdummy, &stratdummy } };
89
90 static union { /* Default parameters for nested dissection method */
91 HmeshOrderGpParam param;
92 StratNodeMethodData padding;
93 } hmeshorderstdefaultgp = { { 3 } };
94
95 static union { /* Default parameters for nested dissection method */
96 HmeshOrderGrParam param;
97 StratNodeMethodData padding;
98 } hmeshorderstdefaultgr = { { &stratdummy } };
99
100 static union {
101 HmeshOrderHdParam param;
102 StratNodeMethodData padding;
103 } hmeshorderstdefaulthd = { { 1, 1000000, 0.08L } };
104
105 static union {
106 HmeshOrderHfParam param;
107 StratNodeMethodData padding;
108 } hmeshorderstdefaulthf = { { 1, 1000000, 0.08L } };
109
110 static union { /* Default parameters for nested dissection method */
111 HmeshOrderNdParam param;
112 StratNodeMethodData padding;
113 } hmeshorderstdefaultnd = { { &stratdummy, &stratdummy, &stratdummy } };
114
115 static StratMethodTab hmeshorderstmethtab[] = { /* Mesh ordering methods array */
116 { HMESHORDERSTMETHBL, "b", hmeshOrderBl, &hmeshorderstdefaultbl },
117 { HMESHORDERSTMETHCP, "c", hmeshOrderCp, &hmeshorderstdefaultcp },
118 { HMESHORDERSTMETHGP, "g", hmeshOrderGp, &hmeshorderstdefaultgp },
119 { HMESHORDERSTMETHGR, "v", hmeshOrderGr, &hmeshorderstdefaultgr },
120 { HMESHORDERSTMETHHD, "d", hmeshOrderHd, &hmeshorderstdefaulthd },
121 { HMESHORDERSTMETHHF, "f", hmeshOrderHf, &hmeshorderstdefaulthf },
122 { HMESHORDERSTMETHND, "n", hmeshOrderNd, &hmeshorderstdefaultnd },
123 { HMESHORDERSTMETHSI, "s", hmeshOrderSi, NULL },
124 { -1, NULL, NULL, NULL } };
125
126 static StratParamTab hmeshorderstparatab[] = { /* The method parameter list */
127 { HMESHORDERSTMETHBL, STRATPARAMSTRAT, "strat",
128 (byte *) &hmeshorderstdefaultbl.param,
129 (byte *) &hmeshorderstdefaultbl.param.strat,
130 (void *) &hmeshorderststratab },
131 { HMESHORDERSTMETHBL, STRATPARAMINT, "cmin",
132 (byte *) &hmeshorderstdefaultbl.param,
133 (byte *) &hmeshorderstdefaultbl.param.cblkmin,
134 NULL },
135 { HMESHORDERSTMETHCP, STRATPARAMDOUBLE, "rat",
136 (byte *) &hmeshorderstdefaultcp.param,
137 (byte *) &hmeshorderstdefaultcp.param.comprat,
138 NULL },
139 { HMESHORDERSTMETHCP, STRATPARAMSTRAT, "cpr",
140 (byte *) &hmeshorderstdefaultcp.param,
141 (byte *) &hmeshorderstdefaultcp.param.stratcpr,
142 (void *) &hmeshorderststratab },
143 { HMESHORDERSTMETHCP, STRATPARAMSTRAT, "unc",
144 (byte *) &hmeshorderstdefaultcp.param,
145 (byte *) &hmeshorderstdefaultcp.param.stratunc,
146 (void *) &hmeshorderststratab },
147 { HMESHORDERSTMETHGP, STRATPARAMINT, "pass",
148 (byte *) &hmeshorderstdefaultgp.param,
149 (byte *) &hmeshorderstdefaultgp.param.passnbr,
150 NULL },
151 { HMESHORDERSTMETHGR, STRATPARAMSTRAT, "strat",
152 (byte *) &hmeshorderstdefaultgr.param,
153 (byte *) &hmeshorderstdefaultgr.param.stratptr,
154 (void *) &hgraphorderststratab },
155 { HMESHORDERSTMETHHD, STRATPARAMINT, "cmin",
156 (byte *) &hmeshorderstdefaulthd.param,
157 (byte *) &hmeshorderstdefaulthd.param.colmin,
158 NULL },
159 { HMESHORDERSTMETHHD, STRATPARAMINT, "cmax",
160 (byte *) &hmeshorderstdefaulthd.param,
161 (byte *) &hmeshorderstdefaulthd.param.colmax,
162 NULL },
163 { HMESHORDERSTMETHHD, STRATPARAMDOUBLE, "frat",
164 (byte *) &hmeshorderstdefaulthd.param,
165 (byte *) &hmeshorderstdefaulthd.param.fillrat,
166 NULL },
167 { HMESHORDERSTMETHHF, STRATPARAMINT, "cmin",
168 (byte *) &hmeshorderstdefaulthf.param,
169 (byte *) &hmeshorderstdefaulthf.param.colmin,
170 NULL },
171 { HMESHORDERSTMETHHF, STRATPARAMINT, "cmax",
172 (byte *) &hmeshorderstdefaulthf.param,
173 (byte *) &hmeshorderstdefaulthf.param.colmax,
174 NULL },
175 { HMESHORDERSTMETHHF, STRATPARAMDOUBLE, "frat",
176 (byte *) &hmeshorderstdefaulthf.param,
177 (byte *) &hmeshorderstdefaulthf.param.fillrat,
178 NULL },
179 { HMESHORDERSTMETHND, STRATPARAMSTRAT, "sep",
180 (byte *) &hmeshorderstdefaultnd.param,
181 (byte *) &hmeshorderstdefaultnd.param.sepstrat,
182 (void *) &vmeshseparateststratab },
183 { HMESHORDERSTMETHND, STRATPARAMSTRAT, "ole",
184 (byte *) &hmeshorderstdefaultnd.param,
185 (byte *) &hmeshorderstdefaultnd.param.ordstratlea,
186 (void *) &hmeshorderststratab },
187 { HMESHORDERSTMETHND, STRATPARAMSTRAT, "ose",
188 (byte *) &hmeshorderstdefaultnd.param,
189 (byte *) &hmeshorderstdefaultnd.param.ordstratsep,
190 (void *) &hmeshorderststratab },
191 { HMESHORDERSTMETHNBR, STRATPARAMINT, NULL,
192 NULL, NULL, NULL } };
193
194 static StratParamTab hmeshorderstcondtab[] = { /* Mesh condition parameter table */
195 { STRATNODECOND, STRATPARAMINT, "edge",
196 (byte *) &hmeshorderstmeshdummy,
197 (byte *) &hmeshorderstmeshdummy.m.edgenbr,
198 NULL },
199 { STRATNODECOND, STRATPARAMINT, "levl",
200 (byte *) &hmeshorderstmeshdummy,
201 (byte *) &hmeshorderstmeshdummy.levlnum,
202 NULL },
203 { STRATNODECOND, STRATPARAMINT, "load",
204 (byte *) &hmeshorderstmeshdummy,
205 (byte *) &hmeshorderstmeshdummy.vnhlsum,
206 NULL },
207 { STRATNODECOND, STRATPARAMDOUBLE, "mdeg",
208 (byte *) &hmeshorderstmeshdummy,
209 (byte *) &hmeshorderstmeshdummy.m.degrmax,
210 NULL },
211 { STRATNODECOND, STRATPARAMINT, "vnod",
212 (byte *) &hmeshorderstmeshdummy,
213 (byte *) &hmeshorderstmeshdummy.vnohnbr,
214 NULL },
215 { STRATNODECOND, STRATPARAMINT, "velm",
216 (byte *) &hmeshorderstmeshdummy,
217 (byte *) &hmeshorderstmeshdummy.m.velmnbr,
218 NULL },
219 { STRATNODENBR, STRATPARAMINT, NULL,
220 NULL, NULL, NULL } };
221
222 StratTab hmeshorderststratab = { /* Strategy tables for mesh ordering methods */
223 hmeshorderstmethtab,
224 hmeshorderstparatab,
225 hmeshorderstcondtab };
226
227 /***********************************/
228 /* */
229 /* This routine is the entry point */
230 /* for the mesh ordering routines. */
231 /* */
232 /***********************************/
233
234 /* This routine computes an ordering
235 ** with respect to a given strategy.
236 ** It returns:
237 ** - 0 : on success.
238 ** - !0 : on error.
239 */
240
241 int
hmeshOrderSt(const Hmesh * restrict const meshptr,Order * restrict const ordeptr,const Gnum ordenum,OrderCblk * restrict const cblkptr,const Strat * restrict const strat)242 hmeshOrderSt (
243 const Hmesh * restrict const meshptr, /*+ Submesh to which list apply +*/
244 Order * restrict const ordeptr, /*+ Ordering to complete +*/
245 const Gnum ordenum, /*+ Index to start ordering at +*/
246 OrderCblk * restrict const cblkptr, /*+ Current column block +*/
247 const Strat * restrict const strat) /*+ Mesh ordering strategy +*/
248 {
249 StratTest val;
250 int o;
251
252 if (meshptr->vnohnbr == 0) /* Return immediately if nothing to do */
253 return (0);
254
255 o = 0;
256 switch (strat->type) {
257 case STRATNODECONCAT :
258 errorPrint ("hmeshOrderSt: concatenation operator not implemented for ordering strategies");
259 return (1);
260 case STRATNODECOND :
261 o = stratTestEval (strat->data.cond.test, &val, (void *) meshptr); /* Evaluate expression */
262 if (o == 0) { /* If evaluation was correct */
263 #ifdef SCOTCH_DEBUG_HMESH2
264 if ((val.typetest != STRATTESTVAL) &&
265 (val.typenode != STRATPARAMLOG)) {
266 errorPrint ("hmeshOrderSt: invalid test result");
267 o = 1;
268 break;
269 }
270 #endif /* SCOTCH_DEBUG_HMESH2 */
271 if (val.data.val.vallog == 1) /* If expression is true */
272 o = hmeshOrderSt (meshptr, ordeptr, ordenum, cblkptr, strat->data.cond.strat[0]); /* Apply first strategy */
273 else { /* Else if expression is false */
274 if (strat->data.cond.strat[1] != NULL) /* And if there is an else statement */
275 o = hmeshOrderSt (meshptr, ordeptr, ordenum, cblkptr, strat->data.cond.strat[1]); /* Apply second strategy */
276 }
277 }
278 break;
279 case STRATNODEEMPTY :
280 hmeshOrderSi (meshptr, ordeptr, ordenum, cblkptr); /* Always maintain a coherent ordering */
281 break;
282 case STRATNODESELECT :
283 errorPrint ("hmeshOrderSt: selection operator not available for mesh ordering strategies");
284 return (1);
285 #ifdef SCOTCH_DEBUG_HMESH2
286 case STRATNODEMETHOD :
287 #else /* SCOTCH_DEBUG_HMESH2 */
288 default :
289 #endif /* SCOTCH_DEBUG_HMESH2 */
290 return (strat->tabl->methtab[strat->data.method.meth].func (meshptr, ordeptr, ordenum, cblkptr, (void *) &strat->data.method.data));
291 #ifdef SCOTCH_DEBUG_HMESH2
292 default :
293 errorPrint ("hmeshOrderSt: invalid parameter");
294 return (1);
295 #endif /* SCOTCH_DEBUG_HMESH2 */
296 }
297 return (o);
298 }
299