Greedily allocates to each processor the smallest interval with load less than average load. More...
#include <oned/direct_cut.hpp>
Greedily allocates to each processor the smallest interval with load less than average load.
This algorithm was introduced in "Serge Miguet and Jean-Marc Pierson, Heuristics for 1D Rectilinear Partitioning as a Low Cost and High Quality Answer to Dynamic Load Balancing, HPCN Europe 1997" under the name H1. It sets cut points where B=P_iter*(Wtot/P).
T | data type of weight of instance | |
Pr | data type of prefixSumArray |
Static Public Member Functions | |
static T | direct_cut (int procCount, const Pr &prefixSumArray, int length, int *cutIndexes, T) |
Applies direct cut algorithm to a given prefixSumArray. | |
Static Private Member Functions | |
static T | direct_cut_internal (int procCount, const Pr &prefixSumArray, int length, int *cutIndexes) |
T oned::DirectCut< T, Pr >::direct_cut | ( | int | procCount, | |
const Pr & | prefixSumArray, | |||
int | length, | |||
int * | cutIndexes, | |||
T | ||||
) | [static] |
Applies direct cut algorithm to a given prefixSumArray.
[in] | procCount | is the total number of processors |
[in] | prefixSumArray | always begins with 0 as first element. |
[in] | length | is the exact size of prefixSumArray |
[out] | cutIndexes | (must be allocated before calling!) |
T oned::DirectCut< T, Pr >::direct_cut_internal | ( | int | procCount, | |
const Pr & | prefixSumArray, | |||
int | length, | |||
int * | cutIndexes | |||
) | [static, private] |