SpatialOps
BitField.h
1 /*
2  * Copyright (c) 2014 The University of Utah
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to
6  * deal in the Software without restriction, including without limitation the
7  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8  * sell copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20  * IN THE SOFTWARE.
21  */
22 
23 #ifndef SpatialOps_BitField_h
24 #define SpatialOps_BitField_h
25 
26 
27 #include <iostream>
28 #include <cassert>
29 #include <sstream>
30 #include <vector>
31 
32 #include <spatialops/SpatialOpsConfigure.h>
33 
38 
39 #include <climits> // for CHAR_BIT below.
40 
41 #define NEBO_INT_BIT ((signed int)(sizeof(unsigned int) * CHAR_BIT))
42 #define NEBO_INT_BYTE ((signed int)(sizeof(unsigned int)))
43 #define NEBO_ROUND_TO_INT(size) ((signed int)((size + NEBO_INT_BIT - 1) / NEBO_INT_BIT))
44 
45 namespace SpatialOps{
46 
47  class ConstMaskIterator : public std::iterator<std::random_access_iterator_tag, bool> {
48  typedef ConstMaskIterator MyType;
49 
50  public:
51  ConstMaskIterator(unsigned int * field_values,
52  const MemoryWindow & w)
53  : bitField_(field_values),
54  bitPosition_((w.offset(0) +
55  w.glob_dim(0) * (w.offset(1) +
56  w.glob_dim(1) * w.offset(2)))
57  % NEBO_INT_BIT),
58  blockPosition_((w.offset(0) +
59  w.glob_dim(0) * (w.offset(1) +
60  w.glob_dim(1) * w.offset(2)))
61  / NEBO_INT_BIT),
62  count_(0),
63  size_(NEBO_ROUND_TO_INT(w.glob_npts())),
64  xIndex_(0),
65  yIndex_(0),
66  zIndex_(0),
67  yStep_(w.glob_dim(0) - w.extent(0)),
68  zStep_((w.glob_dim(1) - w.extent(1)) * w.glob_dim(0)),
69  xExtent_(w.extent(0)),
70  yExtent_(w.extent(1)),
71  zExtent_(w.extent(2)),
72  xyExtent_(w.extent(0) * w.extent(1))
73  {}
74 
75  //immutable dereference
76  inline bool operator*() const {
77 # ifndef NDEBUG
78  if(bitPosition_ < 0 ||
79  bitPosition_ >= NEBO_INT_BIT) {
80  std::ostringstream msg;
81  msg << __FILE__ << " : " << __LINE__ << std::endl
82  << "iterator's bitPosition_ is out of bounds";
83  throw std::runtime_error(msg.str());
84  }
85  if(blockPosition_ < 0 ||
86  blockPosition_ >= size_) {
87  std::ostringstream msg;
88  msg << __FILE__ << " : " << __LINE__ << std::endl
89  << "iterator's blockPosition_ is out of bounds";
90  throw std::runtime_error(msg.str());
91  }
92  if(count_ != (xIndex_ +
93  yIndex_ * xExtent_ +
94  zIndex_ * xyExtent_)) {
95  std::ostringstream msg;
96  msg << __FILE__ << " : " << __LINE__ << std::endl
97  << "iterator's internal count is off";
98  throw std::runtime_error(msg.str());
99  }
100  if(xIndex_ >= xExtent_ ||
101  yIndex_ >= yExtent_ ||
102  zIndex_ >= zExtent_ ||
103  xIndex_ < 0 ||
104  yIndex_ < 0 ||
105  zIndex_ < 0) {
106  std::ostringstream msg;
107  msg << __FILE__ << " : " << __LINE__ << std::endl
108  << "iterator is in an invalid state for dereference";
109  throw std::runtime_error(msg.str());
110  }
111 # endif
112  return !!(*(bitField_ + blockPosition_) & (1 << bitPosition_));
113  }
114 
115  //increment
116  inline MyType & operator++() {
117  bitPosition_++; //xStep
118  count_++;
119  xIndex_++;
120  if(xIndex_ == xExtent_){
121  bitPosition_ += yStep_; //yStep
122  xIndex_ = 0;
123  yIndex_++;
124  if(yIndex_ == yExtent_){
125  bitPosition_ += zStep_; //zStep
126  yIndex_ = 0;
127  zIndex_++;
128  }
129  }
130 
131  //recalculate bitPosition_ and blockPosition_
132  update_positions();
133 
134  return *this;
135  };
136 
137  inline MyType operator++(int) { MyType result = *this; ++(*this); return result; };
138 
139  //decrement
140  inline MyType & operator--() {
141  --bitPosition_; //xStep
142  --count_;
143  --xIndex_;
144  if( xIndex_ == -1 ){
145  bitPosition_ -= yStep_; //yStep
146  xIndex_ = xExtent_ - 1;
147  --yIndex_;
148  if( yIndex_ == -1 ){
149  bitPosition_ -= zStep_; //zStep
150  yIndex_ = yExtent_ - 1;
151  --zIndex_;
152  }
153  }
154 
155  //recalculate bitPosition_ and blockPosition_
156  update_positions();
157 
158  return *this;
159  }
160 
161  inline MyType operator--(int) { MyType result = *this; --(*this); return result; };
162 
163  //compound assignment
164  inline MyType & operator+=(int change) {
165  //small change (only changes xIndex_)
166  if( (change > 0 && change < xExtent_ - xIndex_) || //positive change
167  (change < 0 && - change < xIndex_) ){ //negative change
168  bitPosition_ += change;
169  xIndex_ += change;
170  count_ += change;
171  }
172  else { //bigger change (changes yIndex_ and/or zIndex_)
173  int new_count = count_ + change;
174  int old_count = count_;
175  bitPosition_ += (change + //xStep
176  yStep_ * ((new_count / xExtent_) - (old_count / xExtent_)) +
177  zStep_ * ((new_count / xyExtent_) - (old_count /xyExtent_)));
178  count_ += change;
179  xIndex_ = count_ % xExtent_;
180  yIndex_ = (count_ % xyExtent_) / xExtent_;
181  zIndex_ = count_ / xyExtent_;
182  }
183 
184  //recalculate bitPosition_ and blockPosition_
185  update_positions();
186 
187  return *this;
188  }
189 
190  inline MyType & operator-=(int change) { return *this += -change; }
191 
192  //addition/subtraction
193  inline MyType operator+ (int change) const { MyType result = *this; result += change; return result; }
194  inline MyType operator- (int change) const { return *this + (-change); };
195 
196  //iterator subtraction
197  inline ptrdiff_t operator- (MyType const & other) const { return count_ - other.count_; }
198 
199  //offset dereference
200  inline bool operator[](int change) { MyType result = *this; result += change; return *result; }
201 
202  //comparisons
203  inline bool operator==(MyType const & other) const { return bitField_ == other.bitField_ && count_ == other.count_; }
204  inline bool operator!=(MyType const & other) const { return bitField_ != other.bitField_ || count_ != other.count_; }
205  inline bool operator< (MyType const & other) const { return bitField_ == other.bitField_ && count_ < other.count_; }
206  inline bool operator> (MyType const & other) const { return bitField_ == other.bitField_ && count_ > other.count_; }
207  inline bool operator<=(MyType const & other) const { return bitField_ == other.bitField_ && count_ <= other.count_; }
208  inline bool operator>=(MyType const & other) const { return bitField_ == other.bitField_ && count_ >= other.count_; }
209 
210  private:
211 
212  inline void update_positions(void) {
213  if(bitPosition_ < 0 ||
214  bitPosition_ >= NEBO_INT_BIT) {
215  const int flatPosition = blockPosition_ * NEBO_INT_BIT + bitPosition_;
216  blockPosition_ = flatPosition / NEBO_INT_BIT;
217  bitPosition_ = flatPosition % NEBO_INT_BIT;
218  }
219  }
220 
221  unsigned int * bitField_;
222  int bitPosition_;
223  int blockPosition_;
224  int count_;
225  int size_;
226  int xIndex_, yIndex_, zIndex_;
227  int yStep_;
228  int zStep_;
229  int xExtent_, yExtent_, zExtent_;
230  int xyExtent_;
231  };
232 
246  class BitField
247  {
248  public:
249 
250  typedef MemoryWindow memory_window;
252 
253  private:
254  typedef std::map<unsigned short int, unsigned int*> ConsumerMap;
255 
256  MemoryWindow maskWindow_;
257  const GhostData ghosts_;
258 
259  const unsigned long int size_;
260  const unsigned long int bytes_;
261 
262  unsigned int * bitValues_;
263  unsigned int * bitValuesExtDevice_;
264  const bool builtMask_;
265  bool hasgpuConsumer_;
266 
267  const short int deviceIndex_;
268 
269 
270  //Note: Presently this is assumed to be a collection of GPU based < index, pointer pairs >;
271  // which is not as general is it likely should be, but GPUs are currently the only external
272  // device we're interested in supporting.
273  ConsumerMap consumerBitValues_;
274  ConsumerMap myConsumerBitValues_;
275 
276  inline void reset_values(void)
277  {
278  if( deviceIndex_ == CPU_INDEX ){
279  for( unsigned int long i = 0; i < size_; ++i )
280  bitValues_[i] = 0;
281  }
282  else{
283  std::ostringstream msg;
284  msg << "Reset values called for unsupported field type ( "
285  << DeviceTypeTools::get_memory_type_description(deviceIndex_) << " )"
286  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
287  throw(std::runtime_error(msg.str()));
288  }
289  }
290 
291  inline int find_position(const IntVec & point) const
292  {
293 # ifndef NDEBUG
294  //check that point is in bounds
295  assert(point[0] >= -ghosts_.get_minus(0));
296  assert(point[0] < (signed int)(maskWindow_.extent(0)) + ghosts_.get_plus(0));
297  assert(point[1] >= -ghosts_.get_minus(1));
298  assert(point[1] < (signed int)(maskWindow_.extent(1)) + ghosts_.get_plus(1));
299  assert(point[2] >= -ghosts_.get_minus(2));
300  assert(point[2] < (signed int)(maskWindow_.extent(2)) + ghosts_.get_plus(2));
301 # endif
302 
303  const int xIndex = maskWindow_.offset(0) + point[0];
304  const int yIndex = maskWindow_.offset(1) + point[1];
305  const int zIndex = maskWindow_.offset(2) + point[2];
306 
307  const int xTotal = maskWindow_.glob_dim(0);
308  const int yTotal = maskWindow_.glob_dim(1);
309 
310  return xIndex + xTotal * (yIndex + yTotal * zIndex);
311  };
312 
313  inline int find_block(const int flat) const { return flat / NEBO_INT_BIT; };
314 
315  inline int find_bit_position(const int flat) const { return flat % NEBO_INT_BIT; };
316 
317  inline void add_point(const IntVec & point)
318  {
319  if( bitValues_ != NULL ){
320  const int position = find_position(point);
321  unsigned int * const blockPosition = bitValues_ + find_block(position);
322  const int bitPosition = find_bit_position(position);
323  //update block with new point
324  *blockPosition = (*blockPosition | (1 << bitPosition));
325  }
326  else{
327  std::ostringstream msg;
328  msg << "Unsupported attempt to add points to a mask of type ( "
329  << DeviceTypeTools::get_memory_type_description(deviceIndex_)
330  << " )\n" << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
331  throw(std::runtime_error(msg.str()));
332  }
333  }
334 
335  inline void add_points( const std::vector<IntVec> & points )
336  {
337  for( std::vector<IntVec>::const_iterator i = points.begin(); i != points.end(); ++i )
338  add_point(*i);
339  }
340 
341  public:
342 
349  BitField(const std::vector<IntVec> & points,
350  const MemoryWindow & window,
351  const GhostData & ghosts)
352  : maskWindow_(window),
353  ghosts_(ghosts),
354  size_(NEBO_ROUND_TO_INT(window.glob_npts())),
355  bytes_(NEBO_ROUND_TO_INT(window.glob_npts()) * NEBO_INT_BYTE),
356  bitValues_(Pool<unsigned int>::get(CPU_INDEX, size_)),
357  builtMask_(true),
358  hasgpuConsumer_(false),
359  deviceIndex_(CPU_INDEX)
360  {
361  reset_values();
362  add_points(points);
363  }
364 
369  BitField(const BitField& other)
370  : maskWindow_(other.maskWindow_),
371  ghosts_(other.ghosts_),
372  size_(other.size_),
373  bytes_(other.bytes_),
374  bitValues_(other.bitValues_),
375  builtMask_(false),
376  hasgpuConsumer_(false),
377  deviceIndex_(other.deviceIndex_),
378  consumerBitValues_(other.consumerBitValues_)
379  {}
380 
381  ~BitField()
382  {
383 # ifdef ENABLE_CUDA
384  //Release any masks allocated for consumer use
385  if( hasgpuConsumer_ ){
386  for( ConsumerMap::iterator i = myConsumerBitValues_.begin(); i != myConsumerBitValues_.end(); ++i ){
387  Pool<unsigned int>::put( i->first, i->second );
388  }
389  }
390  consumerBitValues_.clear();
391  myConsumerBitValues_.clear();
392  hasgpuConsumer_ = false;
393 # endif // ENABLE_CUDA
394 
395  if ( builtMask_ && !hasgpuConsumer_ ) {
396  if( deviceIndex_ == CPU_INDEX ){
397  Pool<unsigned int>::put( CPU_INDEX, bitValues_ );
398  bitValues_ = NULL;
399  }
400  else{
401  std::ostringstream msg;
402  msg << "Attempt to release ( "
403  << DeviceTypeTools::get_memory_type_description(deviceIndex_)
404  << " ) mask type, without supporting libraries -- this likely indicates a serious problem in mask initialization\n"
405  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
406  throw( std::runtime_error( msg.str() ) );
407  }
408  }
409  }
410 
416  inline bool operator()(const IntVec& point) const
417  {
418 # ifndef NDEBUG
419  if( bitValues_ == NULL ){
420  std::ostringstream msg;
421  msg << "Unsupported attempt to add points to a mask of type ( "
422  << DeviceTypeTools::get_memory_type_description(deviceIndex_)
423  << " )\n" << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
424  throw(std::runtime_error(msg.str()));
425  }
426 # endif
427  const int position = find_position(point);
428  unsigned int * const block = bitValues_ + find_block(position);
429  const int bitPosition = find_bit_position(position);
430  //update block with new point
431  return !!(*block & (1 << bitPosition));
432  }
433 
438  inline const_iterator begin(const MemoryWindow & window) const {
439  if( bitValues_ == NULL) {
440  std::ostringstream msg;
441  msg << "Mask type ( "
442  << DeviceTypeTools::get_memory_type_description(deviceIndex_) << " ) ,"
443  << " does not support direct iteration, and has no local consumer mask allocated.\n"
444  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
445  throw(std::runtime_error(msg.str()));
446  }
447  return const_iterator(bitValues_, window);
448  }
449 
450  inline const_iterator end(const MemoryWindow & window) const
451  {
452  if(bitValues_ != NULL ) {
453  int extent = window.extent(0) * window.extent(1) * window.extent(2);
454  const_iterator i(bitValues_, window);
455  return i + extent;
456  } else {
457  std::ostringstream msg;
458  msg << __FILE__ << " : " << __LINE__ << std::endl
459  << "Unsupported request for const_iterator to mask type ( "
460  << DeviceTypeTools::get_memory_type_description(deviceIndex_) << " )"
461  << "\t - No consumer allocated." << std::endl;
462  throw std::runtime_error( msg.str() );
463  }
464  }
465 
466  inline void add_consumer( const short int consumerDeviceIndex )
467  {
468  // CPU Masks are always exist and hence create only GPU Masks.
469  if( consumerDeviceIndex == CPU_INDEX ) return;
470 # ifdef ENABLE_CUDA
471  else if( IS_GPU_INDEX(consumerDeviceIndex) ){
472  //CPU Mask needs to be available on GPU
473  ema::cuda::CUDADeviceInterface& CDI = ema::cuda::CUDADeviceInterface::self();
474 
475  //Check to see if GPU mask memory exists
476  if(consumerBitValues_.find(consumerDeviceIndex) == consumerBitValues_.end()) {
477  consumerBitValues_[consumerDeviceIndex] = Pool<unsigned int>::get(consumerDeviceIndex, size_);
478  myConsumerBitValues_[consumerDeviceIndex] = consumerBitValues_[consumerDeviceIndex];
479  };
480 
481  CDI.memcpy_to((void*)consumerBitValues_[consumerDeviceIndex], bitValues_, bytes_, consumerDeviceIndex);
482  hasgpuConsumer_ = true;
483  return;
484  }
485 # endif // ENABLE_CUDA
486  else{
487  std::ostringstream msg;
488  msg << "Failed call to add_consumer on Spatial Mask, unknown destination device type : " << consumerDeviceIndex << std::endl
489  << "Ensure that you are compiling spatial ops with the proper end device support\n"
490  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
491  throw(std::runtime_error(msg.str()));
492  }
493  }
494 
495  inline bool find_consumer(const short int consumerDeviceIndex) const
496  {
497  //Check for local allocation
498  if( consumerDeviceIndex == CPU_INDEX ) return true;
499 # ifdef ENABLE_CUDA
500  else if( IS_GPU_INDEX(consumerDeviceIndex) ){
501  return consumerBitValues_.find( consumerDeviceIndex ) != consumerBitValues_.end();
502  }
503 # endif // ENABLE_CUDA
504  else
505  {
506  std::ostringstream msg;
507  msg << "Failed call to find_consumer on SpatialMask, unknown destination device type : " << consumerDeviceIndex << std::endl
508  << "Ensure that you are compiling spatial ops with the proper end device support\n"
509  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
510  throw(std::runtime_error(msg.str()));
511  }
512  }
513 
514  inline bool has_consumers(){
515  return consumerBitValues_.size() > 0;
516  }
517 
518  inline short int active_device_index() const { return deviceIndex_; };
519 
520  inline const unsigned int * mask_values( const short int consumerDeviceIndex = CPU_INDEX ) const
521  {
522  if( consumerDeviceIndex == CPU_INDEX ){
523 # ifndef NDEBUG
524  if( bitValues_ == NULL ){
525  std::ostringstream msg;
526  msg << "Request for consumer mask pointer on a CPU_INDEX for which it has not been allocated\n"
527  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
528  throw(std::runtime_error(msg.str()));
529  }
530 # endif
531  return bitValues_;
532  }
533  else if( IS_GPU_INDEX(consumerDeviceIndex) ){
534 # ifdef ENABLE_CUDA
535  ConsumerMap::const_iterator citer = consumerBitValues_.find(consumerDeviceIndex);
536  if( citer != consumerBitValues_.end() ){
537 # ifndef NDEBUG
538  if(citer->second == NULL) {
539  std::ostringstream msg;
540  msg << "Request for consumer mask pointer on a GPU index for which it has not been allocated\n"
541  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
542  throw(std::runtime_error(msg.str()));
543  }
544 # endif
545  return citer->second;
546  }
547 # endif
548  }
549  else{
550  std::ostringstream msg;
551  msg << "Request for consumer mask pointer to unknown or unsupported device\n"
552  << "\t - " << __FILE__ << " : " << __LINE__ << std::endl;
553  throw(std::runtime_error(msg.str()));
554  }
555  return NULL; // should never get here. This line is just to eliminate compiler warnings.
556  }
557  };
558 
559 } // namespace SpatialOps
560 
561 #endif // SpatialOps_BitField_h
Provides tools to index into a sub-block of memory.
Definition: MemoryWindow.h:63
BitField(const std::vector< IntVec > &points, const MemoryWindow &window, const GhostData &ghosts)
Construct a BitField.
Definition: BitField.h:349
BitField(const BitField &other)
Shallow copy constructor. This results in two masks that share the same underlying memory...
Definition: BitField.h:369
static void put(const short int deviceLocation, T *t)
Return the requested block of memory to the pool. This should only be done for memory requested from ...
Definition: MemoryPool.cpp:217
size_t glob_npts() const
obtain the global number of points in the field. Note that this is not necessarily contiguous memory ...
Definition: MemoryWindow.h:155
static T * get(const short int deviceLocation, const size_t n)
Obtain a pointer to a block of memory with the requested size. If the requested size is zero...
Definition: MemoryPool.cpp:116
Implements a mask as a bitfield.
Definition: BitField.h:246
const_iterator begin(const MemoryWindow &window) const
Iterator constructs for traversing memory windows. Note: Iteration is not directly supported for exte...
Definition: BitField.h:438
bool operator()(const IntVec &point) const
Given an index in this mask, return whether or not index is a mask point. WARNING: slow! NOTE: Not su...
Definition: BitField.h:416
IntVec get_plus() const
obtain the IntVec containing the number of ghost cells on the (+) faces
Definition: GhostData.h:145
Holds information about the number of ghost cells on each side of the domain.
Definition: GhostData.h:54
IntVec get_minus() const
obtain the IntVec containing the number of ghost cells on the (-) faces
Definition: GhostData.h:135