1 #ifndef _ZOLTAN2_PDISTANCE2_HPP_
2 #define _ZOLTAN2_PDISTANCE2_HPP_
5 #include <unordered_map>
22 #include "Tpetra_Core.hpp"
23 #include "Teuchos_RCP.hpp"
24 #include "Tpetra_Import.hpp"
25 #include "Tpetra_FEMultiVector.hpp"
27 #include "Kokkos_Core.hpp"
28 #include "KokkosSparse_CrsMatrix.hpp"
29 #include "KokkosKernels_Handle.hpp"
30 #include "KokkosKernels_IOUtils.hpp"
31 #include "KokkosGraph_Distance2Color.hpp"
32 #include "KokkosGraph_Distance2ColorHandle.hpp"
41 template <
typename Adapter>
51 using map_t = Tpetra::Map<lno_t,gno_t>;
53 using femv_t = Tpetra::FEMultiVector<femv_scalar_t, lno_t, gno_t>;
57 using host_exec =
typename femv_t::host_view_type::device_type::execution_space;
58 using host_mem =
typename femv_t::host_view_type::device_type::memory_space;
62 template<
class ExecutionSpace,
typename MemorySpace>
63 void localColoring(
const size_t nVtx,
64 Kokkos::View<
lno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> adjs_view,
65 Kokkos::View<
offset_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> offset_view,
66 Teuchos::RCP<femv_t> femv,
67 Kokkos::View<
lno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> vertex_list,
68 size_t vertex_list_size = 0,
69 bool use_vertex_based_coloring =
false){
70 using KernelHandle = KokkosKernels::Experimental::KokkosKernelsHandle
77 kh.create_distance2_graph_coloring_handle(KokkosGraph::COLORING_D2_NB_BIT);
81 if(vertex_list_size != 0){
82 kh.get_distance2_graph_coloring_handle()->set_vertex_list(vertex_list, vertex_list_size);
86 kh.get_distance2_graph_coloring_handle()->set_verbose(this->
verbose);
89 auto femvColors = femv->template getLocalView<Kokkos::Device<ExecutionSpace,MemorySpace> >(Tpetra::Access::ReadWrite);
90 auto sv = subview(femvColors,Kokkos::ALL, 0);
91 kh.get_distance2_graph_coloring_handle()->set_vertex_colors(sv);
94 KokkosGraph::Experimental::bipartite_color_rows(&kh, nVtx, nVtx, offset_view, adjs_view,
true);
99 std::cout<<
"\nKokkosKernels Coloring: "
100 <<kh.get_distance2_graph_coloring_handle()->get_overall_coloring_time()
106 virtual void colorInterior(
const size_t nVtx,
107 Kokkos::View<lno_t*, device_type> adjs_view,
108 Kokkos::View<offset_t*, device_type> offset_view,
109 Teuchos::RCP<femv_t> femv,
110 Kokkos::View<lno_t*, device_type> vertex_list,
111 size_t vertex_list_size=0,
113 this->localColoring<execution_space, memory_space>(nVtx,
122 virtual void colorInterior_serial(
const size_t nVtx,
123 typename Kokkos::View<lno_t*, device_type >::HostMirror adjs_view,
124 typename Kokkos::View<offset_t*,device_type >::HostMirror offset_view,
125 Teuchos::RCP<femv_t> femv,
126 typename Kokkos::View<lno_t*, device_type>::HostMirror vertex_list,
127 size_t vertex_list_size = 0,
128 bool recolor=
false) {
129 this->localColoring<host_exec, host_mem>(nVtx,
140 template <
class ExecutionSpace,
typename MemorySpace>
142 Kokkos::View<
offset_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> dist_offsets,
143 Kokkos::View<
lno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> dist_adjs,
144 Kokkos::View<
int*, Kokkos::Device<ExecutionSpace, MemorySpace>> femv_colors,
145 Kokkos::View<
lno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> boundary_verts_view,
147 Kokkos::Device<ExecutionSpace, MemorySpace> > verts_to_recolor_view,
149 Kokkos::Device<ExecutionSpace, MemorySpace>,
150 Kokkos::MemoryTraits<Kokkos::Atomic> > verts_to_recolor_size_atomic,
152 Kokkos::Device<ExecutionSpace, MemorySpace> > verts_to_send_view,
153 Kokkos::View<
size_t*,
154 Kokkos::Device<ExecutionSpace, MemorySpace>,
155 Kokkos::MemoryTraits<Kokkos::Atomic> > verts_to_send_size_atomic,
156 Kokkos::View<
size_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> recoloringSize,
157 Kokkos::View<
int*, Kokkos::Device<ExecutionSpace, MemorySpace>> rand,
158 Kokkos::View<
gno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> gid,
159 Kokkos::View<
gno_t*, Kokkos::Device<ExecutionSpace, MemorySpace>> ghost_degrees,
160 bool recolor_degrees){
162 Kokkos::RangePolicy<ExecutionSpace> policy(0,boundary_verts_view.extent(0));
163 size_t local_recoloring_size;
164 Kokkos::parallel_reduce(
"PD2 conflict detection",policy, KOKKOS_LAMBDA(
const uint64_t& i,
size_t& recoloring_size){
166 const size_t curr_lid = boundary_verts_view(i);
167 const int curr_color = femv_colors(curr_lid);
168 const size_t vid_d1_adj_begin = dist_offsets(curr_lid);
169 const size_t vid_d1_adj_end = dist_offsets(curr_lid+1);
170 const size_t curr_degree = vid_d1_adj_end - vid_d1_adj_begin;
171 for(
size_t vid_d1_adj = vid_d1_adj_begin; vid_d1_adj < vid_d1_adj_end; vid_d1_adj++){
173 size_t vid_d1 = dist_adjs(vid_d1_adj);
174 size_t d2_adj_begin = dist_offsets(vid_d1);
175 size_t d2_adj_end = dist_offsets(vid_d1+1);
181 for(
size_t vid_d2_adj = d2_adj_begin; vid_d2_adj < d2_adj_end; vid_d2_adj++){
182 const size_t vid_d2 = dist_adjs(vid_d2_adj);
183 size_t vid_d2_degree = 0;
186 if(vid_d2 < n_local){
187 vid_d2_degree = dist_offsets(vid_d2+1) - dist_offsets(vid_d2);
189 vid_d2_degree = ghost_degrees(vid_d2-n_local);
192 if(curr_lid != vid_d2 && femv_colors(vid_d2) == curr_color){
193 if(curr_degree < vid_d2_degree && recolor_degrees){
195 femv_colors(curr_lid) = 0;
198 }
else if(vid_d2_degree < curr_degree && recolor_degrees){
199 femv_colors(vid_d2) = 0;
201 }
else if(rand(curr_lid) < rand(vid_d2)){
203 femv_colors(curr_lid) = 0;
206 }
else if(rand(vid_d2) < rand(curr_lid)){
207 femv_colors(vid_d2) = 0;
210 if(gid(curr_lid) >= gid(vid_d2)){
212 femv_colors(curr_lid) = 0;
216 femv_colors(vid_d2) = 0;
224 },local_recoloring_size);
225 Kokkos::deep_copy(recoloringSize, local_recoloring_size);
228 Kokkos::parallel_for(
"rebuild verts_to_send and verts_to_recolor",
229 Kokkos::RangePolicy<ExecutionSpace>(0,femv_colors.size()),
230 KOKKOS_LAMBDA(
const uint64_t& i){
231 if(femv_colors(i) == 0){
234 verts_to_send_view(verts_to_send_size_atomic(0)++) = i;
237 verts_to_recolor_view(verts_to_recolor_size_atomic(0)++) = i;
245 Kokkos::View<offset_t*, device_type > dist_offsets_dev,
246 Kokkos::View<lno_t*, device_type > dist_adjs_dev,
247 Kokkos::View<int*,device_type > femv_colors,
248 Kokkos::View<lno_t*, device_type > boundary_verts_view,
253 Kokkos::MemoryTraits<Kokkos::Atomic>> verts_to_recolor_size_atomic,
256 Kokkos::View<
size_t*,
258 Kokkos::MemoryTraits<Kokkos::Atomic>> verts_to_send_size_atomic,
259 Kokkos::View<size_t*, device_type> recoloringSize,
266 bool recolor_degrees){
268 this->detectPD2Conflicts<execution_space, memory_space>(n_local,
273 verts_to_recolor_view,
274 verts_to_recolor_size_atomic,
276 verts_to_send_size_atomic,
285 typename Kokkos::View<offset_t*, device_type >::HostMirror dist_offsets_host,
286 typename Kokkos::View<lno_t*, device_type >::HostMirror dist_adjs_host,
287 typename Kokkos::View<int*,device_type >::HostMirror femv_colors,
288 typename Kokkos::View<lno_t*, device_type >::HostMirror boundary_verts_view,
289 typename Kokkos::View<lno_t*,device_type>::HostMirror verts_to_recolor,
290 typename Kokkos::View<int*,device_type>::HostMirror verts_to_recolor_size,
291 typename Kokkos::View<lno_t*,device_type>::HostMirror verts_to_send,
292 typename Kokkos::View<size_t*,device_type>::HostMirror verts_to_send_size,
293 typename Kokkos::View<size_t*, device_type>::HostMirror recoloringSize,
294 typename Kokkos::View<int*, device_type>::HostMirror rand,
295 typename Kokkos::View<gno_t*,device_type>::HostMirror gid,
296 typename Kokkos::View<gno_t*,device_type>::HostMirror ghost_degrees,
297 bool recolor_degrees) {
299 this->detectPD2Conflicts<host_exec, host_mem>(n_local,
305 verts_to_recolor_size,
316 Kokkos::View<offset_t*, device_type> dist_offsets_dev,
317 Kokkos::View<lno_t*, device_type> dist_adjs_dev,
318 typename Kokkos::View<offset_t*, device_type>::HostMirror dist_offsets_host,
319 typename Kokkos::View<lno_t*, device_type>::HostMirror dist_adjs_host,
320 Kokkos::View<lno_t*, device_type>& boundary_verts,
323 Kokkos::View<
size_t*,
325 Kokkos::MemoryTraits<Kokkos::Atomic>> verts_to_send_size_atomic){
328 gno_t boundary_size_temp = 0;
329 for(
size_t i = 0; i < n_local; i++){
330 for(
offset_t j = dist_offsets_host(i); j < dist_offsets_host(i+1); j++){
331 if((
size_t)dist_adjs_host(j) >= n_local){
332 boundary_size_temp++;
336 for(
offset_t k = dist_offsets_host(dist_adjs_host(j)); k < dist_offsets_host(dist_adjs_host(j)+1); k++){
337 if((
size_t)dist_adjs_host(k) >= n_local){
338 boundary_size_temp++;
348 boundary_verts = Kokkos::View<lno_t*, device_type>(
"boundary verts",boundary_size_temp);
349 typename Kokkos::View<lno_t*, device_type>::HostMirror boundary_verts_host = Kokkos::create_mirror_view(boundary_verts);
352 boundary_size_temp = 0;
354 for(
size_t i = 0; i < n_local; i++){
355 for(
offset_t j = dist_offsets_host(i); j < dist_offsets_host(i+1); j++){
356 if((
size_t)dist_adjs_host(j) >= n_local){
357 boundary_verts_host(boundary_size_temp++) = i;
361 for(
offset_t k = dist_offsets_host(dist_adjs_host(j)); k < dist_offsets_host(dist_adjs_host(j)+1); k++){
362 if((
size_t)dist_adjs_host(k) >= n_local){
363 boundary_verts_host(boundary_size_temp++) = i;
372 Kokkos::deep_copy(boundary_verts, boundary_verts_host);
375 Kokkos::parallel_for(
"init verts to send",
376 Kokkos::RangePolicy<execution_space, int>(0,n_local),
377 KOKKOS_LAMBDA(
const int& i){
378 for(
offset_t j = dist_offsets_dev(i); j < dist_offsets_dev(i+1); j++){
379 if((
size_t)dist_adjs_dev(j) >= n_local){
380 verts_to_send_view(verts_to_send_size_atomic(0)++) = i;
384 for(
offset_t k = dist_offsets_dev(dist_adjs_dev(j)); k < dist_offsets_dev(dist_adjs_dev(j)+1); k++){
385 if((
size_t)dist_adjs_dev(k) >= n_local){
386 verts_to_send_view(verts_to_send_size_atomic(0)++) = i;
401 const RCP<const base_adapter_t> &adapter_,
402 const RCP<Teuchos::ParameterList> &pl_,
403 const RCP<Environment> &env_,
404 const RCP<
const Teuchos::Comm<int> > &comm_)
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
Tpetra::FEMultiVector< femv_scalar_t, lno_t, gno_t > femv_t
typename Adapter::gno_t gno_t
typename Adapter::lno_t lno_t
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)
typename Adapter::lno_t lno_t
AlgPartialDistance2(const RCP< const base_adapter_t > &adapter_, const RCP< Teuchos::ParameterList > &pl_, const RCP< Environment > &env_, const RCP< const Teuchos::Comm< int > > &comm_)
map_t::global_ordinal_type gno_t
typename Adapter::offset_t offset_t
typename femv_t::host_view_type::device_type::memory_space host_mem
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)
map_t::local_ordinal_type lno_t
typename femv_t::device_type device_type
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t...
typename femv_t::host_view_type::device_type::execution_space host_exec
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)
Defines the ColoringSolution class.
Defines the GraphModel interface.
void detectPD2Conflicts(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)
A gathering of useful namespace methods.
typename Adapter::base_adapter_t base_adapter_t
typename device_type::execution_space execution_space
Tpetra::Map< lno_t, gno_t > map_t
typename Adapter::scalar_t scalar_t
typename device_type::memory_space memory_space
AlltoAll communication methods.
typename Adapter::offset_t offset_t