Zoltan2
Loading...
Searching...
No Matches
Zoltan2_AlgMetis.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
50#ifndef _ZOLTAN2_ALGMETIS_HPP_
51#define _ZOLTAN2_ALGMETIS_HPP_
52
53#include <Zoltan2_Algorithm.hpp>
56#include <Zoltan2_TPLTraits.hpp>
57#ifdef HAVE_ZOLTAN2_METIS
58#include "metis.h"
59#endif
60
61namespace Zoltan2{
62
63template <typename Adapter>
64class AlgMetis : public Algorithm<Adapter>
65{
66 private:
67
68 const RCP<const typename Adapter::base_adapter_t> adapter;
69 const RCP<Teuchos::ParameterList> pl;
70 const RCP<const Teuchos::Comm<int> > comm;
71 RCP<const Environment> env;
72 modelFlag_t graphFlags;
73
74 public:
75
77 const RCP<const typename Adapter::base_adapter_t> &adapter__,
78 const RCP<Teuchos::ParameterList> &pl__,
79 const RCP<const Teuchos::Comm<int> > &comm__,
80 RCP<const Environment> &env__,
81 const modelFlag_t &graphFlags__
82 ) : adapter(adapter__), pl(pl__), comm(comm__), env(env__), graphFlags(graphFlags__)
83 { }
84
86 const RCP<GlobalOrderingSolution<typename Adapter::gno_t> > &/* solution */) {
87 throw std::logic_error("AlgMetis does not yet support global ordering.");
88 }
89
91 const RCP<LocalOrderingSolution<typename Adapter::lno_t> > &solution)
92 {
93#ifndef HAVE_ZOLTAN2_METIS
94 (void)solution; // remove unused parameter warning
95 throw std::runtime_error(
96 "BUILD ERROR: Metis requested but not compiled into Zoltan2.\n"
97 "Please set CMake flag Zoltan2_ENABLE_METIS:BOOL=ON.");
98#else
99 typedef typename Adapter::gno_t gno_t;
100 typedef typename Adapter::lno_t lno_t;
101 typedef typename Adapter::offset_t offset_t;
102 typedef typename Adapter::scalar_t scalar_t;
103
104 int ierr= 0;
105
106 // Get EdgeList
107 const auto model = rcp(new GraphModel<Adapter>(adapter, env, comm, graphFlags));
108 const size_t nVtx = model->getLocalNumVertices();
109 const size_t nNnz = model->getLocalNumEdges();
110 lno_t *perm = (lno_t *) (solution->getPermutationRCP().getRawPtr());
111
112 if (nVtx > 0 && nNnz > 0) {
113 ArrayView<const gno_t> edgeIds;
114 ArrayView<const offset_t> offsets;
115 ArrayView<StridedData<lno_t, scalar_t> > wgts; // wgts are ignored in NodeND
116 model->getEdgeList(edgeIds, offsets, wgts);
117
118 // Prepare for calling metis
119 using Zoltan2OffsetView = typename Kokkos::View<offset_t*, Kokkos::HostSpace>;
120 using Zoltan2EdgeView = typename Kokkos::View<gno_t*, Kokkos::HostSpace>;
121 Zoltan2OffsetView zoltan2_rowptr (const_cast<offset_t*>(offsets.data()), nVtx+1);
122 Zoltan2EdgeView zoltan2_colidx (const_cast<gno_t*>(edgeIds.data()), nNnz);
123
124 using MetisIdxView = typename Kokkos::View<idx_t*, Kokkos::HostSpace>;
125 MetisIdxView metis_rowptr;
126 MetisIdxView metis_colidx;
127
128 // Symmetrize (always for now)
129 KokkosKernels::Impl::symmetrize_graph_symbolic_hashmap<
130 Zoltan2OffsetView, Zoltan2EdgeView, MetisIdxView, MetisIdxView, Kokkos::HostSpace::execution_space>
131 (nVtx, zoltan2_rowptr, zoltan2_colidx, metis_rowptr, metis_colidx);
132
133 // Remove diagonals
134 idx_t metis_nVtx=0;
135 TPL_Traits<idx_t, size_t>::ASSIGN(metis_nVtx, nVtx);
136
137 idx_t nnz = metis_rowptr(0);
138 idx_t old_nnz = nnz;
139 for (idx_t i = 0; i < metis_nVtx; i++) {
140 for (idx_t k = old_nnz; k < metis_rowptr(i+1); k++) {
141 if (metis_colidx(k) != i) {
142 metis_colidx(nnz) = metis_colidx(k);
143 nnz++;
144 }
145 }
146 old_nnz = metis_rowptr(i+1);
147 metis_rowptr(i+1) = nnz;
148 }
149
150 // Allocate Metis perm/iperm
151 idx_t *metis_perm = new idx_t[nVtx];
152 idx_t *metis_iperm = new idx_t[nVtx];
153
154 // Call metis
155 int info = METIS_NodeND(&metis_nVtx, metis_rowptr.data(), metis_colidx.data(),
156 NULL, NULL, metis_perm, metis_iperm);
157 if (METIS_OK != info) {
158 throw std::runtime_error(std::string("METIS_NodeND returned info = " + info));
159 }
160
161 // Copy result back
162 for (size_t i = 0; i < nVtx; i++)
163 TPL_Traits<lno_t, idx_t>::ASSIGN(perm[i], metis_perm[i]);
164
165 delete [] metis_iperm;
166 delete [] metis_perm;
167 } else {
168 for (size_t i = 0; i < nVtx; i++)
169 perm[i] = i;
170 }
171
172 solution->setHavePerm(true);
173 return ierr;
174#endif
175 }
176};
177
178}
179
180
181
182#endif
Defines the GraphModel interface.
Defines the OrderingSolution class.
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t,...
int globalOrder(const RCP< GlobalOrderingSolution< typename Adapter::gno_t > > &)
Ordering method.
AlgMetis(const RCP< const typename Adapter::base_adapter_t > &adapter__, const RCP< Teuchos::ParameterList > &pl__, const RCP< const Teuchos::Comm< int > > &comm__, RCP< const Environment > &env__, const modelFlag_t &graphFlags__)
int localOrder(const RCP< LocalOrderingSolution< typename Adapter::lno_t > > &solution)
Ordering method.
Algorithm defines the base class for all algorithms.
Adapter::scalar_t scalar_t
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
static void ASSIGN(first_t &a, second_t b)