Zoltan2
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 
65 namespace Zoltan2
66 {
67 
68 template <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  ssize_t nDDEntries = (ssize_t)(dd->nodecnt);
93  ssize_t firstIdx;
94  MPI_Scan(&nDDEntries, &firstIdx, 1, MPI_LONG_LONG, MPI_SUM, mpicomm);
95  firstIdx -= nDDEntries; // do not include this rank's entries in prefix sum
96 
97  // Loop over all directory entries, updating their userdata with updated gid
98  DD_NodeIdx cnt = 0;
99  for (DD_NodeIdx i = 0; i < dd->nodelistlen; i++) {
100  DD_Node *ptr = &(dd->nodelist[i]);
101  if (!(ptr->free)) {
102  char *userchar = (char*)(ptr->gid + (dd->gid_length + dd->lid_length));
103  gno_t *newgid = (gno_t*) userchar;
104  *newgid = gno_t(firstIdx + cnt);
105  cnt++;
106  }
107  }
108 
110  // Retrieve the global numbers and put in the result gids vector
111  Zoltan_DD_Find(dd, ddkeys, ddnotneeded, ddnewgids, NULL, int(num_keys), NULL);
112 
113  Zoltan_DD_Destroy(&dd);
114 
115  ssize_t nUnique = 0;
116  MPI_Allreduce(&nDDEntries, &nUnique, 1, MPI_LONG_LONG, MPI_SUM, mpicomm);
117 
118  return size_t(nUnique);
119 }
120 
122 template <typename lno_t, typename gno_t>
124  Tpetra::MultiVector<gno_t, lno_t, gno_t> &keys,
125  Tpetra::Vector<gno_t, lno_t, gno_t> &gids
126 )
127 {
128  // Input: Tpetra MultiVector of keys; key length = numVectors()
129  // May contain duplicate keys within a processor.
130  // May contain duplicate keys across processors.
131  // Input: Empty Tpetra Vector with same map for holding the results
132  // Output: Filled gids vector, containing unique global numbers for
133  // each unique key. Global numbers are in range [0,#UniqueKeys).
134 
135  size_t num_keys = keys.getLocalLength();
136  size_t num_entries = keys.getNumVectors();
137 
138 #ifdef HAVE_ZOLTAN2_MPI
139  MPI_Comm mpicomm = Teuchos::getRawMpiComm(*(keys.getMap()->getComm()));
140 #else
141  // Zoltan's siMPI will be used here
142  {
143  int flag;
144  MPI_Initialized(&flag);
145  if (!flag) {
146  int narg = 0;
147  char **argv = NULL;
148  MPI_Init(&narg, &argv);
149  }
150  }
151  MPI_Comm mpicomm = MPI_COMM_WORLD; // Will get MPI_COMM_WORLD from siMPI
152 #endif
153 
154  int num_gid = TPL_Traits<ZOLTAN_ID_PTR,gno_t>::NUM_ID * num_entries;
155  int num_user = sizeof(gno_t);
156 
157  // Buffer the keys for Zoltan_DD
158  Teuchos::ArrayRCP<const gno_t> *tmpKeyVecs =
159  new Teuchos::ArrayRCP<const gno_t>[num_entries];
160  for (size_t v = 0; v < num_entries; v++) tmpKeyVecs[v] = keys.getData(v);
161 
162  ZOLTAN_ID_PTR ddkeys = new ZOLTAN_ID_TYPE[num_gid * num_keys];
163  size_t idx = 0;
164  for (size_t i = 0; i < num_keys; i++) {
165  for (size_t v = 0; v < num_entries; v++) {
166  ZOLTAN_ID_PTR ddkey = &(ddkeys[idx]);
167  TPL_Traits<ZOLTAN_ID_PTR,gno_t>::ASSIGN(ddkey, tmpKeyVecs[v][i]);
169  }
170  }
171  delete [] tmpKeyVecs;
172 
173  // Allocate memory for the result
174  char *ddnewgids = new char[num_user * num_keys];
175 
176  // Compute the new GIDs
177  size_t nUnique = findUniqueGidsCommon<gno_t>(num_keys, num_gid,
178  ddkeys, ddnewgids, mpicomm);
179 
180  // Copy the result into the output vector
181  gno_t *result = (gno_t *)ddnewgids;
182  for (size_t i = 0; i < num_keys; i++)
183  gids.replaceLocalValue(i, result[i]);
184 
185  // Clean up
186  delete [] ddkeys;
187  delete [] ddnewgids;
188 
189  return nUnique;
190 }
191 
193 template <typename key_t, typename gno_t>
195  std::vector<key_t> &keys,
196  std::vector<gno_t> &gids,
197  const Teuchos::Comm<int> &comm
198 )
199 {
200  // Input: Vector of keys; key length = key_t.size()
201  // Each key must have the same size. std::array<gno_t, N> is
202  // an example of a good key_t.
203  // May contain duplicate keys within a processor.
204  // May contain duplicate keys across processors.
205  // Input: Empty vector for holding the results
206  // Output: Filled gids vector, containing unique global numbers for
207  // each unique key. Global numbers are in range [0,#UniqueKeys).
208  //
209  // Note: This code uses the Zoltan Distributed Directory to assign the
210  // unique global numbers. Right now, it hacks into the Zoltan_DD
211  // data structures. If we like this approach, we can add some
212  // elegance to the Zoltan_DD, allowing operations internal to the
213  // directory.
214 
215  size_t num_keys = keys.size();
216  key_t dummy;
217  size_t num_entries = dummy.size();
218 
219 #ifdef HAVE_ZOLTAN2_MPI
220  MPI_Comm mpicomm = Teuchos::getRawMpiComm(comm);
221 #else
222  // Zoltan's siMPI will be used here
223  {
224  int flag;
225  MPI_Initialized(&flag);
226  if (!flag) {
227  int narg = 0;
228  char **argv = NULL;
229  MPI_Init(&narg, &argv);
230  }
231  }
232  MPI_Comm mpicomm = MPI_COMM_WORLD; // Will get MPI_COMM_WORLD from siMPI
233 #endif
234 
235  int num_gid = TPL_Traits<ZOLTAN_ID_PTR,gno_t>::NUM_ID * num_entries;
236  int num_user = sizeof(gno_t);
237 
238  // Buffer the keys for Zoltan_DD
239  ZOLTAN_ID_PTR ddkeys = new ZOLTAN_ID_TYPE[num_gid * num_keys];
240  size_t idx = 0;
241  for (size_t i = 0; i < num_keys; i++) {
242  for (size_t v = 0; v < num_entries; v++) {
243  ZOLTAN_ID_PTR ddkey = &(ddkeys[idx]);
244  TPL_Traits<ZOLTAN_ID_PTR,gno_t>::ASSIGN(ddkey, keys[i][v]);
246  }
247  }
248 
249  // Allocate memory for the result
250  char *ddnewgids = new char[num_user * num_keys];
251 
252  // Compute the new GIDs
253  size_t nUnique = findUniqueGidsCommon<gno_t>(num_keys, num_gid,
254  ddkeys, ddnewgids, mpicomm);
255 
256  // Copy the result into the output vector
257  gno_t *result = (gno_t *)ddnewgids;
258  for (size_t i = 0; i < num_keys; i++)
259  gids[i] = result[i];
260 
261  // Clean up
262  delete [] ddkeys;
263  delete [] ddnewgids;
264 
265  return nUnique;
266 }
267 
268 
269 } // namespace Zoltan2
270 #endif
size_t findUniqueGidsCommon(size_t num_keys, int num_gid, ZOLTAN_ID_PTR ddkeys, char *ddnewgids, MPI_Comm mpicomm)
size_t findUniqueGids(Tpetra::MultiVector< gno_t, lno_t, gno_t > &keys, Tpetra::Vector< gno_t, lno_t, gno_t > &gids)
static void ASSIGN(first_t &a, second_t b)
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS&#39;s idx_t...
Gathering definitions used in software development.