PaStiX Handbook: Symbol spliting

Data Structures
struct	extracblk_s
	Extra symbol cblk structure. More...

Typedefs
typedef struct extracblk_s	ExtraCblk_t
	Extra symbol cblk structure.

Functions
void	extraCblkInit (pastix_int_t cblknbr, ExtraCblk_t *extracblk)
	Initialize the extracblk structure. More...

void	extraCblkExit (ExtraCblk_t *extracblk)
	Free the extracblk structure. More...

void	extraCblkAdd (ExtraCblk_t *extracblk, pastix_int_t fcolnum, pastix_int_t lcolnum, int8_t selevtx)
	Add a new additional cblk defined by its first and last columns. More...

void	extraCblkMerge (const ExtraCblk_t extracblk, symbol_matrix_t newsymb, Cand **candtab)
	Merge the existing symbol structure with the additional information from the extracblk structure. More...

static void	extraCblkAlloc (ExtraCblk_t *extracblk)
	Allocate the extracblk structure. More...

static pastix_int_t	extraCblkInc (ExtraCblk_t *extracblk)
	Increment the number of extra cblk that can be stored. More...

static pastix_int_t	computeNbSplit (const BlendCtrl *ctrl, pastix_int_t width)
	Compute the number of cut for a given cblk width and number of candidates. More...

static pastix_int_t *	computeNbBlocksPerLine (const symbol_matrix_t *symbmtx, pastix_int_t frowsplit)
	Generate an array with the number of blocks facing each row to minimize the cuts. More...

static pastix_int_t	computeSmallestSplit (const pastix_int_t *nblocksperline, pastix_int_t step, pastix_int_t min, pastix_int_t max, pastix_int_t authorized_percent)
	Compute the cut that minimizes the generation of off-diagonal blocks. More...

static pastix_int_t	computeSmallestSplit_max (const pastix_int_t *nblocksperline, pastix_int_t step, pastix_int_t min, pastix_int_t max, pastix_int_t authorized_percent)
	Compute the cut that minimizes the generation of off-diagonal blocks. More...

static pastix_int_t	computeConstantSplit (const pastix_int_t *nblocksperline, pastix_int_t step, pastix_int_t min, pastix_int_t max, pastix_int_t authorized_percent)
	Compute a constant cut with the given parameters. More...

void	splitSmart (const BlendCtrl ctrl, const symbol_matrix_t symbmtx, ExtraCblk_t *extracblk)
	Split the column blocks to generate parallelism. More...

Detailed Description

This module contains all subroutines to initialize the candidates array for each supernode, as well as supernode properties that are defined by level such as 2D layouts and 2D tasks.

This module handles the splitting of the existing symbol matrix to generate more parallelism with finer granularity tasks.

Data Type Documentation

◆ extracblk_s

struct extracblk_s

Extra symbol cblk structure.

Definition at line 27 of file extracblk.h.

Data Fields
pastix_int_t	cblknbr	Number of cblk allocated
pastix_int_t	addcblk	Number of cblk created
pastix_int_t	addblok	Number of blok created
pastix_int_t	addblof	Number of blok created due to facing cblk splited
pastix_int_t *	sptcblk	Index for splitted cblk in the cblktab
pastix_int_t *	sptcbnb	Number of splitted cblk for a cblk
pastix_int_t	curcblk	Cursor for cblktab
pastix_int_t	sizcblk	Size of allocated cblktab
symbol_cblk_t *	cblktab	Array of column blocks [+1,based]

Function Documentation

◆ extraCblkInit()

void extraCblkInit	(	pastix_int_t	cblknbr,
		ExtraCblk_t *	extracblk
	)

Initialize the extracblk structure.

Parameters

[in]	cblknbr	The starting number of cblk that the structure can hold.
[in,out]	extracblk	Pointer to the allocated extracblk structure to initialize.

Definition at line 127 of file extracblk.c.

References extracblk_s::addblof, extracblk_s::addblok, extracblk_s::addcblk, extracblk_s::cblknbr, extracblk_s::cblktab, extracblk_s::curcblk, extracblk_s::sizcblk, extracblk_s::sptcblk, and extracblk_s::sptcbnb.

Referenced by splitSymbol().

◆ extraCblkExit()

void extraCblkExit ( ExtraCblk_t * extracblk )

Free the extracblk structure.

Parameters

[in,out] extracblk Pointer to the allocated extracblk structure to free.

Definition at line 154 of file extracblk.c.

References extracblk_s::cblktab, extracblk_s::curcblk, extracblk_s::sizcblk, extracblk_s::sptcblk, and extracblk_s::sptcbnb.

Referenced by splitSymbol().

◆ extraCblkAdd()

void extraCblkAdd	(	ExtraCblk_t *	extracblk,
		pastix_int_t	fcolnum,
		pastix_int_t	lcolnum,
		int8_t	selevtx
	)

Add a new additional cblk defined by its first and last columns.

Parameters

[in,out]	extracblk	Pointer to the extracblk structure to add the cblk.
[in]	fcolnum	Index of the first column in the new cblk.
[in]	lcolnum	Index of the last column in the new cblk.
[in]	selevtx	TODO

Definition at line 187 of file extracblk.c.

References symbol_cblk_s::bloknum, extracblk_s::cblktab, extraCblkInc(), symbol_cblk_s::fcolnum, symbol_cblk_s::lcolnum, and pastix_int_t.

Referenced by splitSmart().

◆ extraCblkMerge()

void extraCblkMerge	(	const ExtraCblk_t *	extracblk,
		symbol_matrix_t *	newsymb,
		Cand **	candtab
	)

Merge the existing symbol structure with the additional information from the extracblk structure.

Parameters

[in]	extracblk	Pointer to the extracblk structure that contains information about splited cblk.
[in,out]	newsymb	Symbol matrix to update. On exit, the symbol matrix structure is extended by the splited cblk described in extracblk structure.
[in,out]	candtab	On entry, the candtab aray associated to the input symbol matrix. On exit, the updated candtab array with the extended number of cblk.

Definition at line 222 of file extracblk.c.

References extracblk_s::addcblk, symbol_matrix_s::bloknbr, symbol_cblk_s::bloknum, symbol_matrix_s::bloktab, symbol_matrix_s::browtab, candExit(), candInit(), symbol_matrix_s::cblknbr, extracblk_s::cblktab, symbol_matrix_s::cblktab, extracblk_s::curcblk, symbol_blok_s::fcblknm, symbol_cblk_s::fcolnum, symbol_blok_s::frownum, symbol_blok_s::lcblknm, symbol_cblk_s::lcolnum, symbol_blok_s::lrownum, pastix_int_t, pastixSymbolBuildRowtab(), pastixSymbolExit(), extracblk_s::sptcblk, and extracblk_s::sptcbnb.

Referenced by splitSymbol().

◆ extraCblkAlloc()

static void extraCblkAlloc ( ExtraCblk_t * extracblk )

inlinestatic

Allocate the extracblk structure.

Parameters

[in,out] extracblk Allocate memory space to store extra cblk when they are created. The initial number is the one given at extraCblkInit().

Definition at line 39 of file extracblk.c.

References extracblk_s::cblknbr, extracblk_s::cblktab, pastix_int_t, extracblk_s::sizcblk, extracblk_s::sptcblk, and extracblk_s::sptcbnb.

Referenced by extraCblkInc().

◆ extraCblkInc()

static pastix_int_t extraCblkInc ( ExtraCblk_t * extracblk )

inlinestatic

Increment the number of extra cblk that can be stored.

If there is not enough space, the structure is reallocated to a larger space.

Parameters

[in,out] extracblk Allocate memory space to store extra cblk when they are created. The initial number is the one given at extraCblkInit().

Returns: the current index for the next cblk added to the structure.

Definition at line 83 of file extracblk.c.

References extracblk_s::cblknbr, extracblk_s::cblktab, extracblk_s::curcblk, extraCblkAlloc(), pastix_int_t, and extracblk_s::sizcblk.

Referenced by extraCblkAdd().

◆ computeNbSplit()

static pastix_int_t computeNbSplit	(	const BlendCtrl *	ctrl,
		pastix_int_t	width
	)

inlinestatic

Compute the number of cut for a given cblk width and number of candidates.

Parameters

[in]	ctrl	The blend control structure with the parameters.
[in]	width	The width of a cblk to cut.

Returns: The number of cut that should be done for this width.

Definition at line 79 of file splitsymbol.c.

References blendctrl_s::blcolmax, blendctrl_s::blcolmin, and pastix_int_t.

Referenced by splitSmart().

◆ computeNbBlocksPerLine()

static pastix_int_t* computeNbBlocksPerLine	(	const symbol_matrix_t *	symbmtx,
		pastix_int_t	frowsplit
	)

inlinestatic

Generate an array with the number of blocks facing each row to minimize the cuts.

Parameters

[in]	symbmtx	The symbol matrix structure.
[in]	frowsplit	The index of the first row that might be split to avoid computing it on the full matrix.

Returns: The array with the number of block on each row from frowsplit to n.

Definition at line 125 of file splitsymbol.c.

References symbol_matrix_s::bloknbr, symbol_matrix_s::bloktab, symbol_blok_s::frownum, symbol_blok_s::lrownum, symbol_matrix_s::nodenbr, and pastix_int_t.

Referenced by splitSmart().

◆ computeSmallestSplit()

static pastix_int_t computeSmallestSplit	(	const pastix_int_t *	nblocksperline,
		pastix_int_t	step,
		pastix_int_t	min,
		pastix_int_t	max,
		pastix_int_t	authorized_percent
	)

inlinestatic

Compute the cut that minimizes the generation of off-diagonal blocks.

This function searched first for a smaller block than the initial step to generate the cut, and then for a larger one that is return only if it is strictly better than the first solution found.

Parameters

[in]	nblocksperline	Array of size max with the number of blocks in front of the lines [0;max-1]
[in]	step	The starting cut to refine. 0 < step
[in]	min	TODO
[in]	max	The size of the nblocksperline array. nmax > 0.
[in]	authorized_percent	The authorized percentage move around the initial cut.

Returns: The optimal cut found.

Definition at line 200 of file splitsymbol.c.

References pastix_int_t.

Referenced by splitSmart().

◆ computeSmallestSplit_max()

static pastix_int_t computeSmallestSplit_max	(	const pastix_int_t *	nblocksperline,
		pastix_int_t	step,
		pastix_int_t	min,
		pastix_int_t	max,
		pastix_int_t	authorized_percent
	)

inlinestatic

Compute the cut that minimizes the generation of off-diagonal blocks.

This function searched for the largest cut in the range [step - authorized_percent, step + authorized_percent] that minimizes the number of off-diagonal blocks generated.

Parameters

[in]	nblocksperline	Array of size max with the number of blocks in front of the lines [0;max-1]
[in]	step	The starting cut to refine. 0 < step
[in]	min	TODO
[in]	max	The size of the nblocksperline array. nmax > 0.
[in]	authorized_percent	The authorized percentage move around the initial cut.

Returns: The optimal cut found.

Definition at line 275 of file splitsymbol.c.

References pastix_int_t.

Referenced by splitSmart().

◆ computeConstantSplit()

static pastix_int_t computeConstantSplit	(	const pastix_int_t *	nblocksperline,
		pastix_int_t	step,
		pastix_int_t	min,
		pastix_int_t	max,
		pastix_int_t	authorized_percent
	)

inlinestatic

Compute a constant cut with the given parameters.

Parameters

[in]	nblocksperline	Array of size max with the number of blocks in front of the lines [0;max-1]
[in]	step	The starting cut to refine. 0 < step
[in]	min	TODO
[in]	max	The size of the nblocksperline array. nmax > 0.
[in]	authorized_percent	The authorized percentage move around the initial cut.

Returns: The optimal cut found.

Definition at line 338 of file splitsymbol.c.

Referenced by splitSmart().

◆ splitSmart()

void splitSmart	(	const BlendCtrl *	ctrl,
		const symbol_matrix_t *	symbmtx,
		ExtraCblk_t *	extracblk
	)

Split the column blocks to generate parallelism.

This algorithm can use three different strategies to cut, two of them tries to minimize the number of generated off-diagnonal blocks, one with the minimal size, and the seoncd with teh maximal size in the error percentage around the initially computed split. The third strategy cuts regularly the column blocks without paying attention to the facing off-diagonal blocks.

Parameters

[in]	ctrl	The blend control structure.
[in]	symbmtx	The symbol matrix structure.
[in,out]	extracblk	The initialized structure to store the newly created column blocks. (Blocks are generated later during merge operation, see extraCblkMerge()).

Definition at line 377 of file splitsymbol.c.

References extracblk_s::addcblk, blendctrl_s::blcolmin, symbol_cblk_s::bloknum, symbol_matrix_s::bloktab, symbol_matrix_s::cblknbr, symbol_matrix_s::cblktab, computeConstantSplit(), computeNbBlocksPerLine(), computeNbSplit(), computeSmallestSplit(), computeSmallestSplit_max(), extracblk_s::curcblk, extraCblkAdd(), symbol_cblk_s::fcolnum, symbol_blok_s::frownum, symbol_cblk_s::lcolnum, pastix_int_t, extracblk_s::sptcblk, and extracblk_s::sptcbnb.

Referenced by splitSymbol().

Data Structures

Typedefs

Functions

Detailed Description

Data Type Documentation

◆ extracblk_s

Function Documentation

◆ extraCblkInit()

◆ extraCblkExit()

◆ extraCblkAdd()

◆ extraCblkMerge()

◆ extraCblkAlloc()

◆ extraCblkInc()

◆ computeNbSplit()

◆ computeNbBlocksPerLine()

◆ computeSmallestSplit()

◆ computeSmallestSplit_max()

◆ computeConstantSplit()

◆ splitSmart()