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...