Zoltan2
Loading...
Searching...
No Matches
Zoltan2_findUniqueGids.hpp
Go to the documentation of this file.
1// @HEADER
2//
3// ***********************************************************************
4//
5// Zoltan2: A package of combinatorial algorithms for scientific computing
6// Copyright 2012 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Karen Devine (kddevin@sandia.gov)
39// Erik Boman (egboman@sandia.gov)
40// Siva Rajamanickam (srajama@sandia.gov)
41//
42// ***********************************************************************
43//
44// @HEADER
45
51#ifndef _ZOLTAN2_FINDUNIQUEGIDS_HPP_
52#define _ZOLTAN2_FINDUNIQUEGIDS_HPP_
53
54#include <Zoltan2_Standards.hpp>
55#include <vector>
56
57#include <Tpetra_MultiVector.hpp>
58#include <Tpetra_Vector.hpp>
59
60#include <Zoltan2_TPLTraits.hpp>
61
62#include <zoltan_dd.h>
63#include <zoltan_dd_const.h>
64
65namespace Zoltan2
66{
67
68template <typename gno_t>
70 size_t num_keys,
71 int num_gid,
72 ZOLTAN_ID_PTR ddkeys,
73 char *ddnewgids,
74 MPI_Comm mpicomm
75)
76{
77 int num_lid = 0; // Local IDs not needed
78 int debug_level = 0;
79 int num_user = sizeof(gno_t);
80
81 Zoltan_DD_Struct *dd = NULL;
82 Zoltan_DD_Create(&dd, mpicomm, num_gid, num_lid, num_user, num_keys,
83 debug_level);
84
85 ZOLTAN_ID_PTR ddnotneeded = NULL; // Local IDs not needed
86 Zoltan_DD_Update(dd, ddkeys, ddnotneeded, ddnewgids, NULL, int(num_keys));
87
89 // Insert unique GIDs for DD entries in User data here.
90
91 // Get value of first gid on this rank
92 typedef long long mpi_t;
93 mpi_t nDDEntries = (mpi_t)(dd->nodecnt);
94 mpi_t firstIdx;
95 MPI_Scan(&nDDEntries, &firstIdx, 1, MPI_LONG_LONG, MPI_SUM, mpicomm);
96 firstIdx -= nDDEntries; // do not include this rank's entries in prefix sum
97
98 // Loop over all directory entries, updating their userdata with updated gid
99 DD_NodeIdx cnt = 0;
100
101 for (DD_NodeIdx i = 0; i < dd->nodelistlen; i++) {
102 DD_Node *ptr = &(dd->nodelist[i]);
103 if (!(ptr->free)) {
104 char *userchar = (char*)(ptr->gid + (dd->gid_length + dd->lid_length));
105 gno_t *newgid = (gno_t*) userchar;
106 *newgid = gno_t(firstIdx + cnt);
107 cnt++;
108 }
109 }
110
112 // Retrieve the global numbers and put in the result gids vector
113 Zoltan_DD_Find(dd, ddkeys, ddnotneeded, ddnewgids, NULL, int(num_keys), NULL);
114
115 Zoltan_DD_Destroy(&dd);
116
117 mpi_t nUnique = 0;
118 MPI_Allreduce(&nDDEntries, &nUnique, 1, MPI_LONG_LONG, MPI_SUM, mpicomm);
119
120 return size_t(nUnique);
121}
122
124template <typename lno_t, typename gno_t>
126 Tpetra::MultiVector<gno_t, lno_t, gno_t> &keys,
127 Tpetra::Vector<gno_t, lno_t, gno_t> &gids
128)
129{
130 // Input: Tpetra MultiVector of keys; key length = numVectors()
131 // May contain duplicate keys within a processor.
132 // May contain duplicate keys across processors.
133 // Input: Empty Tpetra Vector with same map for holding the results
134 // Output: Filled gids vector, containing unique global numbers for
135 // each unique key. Global numbers are in range [0,#UniqueKeys).
136
137 size_t num_keys = keys.getLocalLength();
138 size_t num_entries = keys.getNumVectors();
139
140#ifdef HAVE_ZOLTAN2_MPI
141 MPI_Comm mpicomm = Teuchos::getRawMpiComm(*(keys.getMap()->getComm()));
142#else
143 // Zoltan's siMPI will be used here
144 {
145 int flag;
146 MPI_Initialized(&flag);
147 if (!flag) {
148 int narg = 0;
149 char **argv = NULL;
150 MPI_Init(&narg, &argv);
151 }
152 }
153 MPI_Comm mpicomm = MPI_COMM_WORLD; // Will get MPI_COMM_WORLD from siMPI
154#endif
155
156 int num_gid = TPL_Traits<ZOLTAN_ID_PTR,gno_t>::NUM_ID * num_entries;
157 int num_user = sizeof(gno_t);
158
159 // Buffer the keys for Zoltan_DD
160 Teuchos::ArrayRCP<const gno_t> *tmpKeyVecs =
161 new Teuchos::ArrayRCP<const gno_t>[num_entries];
162 for (size_t v = 0; v < num_entries; v++) tmpKeyVecs[v] = keys.getData(v);
163
164 ZOLTAN_ID_PTR ddkeys = new ZOLTAN_ID_TYPE[num_gid * num_keys];
165 size_t idx = 0;
166 for (size_t i = 0; i < num_keys; i++) {
167 for (size_t v = 0; v < num_entries; v++) {
168 ZOLTAN_ID_PTR ddkey = &(ddkeys[idx]);
169 TPL_Traits<ZOLTAN_ID_PTR,gno_t>::ASSIGN(ddkey, tmpKeyVecs[v][i]);
171 }
172 }
173 delete [] tmpKeyVecs;
174
175 // Allocate memory for the result
176 char *ddnewgids = new char[num_user * num_keys];
177
178 // Compute the new GIDs
179 size_t nUnique = findUniqueGidsCommon<gno_t>(num_keys, num_gid,
180 ddkeys, ddnewgids, mpicomm);
181
182 // Copy the result into the output vector
183 gno_t *result = (gno_t *)ddnewgids;
184 for (size_t i = 0; i < num_keys; i++)
185 gids.replaceLocalValue(i, result[i]);
186
187 // Clean up
188 delete [] ddkeys;
189 delete [] ddnewgids;
190
191 return nUnique;
192}
193
195template <typename key_t, typename gno_t>
197 std::vector<key_t> &keys,
198 std::vector<gno_t> &gids,
199 const Teuchos::Comm<int> &comm
200)
201{
202 // Input: Vector of keys; key length = key_t.size()
203 // Each key must have the same size. std::array<gno_t, N> is
204 // an example of a good key_t.
205 // May contain duplicate keys within a processor.
206 // May contain duplicate keys across processors.
207 // Input: Empty vector for holding the results
208 // Output: Filled gids vector, containing unique global numbers for
209 // each unique key. Global numbers are in range [0,#UniqueKeys).
210 //
211 // Note: This code uses the Zoltan Distributed Directory to assign the
212 // unique global numbers. Right now, it hacks into the Zoltan_DD
213 // data structures. If we like this approach, we can add some
214 // elegance to the Zoltan_DD, allowing operations internal to the
215 // directory.
216
217 size_t num_keys = keys.size();
218 key_t dummy;
219 size_t num_entries = dummy.size();
220
221#ifdef HAVE_ZOLTAN2_MPI
222 MPI_Comm mpicomm = Teuchos::getRawMpiComm(comm);
223#else
224 // Zoltan's siMPI will be used here
225 {
226 int flag;
227 MPI_Initialized(&flag);
228 if (!flag) {
229 int narg = 0;
230 char **argv = NULL;
231 MPI_Init(&narg, &argv);
232 }
233 }
234 MPI_Comm mpicomm = MPI_COMM_WORLD; // Will get MPI_COMM_WORLD from siMPI
235#endif
236
237 int num_gid = TPL_Traits<ZOLTAN_ID_PTR,gno_t>::NUM_ID * num_entries;
238 int num_user = sizeof(gno_t);
239
240 // Buffer the keys for Zoltan_DD
241 ZOLTAN_ID_PTR ddkeys = new ZOLTAN_ID_TYPE[num_gid * num_keys];
242 size_t idx = 0;
243 for (size_t i = 0; i < num_keys; i++) {
244 for (size_t v = 0; v < num_entries; v++) {
245 ZOLTAN_ID_PTR ddkey = &(ddkeys[idx]);
248 }
249 }
250
251 // Allocate memory for the result
252 char *ddnewgids = new char[num_user * num_keys];
253
254 // Compute the new GIDs
255 size_t nUnique = findUniqueGidsCommon<gno_t>(num_keys, num_gid,
256 ddkeys, ddnewgids, mpicomm);
257
258 // Copy the result into the output vector
259 gno_t *result = (gno_t *)ddnewgids;
260 for (size_t i = 0; i < num_keys; i++)
261 gids[i] = result[i];
262
263 // Clean up
264 delete [] ddkeys;
265 delete [] ddnewgids;
266
267 return nUnique;
268}
269
270
271} // namespace Zoltan2
272#endif
Gathering definitions used in software development.
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t,...
map_t::global_ordinal_type gno_t
Created by mbenlioglu on Aug 31, 2020.
size_t findUniqueGids(Tpetra::MultiVector< gno_t, lno_t, gno_t > &keys, Tpetra::Vector< gno_t, lno_t, gno_t > &gids)
size_t findUniqueGidsCommon(size_t num_keys, int num_gid, ZOLTAN_ID_PTR ddkeys, char *ddnewgids, MPI_Comm mpicomm)
static void ASSIGN(first_t &a, second_t b)