Nicol 1D¶
Defined in algorithms/nicol1d.hpp
-
namespace
sarma
::
nicol1d
¶ Functions
-
template<class
Ordinal
, classValue
, boolversion
= false>
autoprobe
(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 arraysQ
: number of prefix sum arraysL
: upper bound of load sizeUB
: upper bound of each cut
-
template<class
Ordinal
, classValue
>
boolprobe
(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 partsB
: upper bound
-
template<class
Ordinal
, classValue
>
autopartition_values
(std::vector<Value> const *prefixes, const Ordinal Q, const Ordinal P)¶
-
template<class
Ordinal
, classValue
>
autopartition_indices
(std::vector<Value> const *prefixes, const Ordinal Q, const Ordinal P)¶
-
template<class
Ordinal
, classValue
, booluse_indices
= true>
autopartition
(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 1DP
: number of part
-
template<class
Ordinal
, classValue
>
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
: vectorP
: number of partson
: dimension that Matrix will be cut
-
template<class
Ordinal
, classValue
>
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 arrayP
: number of part
-
template<class