Kokkos Core Kernels Package  Version of the Day
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  using int_type = typename RowOffsetsType::non_const_value_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  using ordinal_type = const typename GraphType::data_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  class Arg3Type = void,
283  typename SizeType = typename ViewTraits<DataType*, Arg1Type, Arg2Type,
284  Arg3Type>::size_type>
286  private:
288 
289  public:
290  using data_type = DataType;
291  using array_layout = typename traits::array_layout;
292  using execution_space = typename traits::execution_space;
293  using device_type = typename traits::device_type;
294  using memory_traits = typename traits::memory_traits;
295  using size_type = SizeType;
296 
297  using staticcrsgraph_type =
299  using HostMirror = StaticCrsGraph<data_type, array_layout,
300  typename traits::host_mirror_space,
301  memory_traits, size_type>;
302 
303  using row_map_type =
305  using entries_type =
307  using row_block_type =
309 
310  entries_type entries;
311  row_map_type row_map;
312  row_block_type row_block_offsets;
313 
315  KOKKOS_INLINE_FUNCTION
316  StaticCrsGraph() : entries(), row_map(), row_block_offsets() {}
317 
319  KOKKOS_INLINE_FUNCTION
321  : entries(rhs.entries),
322  row_map(rhs.row_map),
323  row_block_offsets(rhs.row_block_offsets) {}
324 
325  template <class EntriesType, class RowMapType>
326  KOKKOS_INLINE_FUNCTION StaticCrsGraph(const EntriesType& entries_,
327  const RowMapType& row_map_)
328  : entries(entries_), row_map(row_map_), row_block_offsets() {}
329 
334  KOKKOS_INLINE_FUNCTION
336  entries = rhs.entries;
337  row_map = rhs.row_map;
338  row_block_offsets = rhs.row_block_offsets;
339  return *this;
340  }
341 
345  KOKKOS_DEFAULTED_FUNCTION
346  ~StaticCrsGraph() = default;
347 
350  KOKKOS_INLINE_FUNCTION
351  size_type numRows() const {
352  return (row_map.extent(0) != 0)
353  ? row_map.extent(0) - static_cast<size_type>(1)
354  : static_cast<size_type>(0);
355  }
356 
357  KOKKOS_INLINE_FUNCTION constexpr bool is_allocated() const {
358  return (row_map.is_allocated() && entries.is_allocated());
359  }
360 
379  KOKKOS_INLINE_FUNCTION
380  GraphRowViewConst<StaticCrsGraph> rowConst(const data_type i) const {
381  const size_type start = row_map(i);
382  // count is guaranteed to fit in ordinal_type, as long as no row
383  // has duplicate entries.
384  const data_type count = static_cast<data_type>(row_map(i + 1) - start);
385 
386  if (count == 0) {
387  return GraphRowViewConst<StaticCrsGraph>(nullptr, 1, 0);
388  } else {
389  return GraphRowViewConst<StaticCrsGraph>(entries, 1, count, start);
390  }
391  }
392 
396  void create_block_partitioning(size_type num_blocks,
397  size_type fix_cost_per_row = 4) {
399  "StatisCrsGraph::load_balance_offsets", num_blocks + 1);
400 
401  Impl::StaticCrsGraphBalancerFunctor<
403  partitioner(row_map, block_offsets, fix_cost_per_row, num_blocks);
404 
405  Kokkos::parallel_for("Kokkos::StaticCrsGraph::create_block_partitioning",
407  partitioner);
408  typename device_type::execution_space().fence();
409 
410  row_block_offsets = block_offsets;
411  }
412 };
413 
414 //----------------------------------------------------------------------------
415 
416 template <class StaticCrsGraphType, class InputSizeType>
417 typename StaticCrsGraphType::staticcrsgraph_type create_staticcrsgraph(
418  const std::string& label, const std::vector<InputSizeType>& input);
419 
420 template <class StaticCrsGraphType, class InputSizeType>
421 typename StaticCrsGraphType::staticcrsgraph_type create_staticcrsgraph(
422  const std::string& label,
423  const std::vector<std::vector<InputSizeType> >& input);
424 
425 //----------------------------------------------------------------------------
426 
427 template <class DataType, class Arg1Type, class Arg2Type, class Arg3Type,
428  typename SizeType>
429 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
430  SizeType>::HostMirror
431 create_mirror_view(const StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
432  SizeType>& input);
433 
434 template <class DataType, class Arg1Type, class Arg2Type, class Arg3Type,
435  typename SizeType>
436 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
437  SizeType>::HostMirror
438 create_mirror(const StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
439  SizeType>& input);
440 
441 } // namespace Kokkos
442 
443 //----------------------------------------------------------------------------
444 //----------------------------------------------------------------------------
445 
446 #include <impl/Kokkos_StaticCrsGraph_factory.hpp>
447 
448 //----------------------------------------------------------------------------
449 //----------------------------------------------------------------------------
450 
451 namespace Kokkos {
452 namespace Impl {
453 
454 template <class GraphType>
455 struct StaticCrsGraphMaximumEntry {
456  using execution_space = typename GraphType::execution_space;
457  using value_type = typename GraphType::data_type;
458 
459  const typename GraphType::entries_type entries;
460 
461  StaticCrsGraphMaximumEntry(const GraphType& graph) : entries(graph.entries) {}
462 
463  KOKKOS_INLINE_FUNCTION
464  void operator()(const unsigned i, value_type& update) const {
465  if (update < entries(i)) update = entries(i);
466  }
467 
468  KOKKOS_INLINE_FUNCTION
469  void init(value_type& update) const { update = 0; }
470 
471  KOKKOS_INLINE_FUNCTION
472  void join(volatile value_type& update,
473  volatile const value_type& input) const {
474  if (update < input) update = input;
475  }
476 };
477 
478 } // namespace Impl
479 
480 template <class DataType, class Arg1Type, class Arg2Type, class Arg3Type,
481  typename SizeType>
482 DataType maximum_entry(const StaticCrsGraph<DataType, Arg1Type, Arg2Type,
483  Arg3Type, SizeType>& graph) {
484  using GraphType =
485  StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type, SizeType>;
486  using FunctorType = Impl::StaticCrsGraphMaximumEntry<GraphType>;
487 
488  DataType result = 0;
489  Kokkos::parallel_reduce("Kokkos::maximum_entry", graph.entries.extent(0),
490  FunctorType(graph), result);
491  return result;
492 }
493 
494 } // namespace Kokkos
495 
496 //----------------------------------------------------------------------------
497 //----------------------------------------------------------------------------
498 
499 #endif /* #ifndef KOKKOS_CRSARRAY_HPP */
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< StaticCrsGraph > rowConst(const data_type i) const
Return a const view of row i of the graph.
KOKKOS_INLINE_FUNCTION GraphRowViewConst(ordinal_type *const colidx_in, const ordinal_type &stride, const ordinal_type &count)
Constructor.
KOKKOS_DEFAULTED_FUNCTION ~StaticCrsGraph()=default
Destroy this view of the array. If the last view then allocated memory is deallocated.
const typename GraphType::data_type ordinal_type
The type of the column indices in the row.
KOKKOS_INLINE_FUNCTION size_type numRows() const
Return number of rows in the graph.
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.
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.
Execution policy for work over a range of an integral type.
Compressed row storage array.
Traits class for accessing attributes of a View.
Definition: dummy.cpp:3
KOKKOS_INLINE_FUNCTION ordinal_type & operator()(const ordinal_type &i) const
An alias for colidx.
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...
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.