PaStiX Handbook 6.4.0
Loading...
Searching...
No Matches
order_compute_scotch.c
Go to the documentation of this file.
1/**
2 *
3 * @file order_compute_scotch.c
4 *
5 * PaStiX order driver to perform ordering with Scotch library.
6 *
7 * @copyright 2004-2024 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
8 * Univ. Bordeaux. All rights reserved.
9 *
10 * @version 6.4.0
11 * @author Xavier Lacoste
12 * @author Pierre Ramet
13 * @author Mathieu Faverge
14 * @author Tony Delarue
15 * @author Vincent Bridonneau
16 * @date 2024-07-05
17 *
18 **/
19#include "common.h"
20#include "graph/graph.h"
21#include "order/order_internal.h"
22#if defined(PASTIX_ORDERING_PTSCOTCH)
23#include <ptscotch.h>
24#elif defined(PASTIX_ORDERING_SCOTCH)
25#include <scotch.h>
26#endif /* defined(PASTIX_ORDERING_PTSCOTCH) */
27
28/**
29 *******************************************************************************
30 *
31 * @ingroup pastix_order
32 *
33 * @brief Check the generated Scotch graph.
34 *
35 *******************************************************************************
36 *
37 * @param[in] graph
38 * Pointer to the SCOTCH_Graph structure.
39 *
40 * @param[in] procnum
41 * Procnum of the process. Output purpose.
42 *
43 *******************************************************************************/
44static inline void
45ocs_graph_check( const SCOTCH_Graph *graph,
46 int procnum )
47{
48#if defined(PASTIX_DEBUG_ORDERING)
49 Clock timer;
50 clockStart(timer);
51 if ( SCOTCH_graphCheck( graph ) ) {
52 pastix_print_error( "pastix: graphCheck" );
53 }
54 clockStop(timer);
55 pastix_print( procnum, 0, "SCOTCH_graphCheck done in %lf second\n", clockVal(timer) );
56#else
57 (void)graph;
58 (void)procnum;
59#endif /* defined(PASTIX_DEBUG_ORDERING) */
60}
61
62/**
63 *******************************************************************************
64 *
65 * @ingroup pastix_order
66 *
67 * @brief Build the Scotch graph.
68 *
69 *******************************************************************************
70 *
71 * @param[inout] scotchgraph
72 * The SCOTCH_Graph structure that will be build.
73 *
74 * @param[inout] graph
75 * The graph prepared by graphPrepare function on which we want to
76 * perform the ordering.
77 *
78 *******************************************************************************/
79static inline void
80ocs_graph_init( SCOTCH_Graph *scotchgraph,
81 pastix_graph_t *graph )
82{
83 pastix_int_t *colptr, *rowptr;
84 pastix_int_t *weights;
85 pastix_int_t n, nnz, baseval;
86
87 /* Make sure graph is 0-based */
88 graphBase( graph, 0 );
89
90 n = graph->n;
91 nnz = graph->nnz;
92 colptr = graph->colptr;
93 rowptr = graph->rowptr;
94 baseval = graph->baseval;
95 weights = NULL;
96
97 assert( baseval == colptr[0] );
98 assert( nnz == colptr[n] - colptr[0] );
99
100 SCOTCH_graphInit( scotchgraph );
101
102 /*
103 * Generate the vertex load array if dof != 1
104 */
105 weights = graphGetWeights( graph );
106
107 if ( SCOTCH_graphBuild( scotchgraph, /* Graph to build */
108 baseval, /* baseval */
109 n, /* Number of vertices */
110 colptr, /* Vertex array */
111 NULL,
112 weights, /* Array of vertex weights (DOFs) */
113 NULL,
114 nnz, /* Number of arcs */
115 rowptr, /* Edge array */
116 NULL) )
117 {
118 pastix_print_error( "pastix : SCOTCH_graphBuild" );
119 }
120
121 /* Check the generated Scotch graph structure */
122 ocs_graph_check( scotchgraph, 0 );
123
124 return;
125}
126
127/**
128 *******************************************************************************
129 *
130 * @ingroup pastix_order
131 *
132 * @brief Cleanup the Scotch graph structure and free the associated data.
133 *
134 *******************************************************************************
135 *
136 * @param[inout] scotchgraph
137 * The Scotch graph structure that will be cleaned.
138 *
139 *******************************************************************************/
140static inline void
141ocs_graph_exit( SCOTCH_Graph *scotchgraph )
142{
143 pastix_int_t *colptr = NULL;
144 pastix_int_t *rowptr = NULL;
145 pastix_int_t *weights = NULL;
146
147 SCOTCH_graphData (
148 scotchgraph,
149 NULL, /* Base value */
150 NULL, /* Number of vertices */
151 &colptr, /* Vertex array [vertnbr+1] */
152 NULL, /* Vertex array [vertnbr] */
153 &weights, /* Vertex load array */
154 NULL, /* Vertex label array */
155 NULL, /* Number of edges (arcs) */
156 &rowptr, /* Edge array [edgenbr] */
157 NULL /* Edge load array */ );
158
159 /* Free the vertex load array */
160 if ( weights != NULL ) {
161 memFree_null( weights );
162 }
163
164 SCOTCH_graphExit( scotchgraph );
165
166 return;
167}
168
169/**
170 *******************************************************************************
171 *
172 * @ingroup pastix_order
173 *
174 * @brief Compute the graph ordering
175 *
176 *******************************************************************************
177 *
178 * @param[inout] pastix_data
179 * Pointer to the pastix_data instance.
180 *
181 * @param[inout] scotchgraph
182 * The SCOTCH_Graph structure that will be ordered.
183 *
184 ********************************************************************************
185 *
186 * @retval The return value of SCOTCH_graphOrderList.
187 *
188 *******************************************************************************/
189static inline int
191 SCOTCH_Graph *scotchgraph )
192{
193 pastix_order_t *ordemesh = pastix_data->ordemesh;
194 SCOTCH_Strat stratdat;
195 int ret;
196 char *strat;
197
198 /* Create Strategy string for Scotch */
199 SCOTCH_stratInit( &stratdat );
200 strat = order_scotch_build_strategy( pastix_data->iparm, pastix_data->procnum, 0 );
201
202 /* Make sure the call to flex/yacc is serialized thanks to a global lock */
203 {
204 static volatile pastix_atomic_lock_t strat_lock = PASTIX_ATOMIC_UNLOCKED;
205 pastix_atomic_lock( &strat_lock );
206 ret = SCOTCH_stratGraphOrder( &stratdat, strat );
207 pastix_atomic_unlock( &strat_lock );
208 }
209
210 if ( ret == 0 ) {
211 /* Compute graph ordering memory */
212 ret = SCOTCH_graphOrderList( scotchgraph,
213 (SCOTCH_Num) ordemesh->vertnbr,
214 (SCOTCH_Num *) NULL,
215 &stratdat,
216 (SCOTCH_Num *) ordemesh->permtab,
217 (SCOTCH_Num *) ordemesh->peritab,
218 (SCOTCH_Num *)&ordemesh->cblknbr,
219 (SCOTCH_Num *) ordemesh->rangtab,
220 (SCOTCH_Num *) ordemesh->treetab );
221 }
222 SCOTCH_stratExit( &stratdat );
223
224 memFree_null( strat );
225 return ret;
226}
227
228#if defined(PASTIX_ORDERING_SCOTCH_MT)
229struct args_ocs_mt {
230 pastix_data_t *pastix_data;
231 SCOTCH_Context *scotch_ctx;
232 SCOTCH_Graph *scotch_grf;
233 int ret;
234};
235
236/**
237 *******************************************************************************
238 *
239 * @ingroup pastix_order
240 *
241 * @brief Compute the ordering step in shared memory.
242 *
243 *******************************************************************************
244 *
245 * @param[in] ctx
246 * The pastix shared memory context
247 *
248 * @param[inout] args
249 * Shared args for the computation
250 *
251 *******************************************************************************/
252static inline void
253ocs_compute_graph_ordering_mt( isched_thread_t *ctx, void *args )
254{
255 struct args_ocs_mt *arg = (struct args_ocs_mt *)args;
256 pastix_data_t *pastix_data = arg->pastix_data;
257 SCOTCH_Context *sctx = arg->scotch_ctx;
258 int rank = ctx->rank;
259
260 if ( rank == 0 ) {
261 SCOTCH_contextInit( sctx ); /* Initialize context */
262 SCOTCH_contextRandomClone( sctx ); /* Set private random generator */
263
264 /* Enable this define to fix the SCOTCH random generator */
265#if defined(PASTIX_ORDERING_FIX_SEED)
266 SCOTCH_contextRandomSeed( sctx, (SCOTCH_Num)(pastix_data->id) );
267#if defined(SCOTCH_OPTIONNUMDETERMINISTIC)
268 /* Makes scotch deterministic */
269 SCOTCH_contextOptionSetNum( sctx, SCOTCH_OPTIONNUMDETERMINISTIC, 1 );
270#endif
271#endif
272
273 /*
274 * Initiates the capture, into the given context,
275 * of an existing pool of threads.
276 */
277 SCOTCH_contextThreadImport1( sctx, pastix_data->isched->world_size );
278 }
279
280 /* Synchronize all threads */
281 isched_barrier_wait( &(ctx->global_ctx->barrier) );
282
283 /* Finalyse the capture */
284 SCOTCH_contextThreadImport2( sctx, rank );
285
286 if ( rank == 0 ) {
287 SCOTCH_Graph *scotchgraph0 = arg->scotch_grf;
288 SCOTCH_Graph scotchgraph1;
289 int ret;
290
291 /* Initialize MT graph, and bind it to the global one in the Scotch context */
292 SCOTCH_graphInit( &scotchgraph1 );
293 SCOTCH_contextBindGraph( sctx, scotchgraph0, &scotchgraph1 );
294
295 /* Compute the ordering */
296 ret = ocs_compute_graph_ordering( pastix_data, &scotchgraph1 );
297
298 /* Destroy the context graph */
299 SCOTCH_graphExit( &scotchgraph1 );
300
301 /* Destroy the context and release the slave threads */
302 SCOTCH_contextExit( sctx );
303
304 arg->ret = ret;
305 }
306}
307#endif
308
309/**
310 *******************************************************************************
311 *
312 * @ingroup pastix_order
313 *
314 * @brief Compute the ordering of the graph given as parameter
315 * with Scotch library.
316 *
317 * This routine is affected by the following parameters:
318 * IPARM_VERBOSE, IPARM_ORDERING_DEFAULT, IPARM_SCOTCH_SWITCH_LEVEL,
319 * IPARM_SCOTCH_CMIN, IPARM_SCOTCH_CMAX, IPARM_SCOTCH_FRAT
320 * If PASTIX_ORDERING_SCOTCH_MT is enabled, we will compute the ordering
321 * in shared memory
322 *
323 *******************************************************************************
324 *
325 * @param[inout] pastix_data
326 * The pastix_data structure that describes the solver instance.
327 * On exit, the field ordemesh is initialized with the result of the
328 * ordering realized by Scotch.
329 *
330 * @param[inout] graph
331 * The graph prepared by graphPrepare function on which we want to
332 * perform the ordering. On exit, the graph might be rebased.
333 *
334 *******************************************************************************
335 *
336 * @retval PASTIX_SUCCESS on successful exit,
337 * @retval PASTIX_ERR_BADPARAMETER if one parameter is incorrect,
338 * @retval PASTIX_ERR_OUTOFMEMORY if one allocation failed,
339 * @retval PASTIX_ERR_INTEGER_TYPE if Scotch integer type is not the
340 * same size as PaStiX ones,
341 * @retval PASTIX_ERR_INTERNAL if an error occurs internally to Scotch.
342 *
343 *******************************************************************************/
344int
346 pastix_graph_t *graph )
347{
348 SCOTCH_Graph scotchgraph;
349 int ret = PASTIX_SUCCESS;
350 pastix_order_t *ordemesh = pastix_data->ordemesh;
351
352 /* Check integer compatibility */
353 if ( sizeof(pastix_int_t) != sizeof(SCOTCH_Num) ) {
354 pastix_print_error( "orderComputeScotch: Inconsistent integer type between Pastix and Scotch\n" );
356 }
357
358 /*
359 * Enable this define to fix the SCOTCH random generator
360 * compiling with SCOTCH_DETERMINISTIC is nonetheless advised
361 */
362#if defined(PASTIX_ORDERING_FIX_SEED)
363 SCOTCH_randomSeed( (SCOTCH_Num)(pastix_data->id) );
364 SCOTCH_randomReset();
365#endif
366
367 /* Build The Scotch Graph */
368 ocs_graph_init( &scotchgraph, graph );
369
370 /* Allocate the ordering structure */
371 pastixOrderAlloc( ordemesh, graph->n, graph->n );
372
373 /*
374 * Compute the ordering
375 */
376#if defined(PASTIX_ORDERING_SCOTCH_MT)
377 if ( pastix_data->iparm[IPARM_SCOTCH_MT] )
378 {
379 SCOTCH_Context sctx;
380
381 struct args_ocs_mt args = {
382 .pastix_data = pastix_data,
383 .scotch_ctx = &sctx,
384 .scotch_grf = &scotchgraph,
385 .ret = ret,
386 };
387 isched_parallel_call( pastix_data->isched, ocs_compute_graph_ordering_mt, &args );
388 ret = args.ret;
389 }
390 else
391#endif
392 {
393 ret = ocs_compute_graph_ordering( pastix_data, &scotchgraph );
394 }
395
396 /* Free the Scotch graph structure */
397 ocs_graph_exit( &scotchgraph );
398
399 /* If something has failed in Scotch */
400 if ( ret != PASTIX_SUCCESS ) {
401 pastixOrderExit( ordemesh );
402 return PASTIX_ERR_INTERNAL;
403 }
405
406 return ret;
407}
BEGIN_C_DECLS typedef int pastix_int_t
Definition datatypes.h:51
@ IPARM_SCOTCH_MT
Definition api.h:54
@ PASTIX_ERR_INTERNAL
Definition api.h:373
@ PASTIX_ERR_INTEGER_TYPE
Definition api.h:376
@ PASTIX_SUCCESS
Definition api.h:367
void graphBase(pastix_graph_t *graph, pastix_int_t baseval)
Rebase the graph to the given value.
Definition graph.c:102
pastix_int_t * graphGetWeights(const pastix_graph_t *graph)
Build the vertex weight array out of the dof array.
Definition graph.c:433
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
static int ocs_compute_graph_ordering(pastix_data_t *pastix_data, SCOTCH_Graph *scotchgraph)
Compute the graph ordering.
void order_scotch_reallocate_ordemesh(pastix_order_t *ordemesh)
Reallocate the ordering structure.
static void ocs_graph_check(const SCOTCH_Graph *graph, int procnum)
Check the generated Scotch graph.
int orderComputeScotch(pastix_data_t *pastix_data, pastix_graph_t *graph)
Compute the ordering of the graph given as parameter with Scotch library.
static void ocs_graph_exit(SCOTCH_Graph *scotchgraph)
Cleanup the Scotch graph structure and free the associated data.
char * order_scotch_build_strategy(const pastix_int_t *iparm, pastix_int_t procnum, int isPTscotch)
Generate the ordering strategy string based on the input parameters.
static void ocs_graph_init(SCOTCH_Graph *scotchgraph, pastix_graph_t *graph)
Build the Scotch graph.
void pastixOrderExit(pastix_order_t *ordeptr)
Free the arrays initialized in the order structure.
Definition order.c:273
Order structure.
Definition order.h:47
pastix_order_t * ordemesh
Definition pastixdata.h:98
pastix_int_t * iparm
Definition pastixdata.h:70
pastix_int_t id
Definition pastixdata.h:69
isched_t * isched
Definition pastixdata.h:86
Main PaStiX data structure.
Definition pastixdata.h:68