Branch data Line data Source code
1 : : // *****************************************************************************
2 : : /*!
3 : : \file src/Partition/ZoltanGraph.cpp
4 : : \copyright 2012-2015 J. Bakosi,
5 : : 2016-2018 Los Alamos National Security, LLC.,
6 : : 2019-2021 Triad National Security, LLC.,
7 : : 2022-2024 J. Bakosi
8 : : All rights reserved. See the LICENSE file for details.
9 : : \brief Interoperation with the Zoltan library's graph partitioners.
10 : : */
11 : : // *****************************************************************************
12 : :
13 : : #include "Compiler.hpp"
14 : :
15 : : #if defined(__clang__)
16 : : #pragma clang diagnostic push
17 : : #elif defined(STRICT_GNUC)
18 : : #pragma GCC diagnostic push
19 : : #pragma GCC diagnostic ignored "-Wcast-function-type"
20 : : #endif
21 : :
22 : : #include "zoltan.h"
23 : :
24 : : #if defined(__clang__)
25 : : #pragma clang diagnostic pop
26 : : #elif defined(STRICT_GNUC)
27 : : #pragma GCC diagnostic pop
28 : : #endif
29 : :
30 : : #include "ZoltanGraph.hpp"
31 : : #include "ContainerUtil.hpp"
32 : : #include "DerivedData.hpp"
33 : : #include "Reorder.hpp"
34 : :
35 : : namespace inciter {
36 : :
37 : : //! Zoltan mesh data structure
38 : : struct MESH_DATA {
39 : : int numMyVertices; //!< number of vertices that I own initially
40 : : ZOLTAN_ID_TYPE* vtxGID; //!< global ID of these vertices
41 : : int numMyHEdges; //!< number of my hyperedges
42 : : int numAllNbors; //!< number of vertices in my hyperedges
43 : : ZOLTAN_ID_TYPE *edgeGID; //!< global ID of each of my hyperedges
44 : : int *nborIndex; //!< index into nborGID array of edge ids
45 : : ZOLTAN_ID_TYPE *nborGID; //!< array of edge ids
46 : : };
47 : :
48 : : static int
49 : 47 : get_number_of_objects( void* data, int* ierr ) {
50 : : MESH_DATA* mesh = static_cast< MESH_DATA* >( data );
51 : 47 : *ierr = ZOLTAN_OK;
52 : 47 : return mesh->numMyVertices;
53 : : }
54 : :
55 : : static void
56 : 29 : get_object_list( void *data, int /* sizeGID */, int /* sizeLID */,
57 : : ZOLTAN_ID_PTR globalID, ZOLTAN_ID_PTR localID,
58 : : int /* wgt_dim */, float* /*obj_wgts */, int* ierr )
59 : : {
60 : : MESH_DATA* mesh = static_cast< MESH_DATA* >( data );
61 : 29 : *ierr = ZOLTAN_OK;
62 [ + + ]: 72508 : for (int i=0; i<mesh->numMyVertices; ++i){
63 : 72479 : globalID[i] = mesh->vtxGID[i];
64 : 72479 : localID[i] = static_cast< ZOLTAN_ID_TYPE >( i );
65 : : }
66 : 29 : }
67 : :
68 : : static void
69 : 21 : get_hypergraph_size( void* data, int* num_lists, int* num_nonzeros,
70 : : int* format, int* ierr )
71 : : {
72 : : MESH_DATA* hg = static_cast< MESH_DATA* >( data );
73 : 21 : *ierr = ZOLTAN_OK;
74 : 21 : *num_lists = hg->numMyHEdges;
75 : 21 : *num_nonzeros = hg->numAllNbors;
76 : 21 : *format = ZOLTAN_COMPRESSED_EDGE;
77 : 21 : }
78 : :
79 : : static void
80 : 21 : get_hypergraph( void* data, int /* sizeGID */, int num_edges, int num_nonzeros,
81 : : int format, ZOLTAN_ID_PTR edgeGID, int* vtxPtr,
82 : : ZOLTAN_ID_PTR vtxGID, int* ierr )
83 : : {
84 : : MESH_DATA* hg = static_cast< MESH_DATA* >( data );
85 : 21 : *ierr = ZOLTAN_OK;
86 : :
87 [ + - ]: 21 : if ( (num_edges != hg->numMyHEdges) ||
88 [ + - ][ - + ]: 21 : (num_nonzeros != hg->numAllNbors) ||
89 : : (format != ZOLTAN_COMPRESSED_EDGE) )
90 : : {
91 : 0 : *ierr = ZOLTAN_FATAL;
92 : 0 : return;
93 : : }
94 : :
95 [ + + ]: 38240 : for (int i=0; i<num_edges; ++i) {
96 : 38219 : edgeGID[i] = hg->edgeGID[i];
97 : 38219 : vtxPtr[i] = hg->nborIndex[i];
98 : : }
99 : :
100 [ + + ]: 527444 : for (int i=0; i<num_nonzeros; ++i) vtxGID[i] = hg->nborGID[i];
101 : : }
102 : :
103 : : static void
104 [ + - ]: 21 : createHyperGraph( const std::vector< std::size_t >& gid,
105 : : const std::unordered_map< std::size_t,
106 : : std::vector< std::size_t > >& graph,
107 : : MESH_DATA& hg )
108 : : // *****************************************************************************
109 : : // Create hypergraph data structure for Zoltan
110 : : //! \param[in] gid Global node ids
111 : : //! \param[in] graph Aggregated mesh graph point connectivity
112 : : //! \param[inout] hg Hypergraph data structure to fill
113 : : //! \return Number of hyperedges in graph (number of nodes in our mesh chunk)
114 : : // *****************************************************************************
115 : : {
116 : : // Get number of points from graph
117 : : const auto npoin = graph.size();
118 : :
119 : : // Create hypergraph data structure based on mesh graph
120 : 21 : hg.numMyVertices = static_cast< int >( npoin );
121 : 21 : hg.numMyHEdges = hg.numMyVertices;
122 : 21 : hg.vtxGID = static_cast< ZOLTAN_ID_PTR >(
123 : 21 : malloc(sizeof(ZOLTAN_ID_TYPE) * npoin) );
124 : 21 : hg.edgeGID = static_cast< ZOLTAN_ID_PTR >(
125 : 21 : malloc(sizeof(ZOLTAN_ID_TYPE) * npoin) );
126 [ + - ]: 21 : hg.nborIndex = static_cast< int* >( malloc(sizeof(int) * (npoin+1)) );
127 : :
128 : : // generate linked vectors for points surrounding points and their indices
129 : : std::pair< std::vector< std::size_t >, std::vector< std::size_t > > psup;
130 : : auto& psup1 = psup.first;
131 : : auto& psup2 = psup.second;
132 [ + - ]: 21 : psup1.resize( 1, 0 );
133 [ + - ]: 21 : psup2.resize( 1, 0 );
134 : :
135 : : std::vector< std::size_t > gp;
136 [ + + ]: 92036 : for (std::size_t p=0; p<gid.size(); ++p) {
137 : : auto i = graph.find( gid[p] );
138 [ + + ]: 92015 : if (i == end(graph)) continue;
139 [ + - ]: 38219 : gp.push_back( gid[p] );
140 : : const auto& n = i->second;
141 [ + - ][ + - ]: 38219 : psup2.push_back( psup2.back() + n.size() );
142 [ + - ][ - - ]: 38219 : psup1.insert( end(psup1), begin(n), end(n) );
143 : : }
144 : :
145 : : Assert( gp.size() == graph.size(), "Size mismatch" );
146 : :
147 : : // Compute sum of number of vertices of hyperedges and allocate memory
148 : 21 : auto nedge = psup.first.size() - 1 + npoin;
149 : 21 : hg.numAllNbors = static_cast< int >( nedge );
150 : 21 : hg.nborGID = static_cast< ZOLTAN_ID_PTR >(
151 : 21 : malloc(sizeof(ZOLTAN_ID_TYPE) * nedge) );
152 : :
153 : : // Fill up hypergraph edge ids and their indices
154 : 21 : hg.nborIndex[0] = 0;
155 [ + + ]: 38240 : for (std::size_t p=0; p<npoin; ++p) {
156 : 38219 : auto g = static_cast< ZOLTAN_ID_TYPE >( gp[p] );
157 : 38219 : hg.vtxGID[p] = hg.edgeGID[p] = hg.nborGID[ hg.nborIndex[p] ] = g;
158 : : int j = 1;
159 [ + + ]: 527423 : for (auto i=psup2[p]+1; i<=psup2[p+1]; ++i, ++j) {
160 : 489204 : hg.nborGID[ hg.nborIndex[p] + j ] =
161 : : static_cast< ZOLTAN_ID_TYPE >( psup1[i] );
162 : : }
163 : 38219 : hg.nborIndex[p+1] = hg.nborIndex[p] + j;
164 : : }
165 : 21 : }
166 : :
167 : : std::unordered_map< std::size_t, std::size_t >
168 : 21 : graphPartMesh( const std::vector< std::size_t >& ginpoel,
169 : : const std::unordered_map< std::size_t,
170 : : std::vector< std::size_t > >& graph,
171 : : const std::vector< std::string >& zoltan_params,
172 : : int npart )
173 : : // *****************************************************************************
174 : : // Partition mesh using Zoltan with a geometric partitioner
175 : : //! \param[in] ginpoel Mesh connectivity with global ids
176 : : //! \param[in] graph Mesh graph point connectivity
177 : : //! \param[in] zoltan_params Extra parameters pass to zoltan
178 : : //! \param[in] npart Number of desired partitions
179 : : //! \return Array of chare ownership IDs mapping points owned to chares
180 : : //! \details This function uses Zoltan to partition the mesh in parallel.
181 : : //! It assumes that the mesh is distributed among all the MPI ranks.
182 : : // *****************************************************************************
183 : : {
184 : : float ver;
185 : : struct Zoltan_Struct *zz;
186 : : int changes, numGidEntries, numLidEntries, numImport, numExport;
187 : : ZOLTAN_ID_PTR importGlobalGids, importLocalGids, exportGlobalGids,
188 : : exportLocalGids;
189 : : int *importProcs, *importToPart, *exportProcs, *exportToPart;
190 : :
191 : 21 : Zoltan_Initialize( 0, nullptr, &ver );
192 : :
193 : 21 : zz = Zoltan_Create( MPI_COMM_WORLD );
194 : :
195 : 21 : Zoltan_Set_Param( zz, "DEBUG_LEVEL", "0" );
196 : 21 : Zoltan_Set_Param( zz, "PHG_OUTPUT_LEVEL", "0" );
197 : 21 : Zoltan_Set_Param( zz, "LB_METHOD", "HYPERGRAPH" );
198 : 21 : Zoltan_Set_Param( zz, "HYPERGRAPH_PACKAGE", "PHG" );
199 : 21 : Zoltan_Set_Param( zz, "LB_APPROACH", "PARTITION" );
200 : 21 : Zoltan_Set_Param( zz, "NUM_GID_ENTRIES", "1" );
201 : 21 : Zoltan_Set_Param( zz, "NUM_LID_ENTRIES", "1" );
202 : 21 : Zoltan_Set_Param( zz, "OBJ_WEIGHT_DIM", "0" );
203 : 21 : Zoltan_Set_Param( zz, "EDGE_WEIGHT_DIM", "0" );
204 : 21 : Zoltan_Set_Param( zz, "RETURN_LISTS", "PART" );
205 [ + - ]: 21 : Zoltan_Set_Param( zz, "NUM_GLOBAL_PARTS", std::to_string(npart).c_str() );
206 : :
207 [ + + ]: 31 : for (std::size_t i=0; i<zoltan_params.size()/2; ++i) {
208 : 10 : const auto p = zoltan_params.data() + i*2;
209 : 10 : Zoltan_Set_Param( zz, p[0].c_str(), p[1].c_str() );
210 : : }
211 : :
212 : : // Generate element connectivity storing local node ids
213 : 21 : const auto& [ inpoel, gid, lid ] = tk::global2local( ginpoel );
214 : :
215 : : MESH_DATA myMesh;
216 [ + - ]: 21 : createHyperGraph( gid, graph, myMesh );
217 : :
218 : : // Set Zoltan query functions
219 [ + - ]: 21 : Zoltan_Set_Num_Obj_Fn( zz, get_number_of_objects, &myMesh );
220 [ + - ]: 21 : Zoltan_Set_Obj_List_Fn( zz, get_object_list, &myMesh );
221 [ + - ]: 21 : Zoltan_Set_HG_Size_CS_Fn( zz, get_hypergraph_size, &myMesh );
222 [ + - ]: 21 : Zoltan_Set_HG_CS_Fn( zz, get_hypergraph, &myMesh );
223 : : //Zoltan_Set_HG_Size_CS_Fn( zz, get_hypergraph_size, &myMesh );
224 : :
225 [ + - ]: 21 : Zoltan_LB_Partition(zz, /* input (all remaining fields are output) */
226 : : &changes, /* 1 if partitioning was changed, 0 otherwise */
227 : : &numGidEntries, /* Number of integers used for a global ID */
228 : : &numLidEntries, /* Number of integers used for a local ID */
229 : : &numImport, /* Number of vertices to be sent to me */
230 : : &importGlobalGids, /* Global IDs of vertices to be sent to me */
231 : : &importLocalGids, /* Local IDs of vertices to be sent to me */
232 : : &importProcs, /* Process rank for source of each incoming vertex */
233 : : &importToPart, /* New partition for each incoming vertex */
234 : : &numExport, /* Number of vertices I must send to other processes*/
235 : : &exportGlobalGids, /* Global IDs of the vertices I must send */
236 : : &exportLocalGids, /* Local IDs of the vertices I must send */
237 : : &exportProcs, /* Process to which I send each of the vertices */
238 : : &exportToPart); /* Partition to which each vertex will belong */
239 : :
240 : : Assert( numExport == static_cast< int >( graph.size() ), "Size mismatch" );
241 : :
242 [ + - ]: 21 : if (myMesh.numMyVertices > 0) free( myMesh.vtxGID );
243 [ + - ]: 21 : if (myMesh.numMyHEdges > 0) free( myMesh.edgeGID );
244 [ + - ]: 21 : if (myMesh.numMyHEdges >= 0) free( myMesh.nborIndex );
245 [ + - ]: 21 : if (myMesh.numAllNbors > 0) free( myMesh.nborGID );
246 : :
247 : : // Copy over array of chare IDs corresponding to the ownership of vertices in
248 : : // our chunk of the mesh, i.e., the coloring or chare ids for the mesh nodes
249 : : // we operate on.
250 : : std::unordered_map< std::size_t, std::size_t > chp;
251 [ + + ]: 38240 : for (std::size_t p=0; p<static_cast<std::size_t>(numExport); ++p ) {
252 [ + - ]: 38219 : chp[ exportGlobalGids[p] ] = static_cast< std::size_t >( exportToPart[p] );
253 : : }
254 : :
255 : : // Free the arrays allocated by Zoltan_LB_Partition
256 [ + - ]: 21 : Zoltan_LB_Free_Part( &importGlobalGids, &importLocalGids,
257 : : &importProcs, &importToPart );
258 [ + - ]: 21 : Zoltan_LB_Free_Part( &exportGlobalGids, &exportLocalGids,
259 : : &exportProcs, &exportToPart );
260 : : // Fee the storage allocated for the Zoltan structure
261 [ + - ]: 21 : Zoltan_Destroy( &zz );
262 : :
263 : 21 : return chp;
264 : : }
265 : :
266 : : } // inciter::
|
