Zoltan2
Loading...
Searching...
No Matches
Zoltan2_AlgHybridD1-2GL.hpp
Go to the documentation of this file.
1#ifndef _ZOLTAN2_DISTANCE1_2GHOSTLAYER_HPP_
2#define _ZOLTAN2_DISTANCE1_2GHOSTLAYER_HPP_
3
4#include <vector>
5#include <unordered_map>
6#include <iostream>
7#include <queue>
8#ifdef _WIN32
9#include <time.h>
10#else
11#include <sys/time.h>
12#endif
13
14#include "Zoltan2_Algorithm.hpp"
17#include "Zoltan2_Util.hpp"
18#include "Zoltan2_TPLTraits.hpp"
19#include "Zoltan2_AlltoAll.hpp"
21
22#include "Tpetra_Core.hpp"
23#include "Teuchos_RCP.hpp"
24#include "Tpetra_Import.hpp"
25#include "Tpetra_FEMultiVector.hpp"
26
27#include "KokkosKernels_Handle.hpp"
28#include "KokkosKernels_IOUtils.hpp"
29#include "KokkosGraph_Distance1Color.hpp"
30#include "KokkosGraph_Distance1ColorHandle.hpp"
31
35
36
37namespace Zoltan2{
38
39template <typename Adapter>
41 public:
42 using lno_t = typename Adapter::lno_t;
43 using gno_t = typename Adapter::gno_t;
44 using offset_t = typename Adapter::offset_t;
45 using scalar_t = typename Adapter::scalar_t;
46 using base_adapter_t = typename Adapter::base_adapter_t;
47 using map_t = Tpetra::Map<lno_t,gno_t>;
48 using femv_scalar_t = int;
49 using femv_t = Tpetra::FEMultiVector<femv_scalar_t, lno_t, gno_t>;
50 using device_type = typename femv_t::device_type;
51 using execution_space = typename device_type::execution_space;
52 using memory_space = typename device_type::memory_space;
53 using host_exec = typename femv_t::host_view_type::device_type::execution_space;
54 using host_mem = typename femv_t::host_view_type::device_type::memory_space;
55
56 private:
57
58 template <class ExecutionSpace, typename MemorySpace>
59 void localColoring(const size_t nVtx,
60 Kokkos::View<lno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> adjs_view,
61 Kokkos::View<offset_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> offset_view,
62 Teuchos::RCP<femv_t> femv,
63 Kokkos::View<lno_t*, Kokkos::Device<ExecutionSpace, MemorySpace> > vertex_list,
64 size_t vertex_list_size = 0,
65 bool use_vertex_based_coloring=false){
66 using KernelHandle = KokkosKernels::Experimental::KokkosKernelsHandle
67 <offset_t, lno_t, lno_t, ExecutionSpace, MemorySpace, MemorySpace>;
68 using lno_row_view_t = Kokkos::View<offset_t*,Kokkos::Device<ExecutionSpace, MemorySpace>>;
69 using lno_nnz_view_t = Kokkos::View<lno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>>;
70 KernelHandle kh;
71
72 //pick which KokkosKernels algorithm to use.
73 //this boolean's value is based on max degree.
74 if(use_vertex_based_coloring){
75 kh.create_graph_coloring_handle(KokkosGraph::COLORING_VBBIT);
76 } else {
77 kh.create_graph_coloring_handle(KokkosGraph::COLORING_EB);
78 }
79
80 //vertex_list_size indicates whether we have provided a list of vertices to recolor
81 //only makes a difference if the algorithm to be used is VBBIT
82 if(vertex_list_size != 0){
83 kh.get_graph_coloring_handle()->set_vertex_list(vertex_list, vertex_list_size);
84 }
85
86 //the verbose argument should carry through the local coloring
87 kh.set_verbose(this->verbose);
88
89 //set initial colors to be the colors from the femv
90 auto femvColors = femv->template getLocalView<Kokkos::Device<ExecutionSpace,MemorySpace> >(Tpetra::Access::ReadWrite);
91 auto sv = subview(femvColors, Kokkos::ALL, 0);
92 kh.get_graph_coloring_handle()->set_vertex_colors(sv);
93
94 //if running verbosely, also report local color timing breakdown
95 kh.get_graph_coloring_handle()->set_tictoc(this->verbose);
96
97 //call coloring
98 KokkosGraph::Experimental::graph_color_symbolic
99 <KernelHandle, lno_row_view_t, lno_nnz_view_t> (&kh,
100 nVtx,
101 nVtx,
102 offset_view,
103 adjs_view);
104
105
106 //output total time and #iterations
107 if(this->verbose){
108 std::cout<<"\nKokkosKernels Coloring: "
109 <<kh.get_graph_coloring_handle()->get_overall_coloring_time()
110 <<" iterations: "
111 <<kh.get_graph_coloring_handle()->get_num_phases()
112 <<"\n\n";
113 }
114 }
115
116 virtual void colorInterior(const size_t nVtx,
117 Kokkos::View<lno_t*,device_type > adjs_view,
118 Kokkos::View<offset_t*,device_type > offset_view,
119 Teuchos::RCP<femv_t> femv,
120 Kokkos::View<lno_t*, device_type > vertex_list,
121 size_t vertex_list_size = 0,
122 bool recolor=false){
123
124 this->localColoring<execution_space, memory_space>(nVtx,
125 adjs_view,
126 offset_view,
127 femv,
128 vertex_list,
129 vertex_list_size,
130 recolor);
131 }
132
133 virtual void colorInterior_serial(const size_t nVtx,
134 typename Kokkos::View<lno_t*, device_type >::HostMirror adjs_view,
135 typename Kokkos::View<offset_t*,device_type >::HostMirror offset_view,
136 Teuchos::RCP<femv_t> femv,
137 typename Kokkos::View<lno_t*, device_type>::HostMirror vertex_list,
138 size_t vertex_list_size = 0,
139 bool recolor=false) {
140 this->localColoring<host_exec, host_mem>(nVtx,
141 adjs_view,
142 offset_view,
143 femv,
144 vertex_list,
145 vertex_list_size,
146 recolor);
147 }
148
149 public:
150 template <class ExecutionSpace, typename MemorySpace>
151 void detectD1Conflicts(const size_t n_local,
152 Kokkos::View<offset_t*,
153 Kokkos::Device<ExecutionSpace, MemorySpace>> dist_offsets,
154 Kokkos::View<lno_t*,
155 Kokkos::Device<ExecutionSpace, MemorySpace>> dist_adjs,
156 Kokkos::View<int*,
157 Kokkos::Device<ExecutionSpace, MemorySpace>> femv_colors,
158 Kokkos::View<lno_t*,
159 Kokkos::Device<ExecutionSpace, MemorySpace>> boundary_verts_view,
160 Kokkos::View<lno_t*,
161 Kokkos::Device<ExecutionSpace, MemorySpace> > verts_to_recolor_view,
162 Kokkos::View<int*,
163 Kokkos::Device<ExecutionSpace, MemorySpace>,
164 Kokkos::MemoryTraits<Kokkos::Atomic> > verts_to_recolor_size_atomic,
165 Kokkos::View<lno_t*,
166 Kokkos::Device<ExecutionSpace, MemorySpace> > verts_to_send_view,
167 Kokkos::View<size_t*,
168 Kokkos::Device<ExecutionSpace, MemorySpace>,
169 Kokkos::MemoryTraits<Kokkos::Atomic> > verts_to_send_size_atomic,
170 Kokkos::View<size_t*, Kokkos::Device<ExecutionSpace, MemorySpace> > recoloringSize,
171 Kokkos::View<int*,
172 Kokkos::Device<ExecutionSpace, MemorySpace> > rand,
173 Kokkos::View<gno_t*,
174 Kokkos::Device<ExecutionSpace, MemorySpace> > gid,
175 Kokkos::View<gno_t*,
176 Kokkos::Device<ExecutionSpace, MemorySpace> > ghost_degrees,
177 bool recolor_degrees){
178 size_t local_recoloring_size;
179 Kokkos::RangePolicy<ExecutionSpace> policy(n_local,rand.size());
180 Kokkos::parallel_reduce("D1-2GL Conflict Detection",policy, KOKKOS_LAMBDA (const int& i, size_t& recoloring_size){
181 lno_t localIdx = i;
182 int currColor = femv_colors(localIdx);
183 int currDegree = ghost_degrees(i-n_local);
184 for(offset_t j = dist_offsets(i); j < dist_offsets(i+1); j++){
185 int nborColor = femv_colors(dist_adjs(j));
186 int nborDegree = 0;
187 if((size_t)dist_adjs(j) < n_local) nborDegree = dist_offsets(dist_adjs(j)+1) - dist_offsets(dist_adjs(j));
188 else nborDegree = ghost_degrees(dist_adjs(j) - n_local);
189 if(currColor == nborColor ){
190 if(currDegree < nborDegree && recolor_degrees){
191 femv_colors(localIdx) = 0;
192 recoloring_size++;
193 break;
194 }else if(nborDegree < currDegree && recolor_degrees){
195 femv_colors(dist_adjs(j)) = 0;
196 recoloring_size++;
197 }else if(rand(localIdx) > rand(dist_adjs(j))){
198 recoloring_size++;
199 femv_colors(localIdx) = 0;
200 break;
201 }else if(rand(dist_adjs(j)) > rand(localIdx)){
202 recoloring_size++;
203 femv_colors(dist_adjs(j)) = 0;
204 } else {
205 if (gid(localIdx) >= gid(dist_adjs(j))){
206 femv_colors(localIdx) = 0;
207 recoloring_size++;
208 break;
209 } else {
210 femv_colors(dist_adjs(j)) = 0;
211 recoloring_size++;
212 }
213 }
214 }
215 }
216 },local_recoloring_size);
217 Kokkos::deep_copy(recoloringSize, local_recoloring_size);
218 Kokkos::fence();
219 Kokkos::parallel_for("rebuild verts_to_send and verts_to_recolor",
220 Kokkos::RangePolicy<ExecutionSpace>(0,femv_colors.size()),
221 KOKKOS_LAMBDA (const size_t& i){
222 if(femv_colors(i) == 0){
223 if(i < n_local){
224 verts_to_send_view(verts_to_send_size_atomic(0)++) = i;
225 }
226 verts_to_recolor_view(verts_to_recolor_size_atomic(0)++) = i;
227 }
228 });
229 Kokkos::fence();
230
231 }
232
233 virtual void detectConflicts(const size_t n_local,
234 Kokkos::View<offset_t*, device_type > dist_offsets_dev,
235 Kokkos::View<lno_t*, device_type > dist_adjs_dev,
236 Kokkos::View<int*,device_type > femv_colors,
237 Kokkos::View<lno_t*, device_type > boundary_verts_view,
238 Kokkos::View<lno_t*,
239 device_type > verts_to_recolor_view,
240 Kokkos::View<int*,
242 Kokkos::MemoryTraits<Kokkos::Atomic>> verts_to_recolor_size_atomic,
243 Kokkos::View<lno_t*,
244 device_type > verts_to_send_view,
245 Kokkos::View<size_t*,
247 Kokkos::MemoryTraits<Kokkos::Atomic>> verts_to_send_size_atomic,
248 Kokkos::View<size_t*, device_type> recoloringSize,
249 Kokkos::View<int*,
250 device_type> rand,
251 Kokkos::View<gno_t*,
252 device_type> gid,
253 Kokkos::View<gno_t*,
254 device_type> ghost_degrees,
255 bool recolor_degrees){
256 this->detectD1Conflicts<execution_space, memory_space>(n_local,
257 dist_offsets_dev,
258 dist_adjs_dev,
259 femv_colors,
260 boundary_verts_view,
261 verts_to_recolor_view,
262 verts_to_recolor_size_atomic,
263 verts_to_send_view,
264 verts_to_send_size_atomic,
265 recoloringSize,
266 rand,
267 gid,
268 ghost_degrees,
269 recolor_degrees);
270 }
271
272 virtual void detectConflicts_serial(const size_t n_local,
273 typename Kokkos::View<offset_t*, device_type >::HostMirror dist_offsets_host,
274 typename Kokkos::View<lno_t*, device_type >::HostMirror dist_adjs_host,
275 typename Kokkos::View<int*,device_type >::HostMirror femv_colors,
276 typename Kokkos::View<lno_t*, device_type >::HostMirror boundary_verts_view,
277 typename Kokkos::View<lno_t*,device_type>::HostMirror verts_to_recolor,
278 typename Kokkos::View<int*,device_type>::HostMirror verts_to_recolor_size,
279 typename Kokkos::View<lno_t*,device_type>::HostMirror verts_to_send,
280 typename Kokkos::View<size_t*,device_type>::HostMirror verts_to_send_size,
281 typename Kokkos::View<size_t*, device_type>::HostMirror recoloringSize,
282 typename Kokkos::View<int*, device_type>::HostMirror rand,
283 typename Kokkos::View<gno_t*,device_type>::HostMirror gid,
284 typename Kokkos::View<gno_t*,device_type>::HostMirror ghost_degrees,
285 bool recolor_degrees) {
286 this->detectD1Conflicts<host_exec, host_mem >(n_local,
287 dist_offsets_host,
288 dist_adjs_host,
289 femv_colors,
290 boundary_verts_view,
291 verts_to_recolor,
292 verts_to_recolor_size,
293 verts_to_send,
294 verts_to_send_size,
295 recoloringSize,
296 rand,
297 gid,
298 ghost_degrees,
299 recolor_degrees);
300
301 }
302
303 virtual void constructBoundary(const size_t n_local,
304 Kokkos::View<offset_t*, device_type> dist_offsets_dev,
305 Kokkos::View<lno_t*, device_type> dist_adjs_dev,
306 typename Kokkos::View<offset_t*, device_type>::HostMirror dist_offsets_host,
307 typename Kokkos::View<lno_t*, device_type>::HostMirror dist_adjs_host,
308 Kokkos::View<lno_t*, device_type>& boundary_verts,
309 Kokkos::View<lno_t*,
310 device_type > verts_to_send_view,
311 Kokkos::View<size_t*,
313 Kokkos::MemoryTraits<Kokkos::Atomic>> verts_to_send_size_atomic){
314
315 Kokkos::parallel_for("constructBoundary",
316 Kokkos::RangePolicy<execution_space, int>(0,n_local),
317 KOKKOS_LAMBDA(const int& i){
318 for(offset_t j = dist_offsets_dev(i); j < dist_offsets_dev(i+1); j++){
319 if((size_t)dist_adjs_dev(j) >= n_local){
320 verts_to_send_view(verts_to_send_size_atomic(0)++) = i;
321 break;
322 }
323 bool found = false;
324 for(offset_t k = dist_offsets_dev(dist_adjs_dev(j)); k < dist_offsets_dev(dist_adjs_dev(j)+1); k++){
325 if((size_t)dist_adjs_dev(k) >= n_local){
326 verts_to_send_view(verts_to_send_size_atomic(0)++) = i;
327 found = true;
328 break;
329 }
330 }
331 if(found) break;
332 }
333 });
334 Kokkos::fence();
335 }
336
337
338 public:
340 const RCP<const base_adapter_t> &adapter_,
341 const RCP<Teuchos::ParameterList> &pl_,
342 const RCP<Environment> &env_,
343 const RCP<const Teuchos::Comm<int> > &comm_)
344 : AlgTwoGhostLayer<Adapter>(adapter_,pl_,env_,comm_){
345 }
346
347
348
349}; //end class
350
351
352
353}//end namespace Zoltan2
354
355#endif
AlltoAll communication methods.
Defines the ColoringSolution class.
Defines the GraphModel interface.
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t,...
A gathering of useful namespace methods.
virtual void detectConflicts(const size_t n_local, Kokkos::View< offset_t *, device_type > dist_offsets_dev, Kokkos::View< lno_t *, device_type > dist_adjs_dev, Kokkos::View< int *, device_type > femv_colors, Kokkos::View< lno_t *, device_type > boundary_verts_view, Kokkos::View< lno_t *, device_type > verts_to_recolor_view, Kokkos::View< int *, device_type, Kokkos::MemoryTraits< Kokkos::Atomic > > verts_to_recolor_size_atomic, Kokkos::View< lno_t *, device_type > verts_to_send_view, Kokkos::View< size_t *, device_type, Kokkos::MemoryTraits< Kokkos::Atomic > > verts_to_send_size_atomic, Kokkos::View< size_t *, device_type > recoloringSize, Kokkos::View< int *, device_type > rand, Kokkos::View< gno_t *, device_type > gid, Kokkos::View< gno_t *, device_type > ghost_degrees, bool recolor_degrees)
void detectD1Conflicts(const size_t n_local, Kokkos::View< offset_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > dist_offsets, Kokkos::View< lno_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > dist_adjs, Kokkos::View< int *, Kokkos::Device< ExecutionSpace, MemorySpace > > femv_colors, Kokkos::View< lno_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > boundary_verts_view, Kokkos::View< lno_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > verts_to_recolor_view, Kokkos::View< int *, Kokkos::Device< ExecutionSpace, MemorySpace >, Kokkos::MemoryTraits< Kokkos::Atomic > > verts_to_recolor_size_atomic, Kokkos::View< lno_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > verts_to_send_view, Kokkos::View< size_t *, Kokkos::Device< ExecutionSpace, MemorySpace >, Kokkos::MemoryTraits< Kokkos::Atomic > > verts_to_send_size_atomic, Kokkos::View< size_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > recoloringSize, Kokkos::View< int *, Kokkos::Device< ExecutionSpace, MemorySpace > > rand, Kokkos::View< gno_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > gid, Kokkos::View< gno_t *, Kokkos::Device< ExecutionSpace, MemorySpace > > ghost_degrees, bool recolor_degrees)
Tpetra::FEMultiVector< femv_scalar_t, lno_t, gno_t > femv_t
virtual void constructBoundary(const size_t n_local, Kokkos::View< offset_t *, device_type > dist_offsets_dev, Kokkos::View< lno_t *, device_type > dist_adjs_dev, typename Kokkos::View< offset_t *, device_type >::HostMirror dist_offsets_host, typename Kokkos::View< lno_t *, device_type >::HostMirror dist_adjs_host, Kokkos::View< lno_t *, device_type > &boundary_verts, Kokkos::View< lno_t *, device_type > verts_to_send_view, Kokkos::View< size_t *, device_type, Kokkos::MemoryTraits< Kokkos::Atomic > > verts_to_send_size_atomic)
typename Adapter::base_adapter_t base_adapter_t
virtual void detectConflicts_serial(const size_t n_local, typename Kokkos::View< offset_t *, device_type >::HostMirror dist_offsets_host, typename Kokkos::View< lno_t *, device_type >::HostMirror dist_adjs_host, typename Kokkos::View< int *, device_type >::HostMirror femv_colors, typename Kokkos::View< lno_t *, device_type >::HostMirror boundary_verts_view, typename Kokkos::View< lno_t *, device_type >::HostMirror verts_to_recolor, typename Kokkos::View< int *, device_type >::HostMirror verts_to_recolor_size, typename Kokkos::View< lno_t *, device_type >::HostMirror verts_to_send, typename Kokkos::View< size_t *, device_type >::HostMirror verts_to_send_size, typename Kokkos::View< size_t *, device_type >::HostMirror recoloringSize, typename Kokkos::View< int *, device_type >::HostMirror rand, typename Kokkos::View< gno_t *, device_type >::HostMirror gid, typename Kokkos::View< gno_t *, device_type >::HostMirror ghost_degrees, bool recolor_degrees)
typename femv_t::device_type device_type
typename femv_t::host_view_type::device_type::execution_space host_exec
AlgDistance1TwoGhostLayer(const RCP< const base_adapter_t > &adapter_, const RCP< Teuchos::ParameterList > &pl_, const RCP< Environment > &env_, const RCP< const Teuchos::Comm< int > > &comm_)
typename device_type::memory_space memory_space
typename device_type::execution_space execution_space
typename femv_t::host_view_type::device_type::memory_space host_mem
Created by mbenlioglu on Aug 31, 2020.