Tpetra parallel linear algebra  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Tpetra_Details_computeOffsets.hpp
Go to the documentation of this file.
1 /*
2 // @HEADER
3 // ***********************************************************************
4 //
5 // Tpetra: Templated Linear Algebra Services Package
6 // Copyright (2008) 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 Michael A. Heroux (maherou@sandia.gov)
39 //
40 // ************************************************************************
41 // @HEADER
42 */
43 
44 #ifndef TPETRA_DETAILS_COMPUTEOFFSETS_HPP
45 #define TPETRA_DETAILS_COMPUTEOFFSETS_HPP
46 
52 
53 #include "TpetraCore_config.h"
55 #include <limits>
56 #include <type_traits>
57 
58 namespace Tpetra {
59 namespace Details {
60 
61 //
62 // Implementation details for computeOffsetsFromCounts (see below).
63 // Users should skip over this anonymous namespace.
64 //
65 namespace { // (anonymous)
66 
84 template<class OffsetsViewType,
85  class CountsViewType,
86  class SizeType = typename OffsetsViewType::size_type>
87 class ComputeOffsetsFromCounts {
88 public:
89  static_assert (Kokkos::Impl::is_view<OffsetsViewType>::value,
90  "OffsetsViewType (the type of ptr) must be a Kokkos::View.");
91  static_assert (Kokkos::Impl::is_view<CountsViewType>::value,
92  "CountsViewType (the type of counts) must be a Kokkos::View.");
93  static_assert (std::is_same<typename OffsetsViewType::value_type,
94  typename OffsetsViewType::non_const_value_type>::value,
95  "OffsetsViewType (the type of ptr) must be a nonconst Kokkos::View.");
96  static_assert (static_cast<int> (OffsetsViewType::rank) == 1,
97  "OffsetsViewType (the type of ptr) must be a rank-1 Kokkos::View.");
98  static_assert (static_cast<int> (CountsViewType::rank) == 1,
99  "CountsViewType (the type of counts) must be a rank-1 Kokkos::View.");
100  static_assert (std::is_integral<typename OffsetsViewType::non_const_value_type>::value,
101  "The entries of ptr must be built-in integers.");
102  static_assert (std::is_integral<typename CountsViewType::non_const_value_type>::value,
103  "The entries of counts must be built-in integers.");
104  static_assert (std::is_integral<SizeType>::value,
105  "SizeType must be a built-in integer type.");
106 
107  typedef OffsetsViewType offsets_view_type;
108  typedef typename CountsViewType::const_type counts_view_type;
109  typedef SizeType size_type;
110  typedef typename OffsetsViewType::non_const_value_type value_type;
111 
117  ComputeOffsetsFromCounts (const offsets_view_type& offsets,
118  const counts_view_type& counts) :
119  offsets_ (offsets),
120  counts_ (counts),
121  size_ (counts.extent (0))
122  {}
123 
125  KOKKOS_INLINE_FUNCTION void init (value_type& dst) const
126  {
127  dst = 0;
128  }
129 
131  KOKKOS_INLINE_FUNCTION void
132  join (volatile value_type& dst,
133  const volatile value_type& src) const
134  {
135  dst += src;
136  }
137 
139  KOKKOS_INLINE_FUNCTION void
140  operator () (const size_type& i, value_type& update, const bool final) const
141  {
142  const auto curVal = (i < size_) ? counts_[i] : value_type ();
143  if (final) {
144  offsets_[i] = update;
145  }
146  update += (i < size_) ? curVal : value_type ();
147 
148  // if (final) {
149  // offsets_[i] = update;
150  // }
151  // if (i < size_) {
152  // update += counts_[i];
153  // }
154  }
155 
156 private:
158  offsets_view_type offsets_;
160  counts_view_type counts_;
162  size_type size_;
163 };
164 
182 template<class OffsetsViewType,
183  class CountType,
184  class SizeType = typename OffsetsViewType::size_type>
185 class ComputeOffsetsFromConstantCount {
186 public:
187  static_assert (Kokkos::Impl::is_view<OffsetsViewType>::value,
188  "OffsetsViewType (the type of ptr) must be a Kokkos::View.");
189  static_assert (std::is_same<typename OffsetsViewType::value_type,
190  typename OffsetsViewType::non_const_value_type>::value,
191  "OffsetsViewType (the type of ptr) must be a nonconst Kokkos::View.");
192  static_assert (static_cast<int> (OffsetsViewType::rank) == 1,
193  "OffsetsViewType (the type of ptr) must be a rank-1 Kokkos::View.");
194  static_assert (std::is_integral<typename OffsetsViewType::non_const_value_type>::value,
195  "The entries of ptr must be built-in integers.");
196  static_assert (std::is_integral<CountType>::value,
197  "CountType must be a built-in integer type.");
198  static_assert (std::is_integral<SizeType>::value,
199  "SizeType must be a built-in integer type.");
200 
201  typedef OffsetsViewType offsets_view_type;
202  typedef CountType count_type;
203  typedef SizeType size_type;
204  typedef typename offsets_view_type::non_const_value_type value_type;
205 
211  ComputeOffsetsFromConstantCount (const offsets_view_type& offsets,
212  const count_type count) :
213  offsets_ (offsets),
214  count_ (count),
215  size_ (offsets_.extent (0) == 0 ?
216  static_cast<size_type> (0) :
217  static_cast<size_type> (offsets_.extent (0) - 1))
218  {}
219 
221  KOKKOS_INLINE_FUNCTION void init (value_type& dst) const
222  {
223  dst = 0;
224  }
225 
227  KOKKOS_INLINE_FUNCTION void
228  join (volatile value_type& dst,
229  const volatile value_type& src) const
230  {
231  dst += src;
232  }
233 
235  KOKKOS_INLINE_FUNCTION void
236  operator () (const size_type& i, value_type& update, const bool final) const
237  {
238  if (final) {
239  offsets_[i] = update;
240  }
241  if (i < size_) {
242  update += count_;
243  }
244  }
245 
246 private:
248  offsets_view_type offsets_;
250  count_type count_;
252  size_type size_;
253 };
254 
255 } // namespace (anonymous)
256 
280 template<class OffsetsViewType,
281  class CountsViewType,
282  class SizeType = typename OffsetsViewType::size_type>
283 typename OffsetsViewType::non_const_value_type
284 computeOffsetsFromCounts (const OffsetsViewType& ptr,
285  const CountsViewType& counts)
286 {
287  static_assert (Kokkos::Impl::is_view<OffsetsViewType>::value,
288  "OffsetsViewType (the type of ptr) must be a Kokkos::View.");
289  static_assert (Kokkos::Impl::is_view<CountsViewType>::value,
290  "CountsViewType (the type of counts) must be a Kokkos::View.");
291  static_assert (std::is_same<typename OffsetsViewType::value_type,
292  typename OffsetsViewType::non_const_value_type>::value,
293  "OffsetsViewType (the type of ptr) must be a nonconst Kokkos::View.");
294  static_assert (static_cast<int> (OffsetsViewType::rank) == 1,
295  "OffsetsViewType (the type of ptr) must be a rank-1 Kokkos::View.");
296  static_assert (static_cast<int> (CountsViewType::rank) == 1,
297  "CountsViewType (the type of counts) must be a rank-1 Kokkos::View.");
298  static_assert (std::is_integral<typename OffsetsViewType::non_const_value_type>::value,
299  "The entries of ptr must be built-in integers.");
300  static_assert (std::is_integral<typename CountsViewType::non_const_value_type>::value,
301  "The entries of counts must be built-in integers.");
302  static_assert (std::is_integral<SizeType>::value,
303  "SizeType must be a built-in integer type.");
304 
305  typedef typename CountsViewType::non_const_value_type count_type;
306  typedef typename OffsetsViewType::non_const_value_type offset_type;
307  typedef typename OffsetsViewType::device_type device_type;
308  typedef typename device_type::execution_space execution_space;
309  typedef typename device_type::memory_space memory_space;
310 
311  const auto numOffsets = ptr.size ();
312  const auto numCounts = counts.size ();
313  if (numOffsets != 0) {
314  TEUCHOS_TEST_FOR_EXCEPTION
315  (numCounts >= numOffsets, std::invalid_argument,
316  "Tpetra::Details::computeOffsetsFromCounts: "
317  "counts.extent(0) = " << numCounts
318  << " >= ptr.extent(0) = " << numOffsets << ".");
319 
320  Kokkos::RangePolicy<execution_space, SizeType> range (0, numCounts+1);
321  try {
322  // We always want to run in the offsets' execution space, since
323  // that is the output argument. (This gives us first touch, if
324  // applicable, and in general improves locality.) However, we
325  // need to make sure that we can access counts from this
326  // execution space. If we can't, we need to make a temporary
327  // "device" copy of counts in offsets' memory space.
328 
329  // The first template parameter needs to be a memory space.
330  constexpr bool countsAccessibleFromOffsets =
331  Kokkos::Impl::VerifyExecutionCanAccessMemorySpace<memory_space,
332  typename CountsViewType::memory_space>::value;
333  if (countsAccessibleFromOffsets) {
334 #ifdef KOKKOS_ENABLE_CUDA
335  // If 'counts' is a UVM allocation, then conservatively fence
336  // first, in case it was last accessed on host. We're about
337  // to access it on device.
338  using counts_memory_space = typename CountsViewType::memory_space;
339  if (std::is_same<counts_memory_space, Kokkos::CudaUVMSpace>::value) {
340  using counts_exec_space = typename counts_memory_space::execution_space;
341  counts_exec_space::fence (); // for UVM's sake.
342  }
343 #endif // KOKKOS_ENABLE_CUDA
344  typedef ComputeOffsetsFromCounts<OffsetsViewType, CountsViewType,
345  SizeType> functor_type;
346  // offsets' execution space can access counts
347  functor_type functor (ptr, counts);
348  Kokkos::parallel_scan (range, functor);
349  }
350  else {
351  // Make a temporary copy of counts in offsets' execution
352  // space. Use the same array layout as the original, so we
353  // can deep copy.
354  typedef Kokkos::View<count_type*, typename CountsViewType::array_layout,
355  device_type> dev_counts_type;
356  dev_counts_type counts_d ("counts_d", numCounts);
357  Kokkos::deep_copy (counts_d, counts);
358 
359  typedef ComputeOffsetsFromCounts<OffsetsViewType, dev_counts_type,
360  SizeType> functor_type;
361  functor_type functor (ptr, counts_d);
362  Kokkos::parallel_scan (range, functor);
363  }
364  }
365  catch (std::exception& e) {
366  TEUCHOS_TEST_FOR_EXCEPTION
367  (true, std::runtime_error,
368  "Tpetra::Details::computeOffsetsFromCounts: "
369  "Kokkos::parallel_scan (with device_type Kokkos::Device<"
370  << typeid (execution_space).name () << ", "
371  << typeid (memory_space).name () << ">) threw an std::exception: "
372  << e.what ());
373  }
374  catch (...) {
375  TEUCHOS_TEST_FOR_EXCEPTION
376  (true, std::runtime_error,
377  "Tpetra::Details::computeOffsetsFromCounts: "
378  "Kokkos::parallel_scan threw an exception "
379  "not a subclass of std::exception");
380  }
381  // Get the sum of all entries of counts from the last entry of ptr.
382  return ::Tpetra::Details::getEntryOnHost (ptr, numCounts);
383  }
384  else {
385  return static_cast<offset_type> (0);
386  }
387 }
388 
411 template<class OffsetsViewType,
412  class CountType,
413  class SizeType = typename OffsetsViewType::size_type>
414 typename OffsetsViewType::non_const_value_type
415 computeOffsetsFromConstantCount (const OffsetsViewType& ptr,
416  const CountType& count)
417 {
418  static_assert (Kokkos::Impl::is_view<OffsetsViewType>::value,
419  "OffsetsViewType (the type of ptr) must be a Kokkos::View.");
420  static_assert (std::is_same<typename OffsetsViewType::value_type,
421  typename OffsetsViewType::non_const_value_type>::value,
422  "OffsetsViewType (the type of ptr) must be a nonconst Kokkos::View.");
423  static_assert (static_cast<int> (OffsetsViewType::rank) == 1,
424  "OffsetsViewType (the type of ptr) must be a rank-1 Kokkos::View.");
425  static_assert (std::is_integral<typename OffsetsViewType::non_const_value_type>::value,
426  "The entries of ptr must be built-in integers.");
427  static_assert (std::is_integral<CountType>::value,
428  "CountType must be a built-in integer type.");
429  static_assert (std::is_integral<SizeType>::value,
430  "SizeType must be a built-in integer type.");
431 
432  typedef typename std::decay<CountType>::type count_type;
433  typedef typename OffsetsViewType::non_const_value_type offset_type;
434  typedef typename OffsetsViewType::device_type device_type;
435  typedef typename device_type::execution_space execution_space;
436  typedef typename device_type::memory_space memory_space;
437 
438  const auto numOffsets = ptr.size ();
439  if (numOffsets != 0) {
440  ComputeOffsetsFromConstantCount<OffsetsViewType, count_type,
441  SizeType> functor (ptr, count);
442  Kokkos::RangePolicy<execution_space, SizeType> range (0, numOffsets);
443  try {
444  Kokkos::parallel_scan (range, functor);
445  }
446  catch (std::exception& e) {
447  TEUCHOS_TEST_FOR_EXCEPTION
448  (true, std::runtime_error, "computeOffsetsFromConstantCount: "
449  "parallel_scan (with device_type Kokkos::Device<" <<
450  typeid (execution_space).name () << ", " <<
451  typeid (memory_space).name () << ">) threw an std::exception: "
452  << e.what ());
453  }
454  catch (...) {
455  TEUCHOS_TEST_FOR_EXCEPTION
456  (true, std::runtime_error, "Kokkos::parallel_scan threw an "
457  "exception not a subclass of std::exception");
458  }
459  // Get the sum from the last entry of ptr.
460  return ::Tpetra::Details::getEntryOnHost (ptr, numOffsets - 1);
461  }
462  else {
463  return static_cast<offset_type> (0);
464  }
465 }
466 
467 } // namespace Details
468 } // namespace Tpetra
469 
470 #endif // TPETRA_DETAILS_COMPUTEOFFSETS_HPP
counts_view_type counts_
Bucket counts (input argument).
offsets_view_type offsets_
Offsets (output argument)
void deep_copy(MultiVector< DS, DL, DG, DN > &dst, const MultiVector< SS, SL, SG, SN > &src)
Copy the contents of the MultiVector src into dst.
OffsetsViewType::non_const_value_type computeOffsetsFromCounts(const OffsetsViewType &ptr, const CountsViewType &counts)
Compute offsets from counts.
OffsetsViewType::non_const_value_type computeOffsetsFromConstantCount(const OffsetsViewType &ptr, const CountType &count)
Compute offsets from a constant count.
size_type size_
Number of entries in counts_.
Declaration and definition of Tpetra::Details::getEntryOnHost.
count_type count_
&quot;Count&quot; input argument