1 /* Copyright 2007-2011 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 : wgraph_part_st.c **/
35 /** **/
36 /** AUTHOR : Jun-Ho HER (v6.0) **/
37 /** Charles-Edmond BICHOT (v5.1b) **/
38 /** Sebastien FOURESTIER (v6.0) **/
39 /** **/
40 /** FUNCTION : This module contains the global **/
41 /** vertex overlapped graph partitioning **/
42 /** strategy and method tables. **/
43 /** **/
44 /** DATES : # Version 5.1 : from : 01 dec 2007 **/
45 /** to : 01 jul 2008 **/
46 /** # Version 6.0 : from : 05 nov 2009 **/
47 /** to 16 apr 2011 **/
48 /** **/
49 /************************************************************/
50
51 /*
52 ** The defines and includes.
53 */
54
55 #define WGRAPH_PART_ST
56
57 #include "module.h"
58 #include "common.h"
59 #include "gain.h"
60 #include "parser.h"
61 #include "graph.h"
62 #include "arch.h"
63 #include "mapping.h"
64 #include "graph_coarsen.h"
65 #include "vgraph.h"
66 #include "vgraph_separate_st.h"
67 #include "wgraph.h"
68 #include "wgraph_part_fm.h"
69 #include "wgraph_part_gg.h"
70 #include "wgraph_part_gp.h"
71 #include "wgraph_part_ml.h"
72 #include "wgraph_part_rb.h"
73 #include "wgraph_part_st.h"
74 #include "wgraph_part_zr.h"
75
76 /*
77 ** The static and global variables.
78 */
79
80 static Wgraph wgraphdummy; /* Dummy overlap graph for offset computations */
81
82 static union {
83 WgraphPartFmParam param;
84 StratNodeMethodData padding;
85 } wgraphpartdefaultfm = { { 10, 40, 0.1L } };
86
87 static union {
88 WgraphPartGgParam param;
89 StratNodeMethodData padding;
90 } wgraphpartdefaultgg = { { 10 } };
91
92 static union {
93 WgraphPartGpParam param;
94 StratNodeMethodData padding;
95 } wgraphpartdefaultgp = { { 5 } };
96
97 static union {
98 WgraphPartMlParam param;
99 StratNodeMethodData padding;
100 } wgraphpartdefaultml = { { 20, 0.8L, &stratdummy, &stratdummy } };
101
102 static union {
103 WgraphPartRbParam param;
104 StratNodeMethodData padding;
105 } wgraphpartdefaultrb = { { &stratdummy } };
106
107 static StratMethodTab wgraphpartstmethtab[] = { /* Graph overlap partitioning methods array */
108 { WGRAPHSEPASTMETHGG, "h", wgraphPartGg, &wgraphpartdefaultgg },
109 { WGRAPHSEPASTMETHGP, "g", wgraphPartGp, &wgraphpartdefaultgp },
110 { WGRAPHSEPASTMETHFM, "f", wgraphPartFm, &wgraphpartdefaultfm },
111 { WGRAPHSEPASTMETHML, "m", wgraphPartMl, &wgraphpartdefaultml },
112 { WGRAPHSEPASTMETHRB, "r", wgraphPartRb, &wgraphpartdefaultrb },
113 { WGRAPHSEPASTMETHZR, "z", wgraphPartZr, NULL },
114 { -1, NULL, NULL, NULL } };
115
116 static StratParamTab wgraphpartstparatab[] = { /* Method parameter list */
117 { WGRAPHSEPASTMETHFM, STRATPARAMINT, "pass",
118 (byte *) &wgraphpartdefaultfm.param,
119 (byte *) &wgraphpartdefaultfm.param.passnbr,
120 NULL },
121 { WGRAPHSEPASTMETHFM, STRATPARAMINT, "move",
122 (byte *) &wgraphpartdefaultfm.param,
123 (byte *) &wgraphpartdefaultfm.param.movenbr,
124 NULL },
125 { WGRAPHSEPASTMETHFM, STRATPARAMDOUBLE, "bal",
126 (byte *) &wgraphpartdefaultfm.param,
127 (byte *) &wgraphpartdefaultfm.param.deltrat,
128 NULL },
129 { WGRAPHSEPASTMETHGG, STRATPARAMINT, "pass",
130 (byte *) &wgraphpartdefaultgg.param,
131 (byte *) &wgraphpartdefaultgg.param.passnbr,
132 NULL },
133 { WGRAPHSEPASTMETHGP, STRATPARAMINT, "pass",
134 (byte *) &wgraphpartdefaultgp.param,
135 (byte *) &wgraphpartdefaultgp.param.passnbr,
136 NULL },
137 { WGRAPHSEPASTMETHML, STRATPARAMSTRAT, "asc",
138 (byte *) &wgraphpartdefaultml.param,
139 (byte *) &wgraphpartdefaultml.param.stratasc,
140 (void *) &wgraphpartststratab },
141 { WGRAPHSEPASTMETHML, STRATPARAMSTRAT, "low",
142 (byte *) &wgraphpartdefaultml.param,
143 (byte *) &wgraphpartdefaultml.param.stratlow,
144 (void *) &wgraphpartststratab },
145 { WGRAPHSEPASTMETHML, STRATPARAMINT, "vert",
146 (byte *) &wgraphpartdefaultml.param,
147 (byte *) &wgraphpartdefaultml.param.coarnbr,
148 NULL },
149 { WGRAPHSEPASTMETHML, STRATPARAMDOUBLE, "rat",
150 (byte *) &wgraphpartdefaultml.param,
151 (byte *) &wgraphpartdefaultml.param.coarval,
152 NULL },
153 { WGRAPHSEPASTMETHRB, STRATPARAMSTRAT, "sep",
154 (byte *) &wgraphpartdefaultrb.param,
155 (byte *) &wgraphpartdefaultrb.param.stratptr,
156 (void *) &vgraphseparateststratab },
157 { WGRAPHSEPASTMETHNBR, STRATPARAMINT, NULL,
158 NULL, NULL, NULL } };
159
160 static StratParamTab wgraphpartstcondtab[] = { /* Overlap graph condition parameter table*/
161 { STRATNODENBR, STRATPARAMINT, NULL,
162 NULL, NULL, NULL } };
163
164 StratTab wgraphpartststratab = { /* Strategy tables for overlap partitioning methods */
165 wgraphpartstmethtab,
166 wgraphpartstparatab,
167 wgraphpartstcondtab };
168
169 /*********************************************/
170 /* */
171 /* This is the generic partitioning routine. */
172 /* */
173 /*********************************************/
174
175 /* This routine computes the separation of
176 ** the given graph according to the given
177 ** strategy.
178 ** It returns:
179 ** - 0 : on success.
180 ** - !0 : on error.
181 */
182
183 int
wgraphPartSt(Wgraph * restrict const grafptr,const Strat * restrict const strat)184 wgraphPartSt (
185 Wgraph * restrict const grafptr, /*+ Overlap partitioning graph +*/
186 const Strat * restrict const strat) /*+ Overlap partitioning strategy +*/
187 {
188 StratTest val; /* Result of condition evaluation */
189 WgraphStore savetab[2]; /* Results of the two strategies */
190 int o;
191 int o2;
192
193 #ifdef SCOTCH_DEBUG_WGRAPH2
194 if (sizeof (Gnum) != sizeof (INT)) {
195 errorPrint ("wgraphPartSt: invalid type specification for parser variables");
196 return (1);
197 }
198 if ((sizeof (WgraphPartFmParam) > sizeof (StratNodeMethodData)) ||
199 (sizeof (WgraphPartGgParam) > sizeof (StratNodeMethodData)) ||
200 (sizeof (WgraphPartGpParam) > sizeof (StratNodeMethodData)) ||
201 (sizeof (WgraphPartMlParam) > sizeof (StratNodeMethodData)) ||
202 (sizeof (WgraphPartRbParam) > sizeof (StratNodeMethodData))) {
203 errorPrint ("wgraphPartSt: invalid type specification");
204 return (1);
205 }
206 #endif /* SCOTCH_DEBUG_WGRAPH2 */
207 #ifdef SCOTCH_DEBUG_WGRAPH1
208 if ((strat->tabl != &wgraphpartststratab) &&
209 (strat != &stratdummy)) {
210 errorPrint ("wgraphPartSt: invalid parameter (1)");
211 return (1);
212 }
213 #endif /* SCOTCH_DEBUG_WGRAPH1 */
214
215 o = 0;
216 switch (strat->type) {
217 case STRATNODECONCAT :
218 o = wgraphPartSt (grafptr, strat->data.concat.strat[0]); /* Apply the first strategy */
219 if (o == 0) /* If it worked all right */
220 o |= wgraphPartSt (grafptr, strat->data.concat.strat[1]); /* Then apply second strategy */
221 break;
222 case STRATNODECOND :
223 o = stratTestEval (strat->data.cond.test, &val, (void *) grafptr); /* Evaluate expression */
224 if (o == 0) { /* If evaluation was correct */
225 #ifdef SCOTCH_DEBUG_WGRAPH2
226 if ((val.typetest != STRATTESTVAL) ||
227 (val.typenode != STRATPARAMLOG)) {
228 errorPrint ("wgraphPartSt: invalid test result");
229 o = 1;
230 break;
231 }
232 #endif /* SCOTCH_DEBUG_WGRAPH2 */
233 if (val.data.val.vallog == 1) /* If expression is true */
234 o = wgraphPartSt (grafptr, strat->data.cond.strat[0]); /* Apply first strategy */
235 else { /* Else if expression is false */
236 if (strat->data.cond.strat[1] != NULL) /* And if there is an else statement */
237 o = wgraphPartSt (grafptr, strat->data.cond.strat[1]); /* Apply second strategy */
238 }
239 }
240 break;
241 case STRATNODEEMPTY :
242 break;
243 case STRATNODESELECT :
244 if (((wgraphStoreInit (grafptr, &savetab[0])) != 0) || /* Allocate save areas */
245 ((wgraphStoreInit (grafptr, &savetab[1])) != 0)) {
246 errorPrint ("wgraphPartSt: out of memory");
247 wgraphStoreExit (&savetab[0]);
248 return (1);
249 }
250
251 wgraphStoreSave (grafptr, &savetab[1]); /* Save initial partition */
252 o = wgraphPartSt (grafptr, strat->data.select.strat[0]); /* Apply first strategy */
253 wgraphStoreSave (grafptr, &savetab[0]); /* Save its result */
254 wgraphStoreUpdt (grafptr, &savetab[1]); /* Restore initial partition */
255 o2 = wgraphPartSt (grafptr, strat->data.select.strat[1]); /* Apply second strategy */
256
257 if ((o == 0) || (o2 == 0)) { /* If at least one method make a k-partition */
258 if (savetab[0].fronload < grafptr->fronload) /* If first strategy is better */
259 wgraphStoreUpdt (grafptr, &savetab[0]); /* Restore its result */
260 }
261
262 wgraphStoreExit (&savetab[0]); /* Free both save areas */
263 wgraphStoreExit (&savetab[1]);
264 break;
265 #ifdef SCOTCH_DEBUG_WGRAPH2
266 case STRATNODEMETHOD :
267 #else /* SCOTCH_DEBUG_WGRAPH2 */
268 default :
269 #endif /* SCOTCH_DEBUG_WGRAPH2 */
270 return (strat->tabl->methtab[strat->data.method.meth].func (grafptr, (void *) &strat->data.method.data));
271 #ifdef SCOTCH_DEBUG_WGRAPH2
272 default :
273 errorPrint ("wgraphPartSt: invalid parameter (2)");
274 return (1);
275 #endif /* SCOTCH_DEBUG_WGRAPH2 */
276 }
277 return (o);
278 }
279