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. 2.0
6 // Copyright (2014) Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Christian R. Trott (crtrott@sandia.gov)
39 //
40 // ************************************************************************
41 //@HEADER
42 */
43 
44 #ifndef KOKKOS_STATICCRSGRAPH_HPP
45 #define KOKKOS_STATICCRSGRAPH_HPP
46 
47 #include <string>
48 #include <vector>
49 
50 #include <Kokkos_View.hpp>
51 #include <Kokkos_Parallel.hpp>
52 #include <Kokkos_Parallel_Reduce.hpp>
53 
54 namespace Kokkos {
55 
56 namespace Impl {
57  template<class RowOffsetsType, class RowBlockOffsetsType>
58  struct StaticCrsGraphBalancerFunctor {
59  typedef typename RowOffsetsType::non_const_value_type int_type;
60  RowOffsetsType row_offsets;
61  RowBlockOffsetsType row_block_offsets;
62 
63  int_type cost_per_row, num_blocks;
64 
65  StaticCrsGraphBalancerFunctor(RowOffsetsType row_offsets_,
66  RowBlockOffsetsType row_block_offsets_,
67  int_type cost_per_row_, int_type num_blocks_):
68  row_offsets(row_offsets_),
69  row_block_offsets(row_block_offsets_),
70  cost_per_row(cost_per_row_),
71  num_blocks(num_blocks_){}
72 
73  KOKKOS_INLINE_FUNCTION
74  void operator() (const int_type& iRow) const {
75  const int_type num_rows = row_offsets.extent(0)-1;
76  const int_type num_entries = row_offsets(num_rows);
77  const int_type total_cost = num_entries + num_rows*cost_per_row;
78 
79  const double cost_per_workset = 1.0*total_cost/num_blocks;
80 
81  const int_type row_cost = row_offsets(iRow+1)-row_offsets(iRow) + cost_per_row;
82 
83  int_type count = row_offsets(iRow+1) + cost_per_row*iRow;
84 
85  if(iRow == num_rows-1) row_block_offsets(num_blocks) = num_rows;
86 
87  if(true) {
88  int_type current_block = (count-row_cost-cost_per_row)/cost_per_workset;
89  int_type end_block = count/cost_per_workset;
90 
91  // Handle some corner cases for the last two blocks.
92  if(current_block >= num_blocks-2) {
93  if((current_block == num_blocks-2) && (count >= (current_block + 1) * cost_per_workset)) {
94  int_type row = iRow;
95  int_type cc = count-row_cost-cost_per_row;
96  int_type block = cc/cost_per_workset;
97  while((block>0) && (block==current_block)) {
98  cc = row_offsets(row)+row*cost_per_row;
99  block = cc/cost_per_workset;
100  row--;
101  }
102  if((count-cc-row_cost-cost_per_row) < num_entries-row_offsets(iRow+1)) {
103  row_block_offsets(current_block+1) = iRow+1;
104  } else {
105  row_block_offsets(current_block+1) = iRow;
106  }
107  }
108  } else {
109  if((count >= (current_block + 1) * cost_per_workset) ||
110  (iRow+2 == row_offsets.extent(0))) {
111  if(end_block>current_block+1) {
112  int_type num_block = end_block-current_block;
113  row_block_offsets(current_block+1) = iRow;
114  for(int_type block = current_block+2; block <= end_block; block++)
115  if((block<current_block+2+(num_block-1)/2))
116  row_block_offsets(block) = iRow;
117  else
118  row_block_offsets(block) = iRow+1;
119  } else {
120  row_block_offsets(current_block+1) = iRow+1;
121  }
122  }
123  }
124 
125  }
126  }
127  };
128 }
129 
163 template<class GraphType>
166  typedef const typename GraphType::data_type ordinal_type;
167 
168 private:
170  ordinal_type* colidx_;
178  const ordinal_type stride_;
179 
180 public:
188  KOKKOS_INLINE_FUNCTION
189  GraphRowViewConst ( ordinal_type* const colidx_in,
190  const ordinal_type& stride,
191  const ordinal_type& count) :
192  colidx_ (colidx_in), stride_ (stride), length (count)
193  {}
194 
207  template<class OffsetType>
208  KOKKOS_INLINE_FUNCTION
209  GraphRowViewConst ( const typename GraphType::entries_type& colidx_in,
210  const ordinal_type& stride,
211  const ordinal_type& count,
212  const OffsetType& idx,
213  const typename std::enable_if<std::is_integral<OffsetType>::value, int>::type& = 0) :
214  colidx_ (&colidx_in(idx)), stride_ (stride), length (count)
215  {}
216 
228 
234  KOKKOS_INLINE_FUNCTION
235  ordinal_type& colidx (const ordinal_type& i) const {
236  return colidx_[i*stride_];
237  }
238 
240  KOKKOS_INLINE_FUNCTION
242  return colidx(i);
243  }
244 };
245 
246 
280 template< class DataType,
281  class Arg1Type,
282  class Arg2Type = void,
283 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
284  typename SizeType = 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, Arg3Type >::size_type>
289 #endif
291 private:
293 
294 public:
295  typedef DataType data_type;
296  typedef typename traits::array_layout array_layout;
297  typedef typename traits::execution_space execution_space;
298  typedef typename traits::device_type device_type;
299  typedef typename traits::memory_traits memory_traits;
300  typedef SizeType size_type;
301 
302 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
305 #else
308 #endif
309 
313 
314  entries_type entries;
315  row_map_type row_map;
316  row_block_type row_block_offsets;
317 
319  KOKKOS_INLINE_FUNCTION
320  StaticCrsGraph () : entries(), row_map(), row_block_offsets() {}
321 
323  KOKKOS_INLINE_FUNCTION
324  StaticCrsGraph (const StaticCrsGraph& rhs) : entries (rhs.entries), row_map (rhs.row_map),
325  row_block_offsets(rhs.row_block_offsets)
326  {}
327 
328  template<class EntriesType, class RowMapType>
329  KOKKOS_INLINE_FUNCTION
330  StaticCrsGraph (const EntriesType& entries_,const RowMapType& row_map_) : entries (entries_), row_map (row_map_),
331  row_block_offsets()
332  {}
333 
338  KOKKOS_INLINE_FUNCTION
340  entries = rhs.entries;
341  row_map = rhs.row_map;
342  row_block_offsets = rhs.row_block_offsets;
343  return *this;
344  }
345 
349  KOKKOS_INLINE_FUNCTION
351 
354  KOKKOS_INLINE_FUNCTION
355  size_type numRows() const {
356  return (row_map.extent(0) != 0) ?
357  row_map.extent(0) - static_cast<size_type> (1) :
358  static_cast<size_type> (0);
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> (NULL, 1, 0);
388  } else {
389  return GraphRowViewConst<StaticCrsGraph> (entries, 1, count, start);
390  }
391  }
392 
396  void create_block_partitioning(size_type num_blocks, size_type fix_cost_per_row = 4) {
398  block_offsets("StatisCrsGraph::load_balance_offsets",num_blocks+1);
399 
400  Impl::StaticCrsGraphBalancerFunctor<row_map_type,View< size_type* , array_layout, device_type > >
401  partitioner(row_map,block_offsets,fix_cost_per_row,num_blocks);
402 
404  Kokkos::fence();
405 
406  row_block_offsets = block_offsets;
407  }
408 };
409 
410 //----------------------------------------------------------------------------
411 
412 template< class StaticCrsGraphType , class InputSizeType >
413 typename StaticCrsGraphType::staticcrsgraph_type
414 create_staticcrsgraph( const std::string & label ,
415  const std::vector< InputSizeType > & input );
416 
417 template< class StaticCrsGraphType , class InputSizeType >
418 typename StaticCrsGraphType::staticcrsgraph_type
419 create_staticcrsgraph( const std::string & label ,
420  const std::vector< std::vector< InputSizeType > > & input );
421 
422 //----------------------------------------------------------------------------
423 
424 template< class DataType ,
425  class Arg1Type ,
426  class Arg2Type ,
427 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
428  typename SizeType ,
429  class Arg3Type >
430 typename StaticCrsGraph< DataType , Arg1Type , Arg2Type , SizeType , Arg3Type >::HostMirror
431 create_mirror_view( const StaticCrsGraph<DataType,Arg1Type,Arg2Type,SizeType,Arg3Type > & input );
432 #else
433  class Arg3Type ,
434  typename SizeType >
435 typename StaticCrsGraph< DataType , Arg1Type , Arg2Type , Arg3Type , SizeType >::HostMirror
436 create_mirror_view( const StaticCrsGraph<DataType,Arg1Type,Arg2Type,Arg3Type,SizeType > & input );
437 #endif
438 
439 template< class DataType ,
440  class Arg1Type ,
441  class Arg2Type ,
442 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
443  typename SizeType ,
444  class Arg3Type >
445 typename StaticCrsGraph< DataType , Arg1Type , Arg2Type , SizeType , Arg3Type >::HostMirror
446 create_mirror_view( const StaticCrsGraph<DataType,Arg1Type,Arg2Type,SizeType,Arg3Type > & input );
447 #else
448  class Arg3Type ,
449  typename SizeType >
450 typename StaticCrsGraph< DataType , Arg1Type , Arg2Type , Arg3Type , SizeType >::HostMirror
451 create_mirror( const StaticCrsGraph<DataType,Arg1Type,Arg2Type,Arg3Type,SizeType > & input );
452 #endif
453 
454 } // namespace Kokkos
455 
456 //----------------------------------------------------------------------------
457 //----------------------------------------------------------------------------
458 
459 #include <impl/Kokkos_StaticCrsGraph_factory.hpp>
460 
461 //----------------------------------------------------------------------------
462 //----------------------------------------------------------------------------
463 
464 namespace Kokkos {
465 namespace Impl {
466 
467 template< class GraphType >
468 struct StaticCrsGraphMaximumEntry {
469 
470  typedef typename GraphType::execution_space execution_space ;
471  typedef typename GraphType::data_type value_type ;
472 
473  const typename GraphType::entries_type entries ;
474 
475  StaticCrsGraphMaximumEntry( const GraphType & graph ) : entries( graph.entries ) {}
476 
477  KOKKOS_INLINE_FUNCTION
478  void operator()( const unsigned i , value_type & update ) const
479  { if ( update < entries(i) ) update = entries(i); }
480 
481  KOKKOS_INLINE_FUNCTION
482  void init( value_type & update ) const
483  { update = 0 ; }
484 
485  KOKKOS_INLINE_FUNCTION
486  void join( volatile value_type & update ,
487  volatile const value_type & input ) const
488  { if ( update < input ) update = input ; }
489 };
490 
491 }
492 
493 #ifdef KOKKOS_ENABLE_DEPRECATED_CODE
494 template< class DataType, class Arg1Type, class Arg2Type, typename SizeType , class Arg3Type >
495 DataType maximum_entry( const StaticCrsGraph< DataType , Arg1Type , Arg2Type , SizeType , Arg3Type > & graph )
496 {
497  typedef StaticCrsGraph<DataType,Arg1Type,Arg2Type,SizeType,Arg3Type> GraphType ;
498 #else
499 template< class DataType, class Arg1Type, class Arg2Type, class Arg3Type, typename SizeType >
500 DataType maximum_entry( const StaticCrsGraph< DataType , Arg1Type , Arg2Type , Arg3Type , SizeType > & graph )
501 {
502  typedef StaticCrsGraph<DataType,Arg1Type,Arg2Type,Arg3Type,SizeType> GraphType ;
503 #endif
504  typedef Impl::StaticCrsGraphMaximumEntry< GraphType > FunctorType ;
505 
506  DataType result = 0 ;
507  Kokkos::parallel_reduce( graph.entries.extent(0),
508  FunctorType(graph), result );
509  return result ;
510 }
511 
512 } // namespace Kokkos
513 
514 //----------------------------------------------------------------------------
515 //----------------------------------------------------------------------------
516 
517 #endif /* #ifndef KOKKOS_CRSARRAY_HPP */
518 
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).
void parallel_for(const ExecPolicy &policy, const FunctorType &functor, const std::string &str="", typename Impl::enable_if< Kokkos::Impl::is_execution_policy< ExecPolicy >::value >::type *=0)
Execute functor in parallel according to the execution policy.
void parallel_reduce(const std::string &label, const PolicyType &policy, const FunctorType &functor, ReturnType &return_value, typename Impl::enable_if< Kokkos::Impl::is_execution_policy< PolicyType >::value >::type *=0)
Parallel reduction.
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.
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.
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.
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...
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 ~StaticCrsGraph()
Destroy this view of the array. If the last view then allocated memory is deallocated.