Refine a Cut (RaC)

Defined in algorithms/refine_a_cut.hpp

namespace sarma::refine_a_cut

Enums

enum LOOKUP

An enum type used to define refinement direction.

Values:

enumerator DIM_X

column direction

enumerator DIM_Y

row direction

Functions

template<typename Ordinal, typename Value>
auto refinement(const Matrix<Ordinal, Value> &A, std::vector<Value> &prefix, const std::vector<Ordinal> &prev_cuts)

Implements a simplified refinement technique inspired from Nicol’s refinement precedure. Here instead of running simultaneous binary searches over prefix sum arrays of each interval we first compute the maximum of the each interval than apply an optimal one-dimensional partitioning.

Return

a cut vector

Parameters

  • A: a matrix

  • prefix: prefix sum array

  • prev_cuts: cuts of the previous iteration

Template Parameters

template<typename Ordinal, typename Value>
auto nic_refinement(const Matrix<Ordinal, Value> &A, std::vector<std::vector<Value>> &prefixes, const std::vector<Ordinal> &prev_cuts)

Implements Nicol’s refinement precedure. This procedure runs simultaneous binary searches over prefix sum arrays of each interval.

Return

a cut vector

Parameters

  • A: a matrix

  • prefix: prefix sum array

  • prev_cuts: cuts of the previous iteration

Template Parameters

template<class Ordinal, class Value>
auto partition(const Matrix<Ordinal, Value> &A, const std::vector<Ordinal> &p, bool pdf = true, int max_iteration = 0, bool nic_ref = false)

Implements the Refine a Cut algorithm. Applies row and column based mapping to map 2D into 1D chooses the direction that gives better load imbalance.

Return

a cut vector

Parameters

  • A: Matrix

  • p: starting cut vector after choosing the direction

  • pdf: pick direction first if it is true.

  • max_iteration: limit on refinement iterations

Template Parameters

template<typename Ordinal, typename Value>
auto bal(const Matrix<Ordinal, Value> &A, const Value Z)

Implements Bound a Load (BaL) algorithm using RaC as the mLI algorithm.

Return

a cut vector

Parameters
Template Parameters

template<class Ordinal, class Value>
std::vector<Ordinal> partition(const Matrix<Ordinal, Value> &A, const Ordinal P, const Value Z = 0, bool pdf = true, int max_iteration = 0, bool nic_ref = false)

Implements the Refine a Cut (RaC) algorithm. Applies row and column based mapping to map 2D into 1D chooses the direction that gives better load imbalance. Note that if Z is greater than zero then this function overrides P and calls the dual of the uniform partitioning that solves MNc problem. If pdf is false then in each iteration this algorithm applies row-wise and column-wise refinement and picks the best cuts for the next iteration.

Return

a cut vector

Parameters

  • A: Matrix

  • P: number of cuts

  • Z: target load

  • pdf: pick direction first if it is true.

  • max_iteration: limit on refinement iterations

Template Parameters