PaStiX Handbook: Candidate structure

Data Structures
struct	cand_s
	Processor candidate group to own a column blok. More...

Typedefs
typedef struct cand_s	Cand
	Processor candidate group to own a column blok.

Functions
Cand *	candInit (pastix_int_t cblknbr)
	Initialize the candtab array with default values. More...

void	candExit (Cand *candtab)
	Exit and free the candtab structure given. More...

int	candCheck (const Cand candtab, const symbol_matrix_t symbmtx)
	Check the correctness of the computed candidates. More...

void	candSave (const Cand candtab, pastix_int_t cblknbr, const char directory)
	Print the candidates array into the candtab.txt file. More...

void	candBuild (pastix_int_t level_tasks2d, pastix_int_t width_tasks2d, pastix_compress_when_t lr_when, pastix_int_t lr_width, Cand candtab, EliminTree etree, const symbol_matrix_t symbmtx, const CostMatrix costmtx)
	Finish to build the candtab array for the proportionnal mapping. More...

void	candUpdate (Cand candtab, EliminTree etree, const symbol_matrix_t symbmtx, const CostMatrix costmtx)
	Update the candtab array costs after the symbol split algorithm has been applied. More...

void	candSetClusterCand (Cand candtab, pastix_int_t cblknbr, const pastix_int_t core2clust, pastix_int_t coresnbr)
	Set the clusters candidates from the cores canditates. More...

void	candGenDot (const EliminTree etree, const Cand candtab, FILE *stream)
	Print the elimination tree in a dot file. More...

void	candGenDotLevel (const EliminTree etree, const Cand candtab, FILE *stream, pastix_int_t level)
	Print the first levels of the elimination tree in a dot file. More...

void	candGenCompressedDot (const EliminTree etree, const Cand candtab, FILE *stream)
	Print the compressed elimination tree in a dot file, where all nodes with the same candidates are merged together. More...

static double	candSubTreeBuild (pastix_int_t rootnum, Cand candtab, EliminTree etree, const symbol_matrix_t symbmtx, const CostMatrix costmtx, double *cripath)
	Recursive function to update the cost fields of the both the candtab array, and the elimination tree structure. More...

void	candSubTreeDistribFirstWidth (pastix_int_t rootnum, pastix_int_t cblktype, pastix_int_t ratiolimit2D, pastix_int_t ratiolimitLR, Cand candtab, const EliminTree etree, const symbol_matrix_t *symbmtx)
	Recursive function to compute the distribution of the nodes among the different levels. More...

pastix_int_t	candSubTreeDistribDeepestWidth (pastix_int_t rootnum, pastix_int_t cblktype, pastix_int_t ratiolimit2D, pastix_int_t ratiolimitLR, Cand candtab, const EliminTree etree, const symbol_matrix_t *symbmtx)
	Recursive function to compute the distribution of the nodes among the different levels. More...

pastix_int_t	candSubTreeDistribDeepestLevel (pastix_int_t rootnum, pastix_int_t cblktype, pastix_int_t level2D, pastix_int_t ratiolimitLR, Cand candtab, const EliminTree etree, const symbol_matrix_t *symbmtx)
	Recursive function to compute the distribution of the nodes among the different levels based on depth. More...

void	candSubTreeDistribFirstLevel (pastix_int_t rootnum, pastix_int_t cblktype, pastix_int_t level2D, pastix_int_t ratiolimitLR, Cand candtab, const EliminTree etree, const symbol_matrix_t *symbmtx)
	Recursive function to compute the distribution of the nodes among the different levels based on depth. 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.

Data Type Documentation

◆ cand_s

struct cand_s

Processor candidate group to own a column blok.

Definition at line 28 of file cand.h.

Data Fields
double	costlevel	Cost from root to node
pastix_int_t	treelevel	Level of the cblk in the elimination tree (depth from the root)
pastix_int_t	fcandnum	first processor number of this candidate group
pastix_int_t	lcandnum	last processor number of this candidate group
pastix_int_t	fccandnum	first cluster number of the cluster candidate group
pastix_int_t	lccandnum	last cluster number of the cluster candidate group
pastix_int_t	cluster	Cluster id on which the task will be executed
int8_t	cblktype	type of the distribution

Function Documentation

◆ candInit()

Cand * candInit ( pastix_int_t cblknbr )

Initialize the candtab array with default values.

Parameters

[in] cblknbr The size of the candtab array.

Returns: The array of size cblknbr+1 of Cand structure initialized.

Definition at line 48 of file cand.c.

References cand_s::cblktype, cand_s::cluster, cand_s::costlevel, cand_s::fcandnum, cand_s::fccandnum, cand_s::lcandnum, cand_s::lccandnum, pastix_int_t, and cand_s::treelevel.

Referenced by candGenCompressedDot(), extraCblkMerge(), and pastix_subtask_blend().

◆ candExit()

void candExit ( Cand * candtab )

Exit and free the candtab structure given.

Parameters

[in,out] candtab The candtab array to free.

Definition at line 83 of file cand.c.

Referenced by blendCtrlExit(), candGenCompressedDot(), and extraCblkMerge().

◆ candCheck()

int candCheck	(	const Cand *	candtab,
		const symbol_matrix_t *	symbmtx
	)

Check the correctness of the computed candidates.

Each node of the elimination tree must have a set of candidates included in its father's set.

Parameters

[in]	candtab	On entry, the array of candidates to check.
[in]	symbmtx	The symbol matrix structure associated to the candidate array.

Return values

0	if bad candidat set appear.
1	if success.

Definition at line 204 of file cand.c.

References symbol_cblk_s::bloknum, symbol_matrix_s::bloktab, symbol_matrix_s::cblknbr, symbol_matrix_s::cblktab, symbol_blok_s::fcblknm, and pastix_int_t.

Referenced by pastix_subtask_blend().

◆ candSave()

void candSave	(	const Cand *	candtab,
		pastix_int_t	cblknbr,
		const char *	directory
	)

Print the candidates array into the candtab.txt file.

Parameters

[in]	candtab	The array of size cblknbr to print in the file.
[in]	cblknbr	The size of the candtab array.
[in,out]	directory	Directory where to store the file. If NULL, initialized to pastix-XXXXXX, with XXXXXX a random generated string.

Definition at line 108 of file cand.c.

References pastix_fopenw(), and pastix_int_t.

◆ candBuild()

void candBuild	(	pastix_int_t	level_tasks2d,
		pastix_int_t	width_tasks2d,
		pastix_compress_when_t	lr_when,
		pastix_int_t	lr_width,
		Cand *	candtab,
		EliminTree *	etree,
		const symbol_matrix_t *	symbmtx,
		const CostMatrix *	costmtx
	)

Finish to build the candtab array for the proportionnal mapping.

This function defines which cblk are candidates to be stored with a 2D layout, computed as 2D tasks, and/or be part of the Schur complement. It also set the cost of each cblk and the total cost of each subtree.

Parameters

[in]	level_tasks2d	Defines the level in the elimination tree to switch from 1D to 2D tasks in the cblk flag. If < 0, automatic level is defined based on the width of the cblk with respect to the minimal width_tasks2d width. If 0, all cblks are tagged as 1D. If > 0, only the first level_tasks2d level of the tree are tagged as 2D.
[in]	width_tasks2d	If level_tasks2d < 0, defines the minimal width to keep the 2D flag on a goven cblk.
[in]	lr_when	Define if compression technics will be used or not. If not PastixCompressNever, then all cblk with a width larger than lr_width are tagged as compressible.
[in]	lr_width	Define the minimal width to flag a cblk as compressible if lr_when != PastixCompressNever.
[in,out]	candtab	Pointer to the global candtab array that needs to be initialized.
[in,out]	etree	Pointer to the elimination tree that needs to be construct on entry. On exit, the cost of each node, and the total cost of its associated subtree is initialized.
[in]	symbmtx	Pointer to the symbol matrix we are working with.
[in]	costmtx	Pointer to the cost matrix associated to the symbol matrix and that holds the cost of each cblk and blok.

Definition at line 709 of file cand.c.

References candSubTreeBuild(), cand_s::costlevel, eTreeRoot(), pastix_int_t, PastixCompressNever, and cand_s::treelevel.

Referenced by pastix_subtask_blend().

◆ candUpdate()

void candUpdate	(	Cand *	candtab,
		EliminTree *	etree,
		const symbol_matrix_t *	symbmtx,
		const CostMatrix *	costmtx
	)

Update the candtab array costs after the symbol split algorithm has been applied.

This function update the costs and critical path of each node after the symbol matrix has been split to generate more parallelism.

Parameters

[in,out]	candtab	Pointer to the global candtab array that needs to be updated.
[in,out]	etree	Pointer to the elimination tree that needs to be construct on entry. On exit, the cost of each node, and the total cost of its associated subtree is updated.
[in]	symbmtx	Pointer to the symbol matrix we are working with.
[in]	costmtx	Pointer to the cost matrix associated to the symbol matrix and that holds the cost of each cblk and blok.

Definition at line 804 of file cand.c.

References candSubTreeBuild(), cand_s::costlevel, eTreeRoot(), pastix_int_t, and cand_s::treelevel.

Referenced by splitSymbol().

◆ candSetClusterCand()

void candSetClusterCand	(	Cand *	candtab,
		pastix_int_t	cblknbr,
		const pastix_int_t *	core2clust,
		pastix_int_t	coresnbr
	)

Set the clusters candidates from the cores canditates.

Parameters

[in,out]	candtab	On entry, the array of candidates with the first and last core candidates initialized. On exit, the array of candidate with the first and last cluster candidate information updated.
[in]	cblknbr	The size of the candtab array.
[in]	core2clust	An array that defines the cluster (MPI process) that owns each core candidate.
[in]	coresnbr	The size of the core2clust array.

Definition at line 158 of file cand.c.

References cand_s::fcandnum, cand_s::fccandnum, cand_s::lcandnum, cand_s::lccandnum, and pastix_int_t.

Referenced by pastix_subtask_blend().

◆ candGenDot()

void candGenDot	(	const EliminTree *	etree,
		const Cand *	candtab,
		FILE *	stream
	)

Print the elimination tree in a dot file.

Parameters

[in]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]	stream	The file to which write the elimination tree in the dot format.

Definition at line 253 of file cand_gendot.c.

References cand_s::lcandnum, etree_node_s::ndecost, etree_node_s::ndepath, etree_s::nodenbr, etree_s::nodetab, pastix_int_t, etree_node_s::subcost, and etree_node_s::subpath.

Referenced by candGenCompressedDot(), and pastix_subtask_blend().

◆ candGenDotLevel()

void candGenDotLevel	(	const EliminTree *	etree,
		const Cand *	candtab,
		FILE *	stream,
		pastix_int_t	nblevel
	)

Print the first levels of the elimination tree in a dot file.

Parameters

[in]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]	stream	The file to which write the elimination tree in the dot format.
[in]	nblevel	The number of levels of the elimination tree to print.

Definition at line 405 of file cand_gendot.c.

References candGenDotLevelSub(), and eTreeRoot().

Referenced by pastix_subtask_blend().

◆ candGenCompressedDot()

void candGenCompressedDot	(	const EliminTree *	etree,
		const Cand *	candtab,
		FILE *	stream
	)

Print the compressed elimination tree in a dot file, where all nodes with the same candidates are merged together.

Parameters

[in]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information.
[in,out]	stream	The file to which write the elimination tree in the dot format.

Definition at line 441 of file cand_gendot.c.

References candExit(), candGenDot(), candInit(), compress_getNodeNbr(), compress_setSonsNbr(), eTreeExit(), eTreeInit(), eTreeRoot(), etree_s::nodenbr, and pastix_int_t.

Referenced by pastix_subtask_blend().

◆ candSubTreeBuild()

static double candSubTreeBuild	(	pastix_int_t	rootnum,
		Cand *	candtab,
		EliminTree *	etree,
		const symbol_matrix_t *	symbmtx,
		const CostMatrix *	costmtx,
		double *	cripath
	)

inlinestatic

Recursive function to update the cost fields of the both the candtab array, and the elimination tree structure.

Parameters

[in]	rootnum	Root of the subtree.
[in,out]	candtab	Pointer to the global candtab array where fields treelevel and costlevel are updated. Treelevel represent the depth of the node in the elimination tree, and costlevel the cost of the path from rootnum to the root of the tree.
[in,out]	etree	Pointer to the global elimination tree structure. The node fields total and subtree are updated. Total represents the total cost of of the current node only, and subtree the cost of the current node and all its descendants.
[in]	symbmtx	Pointer to the symbol matrix we are working with.
[in]	costmtx	Pointer to the cost matrix associated to the symbol matrix and that holds the cost of each cblk and blok.
[out]	cripath	On exit, contains the length of the critical path of the subtree.

Returns: The cost of the subtree.

Definition at line 271 of file cand.c.

References cost_matrix_s::cblkcost, cost(), cand_s::costlevel, eTreeSonI(), etree_node_s::ndecost, etree_node_s::ndepath, etree_s::nodetab, pastix_int_t, etree_node_s::sonsnbr, etree_node_s::subcost, etree_node_s::subpath, and cand_s::treelevel.

Referenced by candBuild(), and candUpdate().

◆ candSubTreeDistribFirstWidth()

void candSubTreeDistribFirstWidth	(	pastix_int_t	rootnum,
		pastix_int_t	cblktype,
		pastix_int_t	ratiolimit2D,
		pastix_int_t	ratiolimitLR,
		Cand *	candtab,
		const EliminTree *	etree,
		const symbol_matrix_t *	symbmtx
	)

Recursive function to compute the distribution of the nodes among the different levels.

This function defines which cblk are candidates to be stored with a 2D layout, computed as 2D tasks, compressible, and/or be part of the Schur complement. The criterion to remove the 2D task flag or the LR flag is the width of the cblk. As soon as one cblk that does not match the criterion is found, all its descendant loose the flag too.

Parameters

[in]	rootnum	Root of the subtree.
[in]	cblktype	List of flags that can be forwarded to rootnum and its descendants.
[in]	ratiolimit2D	Ratio that defines the minimal size to allow the flag 2D to be forwarded to the sons.
[in]	ratiolimitLR	Ratio that defines the minimal size to allow the flag LR to be forwarded to the sons.
[in,out]	candtab	Pointer to the global candtab array where field cblktype is updated. cblktype defines the optimization/properties that are defined on each cblk and which are defined by level in the tree.
[in]	etree	Pointer to the global elimination tree structure that is used to travel through the cblk, and affect the properies with the correct filiation property.
[in]	symbmtx	Pointer to the symbol matrix we are working with.

Definition at line 369 of file cand.c.

References symbol_matrix_s::cblktab, cand_s::cblktype, eTreeSonI(), symbol_cblk_s::fcolnum, symbol_cblk_s::lcolnum, etree_s::nodetab, pastix_int_t, symbol_matrix_s::schurfcol, and etree_node_s::sonsnbr.

◆ candSubTreeDistribDeepestWidth()

pastix_int_t candSubTreeDistribDeepestWidth	(	pastix_int_t	rootnum,
		pastix_int_t	cblktype,
		pastix_int_t	ratiolimit2D,
		pastix_int_t	ratiolimitLR,
		Cand *	candtab,
		const EliminTree *	etree,
		const symbol_matrix_t *	symbmtx
	)

Recursive function to compute the distribution of the nodes among the different levels.

This function defines which cblk are candidates to be stored with a 2D layout, computed as 2D tasks, compressible, and/or be part of the Schur complement. The criterion to remove the 2D task flag and the LR flag is the width of the cblk. This function enables the flags to the deepest nodes that respect the condition, as well as to all their ascendants in the elimination tree.

Parameters

[in]	rootnum	Root of the subtree.
[in]	cblktype	List of flags that can be forwarded to rootnum and its descendants.
[in]	ratiolimit2D	Ratio that defines the minimal size to allow the flag 2D for a cblk and its ascendants.
[in]	ratiolimitLR	Ratio that defines the minimal size to allow the flag LR for a cblk and its ascendants.
[in,out]	candtab	Pointer to the global candtab array where field cblktype is updated. cblktype defines the optimization/properties that are defined on each cblk and which are defined by level in the tree.
[in]	etree	Pointer to the global elimination tree structure that is used to travel through the cblk, and affect the properies with the correct filiation property.
[in]	symbmtx	Pointer to the symbol matrix we are working with.

Returns: the cblktype flag of the root of the subtree.

Definition at line 455 of file cand.c.

◆ candSubTreeDistribDeepestLevel()

pastix_int_t candSubTreeDistribDeepestLevel	(	pastix_int_t	rootnum,
		pastix_int_t	cblktype,
		pastix_int_t	level2D,
		pastix_int_t	ratiolimitLR,
		Cand *	candtab,
		const EliminTree *	etree,
		const symbol_matrix_t *	symbmtx
	)

Recursive function to compute the distribution of the nodes among the different levels based on depth.

This function defines which cblk are candidates to be stored with a 2D layout, computed as 2D tasks, and/or be part of the Schur complement. The criterion to remove the 2D task flag is the depth on the elimination tree.

Parameters

[in]	rootnum	Root of the subtree.
[in]	cblktype	List of flags that can be forwarded to rootnum and its descendants.
[in]	level2D	The number of levels of the tree that will be flagged as 2D tasks.
[in]	ratiolimitLR	Ratio that defines the minimal size to allow the flag LR for a cblk and its ascendants.
[in,out]	candtab	Pointer to the global candtab array where field cblktype is updated. cblktype defines the optimization/properties that are defined on each cblk and which are defined by level in the tree.
[in]	etree	Pointer to the global elimination tree structure that is used to travel through the cblk, and affect the properies with the correct filiation property.
[in]	symbmtx	Pointer to the symbol matrix we are working with.

Returns: the cblktype flag of the root of the subtree.

Definition at line 540 of file cand.c.

◆ candSubTreeDistribFirstLevel()

void candSubTreeDistribFirstLevel	(	pastix_int_t	rootnum,
		pastix_int_t	cblktype,
		pastix_int_t	level2D,
		pastix_int_t	ratiolimitLR,
		Cand *	candtab,
		const EliminTree *	etree,
		const symbol_matrix_t *	symbmtx
	)

Recursive function to compute the distribution of the nodes among the different levels based on depth.

Parameters

[in]	rootnum	Root of the subtree.
[in]	cblktype	List of flags that can be forwarded to rootnum and its descendants.
[in]	level2D	The number of levels of the tree that will be flagged as 2D tasks.
[in]	ratiolimitLR	Ratio that defines the minimal size to allow the flag LR for a cblk and its ascendants.
[in,out]	candtab	Pointer to the global candtab array where field cblktype is updated. cblktype defines the optimization/properties that are defined on each cblk and which are defined by level in the tree.
[in]	etree	Pointer to the global elimination tree structure that is used to travel through the cblk, and affect the properies with the correct filiation property.
[in]	symbmtx	Pointer to the symbol matrix we are working with.

Definition at line 622 of file cand.c.

Data Structures

Typedefs

Functions

Detailed Description

Data Type Documentation

◆ cand_s

Function Documentation

◆ candInit()

◆ candExit()

◆ candCheck()

◆ candSave()

◆ candBuild()

◆ candUpdate()

◆ candSetClusterCand()

◆ candGenDot()

◆ candGenDotLevel()

◆ candGenCompressedDot()

◆ candSubTreeBuild()

◆ candSubTreeDistribFirstWidth()

◆ candSubTreeDistribDeepestWidth()

◆ candSubTreeDistribDeepestLevel()

◆ candSubTreeDistribFirstLevel()