Public Member Functions | Static Public Member Functions | Private Attributes

twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX > Class Template Reference

implements a PxQ jagged partitioning heuristic using the first dimension as main dimension. More...

#include <twod/her_jag_2d.hpp>

Inheritance diagram for twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >:
twod::PartBase< T, Pr >

Detailed Description

template<typename T, typename Pr, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, false > &prefixSumArray, int length, int *cutIndexes, T) onedalgoY = oned::NicolPlus<T, util::Aggreg2Dto1D<T, Pr, false> >::nicol_plus, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, true > &prefixSumArray, int length, int *cutIndexes, T) onedalgoX = oned::NicolPlus<T, util::Aggreg2Dto1D<T, Pr, true> >::nicol_plus>
class twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >

implements a PxQ jagged partitioning heuristic using the first dimension as main dimension.

The heuristic partitions the main dimension in a number of stripes given by setP(). The elements along the auxilary dimension are (virtually) summed into a one dimensionnal array which is partitioned using onedalgoX (oned::NicolPlus by default). Then each stripe is partitioned using onedalgoY (oned::NicolPlus by default).

This heurisitc has been proposed numerous times for instance in "Ali Pinar and Cevdet Aykanat, Sparse Matrix Decomposition with Optimal Load Balancing, HiPC 1997"

Parameters:
T data type of instance matrix
Pr data type of 2D matrix
*onedalgoY algorithm to be used to fix columns
*onedalgoX algorithm to be used to fix rows

List of all members.

Public Member Functions

 JagPQHeurHor ()
virtual T part (int procCount, const Pr &prefixSumArray, util::RectList< T, Pr > &parts)
void setP (int P)
 selects the number of stripes in the main dimension
virtual ~JagPQHeurHor ()

Static Public Member Functions

static T her_jag_2d_internal (int procX, int procY, const Pr &prefixSumArray, util::RectList< T, Pr > &parts)

Private Attributes

int P

Constructor & Destructor Documentation

template<typename T , typename Pr , T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, false > &prefixSumArray, int length, int *cutIndexes, T) onedalgoY, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, true > &prefixSumArray, int length, int *cutIndexes, T) onedalgoX>
twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >::JagPQHeurHor (  ) 
template<typename T , typename Pr , T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, false > &prefixSumArray, int length, int *cutIndexes, T) onedalgoY, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, true > &prefixSumArray, int length, int *cutIndexes, T) onedalgoX>
twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >::~JagPQHeurHor (  )  [virtual]

Member Function Documentation

template<typename T , typename Pr , T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, false > &prefixSumArray, int length, int *cutIndexes, T) onedalgoY, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, true > &prefixSumArray, int length, int *cutIndexes, T) onedalgoX>
T twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >::her_jag_2d_internal ( int  procX,
int  procY,
const Pr prefixSumArray,
util::RectList< T, Pr > &  parts 
) [static]
template<typename T , typename Pr , T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, false > &prefixSumArray, int length, int *cutIndexes, T) onedalgoY, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, true > &prefixSumArray, int length, int *cutIndexes, T) onedalgoX>
T twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >::part ( int  procCount,
const Pr prefixSumArray,
util::RectList< T, Pr > &  parts 
) [virtual]

Applies 2d heuristic jagged partitioning to a given 2d prefixSumArray

Parameters:
[in] procCount is the number of processors
[in] prefixSumArray first column and first row consists of zero only. But the borders of rectangles in rect_list never touch this area (index 0 in row or column)
[out] parts must be allocated before calling this function. List of rectangles that form the partition.
Returns:
Total load of the maximum loaded rectangle.

Implements twod::PartBase< T, Pr >.

template<typename T , typename Pr , T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, false > &prefixSumArray, int length, int *cutIndexes, T) onedalgoY, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, true > &prefixSumArray, int length, int *cutIndexes, T) onedalgoX>
void twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >::setP ( int  P  ) 

selects the number of stripes in the main dimension

Parameters:
P number of stripes in the main dimension. If 0, the number of stripes will be computed at runtime by taking the square root of the number of processors.

Member Data Documentation

template<typename T, typename Pr, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, false > &prefixSumArray, int length, int *cutIndexes, T) onedalgoY = oned::NicolPlus<T, util::Aggreg2Dto1D<T, Pr, false> >::nicol_plus, T(*)(int procCount, const util::Aggreg2Dto1D< T, Pr, true > &prefixSumArray, int length, int *cutIndexes, T) onedalgoX = oned::NicolPlus<T, util::Aggreg2Dto1D<T, Pr, true> >::nicol_plus>
int twod::JagPQHeurHor< T, Pr, onedalgoY, onedalgoX >::P [private]

The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Friends Defines