Zoltan2
Zoltan2_AlgND.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 // Michael Wolf (mmwolf@sandia.gov)
42 //
43 // ***********************************************************************
44 //
45 // @HEADER
46 
47 //MMW need to specify that this requires Zoltan
48 
49 #ifndef _ZOLTAN2_ALGND_HPP_
50 #define _ZOLTAN2_ALGND_HPP_
51 
54 #include <Zoltan2_Algorithm.hpp>
55 #include <Zoltan2_AlgZoltan.hpp>
56 
57 #include <sstream>
58 #include <string>
59 #include <bitset>
60 
66 void buildPartTree(int level, int leftPart, int splitPart, int rightPart, std::vector<int> &partTree);
67 
68 
69 namespace Zoltan2
70 {
71 
73 
84 template <typename Adapter>
86 class AlgND : public Algorithm<Adapter>
87 {
88 
89 private:
90 
91  typedef typename Adapter::part_t part_t;
92 
93  typedef typename Adapter::lno_t lno_t;
94  typedef typename Adapter::gno_t gno_t;
95 
96 
97  const RCP<const Environment> mEnv;
98  const RCP<Comm<int> > mProblemComm;
99 
100  const RCP<const GraphModel<Adapter> > mGraphModel;
101  const RCP<const CoordinateModel<Adapter> > mIds;
102 
103  const RCP<const Adapter> mBaseInputAdapter;
104 
105 
106  void getBoundLayerSep(int levelIndx, const std::vector<part_t> &partMap,
107  const part_t * parts,
108  std::vector<int> &boundVerts,
109  std::vector<std::vector<int> > &boundVertsST,
110  const std::set<int> &sepVerts);
111 
112 public:
113  // Constructor
114  AlgND(const RCP<const Environment> &env_,
115  const RCP<Comm<int> > &problemComm_,
116  const RCP<const GraphModel<Adapter> > &gModel_,
117  const RCP<const CoordinateModel<Adapter> > &cModel_,
118  const RCP<const Adapter> baseInputAdapter_)
119  :mEnv(env_), mProblemComm(problemComm_), mGraphModel(gModel_), mIds(cModel_),
120  mBaseInputAdapter(baseInputAdapter_)
121  {
122 #ifndef INCLUDE_ZOLTAN2_EXPERIMENTAL
123  Z2_THROW_EXPERIMENTAL("Zoltan2 AlgND is strictly experimental software ")
124 #endif
125 
126 #ifndef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF
127  Z2_THROW_EXPERIMENTAL_WOLF("Zoltan2 algND is strictly experimental software ")
128 #endif
129 
130  if(mProblemComm->getSize()!=1)
131  {
132  Z2_THROW_SERIAL("Zoltan2 AlgND is strictly serial!");
133  }
134 
135  }
136 
137  // Ordering method
138  int order(const RCP<OrderingSolution<lno_t, gno_t> > &solution_);
139 
140 };
142 
145 template <typename Adapter>
147 {
148  // typedef typename Adapter::lno_t lno_t; // local ids
149  // typedef typename Adapter::gno_t gno_t; // global ids
150  // typedef typename Adapter::scalar_t scalar_t; // scalars
151 
152  mEnv->debug(DETAILED_STATUS, std::string("Entering AlgND"));
153 
155  // First, let's partition with RCB using Zoltan. Eventually, we will change this
156  // to use PHG
158 
159  // Q: can I use solution passed into alg or do I need to create a different one?
160  // For now using the one passed into alg
161  // TODO: use new partitioning solution
162 
163 
164  //AlgZoltan<Adapter> algZoltan(this->mEnv, mProblemComm, this->mBaseInputAdapter);
165  // algZoltan.partition(solution_);
166 
167  // size_t numGlobalParts = solution_->getTargetGlobalNumberOfParts();
168 
169  // const part_t *parts = solution_->getPartListView();
170  // //////////////////////////////////////////////////////////////////////
171 
172  // //////////////////////////////////////////////////////////////////////
173  // // Build up tree that represents partitioning subproblems, which will
174  // // be used for determining separators at each level
175  // // -- for now, this is built up artificially
176  // // -- eventually this will be built from PHG output
177  // //////////////////////////////////////////////////////////////////////
178  // // change int to something, part_t?
179  // std::vector<int> partTree;
180 
181  // buildPartTree( 0, 0, (numGlobalParts-1)/2 + 1, numGlobalParts, partTree);
182  // unsigned int numSeparators = partTree.size() / 4;
183  // //////////////////////////////////////////////////////////////////////
184 
185 
186  // //////////////////////////////////////////////////////////////////////
187  // // Create a map that maps each part number to a new number based on
188  // // the level of the hiearchy of the separator tree. This allows us
189  // // to easily identify the boundary value vertices
190  // //////////////////////////////////////////////////////////////////////
191  // int numLevels = partTree[4*(numSeparators-1)]+1;
192 
193  // std::vector<std::vector<int> > partLevelMap(numLevels,std::vector<int>(numGlobalParts));
194 
195  // std::vector<int> sepsInLev(numLevels,0);
196 
197  // for(unsigned int i=0;i<numSeparators;i++)
198  // {
199  // int level = partTree[4*i];
200  // int leftPart = partTree[4*i+1];
201  // int splitPart = partTree[4*i+2];
202  // int rightPart = partTree[4*i+3];
203 
204  // for(int part=leftPart; part<splitPart; part++)
205  // {
206  // partLevelMap[level][part] = 2*sepsInLev[level];
207  // }
208 
209  // for(int part=splitPart; part<rightPart; part++)
210  // {
211  // partLevelMap[level][part] = 2*sepsInLev[level]+1;
212  // }
213 
214  // sepsInLev[level]++;
215  // }
216  // //////////////////////////////////////////////////////////////////////
217 
218  // // Set of separator vertices. Used to keep track of what vertices are
219  // // already in previous calculated separators. These vertices should be
220  // // excluded from future separator calculations
221  // const std::set<int> sepVerts;
222 
223  // //////////////////////////////////////////////////////////////////////
224  // // Loop over each cut
225  // // 1. Build boundary layer between parts
226  // // 2. Build vertex separator from boundary layer
227  // //////////////////////////////////////////////////////////////////////
228  // for(unsigned int level=0;level<numLevels;level++)
229  // {
230  // for(unsigned int levIndx=0;levIndx<sepsInLev[level];levIndx++)
231  // {
232 
233  // std::vector<int> boundVerts;
234  // std::vector<std::vector<int> > boundVertsST(2);
235 
236  // ///////////////////////////////////////////////////////////////
237  // // Build boundary layer between parts (edge separator)
238  // ///////////////////////////////////////////////////////////////
239  // getBoundLayerSep(levIndx, partLevelMap[level], parts, boundVerts,
240  // boundVertsST, sepVerts);
241  // ///////////////////////////////////////////////////////////////
242 
243  // ///////////////////////////////////////////////////////////////
244  // // Calculate vertex separator from boundary layer
245  // ///////////////////////////////////////////////////////////////
246 
247  // //VCOfBoundLayer
248 
249  // ///////////////////////////////////////////////////////////////
250 
251 
252  // }
253  // }
254  // //////////////////////////////////////////////////////////////////////
255 
256  // //TODO: calculate vertex separator for each layer,
257  // //TODO: using vertex separators, compute new ordering and store in solution
258  // //TODO: move to ordering directory
259 
260  mEnv->debug(DETAILED_STATUS, std::string("Exiting AlgND"));
261  return 0;
262 }
264 
266 // Create boundary layer of vertices between 2 partitions
268 template <typename Adapter>
269 void AlgND<Adapter>::getBoundLayerSep(int levelIndx, const std::vector<part_t> &partMap,
270  const part_t * parts,
271  std::vector<int> &boundVerts,
272  std::vector<std::vector<int> > &boundVertsST,
273  const std::set<int> &sepVerts)
274 {
275  typedef typename Adapter::lno_t lno_t; // local ids
276  typedef typename Adapter::scalar_t scalar_t; // scalars
277  typedef StridedData<lno_t, scalar_t> input_t;
278 
279  int numVerts = mGraphModel->getLocalNumVertices();
280 
281  //Teuchos ArrayView
282  ArrayView< const lno_t > eIDs;
283  ArrayView< const lno_t > vOffsets;
284  ArrayView< input_t > wgts;
285 
286  // For some reason getLocalEdgeList seems to be returning empty eIDs
287  //size_t numEdges = ( (GraphModel<typename Adapter::base_adapter_t>) *mGraphModel).getLocalEdgeList(eIDs, vOffsets, wgts);
288 
289  size_t numEdges = ( (GraphModel<typename Adapter::base_adapter_t>) *mGraphModel).getEdgeList(eIDs, vOffsets, wgts);
290 
291 // size_t Zoltan2::GraphModel< Adapter >::getEdgeList(ArrayView< const gno_t > & edgeIds,
292 // ArrayView< const int > & procIds,
293 // ArrayView< const lno_t > & offsets,
294 // ArrayView< input_t > & wgts
295 // )
296 
297  // for(int v1=0;v1<numEdges;v1++)
298  for(int v1=0;v1<numVerts;v1++)
299  {
300 
301  part_t vpart1 = partMap[parts[v1]];
302 
303  bool correctBL = (vpart1 >= 2*levelIndx && vpart1 < 2*(levelIndx+1) );
304 
305  // if vertex is not in the correct range of parts, it cannot be a member of
306  // this boundary layer
307  if(!correctBL)
308  {
309  continue;
310  }
311 
312  // If this vertex belongs to a previous separator, it cannot belong to this
313  // separator
314  if(sepVerts.find(v1)!=sepVerts.end())
315  {
316  continue;
317  }
318 
319  //Loop over edges connected to v1
320  //MMW figure out how to get this from Zoltan2
321  for(int j=vOffsets[v1];j<vOffsets[v1+1];j++)
322  {
323 
324  int v2 = eIDs[j];
325 
326  part_t vpart2 = partMap[parts[v2]];
327 
328  correctBL = (vpart2 >= 2*levelIndx && vpart2 < 2*(levelIndx+1) );
329 
330  // if vertex is not in the correct range of parts, it cannot be a member of
331  // this boundary layer
332  if(!correctBL)
333  {
334  continue;
335  }
336 
337  // If this vertex belongs to a previous separator, it cannot belong to this
338  // separator
339  if(sepVerts.find(v2)!=sepVerts.end())
340  {
341  continue;
342  }
343 
344  if ( vpart1 != vpart2 )
345  {
346  // Vertex added to set of all boundary vertices
347  boundVerts.push_back(v1);
348 
349  // Vertex added to 1st set of boundary vertices
350  if(vpart1<vpart2)
351  {
352  boundVertsST[0].push_back(v1);
353  }
354  // Vertex added to 2nd set of boundary vertices
355  else
356  {
357  boundVertsST[1].push_back(v1);
358  }
359  break;
360  }
361 
362  }
363  }
364 
365 }
367 
368 } // namespace Zoltan2
369 
370 
373 void buildPartTree(int level, int leftPart, int splitPart, int rightPart, std::vector<int> &partTree)
374 {
375  // Insert information for this separator
376  partTree.push_back(level);
377  partTree.push_back(leftPart);
378  partTree.push_back(splitPart);
379  partTree.push_back(rightPart);
380 
381  // Recurse down left side of tree
382  if(splitPart-leftPart > 1)
383  {
384  int newSplit = leftPart+(splitPart-leftPart-1)/2 + 1;
385  buildPartTree(level+1,leftPart,newSplit,splitPart,partTree);
386  }
387 
388  // Recurse down right side of tree
389  if(rightPart-splitPart>1)
390  {
391  int newSplit = splitPart+(rightPart-splitPart-1)/2 + 1;
392  buildPartTree(level+1,splitPart,newSplit,rightPart,partTree);
393  }
394 }
396 
397 
398 
399 
400 #endif
#define Z2_THROW_SERIAL(mystr)
Throw an error when code is run on more than one processor.
#define Z2_THROW_EXPERIMENTAL_WOLF(mystr)
Throw an error when wolf experimental code is requested but not compiled.
AlgND(const RCP< const Environment > &env_, const RCP< Comm< int > > &problemComm_, const RCP< const GraphModel< Adapter > > &gModel_, const RCP< const CoordinateModel< Adapter > > &cModel_, const RCP< const Adapter > baseInputAdapter_)
interface to the Zoltan package
Defines the PartitioningSolution class.
sub-steps, each method&#39;s entry and exit
This class provides geometric coordinates with optional weights to the Zoltan2 algorithm.
Defines the IdentifierModel interface.
void buildPartTree(int level, int leftPart, int splitPart, int rightPart, std::vector< int > &partTree)
Adapter::scalar_t scalar_t
The StridedData class manages lists of weights or coordinates.
Algorithm defines the base class for all algorithms.
#define Z2_THROW_EXPERIMENTAL(mystr)
Throw an error when experimental code is requested but not compiled.
GraphModel defines the interface required for graph models.
The class containing ordering solutions.
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution_)
Ordering method.