Classes

oned Namespace Reference

This namespace provides one dimensional algorithms. More...


Detailed Description

This namespace provides one dimensional algorithms.

This namespace provides one dimensional algorithms. Both optimal and heuristic algorithms are implemented. All algorithms except Nicol variants are heuristic. Nicol has 3 variants which generate the same output but use different bounding tecniques. We recommend using NicolPlus since it is optimal and fast. One should avoid using NicolMinus or Nicol variants and prefer NicolPlus. If you really need use heuristics to improve speed, we recommend DirectCut or RecursiveBisection.

The resulting cut points map to the prefix sum array indexes and exclude leftmost and rightmost cut points, which are constant (0 and arraysize-1). Elements with the same index as cut point value are included to cut points' corresponding processor. For example consider a prefix sum array with elements {0,5,7,15,21,40,52} (correspond to original array with elements {5,2,8,6,19,12}), P=3 and cut points {3,5}. Then processor P0 has {5,2,8}, P1 has {6,19} and P3 has {12} as actual workload. Notice prefix sum array always has 0 as its 1st element. The length of cut point array is always P-1.

All algorithms except Nicol_plus_interval use bracket notation as defined in util::PrefixSumArray1DOfTBracket. Nicol_plus_interval uses interval nototaion as defined in util::PrefixSumArray1DOfTInterval.

Classes

class  DirectCut
 Greedily allocates to each processor the smallest interval with load less than average load. More...
class  DirectCutRefB
 Same as DIRECT-CUT except this one recalculates average load after each allocation. More...
class  GreedyBisection
 Grabs the interval with largest load and cuts it into two equal loaded pieces. More...
class  Nicol
 [Use NicolPlus instead] this is the implementation of the nicols algorithm as it is provided in "Ali Pinar and Cevdet Aykanat, Fast Optimal Load Balancing Algorithms for 1D Partitioning, JPDC, 2004" in figure 5b. NicolPlus should be preferred over Nicol due to speed. More...
class  NicolMinus
 [Use NicolPlus instead] this is the implementation of the nicol's algorithm as it is provided in "Ali Pinar and Cevdet Aykanat, Fast Optimal Load Balancing Algorithms for 1D Partitioning, JPDC, 2004" in figure 5a. NicolPlus should be preferred over NicolMinus due to speed. More...
class  NicolPlus
 this is the implementation of the nicols algorithm as it is provided in "Ali Pinar and Cevdet Aykanat, Fast Optimal Load Balancing Algorithms for 1D Partitioning, JPDC, 2004" in figure 10. This algorithm should be preferred over NicolMinus and Nicol due to speed. More...
class  Nicol_plus_interval
 Given a prefix sum array in interval notation, this algorithm applies NicolPlus. More...
class  Parser
 Converts text into corresponding 1D algorithm function pointer. More...
class  RecursiveBisection
 recursive 1D partitioning algorithm which partition an array in two parts of similiar load and allocates half the processor in each part. More...
class  RecursiveBisectionMinMax
 1D relaxed hierarchical heuristic. More...
class  Uniform
 Cuts prefix sum array into p fixed and equal length parts where p is the processor number. More...
 All Classes Namespaces Files Functions Variables Typedefs Friends Defines