← Back to branch summary

~ubuntu-branches/debian/sid/lammps/sid

« back to all changes in this revision

Viewing changes to lib/kokkos/containers/src/impl/Kokkos_UnorderedMap_impl.hpp

  • Committer: Package Import Robot
  • Author(s): Anton Gladky
  • Date: 2015-04-29 23:44:49 UTC
  • mfrom: (5.1.3 experimental)
  • Revision ID: package-import@ubuntu.com-20150429234449-mbhy9utku6hp6oq8
Tags: 0~20150313.gitfa668e1-1
Upload into unstable.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/kokkos/containers/src/impl/Kokkos_UnorderedMap_impl.hpp
 
1
/*
 
2
//@HEADER
 
3
// ************************************************************************
 
4
//
 
5
//   Kokkos: Manycore Performance-Portable Multidimensional Arrays
 
6
//              Copyright (2012) 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  H. Carter Edwards (hcedwar@sandia.gov)
 
39
//
 
40
// ************************************************************************
 
41
//@HEADER
 
42
*/
 
43
 
 
44
#ifndef KOKKOS_UNORDERED_MAP_IMPL_HPP
 
45
#define KOKKOS_UNORDERED_MAP_IMPL_HPP
 
46
 
 
47
#include <Kokkos_Core_fwd.hpp>
 
48
#include <stdint.h>
 
49
 
 
50
#include <cstdio>
 
51
#include <climits>
 
52
#include <iostream>
 
53
#include <iomanip>
 
54
 
 
55
namespace Kokkos { namespace Impl {
 
56
 
 
57
uint32_t find_hash_size( uint32_t size );
 
58
 
 
59
template <typename Map>
 
60
struct UnorderedMapRehash
 
61
{
 
62
  typedef Map map_type;
 
63
  typedef typename map_type::const_map_type const_map_type;
 
64
  typedef typename map_type::device_type device_type;
 
65
  typedef typename map_type::size_type size_type;
 
66
 
 
67
  map_type       m_dst;
 
68
  const_map_type m_src;
 
69
 
 
70
  UnorderedMapRehash( map_type const& dst, const_map_type const& src)
 
71
    : m_dst(dst), m_src(src)
 
72
  {}
 
73
 
 
74
  void apply() const
 
75
  {
 
76
    parallel_for(m_src.capacity(), *this);
 
77
  }
 
78
 
 
79
  KOKKOS_INLINE_FUNCTION
 
80
  void operator()(size_type i) const
 
81
  {
 
82
    if ( m_src.valid_at(i) )
 
83
      m_dst.insert(m_src.key_at(i), m_src.value_at(i));
 
84
  }
 
85
 
 
86
};
 
87
 
 
88
template <typename UMap>
 
89
struct UnorderedMapErase
 
90
{
 
91
  typedef UMap map_type;
 
92
  typedef typename map_type::device_type device_type;
 
93
  typedef typename map_type::size_type size_type;
 
94
  typedef typename map_type::key_type key_type;
 
95
  typedef typename map_type::impl_value_type value_type;
 
96
 
 
97
  map_type m_map;
 
98
 
 
99
  UnorderedMapErase( map_type const& map)
 
100
    : m_map(map)
 
101
  {}
 
102
 
 
103
  void apply() const
 
104
  {
 
105
    parallel_for(m_map.m_hash_lists.size(), *this);
 
106
  }
 
107
 
 
108
  KOKKOS_INLINE_FUNCTION
 
109
  void operator()( size_type i ) const
 
110
  {
 
111
    const size_type invalid_index = map_type::invalid_index;
 
112
 
 
113
    size_type curr = m_map.m_hash_lists(i);
 
114
    size_type next = invalid_index;
 
115
 
 
116
    // remove erased head of the linked-list
 
117
    while (curr != invalid_index && !m_map.valid_at(curr)) {
 
118
      next = m_map.m_next_index[curr];
 
119
      m_map.m_next_index[curr] = invalid_index;
 
120
      m_map.m_keys[curr] = key_type();
 
121
      if (m_map.is_set) m_map.m_values[curr] = value_type();
 
122
      curr = next;
 
123
      m_map.m_hash_lists(i) = next;
 
124
    }
 
125
 
 
126
    // if the list is non-empty and the head is valid
 
127
    if (curr != invalid_index && m_map.valid_at(curr) ) {
 
128
      size_type prev = curr;
 
129
      curr = m_map.m_next_index[prev];
 
130
 
 
131
      while (curr != invalid_index) {
 
132
        next = m_map.m_next_index[curr];
 
133
        if (m_map.valid_at(curr)) {
 
134
          prev = curr;
 
135
        }
 
136
        else {
 
137
          // remove curr from list
 
138
          m_map.m_next_index[prev] = next;
 
139
          m_map.m_next_index[curr] = invalid_index;
 
140
          m_map.m_keys[curr] = key_type();
 
141
          if (map_type::is_set) m_map.m_values[curr] = value_type();
 
142
        }
 
143
        curr = next;
 
144
      }
 
145
    }
 
146
  }
 
147
};
 
148
 
 
149
template <typename UMap>
 
150
struct UnorderedMapHistogram
 
151
{
 
152
  typedef UMap map_type;
 
153
  typedef typename map_type::device_type device_type;
 
154
  typedef typename map_type::size_type size_type;
 
155
 
 
156
  typedef View<int[100], device_type> histogram_view;
 
157
  typedef typename histogram_view::HostMirror host_histogram_view;
 
158
 
 
159
  map_type m_map;
 
160
  histogram_view m_length;
 
161
  histogram_view m_distance;
 
162
  histogram_view m_block_distance;
 
163
 
 
164
  UnorderedMapHistogram( map_type const& map)
 
165
    : m_map(map)
 
166
    , m_length("UnorderedMap Histogram")
 
167
    , m_distance("UnorderedMap Histogram")
 
168
    , m_block_distance("UnorderedMap Histogram")
 
169
  {}
 
170
 
 
171
  void calculate()
 
172
  {
 
173
    parallel_for(m_map.m_hash_lists.size(), *this);
 
174
  }
 
175
 
 
176
  void clear()
 
177
  {
 
178
    Kokkos::deep_copy(m_length, 0);
 
179
    Kokkos::deep_copy(m_distance, 0);
 
180
    Kokkos::deep_copy(m_block_distance, 0);
 
181
  }
 
182
 
 
183
  void print_length(std::ostream &out)
 
184
  {
 
185
    host_histogram_view host_copy = create_mirror_view(m_length);
 
186
    Kokkos::deep_copy(host_copy, m_length);
 
187
 
 
188
    for (int i=0, size = host_copy.size(); i<size; ++i)
 
189
    {
 
190
      out << host_copy[i] << " , ";
 
191
    }
 
192
    out << "\b\b\b   " << std::endl;
 
193
  }
 
194
 
 
195
  void print_distance(std::ostream &out)
 
196
  {
 
197
    host_histogram_view host_copy = create_mirror_view(m_distance);
 
198
    Kokkos::deep_copy(host_copy, m_distance);
 
199
 
 
200
    for (int i=0, size = host_copy.size(); i<size; ++i)
 
201
    {
 
202
      out << host_copy[i] << " , ";
 
203
    }
 
204
    out << "\b\b\b   " << std::endl;
 
205
  }
 
206
 
 
207
  void print_block_distance(std::ostream &out)
 
208
  {
 
209
    host_histogram_view host_copy = create_mirror_view(m_block_distance);
 
210
    Kokkos::deep_copy(host_copy, m_block_distance);
 
211
 
 
212
    for (int i=0, size = host_copy.size(); i<size; ++i)
 
213
    {
 
214
      out << host_copy[i] << " , ";
 
215
    }
 
216
    out << "\b\b\b   " << std::endl;
 
217
  }
 
218
 
 
219
  KOKKOS_INLINE_FUNCTION
 
220
  void operator()( size_type i ) const
 
221
  {
 
222
    const size_type invalid_index = map_type::invalid_index;
 
223
 
 
224
    uint32_t length = 0;
 
225
    size_type min_index = ~0u, max_index = 0;
 
226
    for (size_type curr = m_map.m_hash_lists(i); curr != invalid_index; curr = m_map.m_next_index[curr]) {
 
227
      ++length;
 
228
      min_index = (curr < min_index) ? curr : min_index;
 
229
      max_index = (max_index < curr) ? curr : max_index;
 
230
    }
 
231
 
 
232
    size_type distance = (0u < length) ? max_index - min_index : 0u;
 
233
    size_type blocks = (0u < length) ? max_index/32u - min_index/32u : 0u;
 
234
 
 
235
    // normalize data
 
236
    length   = length   < 100u ? length   : 99u;
 
237
    distance = distance < 100u ? distance : 99u;
 
238
    blocks   = blocks   < 100u ? blocks   : 99u;
 
239
 
 
240
    if (0u < length)
 
241
    {
 
242
      atomic_fetch_add( &m_length(length), 1);
 
243
      atomic_fetch_add( &m_distance(distance), 1);
 
244
      atomic_fetch_add( &m_block_distance(blocks), 1);
 
245
    }
 
246
  }
 
247
};
 
248
 
 
249
template <typename UMap>
 
250
struct UnorderedMapPrint
 
251
{
 
252
  typedef UMap map_type;
 
253
  typedef typename map_type::device_type device_type;
 
254
  typedef typename map_type::size_type size_type;
 
255
 
 
256
  map_type m_map;
 
257
 
 
258
  UnorderedMapPrint( map_type const& map)
 
259
    : m_map(map)
 
260
  {}
 
261
 
 
262
  void apply()
 
263
  {
 
264
    parallel_for(m_map.m_hash_lists.size(), *this);
 
265
  }
 
266
 
 
267
  KOKKOS_INLINE_FUNCTION
 
268
  void operator()( size_type i ) const
 
269
  {
 
270
    const size_type invalid_index = map_type::invalid_index;
 
271
 
 
272
    uint32_t list = m_map.m_hash_lists(i);
 
273
    for (size_type curr = list, ii=0; curr != invalid_index; curr = m_map.m_next_index[curr], ++ii) {
 
274
      printf("%d[%d]: %d->%d\n", list, ii, m_map.key_at(curr), m_map.value_at(curr));
 
275
    }
 
276
  }
 
277
};
 
278
 
 
279
template <typename DKey, typename DValue, typename SKey, typename SValue>
 
280
struct UnorderedMapCanAssign : public false_ {};
 
281
 
 
282
template <typename Key, typename Value>
 
283
struct UnorderedMapCanAssign<Key,Value,Key,Value> : public true_ {};
 
284
 
 
285
template <typename Key, typename Value>
 
286
struct UnorderedMapCanAssign<const Key,Value,Key,Value> : public true_ {};
 
287
 
 
288
template <typename Key, typename Value>
 
289
struct UnorderedMapCanAssign<const Key,const Value,Key,Value> : public true_ {};
 
290
 
 
291
template <typename Key, typename Value>
 
292
struct UnorderedMapCanAssign<const Key,const Value,const Key,Value> : public true_ {};
 
293
 
 
294
 
 
295
}} //Kokkos::Impl
 
296
 
 
297
#endif // KOKKOS_UNORDERED_MAP_IMPL_HPP