Nicol 1D

Defined in algorithms/nicol1d.hpp

namespace sarma::nicol1d

Functions

template<class Ordinal, class Value, bool version = false>
auto probe(std::vector<Value> const *prefixes, const Ordinal Q, const Value L, std::vector<Ordinal> *UB = nullptr)

Implements 2D probe with ‘version’ choosing different optimizations. Given 2D prefix sum array (Q by N), number of partitions (P = UB.size() - 1) and the maximum load, this algorithm returns a valid cut vector of [0, N-1] (last elements are >= N),if such partition exists, and an unvalid one otherwise.

Return

a cut vector

Parameters
  • prefixes: Q of N prefix sum arrays

  • Q: number of prefix sum arrays

  • L: upper bound of load size

  • UB: upper bound of each cut

template<class Ordinal, class Value>
bool probe(const std::vector<Value> &prefix, const Ordinal P, const Value B)

Implements standard 1D probe Given prefix sum array, number of partitions and the maximum load, this algorithm returns true if such partition exists, and false otherwise.

Return

whether feasiable cuts exists

Parameters
  • prefix:

  • P: number of parts

  • B: upper bound

template<class Ordinal, class Value>
auto partition_values(std::vector<Value> const *prefixes, const Ordinal Q, const Ordinal P)
template<class Ordinal, class Value>
auto partition_indices(std::vector<Value> const *prefixes, const Ordinal Q, const Ordinal P)
template<class Ordinal, class Value, bool use_indices = true>
auto partition(std::vector<Value> const *prefixes, const Ordinal Q, const Ordinal P)

Implements the helper function that computes optimum 1D cut for given prefix sum. The algorithm is described in “David Nicol, Rectilinear Partitioning of Irregular Data Parallel Computations, JPDC, 1994”.

Return

cut vector and optimal bound

Parameters
  • prefix: prefix sum for 1D

  • P: number of part

template<class Ordinal, class Value>
std::vector<Ordinal> partition_prefix(const std::vector<Value> &prefix, const Ordinal P)

Implements optimum 1D partitioning The algorithm is described in “David Nicol, Rectilinear Partitioning of Irregular Data Parallel Computations, JPDC, 1994”.

Return

cut vector and optimal bound

Parameters
  • prefix: vector

  • P: number of parts

  • on: dimension that Matrix will be cut

template<class Ordinal, class Value>
std::vector<Ordinal> partition(const std::vector<Value> &array, const Ordinal P)

Implements optimum 1D partitioning algorithm described in “David Nicol, Rectilinear Partitioning of Irregular Data Parallel Computations, JPDC, 1994”.

Return

cut vector and optimal bound

Parameters
  • array: input 1D array

  • P: number of part