Zoltan2
Zoltan2_AlgPuLP.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 #ifndef _ZOLTAN2_ALGPULP_HPP_
46 #define _ZOLTAN2_ALGPULP_HPP_
47 
48 #include <Zoltan2_GraphModel.hpp>
49 #include <Zoltan2_Algorithm.hpp>
51 #include <Zoltan2_Util.hpp>
52 #include <Zoltan2_TPLTraits.hpp>
53 
57 
59 #ifndef HAVE_ZOLTAN2_PULP
60 
61 namespace Zoltan2 {
62 // Error handling for when PuLP is requested
63 // but Zoltan2 not built with PuLP.
64 
65 template <typename Adapter>
66 class AlgPuLP : public Algorithm<Adapter>
67 {
68 public:
69  typedef typename Adapter::base_adapter_t base_adapter_t;
70  AlgPuLP(const RCP<const Environment> &env,
71  const RCP<const Comm<int> > &problemComm,
72  const RCP<const base_adapter_t> &adapter
73  )
74  {
75  throw std::runtime_error(
76  "BUILD ERROR: PuLP requested but not compiled into Zoltan2.\n"
77  "Please set CMake flag Zoltan2_ENABLE_PuLP:BOOL=ON.");
78  }
79 };
80 }
81 #endif
82 
85 
86 #ifdef HAVE_ZOLTAN2_PULP
87 
88 namespace Zoltan2 {
89 
90 extern "C" {
91 // TODO: XtraPuLP
92 //#ifndef HAVE_ZOLTAN2_MPI
93 #include "pulp.h"
94 //#else
95 //endif
96 }
97 
98 
99 
100 
101 template <typename Adapter>
102 class AlgPuLP : public Algorithm<Adapter>
103 {
104 public:
105  typedef typename Adapter::base_adapter_t base_adapter_t;
106  typedef typename Adapter::lno_t lno_t;
107  typedef typename Adapter::gno_t gno_t;
108  typedef typename Adapter::scalar_t scalar_t;
109  typedef typename Adapter::part_t part_t;
110  typedef typename Adapter::user_t user_t;
111  typedef typename Adapter::userCoord_t userCoord_t;
112 
123  AlgPuLP(const RCP<const Environment> &env__,
124  const RCP<const Comm<int> > &problemComm__,
125  const RCP<const IdentifierAdapter<user_t> > &adapter__) :
126  env(env__), problemComm(problemComm__), adapter(adapter__)
127  {
128  std::string errStr = "cannot build GraphModel from IdentifierAdapter, ";
129  errStr += "PuLP requires Graph, Matrix, or Mesh Adapter";
130  throw std::runtime_error(errStr);
131  }
132 
133  AlgPuLP(const RCP<const Environment> &env__,
134  const RCP<const Comm<int> > &problemComm__,
135  const RCP<const VectorAdapter<user_t> > &adapter__) :
136  env(env__), problemComm(problemComm__), adapter(adapter__)
137  {
138  std::string errStr = "cannot build GraphModel from VectorAdapter, ";
139  errStr += "PuLP requires Graph, Matrix, or Mesh Adapter";
140  throw std::runtime_error(errStr);
141  }
142 
143  AlgPuLP(const RCP<const Environment> &env__,
144  const RCP<const Comm<int> > &problemComm__,
145  const RCP<const GraphAdapter<user_t,userCoord_t> > &adapter__) :
146  env(env__), problemComm(problemComm__), adapter(adapter__)
147  {
148  modelFlag_t flags;
149  flags.reset();
150 
151  buildModel(flags);
152  }
153 
154  AlgPuLP(const RCP<const Environment> &env__,
155  const RCP<const Comm<int> > &problemComm__,
156  const RCP<const MatrixAdapter<user_t,userCoord_t> > &adapter__) :
157  env(env__), problemComm(problemComm__), adapter(adapter__)
158  {
159  modelFlag_t flags;
160  flags.reset();
161 
162  const ParameterList &pl = env->getParameters();
163  const Teuchos::ParameterEntry *pe;
164 
165  std::string defString("default");
166  std::string objectOfInterest(defString);
167  pe = pl.getEntryPtr("objects_to_partition");
168  if (pe)
169  objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
170 
171  if (objectOfInterest == defString ||
172  objectOfInterest == std::string("matrix_rows") )
173  flags.set(VERTICES_ARE_MATRIX_ROWS);
174  else if (objectOfInterest == std::string("matrix_columns"))
175  flags.set(VERTICES_ARE_MATRIX_COLUMNS);
176  else if (objectOfInterest == std::string("matrix_nonzeros"))
177  flags.set(VERTICES_ARE_MATRIX_NONZEROS);
178 
179  buildModel(flags);
180  }
181 
182  AlgPuLP(const RCP<const Environment> &env__,
183  const RCP<const Comm<int> > &problemComm__,
184  const RCP<const MeshAdapter<user_t> > &adapter__) :
185  env(env__), problemComm(problemComm__), adapter(adapter__)
186  {
187  modelFlag_t flags;
188  flags.reset();
189 
190  const ParameterList &pl = env->getParameters();
191  const Teuchos::ParameterEntry *pe;
192 
193  std::string defString("default");
194  std::string objectOfInterest(defString);
195  pe = pl.getEntryPtr("objects_to_partition");
196  if (pe)
197  objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
198 
199  if (objectOfInterest == defString ||
200  objectOfInterest == std::string("mesh_nodes") )
201  flags.set(VERTICES_ARE_MESH_NODES);
202  else if (objectOfInterest == std::string("mesh_elements"))
203  flags.set(VERTICES_ARE_MESH_ELEMENTS);
204 
205  buildModel(flags);
206  }
207 
208  void partition(const RCP<PartitioningSolution<Adapter> > &solution);
209 
210 private:
211 
212  void buildModel(modelFlag_t &flags);
213 
214  const RCP<const Environment> env;
215  const RCP<const Comm<int> > problemComm;
216  const RCP<const base_adapter_t> adapter;
217  RCP<const GraphModel<base_adapter_t> > model;
218 };
219 
220 
222 template <typename Adapter>
224 {
225  const ParameterList &pl = env->getParameters();
226  const Teuchos::ParameterEntry *pe;
227 
228  std::string defString("default");
229  std::string symParameter(defString);
230  pe = pl.getEntryPtr("symmetrize_graph");
231  if (pe){
232  symParameter = pe->getValue<std::string>(&symParameter);
233  if (symParameter == std::string("transpose"))
234  flags.set(SYMMETRIZE_INPUT_TRANSPOSE);
235  else if (symParameter == std::string("bipartite"))
236  flags.set(SYMMETRIZE_INPUT_BIPARTITE); }
237 
238  int sgParameter = 0;
239  pe = pl.getEntryPtr("subset_graph");
240  if (pe)
241  sgParameter = pe->getValue<int>(&sgParameter);
242  if (sgParameter == 1)
243  flags.set(BUILD_SUBSET_GRAPH);
244 
245  flags.set(REMOVE_SELF_EDGES);
246  flags.set(GENERATE_CONSECUTIVE_IDS);
247  flags.set(BUILD_LOCAL_GRAPH);
248  this->env->debug(DETAILED_STATUS, " building graph model");
249  this->model = rcp(new GraphModel<base_adapter_t>(this->adapter, this->env,
250  this->problemComm, flags));
251  this->env->debug(DETAILED_STATUS, " graph model built");
252 }
253 
254 
255 template <typename Adapter>
257  const RCP<PartitioningSolution<Adapter> > &solution
258 )
259 {
260  HELLO;
261 
262  size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
263 
264  int num_parts = (int)numGlobalParts;
265  //TPL_Traits<int, size_t>::ASSIGN_TPL_T(num_parts, numGlobalParts, env);
266 
267  //#ifdef HAVE_ZOLTAN2_MPI
268  // TODO: XtraPuLP
269 
270  int ierr = 0;
271  //int np = problemComm->getSize();
272 
273  // Get number of vertices and edges
274  const size_t modelVerts = model->getLocalNumVertices();
275  const size_t modelEdges = model->getLocalNumEdges();
276  int num_verts = (int)modelVerts;
277  long num_edges = (long)modelEdges;
278  //TPL_Traits<int, size_t>::ASSIGN_TPL_T(num_verts, modelVerts, env);
279  //TPL_Traits<long, size_t>::ASSIGN_TPL_T(num_edges, modelEdges, env);
280 
281  // Get adjacency list and offset pointers
282  ArrayView<const gno_t> adjs;
283  ArrayView<const lno_t> offsets;
284  ArrayView<StridedData<lno_t, scalar_t> > ewgts; // ignore this for now
285  model->getEdgeList(adjs, offsets, ewgts);
286 
287  // Create PuLP's graph structure
288  int *out_edges;
289  long *out_offsets;
292 
293  pulp_graph_t g = {num_verts, num_edges, out_edges, out_offsets};
294 
295  // Create array for PuLP to return results in.
296  // Or write directly into solution parts array
297  ArrayRCP<part_t> partList(new part_t[num_verts], 0, num_verts, true);
298  int* parts = NULL;
299  if (num_verts && (sizeof(int) == sizeof(part_t))) {
300  // Can write directly into the solution's memory
301  parts = (int *) partList.getRawPtr();
302  }
303  else {
304  // Can't use solution memory directly; will have to copy later.
305  parts = new int[num_verts];
306  }
307 
308  // TODO
309  // Implement vertex and edge weights
310 
311  // TODO
312  // Implement target part sizes
313 
314  // Grab options from parameter list
315  const Teuchos::ParameterList &pl = env->getParameters();
316  const Teuchos::ParameterEntry *pe;
317 
318  // figure out which parts of the algorithm we're going to run
319  // Default to PuLP with BFS init
320  // PuLP - do_edge_min = false, do_maxcut_min = false
321  // PuLP-M - do_edge_bal = true, do_maxcut_min = false
322  // PuLP-MM - do_edge_bal = true/false, do_maxcut_min = true
323  int do_lp_init = 0;
324  int do_bfs_init = 1;
325  int do_edge_bal = 0;
326  int do_maxcut_min = 0;
327  int verbose_output = 0;
328 
329  // Do label propagation initialization instead of bfs?
330  pe = pl.getEntryPtr("pulp_lp_init");
331  if (pe) do_lp_init = pe->getValue<int>(&do_lp_init);
332  if (do_lp_init) do_bfs_init = 0;
333 
334  // Now look at additional objective
335  pe = pl.getEntryPtr("pulp_minimize_maxcut");
336  if (pe) {
337  do_maxcut_min = pe->getValue<int>(&do_maxcut_min);
338  // If we're doing the secondary objective,
339  // set the additional constraint as well
340  if (do_maxcut_min) do_edge_bal = 1;
341  }
342 
343  // Now grab vertex and edge imbalances, defaults at 10%
344  double vert_imbalance = 1.1;
345  double edge_imbalance = 1.1;
346 
347  pe = pl.getEntryPtr("pulp_vert_imbalance");
348  if (pe) vert_imbalance = pe->getValue<double>(&vert_imbalance);
349  pe = pl.getEntryPtr("pulp_edge_imbalance");
350  if (pe) {
351  edge_imbalance = pe->getValue<double>(&edge_imbalance);
352  // if manually set edge imbalance, add do_edge_bal flag to true
353  do_edge_bal = 1;
354  }
355 
356  if (vert_imbalance < 1.0)
357  throw std::runtime_error("pulp_vert_imbalance must be '1.0' or greater.");
358  if (edge_imbalance < 1.0)
359  throw std::runtime_error("pulp_edge_imbalance must be '1.0' or greater.");
360 
361  // verbose output?
362  // TODO: fully implement verbose flag throughout PuLP
363  pe = pl.getEntryPtr("pulp_verbose");
364  if (pe) verbose_output = pe->getValue<int>(&verbose_output);
365 
366  // Create PuLP's partitioning data structure
367  pulp_part_control_t ppc = {vert_imbalance, edge_imbalance,
368  (bool)do_lp_init, (bool)do_bfs_init,
369  (bool)do_edge_bal, (bool)do_maxcut_min,
370  (bool)verbose_output};
371 
372  if (verbose_output) {
373  printf("n: %i, m: %li, vb: %lf, eb: %lf, p: %i\n",
374  num_verts, num_edges, vert_imbalance, edge_imbalance, num_parts);
375  }
376 
377  // Call partitioning; result returned in parts array
378  ierr = pulp_run(&g, &ppc, parts, num_parts);
379 
380  env->globalInputAssertion(__FILE__, __LINE__, "pulp_run",
381  !ierr, BASIC_ASSERTION, problemComm);
382 
383  // Load answer into the solution if necessary
384  if ((sizeof(int) != sizeof(part_t)) || (num_verts == 0)) {
385  for (int i = 0; i < num_verts; i++) partList[i] = parts[i];
386  delete [] parts;
387  }
388 
389  solution->setParts(partList);
390 
391  env->memory("Zoltan2-PuLP: After creating solution");
392 
393  // Clean up copies made due to differing data sizes.
396 
397 //#endif // DO NOT HAVE_MPI
398 }
399 
400 } // namespace Zoltan2
401 
402 #endif // HAVE_ZOLTAN2_PULP
403 
405 
406 
407 #endif
408 
409 
410 
411 
412 
413 
use columns as graph vertices
#define HELLO
IdentifierAdapter defines the interface for identifiers.
ignore invalid neighbors
use mesh nodes as vertices
static void DELETE_TPL_T_ARRAY(tpl_t **a)
fast typical checks for valid arguments
MatrixAdapter defines the adapter interface for matrices.
Adapter::base_adapter_t base_adapter_t
GraphAdapter defines the interface for graph-based user data.
algorithm requires consecutive ids
MeshAdapter defines the interface for mesh input.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
model must symmetrize input
model must symmetrize input
Defines the PartitioningSolution class.
sub-steps, each method&#39;s entry and exit
use matrix rows as graph vertices
algorithm requires no self edges
Adapter::scalar_t scalar_t
A PartitioningSolution is a solution to a partitioning problem.
use nonzeros as graph vertices
Adapter::part_t part_t
VectorAdapter defines the interface for vector input.
Algorithm defines the base class for all algorithms.
static void ASSIGN_TPL_T_ARRAY(tpl_t **a, ArrayView< zno_t > &b)
virtual void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS&#39;s idx_t...
use mesh elements as vertices
GraphModel defines the interface required for graph models.
Defines the GraphModel interface.
AlgPuLP(const RCP< const Environment > &env, const RCP< const Comm< int > > &problemComm, const RCP< const base_adapter_t > &adapter)
A gathering of useful namespace methods.
model represents graph within only one rank