This namespace provides one dimensional algorithms. More...

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

Generated on Mon Aug 8 2011 20:27:29 by 1.7.1