oned::RecursiveBisectionMinMax< T, Pr > Class Template Reference

1D relaxed hierarchical heuristic. More...

#include <oned/rec_bisect_minmax.hpp>

---

Detailed Description

template<typename T, typename Pr>
class oned::RecursiveBisectionMinMax< T, Pr >

1D relaxed hierarchical heuristic.

Parameters:

	T	data type of the Prefix Sum Array
	Pr	type of the Prefix Sum Array

List of all members.

Static Public Member Functions
static double	calculateDiff (const Pr prefixSum, int low, int high, int leftProc, int rightProc, int candidate)
static int	findEvenCut (const Pr prefixSum, int low, int high, int leftProc, int rightProc)
static T	rec_bisection (int procCount, const Pr prefixSumArray, int length, int *cutIndexes, T)
Static Private Member Functions
static int	linsrch (const Pr prefixSum, int low, int high, int leftProc, int rightProc)
	For debug purpose only.
static double	pointDiff (const Pr prefixSum, int low, int high, int leftProc, int rightProc, int point)
static int	slopeAt (const Pr prefixSum, int low, int high, int leftProc, int rightProc, int point)
	Finds the slope sign at a given point.
static int	bimonsearch (const Pr prefixSum, int low, int high, int leftProc, int rightProc)
static T	rec_bisection_internal (int numProc, int low, int high, const Pr prefixSum, int *cutPoints)

---

Member Function Documentation

template<typename T , typename Pr >

int oned::RecursiveBisectionMinMax< T, Pr >::bimonsearch	(	const Pr	prefixSum,
		int	low,
		int	high,
		int	leftProc,
		int	rightProc
	)			[static, private]

template<typename T , typename Pr >

double oned::RecursiveBisectionMinMax< T, Pr >::calculateDiff	(	const Pr	prefixSum,
		int	low,
		int	high,
		int	leftProc,
		int	rightProc,
		int	candidate
	)			[static]

template<typename T , typename Pr >

int oned::RecursiveBisectionMinMax< T, Pr >::findEvenCut	(	const Pr	prefixSum,
		int	low,
		int	high,
		int	leftProc,
		int	rightProc
	)			[static]

Finds the best cut point of a given array by calculating Wtot*(leftProc)/(leftProc+rightProc) and then decides whether to cut from left or right. left and low index values are included to calculation. prefixsum[0] = 0.

Parameters:

[in]	prefixSum	1D prefixsum array
[in]	low	lower bound
[in]	high	upper bound
[in]	leftProc	number of processor on left side
[in]	rightProc	number of processor on right side

Returns:

index of even cut point (the index of leftProc's last element)

template<typename T , typename Pr >

int oned::RecursiveBisectionMinMax< T, Pr >::linsrch	(	const Pr	prefixSum,
		int	low,
		int	high,
		int	leftProc,
		int	rightProc
	)			[static, private]

For debug purpose only.

template<typename T , typename Pr >

double oned::RecursiveBisectionMinMax< T, Pr >::pointDiff	(	const Pr	prefixSum,
		int	low,
		int	high,
		int	leftProc,
		int	rightProc,
		int	point
	)			[static, private]

template<typename T , typename Pr >

T oned::RecursiveBisectionMinMax< T, Pr >::rec_bisection	(	int	procCount,
		const Pr	prefixSumArray,
		int	length,
		int *	cutIndexes,
		T
	)			[static]

Performs 1D recursive bisection algorithm

Parameters:

[in]	procCount	total number of processors
[in]	prefixSumArray	prefixSumArray
[in]	length	length of prefixSumArray
[out]	cutIndexes	cut point results

Returns:

Load of the max. loaded processor

template<typename T , typename Pr >

T oned::RecursiveBisectionMinMax< T, Pr >::rec_bisection_internal	(	int	numProc,
		int	low,
		int	high,
		const Pr	prefixSum,
		int *	cutPoints
	)			[static, private]

template<typename T , typename Pr >

int oned::RecursiveBisectionMinMax< T, Pr >::slopeAt	(	const Pr	prefixSum,
		int	low,
		int	high,
		int	leftProc,
		int	rightProc,
		int	point
	)			[static, private]

Finds the slope sign at a given point.

Parameters:

	prefixSum	1D prefix sum array
	low	Lowest index limit of prefix sub-array
	high	Highest index limit of prefix sub-array
	leftProc	number of procs to be assigned to the left
	rightProc	number of procs to be assigned to the right
	point	The index of cut point that we want to retrieve Bottleneck/Cut point sign

Returns:

Returns a signature -1 means we are in decreasing side of the function +1 means we are in increasing side of the function

---

The documentation for this class was generated from the following files:

• include/oned/rec_bisect_minmax.hpp
• include/oned/rec_bisect_minmax_impl.hpp