1 /* Copyright 2007-2010,2012 IPB, Universite de Bordeaux, 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 : dgraph.h **/ 35 /** **/ 36 /** AUTHOR : Francois PELLEGRINI **/ 37 /** Francois CHATENET (P0.0) **/ 38 /** Sebastien FOUCAULT (P0.0) **/ 39 /** Nicolas GICQUEL (P0.1) **/ 40 /** Jerome LACOSTE (P0.1) **/ 41 /** Cedric CHEVALIER (v5.0) **/ 42 /** **/ 43 /** FUNCTION : These lines are the data declarations **/ 44 /** for the distributed source graph **/ 45 /** structure. **/ 46 /** **/ 47 /** DATES : # Version P0.0 : from : 01 apr 1997 **/ 48 /** to : 20 jun 1997 **/ 49 /** # Version P0.1 : from : 07 apr 1998 **/ 50 /** to : 20 jun 1998 **/ 51 /** # Version P0.2 : from : 11 may 1999 **/ 52 /** to : 02 feb 2000 **/ 53 /** # Version P0.3 : from : 16 jun 2005 **/ 54 /** to : 16 jun 2005 **/ 55 /** # Version 5.0 : from : 22 jul 2005 **/ 56 /** to : 03 aug 2007 **/ 57 /** # Version 5.1 : from : 11 nov 2007 **/ 58 /** to : 20 feb 2011 **/ 59 /** # Version 6.0 : from : 30 aug 2012 **/ 60 /** to : 26 sep 2012 **/ 61 /** **/ 62 /************************************************************/ 63 64 #define DGRAPH_H 65 66 #define PTSCOTCH_FOLD_DUP /* Activate folding on coarsening */ 67 68 #ifndef SCOTCH_COMM_PTOP_RAT 69 #define SCOTCH_COMM_PTOP_RAT 0.25 /* Percentage under which point-to-point is allowed */ 70 #endif /* SCOTCH_COMM_PTOP_RAT */ 71 72 /* 73 ** The defines. 74 */ 75 76 /* Graph flags. */ 77 78 #define DGRAPHNONE 0x0000 /* No options set */ 79 80 #define DGRAPHFREEPRIV 0x0001 /* Set if private arrays freed on exit */ 81 #define DGRAPHFREECOMM 0x0002 /* MPI communicator has to be freed */ 82 #define DGRAPHFREETABS 0x0004 /* Set if local arrays freed on exit */ 83 #define DGRAPHFREEPSID 0x0008 /* Set if procsidtab freed on exit */ 84 #define DGRAPHFREEEDGEGST 0x0010 /* Set if edgegsttab freed on exit */ 85 #define DGRAPHHASEDGEGST 0x0020 /* Edge ghost array computed */ 86 #define DGRAPHVERTGROUP 0x0040 /* All vertex arrays grouped */ 87 #define DGRAPHEDGEGROUP 0x0080 /* All edge arrays grouped */ 88 #define DGRAPHFREEALL (DGRAPHFREEPRIV | DGRAPHFREECOMM | DGRAPHFREETABS | DGRAPHFREEPSID | DGRAPHFREEEDGEGST) 89 #define DGRAPHCOMMPTOP 0x0100 /* Use point-to-point collective communication */ 90 91 #define DGRAPHBITSUSED 0x01FF /* Significant bits for plain distributed graph routines */ 92 #define DGRAPHBITSNOTUSED 0x0200 /* Value above which bits not used by plain distributed graph routines */ 93 94 /* Used in algorithms */ 95 96 #define COARPERTPRIME 31 /* Prime number */ 97 #define COARHASHPRIME 179 /* Prime number */ 98 99 /* 100 ** The type and structure definitions. 101 */ 102 103 /* The graph basic types, which must be signed. */ 104 105 #ifndef GNUMMAX /* If graph.h not included */ 106 typedef INT Gnum; /* Vertex or edge number */ 107 #define GNUMMAX (INTVALMAX) /* Maximum Gnum value */ 108 #define GNUMSTRING INTSTRING /* String to printf a Gnum */ 109 #endif /* GNUMMAX */ 110 111 #define GNUM_MPI COMM_INT /* MPI type for Gnum is MPI type for INT */ 112 113 #define GRAPHPART_MPI COMM_BYTE /* Raw byte type for graph parts */ 114 115 /* Tags used for point-to-point communications. */ 116 117 typedef enum DgraphTag_ { 118 TAGPROCVRTTAB = 0, /*+ procvrttab message +*/ 119 TAGVERTLOCTAB, /*+ vertloctab message +*/ 120 TAGVENDLOCTAB, /*+ vendloctab message +*/ 121 TAGVELOLOCTAB, /*+ veloloctab message +*/ 122 TAGVNUMLOCTAB, /*+ vnumloctab message +*/ 123 TAGVLBLLOCTAB, /*+ vlblloctab message +*/ 124 TAGEDGELOCTAB, /*+ edgeloctab message +*/ 125 TAGEDLOLOCTAB, /*+ edloloctab message +*/ 126 TAGDATALOCTAB, /*+ Generic data message +*/ 127 TAGOK, /*+ Positive answer +*/ 128 TAGBAD, /*+ Negative answer +*/ 129 TAGHALO = 100, /*+ Tag class for halo +*/ 130 TAGCOARSEN = 200, /*+ Tag class for coarsening +*/ 131 TAGMATCH = 300, /*+ Tag class for matching +*/ 132 TAGFOLD = 400, /*+ Tag class for folding +*/ 133 TAGBAND = 500 /*+ Tag class for band graph +*/ 134 } DgraphTag; 135 136 /*+ The graph flag type. +*/ 137 138 typedef int DgraphFlag; /*+ Graph property flags +*/ 139 140 /*+ The vertex part type, in compressed form. From graph.h +*/ 141 142 #ifndef GRAPH_H 143 typedef byte GraphPart; 144 #endif /* GRAPH_H */ 145 146 /* The distributed graph structure. */ 147 148 typedef struct Dgraph_ { 149 DgraphFlag flagval; /*+ Graph properties +*/ 150 Gnum baseval; /*+ Base index for edge/vertex arrays +*/ 151 Gnum vertglbnbr; /*+ Global number of vertices +*/ 152 Gnum vertglbmax; /*+ Maximum number of local vertices over all processes +*/ 153 Gnum vertgstnbr; /*+ Number of local + ghost vertices +*/ 154 Gnum vertgstnnd; /*+ vertgstnbr + baseval +*/ 155 Gnum vertlocnbr; /*+ Local number of vertices +*/ 156 Gnum vertlocnnd; /*+ Local number of vertices + baseval +*/ 157 Gnum * vertloctax; /*+ Local vertex beginning index array [based] +*/ 158 Gnum * vendloctax; /*+ Local vertex end index array [based] +*/ 159 Gnum * veloloctax; /*+ Local vertex load array if present +*/ 160 Gnum velolocsum; /*+ Local sum of all vertex loads +*/ 161 Gnum veloglbsum; /*+ Global sum of all vertex loads +*/ 162 Gnum * vnumloctax; /*+ Arrays of global vertex numbers in original graph +*/ 163 Gnum * vlblloctax; /*+ Arrays of vertex labels (when read from file) +*/ 164 Gnum edgeglbnbr; /*+ Global number of arcs +*/ 165 Gnum edgeglbmax; /*+ Maximum number of local edges over all processes +*/ 166 Gnum edgelocnbr; /*+ Number of local edges +*/ 167 Gnum edgelocsiz; /*+ Size of local edge array (= edgelocnbr when compact) +*/ 168 Gnum edgeglbsmx; /*+ Maximum size of local edge arrays over all processes +*/ 169 Gnum * edgegsttax; /*+ Edge array holding local indices of neighbors [based] +*/ 170 Gnum * edgeloctax; /*+ Edge array holding global neighbor numbers [based] +*/ 171 Gnum * edloloctax; /*+ Edge load array +*/ 172 Gnum degrglbmax; /*+ Maximum degree over all processes +*/ 173 MPI_Comm proccomm; /*+ Graph communicator +*/ 174 int prockeyval; /*+ Communicator key value: folded communicators are distinct +*/ 175 int procglbnbr; /*+ Number of processes sharing graph data +*/ 176 int proclocnum; /*+ Number of this process +*/ 177 Gnum * procvrttab; /*+ Global array of vertex number ranges [+1,based] +*/ 178 Gnum * proccnttab; /*+ Count array for local number of vertices +*/ 179 Gnum * procdsptab; /*+ Displacement array with respect to proccnttab [+1,based] +*/ 180 int procngbnbr; /*+ Number of neighboring processes +*/ 181 int procngbmax; /*+ Maximum number of neighboring processes +*/ 182 int * procngbtab; /*+ Array of neighbor process numbers [sorted] +*/ 183 int * procrcvtab; /*+ Number of vertices to receive in ghost vertex sub-arrays +*/ 184 int procsndnbr; /*+ Overall size of local send array +*/ 185 int * procsndtab; /*+ Number of vertices to send in ghost vertex sub-arrays +*/ 186 int * procsidtab; /*+ Array of indices to build communication vectors (send) +*/ 187 int procsidnbr; /*+ Size of the send index array +*/ 188 } Dgraph; 189 190 /* 191 ** The function prototypes. 192 */ 193 194 int dgraphInit (Dgraph * const, MPI_Comm); 195 void dgraphExit (Dgraph * const); 196 void dgraphFree (Dgraph * const); 197 int dgraphLoad (Dgraph * const, FILE * const, const Gnum, const DgraphFlag); 198 int dgraphSave (Dgraph * const, FILE * const); 199 int dgraphBuild (Dgraph * const, const Gnum, const Gnum, const Gnum, Gnum * const, Gnum * const, Gnum * const, Gnum * const, Gnum * const, const Gnum, const Gnum, Gnum * const, Gnum * const, Gnum * const); 200 int dgraphBuild2 (Dgraph * const, const Gnum, const Gnum, const Gnum, Gnum * const, Gnum * const, Gnum * const, const Gnum, Gnum * const, Gnum * const, const Gnum, const Gnum, Gnum * const, Gnum * const, Gnum * const, const Gnum); 201 int dgraphBuild3 (Dgraph * const, const Gnum, const Gnum, Gnum * const, Gnum * const, Gnum * const, const Gnum, Gnum * const, Gnum * const, const Gnum, const Gnum, Gnum * const, Gnum * const, Gnum * const, const Gnum); 202 int dgraphBuild4 (Dgraph * const); 203 int dgraphBuildHcub (Dgraph * const, const Gnum, const Gnum, const Gnum); 204 int dgraphBuildGrid3D (Dgraph * const, const Gnum, const Gnum, const Gnum, const Gnum, const Gnum, const int); 205 int dgraphCheck (const Dgraph * const); 206 int dgraphView (const Dgraph * const, FILE * const); 207 int dgraphGhst2 (Dgraph * const, const int); 208 int dgraphBand (Dgraph * restrict const, const Gnum, Gnum * restrict const, const GraphPart * restrict const, const Gnum, const Gnum, Gnum, Dgraph * restrict const, Gnum * restrict * const, GraphPart * restrict * const, Gnum * const, Gnum * const, Gnum * const); 209 210 int dgraphFold (const Dgraph * restrict const, const int, Dgraph * restrict const, const void * restrict const, void ** restrict const, MPI_Datatype); 211 int dgraphFold2 (const Dgraph * restrict const, const int, Dgraph * restrict const, MPI_Comm, const void * restrict const, void ** restrict const, MPI_Datatype); 212 int dgraphFoldDup (const Dgraph * restrict const, Dgraph * restrict const, void * restrict const, void ** restrict const, MPI_Datatype); 213 int dgraphInduce2 (Dgraph * restrict const, Gnum (*) (Dgraph * restrict const, Dgraph * restrict const, const void * restrict const, Gnum * restrict const), const void * const, const Gnum, Gnum *, Dgraph * restrict const); 214 215 int dgraphInduceList (Dgraph * const, const Gnum, const Gnum * const, Dgraph * const); 216 int dgraphInducePart (Dgraph * const, const GraphPart * restrict const, const Gnum, const GraphPart, Dgraph * const); 217 #ifdef GRAPH_H 218 int dgraphGather (const Dgraph * restrict const, Graph * restrict); 219 int dgraphGather2 (const Dgraph * restrict const, Graph * restrict, const int, const Gnum); 220 int dgraphGatherAll (const Dgraph * restrict const, Graph * restrict); 221 int dgraphGatherAll2 (const Dgraph * restrict const, Graph * restrict, const Gnum, const int); 222 int dgraphScatter (Dgraph * const, const Graph * const); 223 #endif /* GRAPH_H */ 224 225 int dgraphHaloSync (Dgraph * const, void * const, MPI_Datatype); 226 227 /* 228 ** The macro definitions. 229 */ 230 231 #define dgraphGhst(grafptr) dgraphGhst2 (grafptr, 0) /* Build ghost edge array in addition to local edge array */ 232 #define dgraphGhstReplace(grafptr) dgraphGhst2 (grafptr, 1) /* Replace local edge array by ghost edge array */ 233 #define dgraphHasGhst(grafptr) (((grafptr)->flagval & DGRAPHHASEDGEGST) != 0) /* If graph has a ghost edge array */ 234