Kokkos Core Kernels Package  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Kokkos_StaticCrsGraph.hpp
1 /*
2 //@HEADER
3 // ************************************************************************
4 //
5 // Kokkos v. 3.0
6 // Copyright (2020) National Technology & Engineering
7 // Solutions of Sandia, LLC (NTESS).
8 //
9 // Under the terms of Contract DE-NA0003525 with NTESS,
10 // the U.S. Government retains certain rights in this software.
11 //
12 // Redistribution and use in source and binary forms, with or without
13 // modification, are permitted provided that the following conditions are
14 // met:
15 //
16 // 1. Redistributions of source code must retain the above copyright
17 // notice, this list of conditions and the following disclaimer.
18 //
19 // 2. Redistributions in binary form must reproduce the above copyright
20 // notice, this list of conditions and the following disclaimer in the
21 // documentation and/or other materials provided with the distribution.
22 //
23 // 3. Neither the name of the Corporation nor the names of the
24 // contributors may be used to endorse or promote products derived from
25 // this software without specific prior written permission.
26 //
27 // THIS SOFTWARE IS PROVIDED BY NTESS "AS IS" AND ANY
28 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
30 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL NTESS OR THE
31 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
32 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
33 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
34 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
35 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
36 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
37 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 //
39 // Questions? Contact Christian R. Trott (crtrott@sandia.gov)
40 //
41 // ************************************************************************
42 //@HEADER
43 */
44 
45 #ifndef KOKKOS_STATICCRSGRAPH_HPP
46 #define KOKKOS_STATICCRSGRAPH_HPP
47 
48 #include <string>
49 #include <vector>
50 
51 #include <Kokkos_View.hpp>
52 #include <Kokkos_Parallel.hpp>
53 #include <Kokkos_Parallel_Reduce.hpp>
54 
55 namespace Kokkos {
56 
57 namespace Impl {
58 template <class RowOffsetsType, class RowBlockOffsetsType>
59 struct StaticCrsGraphBalancerFunctor {
60  typedef typename RowOffsetsType::non_const_value_type int_type;
61  RowOffsetsType row_offsets;
62  RowBlockOffsetsType row_block_offsets;
63 
64  int_type cost_per_row, num_blocks;
65 
66  StaticCrsGraphBalancerFunctor(RowOffsetsType row_offsets_,
67  RowBlockOffsetsType row_block_offsets_,
68  int_type cost_per_row_, int_type num_blocks_)
69  : row_offsets(row_offsets_),
70  row_block_offsets(row_block_offsets_),
71  cost_per_row(cost_per_row_),
72  num_blocks(num_blocks_) {}
73 
74  KOKKOS_INLINE_FUNCTION
75  void operator()(const int_type& iRow) const {
76  const int_type num_rows = row_offsets.extent(0) - 1;
77  const int_type num_entries = row_offsets(num_rows);
78  const int_type total_cost = num_entries + num_rows * cost_per_row;
79 
80  const double cost_per_workset = 1.0 * total_cost / num_blocks;
81 
82  const int_type row_cost =
83  row_offsets(iRow + 1) - row_offsets(iRow) + cost_per_row;
84 
85  int_type count = row_offsets(iRow + 1) + cost_per_row * iRow;
86 
87  if (iRow == num_rows - 1) row_block_offsets(num_blocks) = num_rows;
88 
89  if (true) {
90  int_type current_block =
91  (count - row_cost - cost_per_row) / cost_per_workset;
92  int_type end_block = count / cost_per_workset;
93 
94  // Handle some corner cases for the last two blocks.
95  if (current_block >= num_blocks - 2) {
96  if ((current_block == num_blocks - 2) &&
97  (count >= (current_block + 1) * cost_per_workset)) {
98  int_type row = iRow;
99  int_type cc = count - row_cost - cost_per_row;
100  int_type block = cc / cost_per_workset;
101  while ((block > 0) && (block == current_block)) {
102  cc = row_offsets(row) + row * cost_per_row;
103  block = cc / cost_per_workset;
104  row--;
105  }
106  if ((count - cc - row_cost - cost_per_row) <
107  num_entries - row_offsets(iRow + 1)) {
108  row_block_offsets(current_block + 1) = iRow + 1;
109  } else {
110  row_block_offsets(current_block + 1) = iRow;
111  }
112  }
113  } else {
114  if ((count >= (current_block + 1) * cost_per_workset) ||
115  (iRow + 2 == int_type(row_offsets.extent(0)))) {
116  if (end_block > current_block + 1) {
117  int_type num_block = end_block - current_block;
118  row_block_offsets(current_block + 1) = iRow;
119  for (int_type block = current_block + 2; block <= end_block;
120  block++)
121  if ((block < current_block + 2 + (num_block - 1) / 2))
122  row_block_offsets(block) = iRow;
123  else
124  row_block_offsets(block) = iRow + 1;
125  } else {
126  row_block_offsets(current_block + 1) = iRow + 1;
127  }
128  }
129  }
130  }
131  }
132 };
133 } // namespace Impl
134 
170 template <class GraphType>
173  typedef const typename GraphType::data_type ordinal_type;
174 
175  private:
177  ordinal_type* colidx_;
185  const ordinal_type stride_;
186 
187  public:
195  KOKKOS_INLINE_FUNCTION
196  GraphRowViewConst(ordinal_type* const colidx_in, const ordinal_type& stride,
197  const ordinal_type& count)
198  : colidx_(colidx_in), stride_(stride), length(count) {}
199 
212  template <class OffsetType>
213  KOKKOS_INLINE_FUNCTION GraphRowViewConst(
214  const typename GraphType::entries_type& colidx_in,
215  const ordinal_type& stride, const ordinal_type& count,
216  const OffsetType& idx,
217  const typename std::enable_if<std::is_integral<OffsetType>::value,
218  int>::type& = 0)
219  : colidx_(&colidx_in(idx)), stride_(stride), length(count) {}
220 
232 
238  KOKKOS_INLINE_FUNCTION
239  ordinal_type& colidx(const ordinal_type& i) const {
240  return colidx_[i * stride_];
241  }
242 
244  KOKKOS_INLINE_FUNCTION
245  ordinal_type& operator()(const ordinal_type& i) const { return colidx(i); }
246 };
247 
281 template <class DataType, class Arg1Type, class Arg2Type = void,
282 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
283  typename SizeType =
284  typename ViewTraits<DataType*, Arg1Type, Arg2Type>::size_type,
285  class Arg3Type = void>
286 #else
287  class Arg3Type = void,
288  typename SizeType = typename ViewTraits<DataType*, Arg1Type, Arg2Type,
289  Arg3Type>::size_type>
290 #endif
292  private:
294 
295  public:
296  typedef DataType data_type;
297  typedef typename traits::array_layout array_layout;
298  typedef typename traits::execution_space execution_space;
299  typedef typename traits::device_type device_type;
300  typedef typename traits::memory_traits memory_traits;
301  typedef SizeType size_type;
302 
303 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
306  typedef StaticCrsGraph<data_type, array_layout,
307  typename traits::host_mirror_space, size_type,
308  memory_traits>
309  HostMirror;
310 #else
313  typedef StaticCrsGraph<data_type, array_layout,
314  typename traits::host_mirror_space, memory_traits,
315  size_type>
316  HostMirror;
317 #endif
318 
320  row_map_type;
322  entries_type;
325 
326  entries_type entries;
327  row_map_type row_map;
328  row_block_type row_block_offsets;
329 
331  KOKKOS_INLINE_FUNCTION
332  StaticCrsGraph() : entries(), row_map(), row_block_offsets() {}
333 
335  KOKKOS_INLINE_FUNCTION
337  : entries(rhs.entries),
338  row_map(rhs.row_map),
339  row_block_offsets(rhs.row_block_offsets) {}
340 
341  template <class EntriesType, class RowMapType>
342  KOKKOS_INLINE_FUNCTION StaticCrsGraph(const EntriesType& entries_,
343  const RowMapType& row_map_)
344  : entries(entries_), row_map(row_map_), row_block_offsets() {}
345 
350  KOKKOS_INLINE_FUNCTION
352  entries = rhs.entries;
353  row_map = rhs.row_map;
354  row_block_offsets = rhs.row_block_offsets;
355  return *this;
356  }
357 
361  KOKKOS_DEFAULTED_FUNCTION
362  ~StaticCrsGraph() = default;
363 
366  KOKKOS_INLINE_FUNCTION
367  size_type numRows() const {
368  return (row_map.extent(0) != 0)
369  ? row_map.extent(0) - static_cast<size_type>(1)
370  : static_cast<size_type>(0);
371  }
372 
391  KOKKOS_INLINE_FUNCTION
392  GraphRowViewConst<StaticCrsGraph> rowConst(const data_type i) const {
393  const size_type start = row_map(i);
394  // count is guaranteed to fit in ordinal_type, as long as no row
395  // has duplicate entries.
396  const data_type count = static_cast<data_type>(row_map(i + 1) - start);
397 
398  if (count == 0) {
399  return GraphRowViewConst<StaticCrsGraph>(nullptr, 1, 0);
400  } else {
401  return GraphRowViewConst<StaticCrsGraph>(entries, 1, count, start);
402  }
403  }
404 
408  void create_block_partitioning(size_type num_blocks,
409  size_type fix_cost_per_row = 4) {
411  "StatisCrsGraph::load_balance_offsets", num_blocks + 1);
412 
413  Impl::StaticCrsGraphBalancerFunctor<
415  partitioner(row_map, block_offsets, fix_cost_per_row, num_blocks);
416 
417  Kokkos::parallel_for("Kokkos::StaticCrsGraph::create_block_partitioning",
419  partitioner);
420  typename device_type::execution_space().fence();
421 
422  row_block_offsets = block_offsets;
423  }
424 };
425 
426 //----------------------------------------------------------------------------
427 
428 template <class StaticCrsGraphType, class InputSizeType>
429 typename StaticCrsGraphType::staticcrsgraph_type create_staticcrsgraph(
430  const std::string& label, const std::vector<InputSizeType>& input);
431 
432 template <class StaticCrsGraphType, class InputSizeType>
433 typename StaticCrsGraphType::staticcrsgraph_type create_staticcrsgraph(
434  const std::string& label,
435  const std::vector<std::vector<InputSizeType> >& input);
436 
437 //----------------------------------------------------------------------------
438 
439 template <class DataType, class Arg1Type, class Arg2Type,
440 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
441  typename SizeType, class Arg3Type>
442 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, SizeType,
443  Arg3Type>::HostMirror
444 create_mirror_view(const StaticCrsGraph<DataType, Arg1Type, Arg2Type, SizeType,
445  Arg3Type>& input);
446 #else
447  class Arg3Type, typename SizeType>
448 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
449  SizeType>::HostMirror
450 create_mirror_view(const StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
451  SizeType>& input);
452 #endif
453 
454 template <class DataType, class Arg1Type, class Arg2Type,
455 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
456  typename SizeType, class Arg3Type>
457 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, SizeType,
458  Arg3Type>::HostMirror
459 create_mirror_view(const StaticCrsGraph<DataType, Arg1Type, Arg2Type, SizeType,
460  Arg3Type>& input);
461 #else
462  class Arg3Type, typename SizeType>
463 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
464  SizeType>::HostMirror
465 create_mirror(const StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
466  SizeType>& input);
467 #endif
468 
469 } // namespace Kokkos
470 
471 //----------------------------------------------------------------------------
472 //----------------------------------------------------------------------------
473 
474 #include <impl/Kokkos_StaticCrsGraph_factory.hpp>
475 
476 //----------------------------------------------------------------------------
477 //----------------------------------------------------------------------------
478 
479 namespace Kokkos {
480 namespace Impl {
481 
482 template <class GraphType>
483 struct StaticCrsGraphMaximumEntry {
484  typedef typename GraphType::execution_space execution_space;
485  typedef typename GraphType::data_type value_type;
486 
487  const typename GraphType::entries_type entries;
488 
489  StaticCrsGraphMaximumEntry(const GraphType& graph) : entries(graph.entries) {}
490 
491  KOKKOS_INLINE_FUNCTION
492  void operator()(const unsigned i, value_type& update) const {
493  if (update < entries(i)) update = entries(i);
494  }
495 
496  KOKKOS_INLINE_FUNCTION
497  void init(value_type& update) const { update = 0; }
498 
499  KOKKOS_INLINE_FUNCTION
500  void join(volatile value_type& update,
501  volatile const value_type& input) const {
502  if (update < input) update = input;
503  }
504 };
505 
506 } // namespace Impl
507 
508 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
509 template <class DataType, class Arg1Type, class Arg2Type, typename SizeType,
510  class Arg3Type>
511 DataType maximum_entry(const StaticCrsGraph<DataType, Arg1Type, Arg2Type,
512  SizeType, Arg3Type>& graph) {
513  typedef StaticCrsGraph<DataType, Arg1Type, Arg2Type, SizeType, Arg3Type>
514  GraphType;
515 #else
516 template <class DataType, class Arg1Type, class Arg2Type, class Arg3Type,
517  typename SizeType>
518 DataType maximum_entry(const StaticCrsGraph<DataType, Arg1Type, Arg2Type,
519  Arg3Type, SizeType>& graph) {
520  typedef StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type, SizeType>
521  GraphType;
522 #endif
523  typedef Impl::StaticCrsGraphMaximumEntry<GraphType> FunctorType;
524 
525  DataType result = 0;
526  Kokkos::parallel_reduce("Kokkos::maximum_entry", graph.entries.extent(0),
527  FunctorType(graph), result);
528  return result;
529 }
530 
531 } // namespace Kokkos
532 
533 //----------------------------------------------------------------------------
534 //----------------------------------------------------------------------------
535 
536 #endif /* #ifndef KOKKOS_CRSARRAY_HPP */
KOKKOS_INLINE_FUNCTION GraphRowViewConst< StaticCrsGraph > rowConst(const data_type i) const
Return a const view of row i of the graph.
KOKKOS_INLINE_FUNCTION StaticCrsGraph()
Construct an empty view.
const ordinal_type length
Number of entries in the row.
KOKKOS_INLINE_FUNCTION StaticCrsGraph(const StaticCrsGraph &rhs)
Copy constructor (shallow copy).
KOKKOS_INLINE_FUNCTION constexpr std::enable_if< std::is_integral< iType >::value, size_t >::type extent(const iType &r) const noexcept
rank() to be implemented
KOKKOS_INLINE_FUNCTION GraphRowViewConst(ordinal_type *const colidx_in, const ordinal_type &stride, const ordinal_type &count)
Constructor.
KOKKOS_INLINE_FUNCTION ordinal_type & colidx(const ordinal_type &i) const
(Const) reference to the column index of entry i in this row of the sparse matrix.
KOKKOS_DEFAULTED_FUNCTION ~StaticCrsGraph()=default
Destroy this view of the array. If the last view then allocated memory is deallocated.
const GraphType::data_type ordinal_type
The type of the column indices in the row.
KOKKOS_INLINE_FUNCTION ordinal_type & operator()(const ordinal_type &i) const
An alias for colidx.
void create_block_partitioning(size_type num_blocks, size_type fix_cost_per_row=4)
Create a row partitioning into a given number of blocks balancing non-zeros + a fixed cost per row...
Declaration of parallel operators.
void parallel_reduce(const std::string &label, const PolicyType &policy, const FunctorType &functor, ReturnType &return_value, typename std::enable_if< Kokkos::Impl::is_execution_policy< PolicyType >::value >::type *=nullptr)
Parallel reduction.
KOKKOS_INLINE_FUNCTION GraphRowViewConst(const typename GraphType::entries_type &colidx_in, const ordinal_type &stride, const ordinal_type &count, const OffsetType &idx, const typename std::enable_if< std::is_integral< OffsetType >::value, int >::type &=0)
Constructor with offset into colidx array.
void parallel_for(const ExecPolicy &policy, const FunctorType &functor, const std::string &str="", typename std::enable_if< Kokkos::Impl::is_execution_policy< ExecPolicy >::value >::type *=nullptr)
Execute functor in parallel according to the execution policy.
KOKKOS_INLINE_FUNCTION size_type numRows() const
Return number of rows in the graph.
Execution policy for work over a range of an integral type.
Compressed row storage array.
Traits class for accessing attributes of a View.
View of a row of a sparse graph.
KOKKOS_INLINE_FUNCTION StaticCrsGraph & operator=(const StaticCrsGraph &rhs)
Assign to a view of the rhs array. If the old view is the last view then allocated memory is dealloca...