Analyze step

This group describes all the analyse routines that prepare data structures for the factorization and solve steps. More...

Modules
	Graph
	Functions to generate and manipulate the graph structure.
	Ordering
	Functions to generate and manipulate the order structure.
	Symbolic Factorization
	Functions to generate and manipulate the symbolic factorization structure.
	Blend

Functions
int	pastix_subtask_order (pastix_data_t *pastix_data, const spmatrix_t *spm, pastix_order_t *myorder)
	Computes the ordering of the given graph in parameters. More...
int	pastix_subtask_reordering (pastix_data_t *pastix_data)
	Apply the reordering step to compact off-diagonal blocks. More...
int	pastix_subtask_symbfact (pastix_data_t *pastix_data)
	Computes the symbolic factorization step. More...
int	pastix_subtask_blend (pastix_data_t *pastix_data)
	Compute the proportional mapping and the final solver structure. More...

Detailed Description

This group describes all the analyse routines that prepare data structures for the factorization and solve steps.

Function Documentation

pastix_subtask_order()

int pastix_subtask_order	(	pastix_data_t *	pastix_data,
		const spmatrix_t *	spm,
		pastix_order_t *	myorder
	)

Computes the ordering of the given graph in parameters.

The graph given by the user is used to generate a graph that can be used by ordering tools and symbolic factorization. This graph is stored in the pastix_data->graph to be pass over to the symbolic factorization. If it exists before to call this routine, then the current structure is cleaned and a new one is created. From this structure, an ordering is computed by the ordering tool chosen by IPARM_ORDERING and stored in pastix_data->ordemesh. At the end the full ordering stucture: pemutation, inverse permutation, partition, and partion tree is generated such that it can be used by any symbolic factorization algorithm. The user can get back the permutation generated by providing allocated ordering structure where the results is stored after computation.

This routine is affected by the following parameters: IPARM_VERBOSE, IPARM_ORDERING, IPARM_IO_STRATEGY

Parameters

[in,out]	pastix_data	The pastix_data structure that describes the solver instance. On exit, the field ordemesh is initialize with the result of the ordering. IPARM_ORDERING will determine which ordering tool is used. IPARM_IO_STRATEGY: If set to PastixIOSave, the results will be written on files on exit. If set to PastixIOLoad and IPARM_ORDERING is set to personal, then the ordering is loaded from files and no ordering is called. If the function pastix_setSchurUnknownList() function has been previously called to set the list of vertices to isolate in the schur complement, those vertices are isolated at the end of the matrix in a dedicated supernode.. If the function pastix_setZerosUnknownList() function has been previously called to set the list of diagonal elements that may cause problem during the factorization, those vertices are isolated at the end of the matrix in a dedicated supernode..
[in]	spm	The sparse matrix given by the user on which the ordering will be computed.
[in,out]	myorder	On entry, the permutation provide by the user if IPARM_ORDERING parameter set to PastixOrderPersonal. Not read otherwise. On exit, if the structure attributs != NULL and IPARM_ORDERING parameter is not set to PastixOrderPersonal, contains the permutation generated. Otherwise, it is not referenced.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORY	if one allocation failed,
PASTIX_ERR_INTEGER_TYPE	if Scotch integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNAL	if an error occurs internally to Scotch.

Definition at line 97 of file pastix_subtask_order.c.

References pastix_order_s::cblknbr, pastix_data_s::csc, pastix_data_s::dparm, DPARM_ORDER_TIME, eTreeExit(), pastix_data_s::graph, graphBase(), graphExit(), graphGatherInPlace(), graphIsolate(), graphPrepare(), graphScatterInPlace(), pastix_data_s::iparm, IPARM_AMALGAMATION_LVLBLAS, IPARM_AMALGAMATION_LVLCBLK, IPARM_COMPRESS_WHEN, IPARM_FLOAT, IPARM_INCOMPLETE, IPARM_IO_STRATEGY, IPARM_LEVEL_OF_FILL, IPARM_ORDERING, IPARM_SPLITTING_STRATEGY, IPARM_TASKS2D_LEVEL, IPARM_TASKS2D_WIDTH, IPARM_VERBOSE, pastix_data_s::ordemesh, orderAddIsolate(), orderAmalgamate(), orderApplyLevelOrder(), orderBuildEtree(), orderComputeMetis(), orderComputePersonal(), orderComputePTScotch(), orderComputeScotch(), orderDraw(), orderFindSupernodes(), orderSupernodes(), pastix_data_s::pastix_comm, PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, PastixCompressNever, PastixIOSave, pastixOrderAlloc(), pastixOrderBase(), pastixOrderBcast(), pastixOrderCheck(), pastixOrderCopy(), pastixOrderExit(), PastixOrderMetis, PastixOrderPersonal, PastixOrderPtScotch, pastixOrderSave(), PastixOrderScotch, PastixSplitNot, PastixVerboseNot, PastixVerboseYes, pastix_order_s::peritab, pastix_order_s::permtab, pastix_data_s::procnum, pastix_order_s::rangtab, pastix_data_s::schur_list, pastix_data_s::schur_n, pastix_order_s::sndenbr, pastix_order_s::sndetab, pastix_data_s::steps, pastix_order_s::treetab, pastix_data_s::zeros_list, and pastix_data_s::zeros_n.

Referenced by pastix(), and pastix_task_analyze().

pastix_subtask_reordering()

int pastix_subtask_reordering

(

pastix_data_t *

pastix_data

)

Apply the reordering step to compact off-diagonal blocks.

During this step, unknowns are reordered within each supernode to compact off-diagonal blocks. It takes as input the ordering provided by pastix_subtask_order(), and the symbolic factorization computed by pastix_subtask_symbfact(). It returns boths structures Order and Symbol updated.

This function reorders the unknowns of the problem based on traveller salesman problem to gather together the contibutions facing each supernodes.

See reordering paper: http://epubs.siam.org/doi/10.1137/16M1062454.

This routine is affected by the following parameters: IPARM_VERBOSE, IPARM_IO_STRATEGY, IPARM_REORDERING_SPLIT, IPARM_REORDERING_STOP

Parameters

[in,out]

pastix_data

The pastix_data structure that describes the solver instance. On exit, the field symbmtx is updated with the new symbol matrix, and the field ordemesh is updated with the new ordering. IPARM_IO_STRATEGY will enable to load/store the result to files. If set to PastixIOSave, the symbmtx and the generated ordemesh are dump to file. If set to PastixIOLoad, the symbmtx (only) is loaded from the files.

Return values

PASTIX_SUCCESS	on successful exit
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect.

Check parameters

Reorder the rows of each supernode in order to compact coupling blocks

Definition at line 60 of file pastix_subtask_reordering.c.

References pastix_data_s::iparm, IPARM_REORDERING_STOP, IPARM_VERBOSE, pastix_data_s::ordemesh, PASTIX_ERR_BADPARAMETER, pastix_int_t, PastixVerboseNot, pastix_data_s::procnum, pastix_order_s::rangtab, and pastix_order_s::treetab.

Referenced by pastix_task_analyze().

pastix_subtask_symbfact()

int pastix_subtask_symbfact

(

pastix_data_t *

pastix_data

)

Computes the symbolic factorization step.

Computes the symbolic matrix structure and if required the amalgamated supernode partition.

The function is a centralized algorithm to generate the symbol matrix structure associated to the problem. It takes as input the ordemesh structure (permutation array, inverse permutation array, and optionnal supernodes array) and returns the modified ordemesh structure if changed, and the symbolic structure.

• If a direct factorization is performed, the structure is generated with pastixSymbolFaxDirect() thanks to the information provided by the ordering steps (permutation, partition, and elimination tree).
• If an ILU(k) factorization is performed, pastixSymbolFaxILUk() is used to generate the symbol matrix structure. It requires an intermediate step to generate the csr graph of L with incomplete factorization.

Both algorithms are working with a centralized version of the graph and are replicated on every nodes. If a distributed graph has been used, it is gathered on each node to compute the symbol matrix.

This routine is affected by the following parameters: IPARM_VERBOSE, IPARM_INCOMPLETE, IPARM_LEVEL_OF_FILL, IPARM_IO_STRATEGY, IPARM_FLOAT, IPARM_FACTORIZATION

On exit, the following parameters are set: IPARM_NNZEROS, DPARM_FACT_THFLOPS, DPARM_FACT_RLFLOPS

Parameters

[in,out]

pastix_data

The pastix_data structure that describes the solver instance. On exit, the field symbmtx is initialized with the symbol matrix, and the field ordemesh is updated if the supernode partition is computed. IPARM_INCOMPLETE switches the factorization mode from direct to ILU(k). IPARM_LEVEL_OF_FILL defines the level of incomplete factorization if IPARM_INCOMPLETE == 1. If IPARM_LEVEL_OF_FILL < 0, the full pattern is generated as for direct factorization. IPARM_IO_STRATEGY will enable to load/store the result to files. If set to PastixIOSave, the symbmtx and the generated ordemesh is dump to file. If set to PastixIOLoad, the symbmtx (only) is loaded from the files.

Return values

PASTIX_SUCCESS	on successful exit
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect.

Definition at line 86 of file pastix_subtask_symbfact.c.

References symbol_matrix_s::baseval, symbol_matrix_s::cblknbr, symbol_matrix_s::cblktab, pastix_data_s::csc, pastix_data_s::dir_global, pastix_data_s::dparm, DPARM_FACT_RLFLOPS, DPARM_FACT_THFLOPS, DPARM_SYMBFACT_TIME, pastix_data_s::graph, graphBase(), graphGatherInPlace(), pastix_data_s::iparm, IPARM_DOF_NBR, IPARM_FACTORIZATION, IPARM_FLOAT, IPARM_INCOMPLETE, IPARM_IO_STRATEGY, IPARM_LEVEL_OF_FILL, IPARM_NNZEROS, IPARM_VERBOSE, pastix_data_s::ordemesh, pastix_data_s::pastix_comm, PASTIX_ERR_BADPARAMETER, pastix_fopen(), pastix_fopenw(), pastix_gendirectories(), pastix_int_t, PASTIX_SUCCESS, PastixIOLoad, PastixIOSave, pastixOrderBase(), pastixOrderCheck(), pastixSymbolBase(), pastixSymbolBuildRowtab(), pastixSymbolCheck(), pastixSymbolDraw(), pastixSymbolExit(), pastixSymbolFaxDirect(), pastixSymbolFaxILUk(), pastixSymbolGetFlops(), pastixSymbolGetNNZ(), pastixSymbolInit(), pastixSymbolLoad(), pastixSymbolPrintStats(), pastixSymbolRealloc(), pastixSymbolSave(), PastixVerboseNo, PastixVerboseNot, pastix_data_s::procnum, pastix_data_s::schur_n, symbol_matrix_s::schurfcol, pastix_order_s::selevtx, pastix_data_s::steps, and pastix_data_s::symbmtx.

Referenced by pastix(), and pastix_task_analyze().

pastix_subtask_blend()

int pastix_subtask_blend

(

pastix_data_t *

pastix_data

)

Compute the proportional mapping and the final solver structure.

This function computes the structural information required to factorize and solve the problem. It requires an ordering structure, as well as the symbolic factorization structure. It computes a solver structure that contains all informations, architecture and problem dependent, to efficiently solve the system. On exit, the symbol structure is destroyed and only local uncompressed information is stored in the solver structure.

This routine is affected by, or returns, the following parameters: IPARM_CUDA_NBR, IPARM_TASKS2D_LEVEL, IPARM_TASKS2D_WIDTH, IPARM_COMPRESS_WHEN, IPARM_COMPRESS_MIN_WIDTH, IPARM_DOF_NBR, IPARM_FACTORIZATION, IPARM_FLOAT, IPARM_GPU_CRITERIUM, IPARM_GPU_MEMORY_PERCENTAGE, IPARM_GPU_NBR, IPARM_INCOMPLETE, IPARM_MAX_BLOCKSIZE, IPARM_MIN_BLOCKSIZE, IPARM_NNZEROS, IPARM_NNZEROS_BLOCK_LOCAL, IPARM_STARPU, IPARM_THREAD_NBR, IPARM_VERBOSE

DPARM_BLEND_TIME, DPARM_FACT_FLOPS, DPARM_FACT_RLFLOPS, DPARM_FACT_THFLOPS, DPARM_FILL_IN, DPARM_PRED_FACT_TIME, DPARM_SOLV_FLOPS

This function is constructed as a sequence of steps that are described below.

Construct an elimination tree

A elimination tree structure is constructed out of the symbol matrix to be able to traverse the tree in a top-down fashion for the proportionnal mapping step.

Construct the cost matrix

For each column-block, and block of the symbolic structure, the cost of each operation is computed to evaluate the cost of each branch of the elimination tree. Costs of the blocks are the cost of the update generated out of this block when used as the B matrix in the GEMM update. Costs of the column block is the total cost associated to it: factorization, solve, and update in a right-looking algorithm. This means that the update cost is the one generated by this column block, and not the one received by the column-block.

Construct the candidate array

Dispatch properties such as low-rank compression, 2D tasks from the top to the bottom of the tree. Candidate array, and elimination tree are computed, and updated, simultaneously with the costs computed previously. This step is impacted by IPARM_TASKS2D_LEVEL and IPARM_TASKS2D_WIDTH that defines the minimal width of nodes which can forward 2D tasks property to their sons. Similarly, IPARM_COMPRESS_WHEN and IPARM_COMPRESS_MIN_WIDTH defines the minimal width of nodes which can forward low-rank property to their sons.

Proportionnal Mapping

This step performs the actual proportional mapping algorithm to define the subset of candidates to compute each supernode.

Split symbol matrix

Once the proportionnal mapping is performed on the original set of supernodes, the symbol matrix is split in smaller supernodes/blocks to allow for more parallelism.

Simulation

The simulation step defines the actual mapping per core of each supernode based on a simulation of the numerical factorization where each task is attributed to the first resource available to compute it.

Solver structure generation

Out of the previous step, the solver generator builds the local structure that is required for the numerical factorization and solve steps. It is mainly represented by a CSC like structure of the local blocks, linked to a CSR for the solve step and the structure that will holds the coefficients of the factorized matrix.

Parameters

[in,out]

pastix_data

The pastix_data structure that describes the solver instance.

Return values

PASTIX_SUCCESS	on successful exit
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect.
PASTIX_ERR_OUTOFMEMORY	if one allocation failed.

Generate the final solver structure that collects data from the different simulation structures and convert to local numbering

Definition at line 121 of file pastix_subtask_blend.c.

References blendctrl_s::allcand, blendCtrlExit(), blendCtrlInit(), candBuild(), candCheck(), candGenCompressedDot(), candGenDot(), candGenDotLevel(), candInit(), candSetClusterCand(), blendctrl_s::candtab, symbol_matrix_s::cblknbr, blendctrl_s::clustnbr, solver_matrix_s::coefnbr, blendctrl_s::core2clust, costMatrixBuild(), costMatrixExit(), blendctrl_s::costmtx, blendctrl_s::count_ops, pastix_data_s::csc, blendctrl_s::debug, pastix_data_s::dir_global, symbol_matrix_s::dof, pastix_data_s::dparm, DPARM_BLEND_TIME, DPARM_FACT_RLFLOPS, DPARM_FACT_THFLOPS, DPARM_FILL_IN, DPARM_PRED_FACT_TIME, DPARM_SOLV_FLOPS, blendctrl_s::etree, eTreeBuild(), eTreeExit(), eTreeRoot(), pastix_data_s::graph, graphExit(), pastix_data_s::inter_node_comm, pastix_data_s::inter_node_procnum, pastix_data_s::iparm, IPARM_COMPRESS_MIN_WIDTH, IPARM_COMPRESS_WHEN, IPARM_FACTORIZATION, IPARM_FLOAT, IPARM_NNZEROS, IPARM_NNZEROS_BLOCK_LOCAL, IPARM_SPLITTING_STRATEGY, IPARM_VERBOSE, pastix_data_s::isched, blendctrl_s::leader, blendctrl_s::level_tasks2d, blendctrl_s::local_nbcores, blendctrl_s::local_nbctxts, blendctrl_s::local_nbthrds, blendctrl_s::nocrossproc, etree_s::nodetab, pastix_data_s::ordemesh, PASTIX_ERR_BADPARAMETER, pastix_fopenw(), pastix_gendirectories(), pastix_int_t, PastixFactLU, PastixSplitKwayProjections, pastixSymbolCheck(), pastixSymbolDraw(), pastixSymbolDrawMap(), pastixSymbolExit(), pastixSymbolGetFlops(), pastixSymbolGetNNZ(), pastixSymbolPrintStats(), pastixSymbolSave(), PastixVerboseNo, PastixVerboseNot, PastixVerboseYes, pastix_data_s::procnum, propMappTree(), blendctrl_s::ricar, simuExit(), simuInit(), simuRun(), simuTaskBuild(), pastix_order_s::sndenbr, solverCheck(), solverExit(), solverMatrixGen(), solverMatrixGenSeq(), solverPrintStats(), solverRealloc(), pastix_data_s::solvglob, pastix_data_s::solvloc, pastix_data_s::solvmatr, splitSymbol(), pastix_data_s::steps, etree_node_s::subcost, etree_node_s::subpath, pastix_data_s::symbmtx, simuctrl_s::tasknbr, blendctrl_s::total_nbcores, blendctrl_s::up_after_split, and blendctrl_s::width_tasks2d.

Referenced by pastix(), and pastix_task_analyze().