Subgradient Method

Defined in algorithms/subgradient_method.hpp

namespace sarma::subgradient_method

Functions

template<typename Int, typename Value>
auto uniform_init(const Int P, const Value total_load)
template<typename Int, typename Value, typename Gen>
auto random_init(const Int P, const Value total_load, Gen &gen)
template<typename pis_to_rs_t>
auto partition(std::vector<std::vector<double>> &pis, pis_to_rs_t to_rs, const std::size_t C = 10, const double eps = 0.001)

Implements the SubGradient Optimization algorithm. This algorithm initializes the cut vectors randomly and tries to refine them at each iteration by moving all the cuts in the negative direction of the gradient to minimize the maximum load.

Return

vector of cut vector parametrizations

Parameters

  • pis: vector of cut vector parametrizations

  • to_rs: lambda function to compute gradients given pis

  • C: number of iterations to wait when objective value flattens

  • eps: the improvement in the optimization objective expected

template<typename Int, typename Value>
auto partition(const std::string s, const std::vector<std::reference_wrapper<const Matrix<Int, Value>>> As, const std::vector<Int> Ps, int seed = 1)

An easy to use wrapper for the the SubGradient Optimization algorithm. This algorithm initializes the cut vectors randomly and tries to refine them at each iteration by moving all the cuts in the negative direction of the gradient to minimize the maximum load. The first parameter, the string s describes the optimization objective. Each term in the optimization objective is made up of a digit indicating the index of the matrix, the name of the first dimension of the matrix and the name of the second dimension of the matrix separated by “+” signs inbetween. As examples, sgo_2dr -> “0ij”, sgo_2ds -> “0ij,i=j”, sgo_3ds -> “0ij+0jk+0ik” and sgo_3dr -> “0ij+1jk”. As one can guess, the part before the comma represents the optimization objective and after the comma includes constraints that can’t be derived automatically from the optimization objective. As an example, for sgo_2ds, we had to explicitly put the constraint that the two cut vectors in the two dimensions need to be the same via stating “i=j”. However, sgo_3ds can do that automatically because the same matrix dimension is named different letters “i” and “j” etc. that that causes all the dimensions to collapse into one removing the need to put the constraints explicitly.

Return

a vector of cut vectors

Parameters

  • s: a string describing the optimization objective

  • A: a vector of references to matrices used in the optimization objective

  • P: number of parts in each dimension of the resulting cut vectors

  • seed:

template<typename Int, typename Value>
auto partition_spmv(const Matrix<Int, Value> &A, const Int P, const double alpha, const double beta, const int seed = 1)
template<typename Int, typename Value>
auto partition_tri(const Matrix<Int, Value> &A, const Int P, const int seed = 1)

Implements the SubGradient Optimization algorithm, where each task is made of 3 tiles and tries to minimize task size. This algorithm initializes the cut vectors randomly and tries to refine them at each iteration by moving all the cuts in the negative direction of the gradient to minimize the maximum load.

Return

a cut vector

Parameters

  • A: Matrix

  • P: number of parts

  • seed:

template<typename Int, typename Value>
auto partition(const Matrix<Int, Value> &A, const Matrix<Int, Value> &B, const Int P, const Int Q, const Int R, int seed = 1)

Implements the SubGradient Optimization algorithm, where each task is made up of 2 tiles from each matrix in SpGEMM matrix multiplication and tries to minimize task size. This algorithm initializes the cut vectors randomly and tries to refine them at each iteration by moving all the cuts in the negative direction of the gradient to minimize the maximum load.

Return

a cut vector

Parameters

  • A: Matrix

  • B: Matrix

  • P: number of parts in 1st dimension

  • Q: number of parts in 2nd dimension

  • R: number of parts in 3rd dimension

  • seed:

template<typename Int, typename Value>
auto partition(const Matrix<Int, Value> &A, const Int P, const int seed = 1)

Implements the SubGradient Optimization algorithm. This algorithm initializes the cut vectors randomly and tries to refine them at each iteration by moving all the cuts in the negative direction of the gradient to minimize the maximum load.

Return

a cut vector

Parameters

  • A: Matrix

  • P: number of parts

  • seed:

template<typename Int, typename Value>
auto partition(const Matrix<Int, Value> &A, const Int P, const Int Q, const int seed = 1)

Implements the SubGradient Optimization algorithm. This algorithm initializes the cut vectors randomly and tries to refine them at each iteration by moving all the cuts in the negative direction of the gradient to minimize the maximum load.

Return

a cut vector

Parameters

  • A: Matrix

  • P: number of parts in row dimension

  • Q: number of parts in column dimension

  • seed: