Tpetra parallel linear algebra  Version of the Day
Tpetra_Details_FixedHashTable_decl.hpp
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_FIXEDHASHTABLE_DECL_HPP
45 #define TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
46 
47 #include <Tpetra_Details_Hash.hpp>
49 #include <Teuchos_Describable.hpp>
50 #include <Kokkos_Core.hpp>
51 
52 namespace Tpetra {
53 namespace Details {
54 
55 //
56 // Implementation details for FixedHashTable (see below).
57 // Users should skip over this anonymous namespace.
58 //
59 namespace { // (anonymous)
60 
61  // Overflow is impossible (the output can fit the input) if the
62  // output type is bigger than the input type, or if the types have
63  // the same size and (the output type is unsigned, or both types are
64  // signed).
65  //
66  // Implicit here is the assumption that both input and output types
67  // are integers.
68  template<class T1, class T2,
69  const bool T1_is_signed = std::is_signed<T1>::value,
70  const bool T2_is_signed = std::is_signed<T2>::value>
71  struct OutputCanFitInput {
72  static const bool value = sizeof (T1) > sizeof (T2) ||
73  (sizeof (T1) == sizeof (T2) &&
74  (std::is_unsigned<T1>::value || (std::is_signed<T1>::value && std::is_signed<T2>::value)));
75  };
76 
77  // Kokkos parallel_reduce functor for copying offset ("ptr") arrays.
78  // Tpetra::Details::FixedHashTable uses this in its "copy"
79  // constructor for converting between different Device types. All
80  // the action happens in the partial specializations for different
81  // values of outputCanFitInput.
82  template<class OutputViewType, class InputViewType,
83  const bool outputCanFitInput = OutputCanFitInput<typename OutputViewType::non_const_value_type,
84  typename InputViewType::non_const_value_type>::value>
85  class CopyOffsets {};
86 
87  // Specialization for when overflow is possible.
88  template<class OutputViewType, class InputViewType>
89  class CopyOffsets<OutputViewType, InputViewType, false> {
90  public:
91  typedef typename OutputViewType::execution_space execution_space;
92  typedef typename OutputViewType::size_type size_type;
93  typedef bool value_type;
94 
95  typedef typename InputViewType::non_const_value_type input_value_type;
96  typedef typename OutputViewType::non_const_value_type output_value_type;
97 
98  CopyOffsets (const OutputViewType& dst, const InputViewType& src) :
99  dst_ (dst),
100  src_ (src),
101  // We know that output_value_type cannot fit all values of
102  // input_value_type, so an input_value_type can fit all values
103  // of output_value_type. This means we can convert from
104  // output_value_type to input_value_type. This is how we test
105  // whether a given input_value_type value can fit in an
106  // output_value_type.
107  minDstVal_ (static_cast<input_value_type> (std::numeric_limits<output_value_type>::min ())),
108  maxDstVal_ (static_cast<input_value_type> (std::numeric_limits<output_value_type>::max ()))
109  {}
110 
111  KOKKOS_INLINE_FUNCTION void
112  operator () (const size_type& i, value_type& noOverflow) const {
113  const input_value_type src_i = src_(i);
114  if (src_i < minDstVal_ || src_i > maxDstVal_) {
115  noOverflow = false;
116  }
117  dst_(i) = static_cast<output_value_type> (src_i);
118  }
119 
120  KOKKOS_INLINE_FUNCTION void init (value_type& noOverflow) const {
121  noOverflow = true; // success (no overflow)
122  }
123 
124  KOKKOS_INLINE_FUNCTION void
125  join (volatile value_type& result,
126  const volatile value_type& current) const {
127  result = result && current; // was there any overflow?
128  }
129 
130  private:
131  OutputViewType dst_;
132  InputViewType src_;
133  input_value_type minDstVal_;
134  input_value_type maxDstVal_;
135  };
136 
137  // Specialization for when overflow is impossible.
138  template<class OutputViewType, class InputViewType>
139  class CopyOffsets<OutputViewType, InputViewType, true> {
140  public:
141  typedef typename OutputViewType::execution_space execution_space;
142  typedef typename OutputViewType::size_type size_type;
143  typedef bool value_type;
144 
145  CopyOffsets (const OutputViewType& dst, const InputViewType& src) :
146  dst_ (dst),
147  src_ (src)
148  {}
149 
150  KOKKOS_INLINE_FUNCTION void
151  operator () (const size_type& i, value_type& /* noOverflow */) const {
152  // Overflow is impossible in this case, so there's no need to check.
153  dst_(i) = src_(i);
154  }
155 
156  KOKKOS_INLINE_FUNCTION void init (value_type& noOverflow) const {
157  noOverflow = true; // success (no overflow)
158  }
159 
160  KOKKOS_INLINE_FUNCTION void
161  join (volatile value_type& result,
162  const volatile value_type& current) const {
163  result = result && current; // was there any overflow?
164  }
165 
166  private:
167  OutputViewType dst_;
168  InputViewType src_;
169  };
170 
171  template<class OutputViewType, class InputViewType>
172  void copyOffsets (const OutputViewType& dst, const InputViewType& src) {
173  TEUCHOS_TEST_FOR_EXCEPTION
174  (dst.dimension_0 () != src.dimension_0 (), std::invalid_argument,
175  "copyOffsets: dst.dimension_0() = " << dst.dimension_0 ()
176  << " != src.dimension_0() = " << src.dimension_0 () << ".");
177  typedef CopyOffsets<OutputViewType, InputViewType> functor_type;
178  bool noOverflow = false;
179  Kokkos::parallel_reduce (dst.dimension_0 (), functor_type (dst, src), noOverflow);
180  TEUCHOS_TEST_FOR_EXCEPTION
181  (! noOverflow, std::runtime_error, "copyOffsets: One or more values in "
182  "src were too big (in the sense of integer overflow) to fit in dst.");
183  }
184 
185 } // namespace (anonymous)
186 
212 template<class KeyType,
213  class ValueType,
214  class DeviceType>
215 class FixedHashTable : public Teuchos::Describable {
216 private:
217  typedef typename DeviceType::execution_space execution_space;
218  typedef typename DeviceType::memory_space memory_space;
219  typedef Kokkos::Device<execution_space, memory_space> device_type;
220 
222  typedef typename hash_type::offset_type offset_type;
223 
231  typedef typename Kokkos::View<const offset_type*, Kokkos::LayoutLeft,
232  device_type> ptr_type;
239  typedef typename Kokkos::View<const Kokkos::pair<KeyType, ValueType>*,
240  Kokkos::LayoutLeft, device_type> val_type;
241 
248  KOKKOS_INLINE_FUNCTION bool hasContiguousValues () const {
249  return contiguousValues_;
250  }
251 
252 public:
256  typedef Kokkos::View<const KeyType*, Kokkos::LayoutLeft, device_type> keys_type;
257 
259  FixedHashTable ();
260 
270  FixedHashTable (const keys_type& keys);
271 
282  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
283  const bool keepKeys = false);
284 
298  FixedHashTable (const keys_type& keys,
299  const ValueType startingValue);
300 
315  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
316  const ValueType startingValue,
317  const bool keepKeys = false);
318 
336  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
337  const KeyType firstContigKey,
338  const KeyType lastContigKey,
339  const ValueType startingValue,
340  const bool keepKeys = false);
341 
353  FixedHashTable (const Teuchos::ArrayView<const KeyType>& keys,
354  const Teuchos::ArrayView<const ValueType>& vals);
355 
356  template<class K, class V, class D>
357  friend class FixedHashTable;
358 
364  template<class InDeviceType>
366  typename std::enable_if<! std::is_same<DeviceType, InDeviceType>::value, int>::type* = NULL)
367  {
368  using Kokkos::ViewAllocateWithoutInitializing;
369  typedef typename ptr_type::non_const_type nonconst_ptr_type;
370  typedef typename val_type::non_const_type nonconst_val_type;
371 
372  // FIXME (mfh 28 May 2015) The code below _always_ copies. This
373  // shouldn't be necessary if the input and output memory spaces
374  // are the same. However, it is always correct.
375 
376  // Different Devices may have different offset_type, because
377  // offset_type comes from the memory space's size_type typedef.
378  // That's why we use a specialized deep copy function here instead
379  // of Kokkos::deep_copy.
380  nonconst_ptr_type ptr (ViewAllocateWithoutInitializing ("ptr"),
381  src.ptr_.dimension_0 ());
382  copyOffsets (ptr, src.ptr_);
383  nonconst_val_type val (ViewAllocateWithoutInitializing ("val"),
384  src.val_.dimension_0 ());
385  // val and src.val_ have the same entry types, unlike (possibly)
386  // ptr and src.ptr_. Thus, we can use Kokkos::deep_copy here.
387  Kokkos::deep_copy (val, src.val_);
388 
389  this->ptr_ = ptr;
390  this->val_ = val;
391  this->minKey_ = src.minKey_;
392  this->maxKey_ = src.maxKey_;
393  this->minVal_ = src.minVal_;
394  this->maxVal_ = src.maxVal_;
395  this->firstContigKey_ = src.firstContigKey_;
396  this->lastContigKey_ = src.lastContigKey_;
397  this->contiguousValues_ = src.contiguousValues_;
398  this->checkedForDuplicateKeys_ = src.checkedForDuplicateKeys_;
399  this->hasDuplicateKeys_ = src.hasDuplicateKeys_;
400 
401 #if defined(HAVE_TPETRA_DEBUG)
402  this->check ();
403 #endif // defined(HAVE_TPETRA_DEBUG)
404  }
405 
407  KOKKOS_INLINE_FUNCTION ValueType get (const KeyType& key) const {
408  const offset_type size = this->getSize ();
409  if (size == 0) {
410  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
411  // because neither have the right device function markings.
413  }
414 
415  // If this object assumes contiguous values, then it doesn't store
416  // the initial sequence of >= 1 contiguous keys in the table.
417  if (this->hasContiguousValues () &&
418  key >= firstContigKey_ && key <= lastContigKey_) {
419  return static_cast<ValueType> (key - firstContigKey_) + this->minVal ();
420  }
421 
422  const typename hash_type::result_type hashVal =
423  hash_type::hashFunc (key, size);
424 
425  const offset_type start = ptr_[hashVal];
426  const offset_type end = ptr_[hashVal+1];
427  for (offset_type k = start; k < end; ++k) {
428  if (val_[k].first == key) {
429  return val_[k].second;
430  }
431  }
432 
433  // Don't use Teuchos::OrdinalTraits or std::numeric_limits here,
434  // because neither have the right device function markings.
436  }
437 
443  bool hasKeys () const;
444 
451  KOKKOS_INLINE_FUNCTION KeyType getKey (const ValueType& val) const {
452  // If there are no keys in the table, then we set minVal_ to the
453  // the max possible ValueType value and maxVal_ to the min
454  // possible ValueType value. Thus, this is always true.
455  if (val < this->minVal () || val > this->maxVal ()) {
457  }
458  else {
459  const ValueType index = val - this->minVal ();
460  return keys_[index];
461  }
462  }
463 
467  KOKKOS_INLINE_FUNCTION offset_type numPairs () const {
468  // NOTE (mfh 26 May 2015) Using val_.dimension_0() only works
469  // because the table stores pairs with duplicate keys separately.
470  // If the table didn't do that, we would have to keep a separate
471  // numPairs_ field (remembering the size of the input array of
472  // keys).
473  if (this->hasContiguousValues ()) {
474  return val_.dimension_0 () + static_cast<offset_type> (lastContigKey_ - firstContigKey_);
475  }
476  else {
477  return val_.dimension_0 ();
478  }
479  }
480 
489  KOKKOS_INLINE_FUNCTION KeyType minKey () const {
490  return minKey_;
491  }
492 
501  KOKKOS_INLINE_FUNCTION KeyType maxKey () const {
502  return maxKey_;
503  }
504 
512  KOKKOS_INLINE_FUNCTION ValueType minVal () const {
513  return minVal_;
514  }
515 
523  KOKKOS_INLINE_FUNCTION ValueType maxVal () const {
524  return maxVal_;
525  }
526 
539  bool hasDuplicateKeys ();
540 
542 
543  std::string description () const;
545 
547  void
548  describe (Teuchos::FancyOStream &out,
549  const Teuchos::EVerbosityLevel verbLevel=
550  Teuchos::Describable::verbLevel_default) const;
552 
553 private:
563  keys_type keys_;
565  ptr_type ptr_;
567  val_type val_;
568 
573  KeyType minKey_;
574 
579  KeyType maxKey_;
580 
585  ValueType minVal_;
586 
591  ValueType maxVal_;
592 
599  KeyType firstContigKey_;
600 
607  KeyType lastContigKey_;
608 
615  bool contiguousValues_;
616 
622  bool checkedForDuplicateKeys_;
623 
627  bool hasDuplicateKeys_;
628 
633  bool checkForDuplicateKeys () const;
634 
636  KOKKOS_INLINE_FUNCTION offset_type getSize () const {
637  return ptr_.dimension_0 () == 0 ?
638  static_cast<offset_type> (0) :
639  static_cast<offset_type> (ptr_.dimension_0 () - 1);
640  }
641 
643  void check () const;
644 
645  typedef Kokkos::View<const KeyType*,
646  typename ptr_type::HostMirror::array_layout,
647  typename ptr_type::HostMirror::execution_space,
648  Kokkos::MemoryUnmanaged> host_input_keys_type;
649 
650  typedef Kokkos::View<const ValueType*,
651  typename ptr_type::HostMirror::array_layout,
652  typename ptr_type::HostMirror::execution_space,
653  Kokkos::MemoryUnmanaged> host_input_vals_type;
654 
661  void
662  init (const keys_type& keys,
663  const ValueType startingValue,
664  KeyType initMinKey,
665  KeyType initMaxKey,
666  KeyType firstContigKey,
667  KeyType lastContigKey,
668  const bool computeInitContigKeys);
669 
676  void
677  init (const host_input_keys_type& keys,
678  const host_input_vals_type& vals,
679  KeyType initMinKey,
680  KeyType initMaxKey);
681 };
682 
683 } // Details namespace
684 } // Tpetra namespace
685 
686 #endif // TPETRA_DETAILS_FIXEDHASHTABLE_DECL_HPP
Namespace Tpetra contains the class and methods constituting the Tpetra library.
Traits class for "invalid" (flag) values of integer types that Tpetra uses as local ordinals or globa...
KOKKOS_INLINE_FUNCTION KeyType getKey(const ValueType &val) const
Get the key corresponding to the given value.
KOKKOS_INLINE_FUNCTION ValueType minVal() const
The minimum value in the table.
ResultType result_type
Type of the return value of the hash function.
void deep_copy(const LittleBlock< ST2, LO > &dst, const LittleBlock< ST1, LO > &src, typename std::enable_if< std::is_convertible< ST1, ST2 >::value &&!std::is_const< ST2 >::value, int >::type *=NULL)
Copy the LittleBlock src into the LittleBlock dst.
Implementation details of Tpetra.
KOKKOS_INLINE_FUNCTION KeyType minKey() const
The minimum key in the table.
Traits class for "invalid" (flag) values of integer types that Tpetra uses as local ordinals or globa...
The hash function for FixedHashTable.
KOKKOS_INLINE_FUNCTION offset_type numPairs() const
Number of (key, value) pairs in the table.
FixedHashTable(const FixedHashTable< KeyType, ValueType, InDeviceType > &src, typename std::enable_if<!std::is_same< DeviceType, InDeviceType >::value, int >::type *=NULL)
"Copy" constructor that takes a FixedHashTable with the same KeyType and ValueType, but a different DeviceType.
KOKKOS_INLINE_FUNCTION KeyType maxKey() const
The maximum key in the table.
OffsetType offset_type
Type of offsets into the hash table&#39;s array of (key,value) pairs.
KOKKOS_INLINE_FUNCTION ValueType maxVal() const
The maximum value in the table.
Kokkos::View< const KeyType *, Kokkos::LayoutLeft, device_type > keys_type
Type of a 1-D Kokkos::View (array) used to store keys.