util::ParametricSearch< T, Pr > Class Template Reference

contains several probe algorithms used for 1d partitioning. More...

#include <util/parametric_search.hpp>

---

Detailed Description

template<typename T, typename Pr>
class util::ParametricSearch< T, Pr >

contains several probe algorithms used for 1d partitioning.

List of all members.

Static Public Member Functions
static int	probeEnhanced (T bottleneck, int cutNumber, const Pr &prefixSumArray, int length, int lowerIndex)
static int	probe (T bottleneck, int cutNumber, const Pr &prefixSumArray, int length)
static int	probeCut (T bottleneck, int cutNumber, const Pr &prefixSumArray, int length, int *cuts)
static int	rprobe (const Pr &wpre, int length, const T &bottleneck, int numproc, int *s, const int *sl, const int *sh)
static int	rprobe_interval (const Pr &wpre, int length, const T &bottleneck, int numproc, int *s, const int *sl, const int *sh)
static int	probeCut_interval (T bottleneck, int cutNumber, const Pr &prefixSumArray, int length, int *cuts)

---

Member Function Documentation

template<typename T , typename Pr >

int util::ParametricSearch< T, Pr >::probe	(	T	bottleneck,
		int	cutNumber,
		const Pr &	prefixSumArray,
		int	length
	)			[static]

Check if it is possible to partition a 1D array given processor number and bottleneck.

Parameters:

	bottleneck	Bottleneck value to be tested.
	cutNumber	The number of cut points (That corrosponds to P-1 where P is the processor number)
	prefixSumArray	1D prefix sum array with prefixSumArray[0]=0 and prefixSumArray[i]=prefixSumArray[i-1]+array[i]. array variable is the original array.
	length	length of prefixSumArray

Returns:

1 if it is possible to partition with given bottleneck, 0 if not length is the length of prefixSumArray

template<typename T , typename Pr >

int util::ParametricSearch< T, Pr >::probeCut	(	T	bottleneck,
		int	cutNumber,
		const Pr &	prefixSumArray,
		int	length,
		int *	cuts
	)			[static]

Save cut points in an array given processor number and bottleneck.

Parameters:

[in]	bottleneck	Bottleneck value to be tested.
[in]	cutNumber	The number of cut points (That corrosponds to P-1 where P is the processor number)
[in]	prefixSumArray	1D prefix sum array with prefixSumArray[0]=0 and prefixSumArray[i]=prefixSumArray[i-1]+array[i]. array variable is the original array.
[in]	length	length of prefixSumArray.
[out]	cuts	Saved cut points. Must be preallocated to cutNumber length.

Returns:

1 if it is possible to partition with given bottleneck, 0 if not length is the length of prefixSumArray

template<typename T , typename Pr >

int util::ParametricSearch< T, Pr >::probeCut_interval	(	T	bottleneck,
		int	cutNumber,
		const Pr &	prefixSumArray,
		int	length,
		int *	cuts
	)			[static]

Save cut points in an array given processor number and bottleneck. Uses interval notation defined in util::PrefixSumArray1DOfTInterval.

Parameters:

[in]	bottleneck	Bottleneck value to be tested.
[in]	cutNumber	The number of cut points (That corrosponds to P-1 where P is the processor number)
[in]	prefixSumArray	1D prefix sum array with prefixSumArray[0]=0 and prefixSumArray[i]=prefixSumArray[i-1]+array[i]. array variable is the original array.
[in]	length	length of prefixSumArray.
[out]	*cuts	Saved cut points. Must be preallocated to cutNumber length.

Returns:

1 if it is possible to partition with given bottleneck, 0 if not length is the length of prefixSumArray

template<typename T , typename Pr >

static int util::ParametricSearch< T, Pr >::probeEnhanced	(	T	bottleneck,
		int	cutNumber,
		const Pr &	prefixSumArray,
		int	length,
		int	lowerIndex
	)			[static]

template<typename T , typename Pr >

int util::ParametricSearch< T, Pr >::rprobe	(	const Pr &	wpre,
		int	length,
		const T &	bottleneck,
		int	numproc,
		int *	s,
		const int *	sl,
		const int *	sh
	)			[static]

Check if it is possible to partition a 1D array given processor number and bottleneck. described in pinar04

Parameters:

[in]	wpre	1D prefix sum array with wpre[0]=0 and wpre[i]=wpre[i-1]+array[i]. array variable is the original array.
[in]	length	length of wpre
[in]	bottleneck	Bottleneck value to be tested.
[in]	numproc	Processor number.
[out]	s	Resulting cut points if it is possible to partition. Must be preallocated to numproc-1
[in]	sl	Lower bound of cut index for processor i is sl[i] for numproc and bottleneck.
[in]	sh	Upper bound of cut index for processor i is sl[i] for numproc and bottleneck.

Returns:

1 if it is possible to partition with given bottleneck, 0 if not length is the length of prefixSumArray

template<typename T , typename Pr >

int util::ParametricSearch< T, Pr >::rprobe_interval	(	const Pr &	wpre,
		int	length,
		const T &	bottleneck,
		int	numproc,
		int *	s,
		const int *	sl,
		const int *	sh
	)			[static]

Check if it is possible to partition a 1D array given processor number and bottleneck. Uses interval notation defined in util::PrefixSumArray1DOfTInterval.

Parameters:

[in]	wpre	1D prefix sum array with wpre[0]=0 and wpre[i]=wpre[i-1]+array[i]. array variable is the original array.
[in]	length	length of wpre
[in]	bottleneck	Bottleneck value to be tested.
[in]	numproc	Processor number.
[out]	s	Resulting cut points if it is possible to partition. Must be preallocated to numproc-1
[in]	sl	Lower bound of cut index for processor i is sl[i] for numproc and bottleneck.
[in]	sh	Upper bound of cut index for processor i is sl[i] for numproc and bottleneck.

Returns:

1 if it is possible to partition with given bottleneck, 0 if not length is the length of prefixSumArray

---

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

• include/util/parametric_search.hpp
• include/util/parametric_search_impl.hpp