Tpetra_Details_radixSort.hpp

// @HEADER
// *****************************************************************************
//          Tpetra: Templated Linear Algebra Services Package
//
// Copyright 2008 NTESS and the Tpetra contributors.
// SPDX-License-Identifier: BSD-3-Clause
// *****************************************************************************
// @HEADER

#ifndef TPETRA_DETAILS_RADIXSORT_HPP
#define TPETRA_DETAILS_RADIXSORT_HPP

#include "TpetraCore_config.h"
#include "Kokkos_Macros.hpp"

namespace Tpetra {
namespace Details {

template <typename KeyType, typename ValueType, typename IndexType>
KOKKOS_INLINE_FUNCTION void
radixSortKeysAndValues(KeyType* keys, KeyType* keysAux, ValueType* values, ValueType* valuesAux, IndexType n, IndexType upperBound) {
  if (n <= 1)
    return;
  KeyType mask = 0xF;
  bool inAux   = false;
  // maskPos counts the low bit index of mask (0, 4, 8, ...)
  IndexType maskPos = 0;
  // Count number of bits required to sort (8 * sizeof(KeyType) - lzcnt(maxKey - minKey))
  IndexType sortBits = 0;
  while (upperBound) {
    upperBound >>= 1;
    sortBits++;
  }
  for (IndexType s = 0; s < (sortBits + 3) / 4; s++) {
    // Count the number of elements in each bucket
    IndexType count[16]  = {0};
    IndexType offset[17] = {0};
    if (!inAux) {
      for (IndexType i = 0; i < n; i++) {
        count[(keys[i] & mask) >> maskPos]++;
      }
    } else {
      for (IndexType i = 0; i < n; i++) {
        count[(keysAux[i] & mask) >> maskPos]++;
      }
    }
    // get offset as the prefix sum for count
    for (IndexType i = 0; i < 16; i++) {
      offset[i + 1] = offset[i] + count[i];
    }
    // now for each element in [lo, hi), move it to its offset in the other buffer
    // this branch should be ok because whichBuf is the same on all threads
    if (!inAux) {
      // copy from *Over to *Aux
      for (IndexType i = 0; i < n; i++) {
        IndexType bucket                              = (keys[i] & mask) >> maskPos;
        keysAux[offset[bucket + 1] - count[bucket]]   = keys[i];
        valuesAux[offset[bucket + 1] - count[bucket]] = values[i];
        count[bucket]--;
      }
    } else {
      // copy from *Aux to *Over
      for (IndexType i = 0; i < n; i++) {
        IndexType bucket                           = (keysAux[i] & mask) >> maskPos;
        keys[offset[bucket + 1] - count[bucket]]   = keysAux[i];
        values[offset[bucket + 1] - count[bucket]] = valuesAux[i];
        count[bucket]--;
      }
    }
    inAux = !inAux;
    mask  = mask << 4;
    maskPos += 4;
  }
  if (inAux) {
    // need to deep copy from aux arrays to main
    for (IndexType i = 0; i < n; i++) {
      keys[i]   = keysAux[i];
      values[i] = valuesAux[i];
    }
  }
}

}  // namespace Details
}  // namespace Tpetra

#endif  // include guard