45 #ifndef KOKKOS_STATICCRSGRAPH_HPP 46 #define KOKKOS_STATICCRSGRAPH_HPP 51 #include <Kokkos_View.hpp> 53 #include <Kokkos_Parallel_Reduce.hpp> 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;
64 int_type cost_per_row, num_blocks;
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_) {}
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;
80 const double cost_per_workset = 1.0 * total_cost / num_blocks;
82 const int_type row_cost =
83 row_offsets(iRow + 1) - row_offsets(iRow) + cost_per_row;
85 int_type count = row_offsets(iRow + 1) + cost_per_row * iRow;
87 if (iRow == num_rows - 1) row_block_offsets(num_blocks) = num_rows;
90 int_type current_block =
91 (count - row_cost - cost_per_row) / cost_per_workset;
92 int_type end_block = count / cost_per_workset;
95 if (current_block >= num_blocks - 2) {
96 if ((current_block == num_blocks - 2) &&
97 (count >= (current_block + 1) * cost_per_workset)) {
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;
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;
110 row_block_offsets(current_block + 1) = iRow;
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;
121 if ((block < current_block + 2 + (num_block - 1) / 2))
122 row_block_offsets(block) = iRow;
124 row_block_offsets(block) = iRow + 1;
126 row_block_offsets(current_block + 1) = iRow + 1;
170 template <
class GraphType>
195 KOKKOS_INLINE_FUNCTION
198 : colidx_(colidx_in), stride_(stride),
length(count) {}
212 template <
class OffsetType>
214 const typename GraphType::entries_type& colidx_in,
216 const OffsetType& idx,
217 const typename std::enable_if<std::is_integral<OffsetType>::value,
219 : colidx_(&colidx_in(idx)), stride_(stride),
length(count) {}
238 KOKKOS_INLINE_FUNCTION
240 return colidx_[i * stride_];
244 KOKKOS_INLINE_FUNCTION
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>
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;
300 typename traits::host_mirror_space,
301 memory_traits, size_type>;
315 KOKKOS_INLINE_FUNCTION
319 KOKKOS_INLINE_FUNCTION
321 : entries(rhs.entries),
322 row_map(rhs.row_map),
323 row_block_offsets(rhs.row_block_offsets) {}
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() {}
334 KOKKOS_INLINE_FUNCTION
336 entries = rhs.entries;
337 row_map = rhs.row_map;
338 row_block_offsets = rhs.row_block_offsets;
345 KOKKOS_DEFAULTED_FUNCTION
350 KOKKOS_INLINE_FUNCTION
352 return (row_map.
extent(0) != 0)
353 ? row_map.
extent(0) -
static_cast<size_type
>(1)
354 : static_cast<size_type>(0);
357 KOKKOS_INLINE_FUNCTION constexpr
bool is_allocated()
const {
358 return (row_map.is_allocated() && entries.is_allocated());
379 KOKKOS_INLINE_FUNCTION
381 const size_type start = row_map(i);
384 const data_type count =
static_cast<data_type
>(row_map(i + 1) - start);
397 size_type fix_cost_per_row = 4) {
399 "StatisCrsGraph::load_balance_offsets", num_blocks + 1);
401 Impl::StaticCrsGraphBalancerFunctor<
403 partitioner(row_map, block_offsets, fix_cost_per_row, num_blocks);
405 Kokkos::parallel_for(
"Kokkos::StaticCrsGraph::create_block_partitioning",
408 typename device_type::execution_space().fence();
410 row_block_offsets = block_offsets;
416 template <
class StaticCrsGraphType,
class InputSizeType>
417 typename StaticCrsGraphType::staticcrsgraph_type create_staticcrsgraph(
418 const std::string& label,
const std::vector<InputSizeType>& input);
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);
427 template <
class DataType,
class Arg1Type,
class Arg2Type,
class Arg3Type,
429 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
430 SizeType>::HostMirror
431 create_mirror_view(
const StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
434 template <
class DataType,
class Arg1Type,
class Arg2Type,
class Arg3Type,
436 typename StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
437 SizeType>::HostMirror
438 create_mirror(
const StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type,
446 #include <impl/Kokkos_StaticCrsGraph_factory.hpp> 454 template <
class GraphType>
455 struct StaticCrsGraphMaximumEntry {
456 using execution_space =
typename GraphType::execution_space;
457 using value_type =
typename GraphType::data_type;
459 const typename GraphType::entries_type entries;
461 StaticCrsGraphMaximumEntry(
const GraphType& graph) : entries(graph.entries) {}
463 KOKKOS_INLINE_FUNCTION
464 void operator()(
const unsigned i, value_type& update)
const {
465 if (update < entries(i)) update = entries(i);
468 KOKKOS_INLINE_FUNCTION
469 void init(value_type& update)
const { update = 0; }
471 KOKKOS_INLINE_FUNCTION
472 void join(
volatile value_type& update,
473 volatile const value_type& input)
const {
474 if (update < input) update = input;
480 template <
class DataType,
class Arg1Type,
class Arg2Type,
class Arg3Type,
482 DataType maximum_entry(
const StaticCrsGraph<DataType, Arg1Type, Arg2Type,
483 Arg3Type, SizeType>& graph) {
485 StaticCrsGraph<DataType, Arg1Type, Arg2Type, Arg3Type, SizeType>;
486 using FunctorType = Impl::StaticCrsGraphMaximumEntry<GraphType>;
489 Kokkos::parallel_reduce(
"Kokkos::maximum_entry", graph.entries.extent(0),
490 FunctorType(graph), result);
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.
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.