PaStiX Handbook  6.3.2

Functions

static void sequential_reorder (pastix_data_t *pastix_data, pastix_int_t maxdepth, pastix_int_t *levels)
 Sequential version for reordering. More...
 
void thread_preorder_basic_stategy (isched_thread_t *ctx, void *args)
 Parallel basic version for reordering. More...
 
void thread_preorder_zigzag_stategy (isched_thread_t *ctx, void *args)
 Parallel improved version for reordering. More...
 
static void thread_preorder (isched_thread_t *ctx, void *args)
 Function called by each thread. More...
 
static double cost (symbol_cblk_t *cblk)
 Computes the cost of a cblk. More...
 
static void order_tasks (isched_t *ctx, struct args_reorder_t *args)
 Order cblks for each process. More...
 
static void thread_reorder (pastix_data_t *pastix_data, pastix_int_t maxdepth, pastix_int_t *levels)
 Prepare arguments for parallel subroutines and order cblks. More...
 
void symbol_reorder (pastix_data_t *pastix_data, pastix_int_t maxdepth, pastix_int_t *levels)
 Reorder all node. More...
 
static pastix_int_t compute_cblklevel (const pastix_int_t *treetab, const pastix_int_t *levels, pastix_int_t cblknum)
 Compute the level of supernode cblknum, with Scotch treetab. More...
 
static pastix_int_t hamming_distance (pastix_int_t **vectors, pastix_int_t *vectors_size, pastix_int_t xi, pastix_int_t xj, pastix_int_t stop)
 Compute the distance between two rows of a same supernode. More...
 
static void symbol_reorder_tsp (pastix_int_t size, pastix_order_t *order, pastix_int_t sn_id, pastix_int_t **lw_vectors, pastix_int_t *lw_vectors_size, pastix_int_t **up_vectors, pastix_int_t *up_vectors_size, pastix_int_t stop_criterion)
 Reorder rows of a supernode with the nearest insertion TSP heuristic. More...
 
void symbol_reorder_cblk (const symbol_matrix_t *symbptr, const symbol_cblk_t *cblk, pastix_order_t *order, const pastix_int_t *levels, pastix_int_t *depthweight, pastix_int_t depthmax, pastix_int_t split_level, pastix_int_t stop_criterion)
 Reorder a supernode. More...
 

Detailed Description

Function Documentation

◆ sequential_reorder()

static void sequential_reorder ( pastix_data_t pastix_data,
pastix_int_t  maxdepth,
pastix_int_t levels 
)
inlinestatic

Sequential version for reordering.

This algorithm reorders cblks. (Sequential version).

Parameters
[in,out]pastix_dataThe pastix_data providing the scheduler, the symbolic structure, and the ordering providing by Scotch that will be updated with the new rows permutation for each supernode. It will also gives a stopping criterion the reordering of each supernode. The split_level field activates the split level heuristic, dividing distances computations into two stages: for upper and for lower contruibuting supernodes.
[out]levelsThe pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside.
[in]maxdepthThe maximum depth in the elimination tree.

Definition at line 54 of file symbol_reorder.c.

References symbol_matrix_s::cblknbr, symbol_matrix_s::cblktab, symbol_cblk_s::fcolnum, pastix_data_s::iparm, IPARM_REORDERING_SPLIT, IPARM_REORDERING_STOP, pastix_data_s::ordemesh, pastix_int_t, symbol_matrix_s::schurfcol, pastix_data_s::symbmtx, and symbol_reorder_cblk().

◆ thread_preorder_basic_stategy()

void thread_preorder_basic_stategy ( isched_thread_t *  ctx,
void *  args 
)

Parallel basic version for reordering.

This algorithm reorders cblks. Tasks are cut such as every thread has the same number of task. (Parallel version)

Parameters
[in]ctxThe context of the current thread. This provides information about total number of thread used and the rank of the current thread.
[in,out]argsThe argument for reordering functions.

Definition at line 129 of file symbol_reorder.c.

References symbol_matrix_s::cblknbr, symbol_matrix_s::cblktab, pastix_data_s::iparm, IPARM_REORDERING_SPLIT, IPARM_REORDERING_STOP, pastix_data_s::ordemesh, pastix_int_t, pastix_data_s::symbmtx, and symbol_reorder_cblk().

Referenced by thread_preorder().

◆ thread_preorder_zigzag_stategy()

void thread_preorder_zigzag_stategy ( isched_thread_t *  ctx,
void *  args 
)

Parallel improved version for reordering.

This algorithm reorders cblks after ordering them according to their size. Priority queue are used to sort cblks increasing their cost and process decreasing their load. (Parallel version)

Parameters
[in]ctxThe context of the current thread. This provides information about total number of thread used and the rank of the current thread.
[in,out]argsThe argument for reordering functions.

Definition at line 195 of file symbol_reorder.c.

References symbol_matrix_s::cblktab, extendint_Read(), extendint_Size(), pastix_data_s::iparm, IPARM_REORDERING_SPLIT, IPARM_REORDERING_STOP, pastix_data_s::ordemesh, pastix_int_t, pastix_data_s::symbmtx, and symbol_reorder_cblk().

Referenced by thread_preorder().

◆ thread_preorder()

static void thread_preorder ( isched_thread_t *  ctx,
void *  args 
)
inlinestatic

Function called by each thread.

This function select and call a strategy to reorder cblks. (Parallel version)

Parameters
[in]ctxThe context of the current thread. This provides information about total number of thread used and the rank of the current thread.
[in,out]argsThe argument for reordering functions.

Definition at line 255 of file symbol_reorder.c.

References thread_preorder_basic_stategy(), and thread_preorder_zigzag_stategy().

Referenced by thread_reorder().

◆ cost()

static double cost ( symbol_cblk_t cblk)
inlinestatic

Computes the cost of a cblk.

This function computes the value of a cblk using the formula : cost = a.(cblk->lcolcum - cblk->fcolnum + 1)^2 where a = (cblk[1].bloknum - cblk[0].bloknum) / 2 + 1 It represents the load (number of calcul) a process needs to reorder the cblk.

Parameters
[in]cblkThe cblk we want to compute the cost.
Return values
TODO

Definition at line 288 of file symbol_reorder.c.

References symbol_cblk_s::fcolnum, and symbol_cblk_s::lcolnum.

Referenced by amalgamate_merge_cost(), candSubTreeBuild(), cblk_time_fact(), cblk_time_solve(), fct_blok_cadd_cost(), fct_blok_cgemmsp_cost(), fct_blok_cgetrfsp_cost(), fct_blok_chetrfsp_cost(), fct_blok_cpotrfsp_cost(), fct_blok_cscalo_cost(), fct_blok_ctrsmsp_cost(), fct_blok_dadd_cost(), fct_blok_dgemmsp_cost(), fct_blok_dgetrfsp_cost(), fct_blok_dpotrfsp_cost(), fct_blok_dscalo_cost(), fct_blok_dtrsmsp_cost(), fct_blok_sadd_cost(), fct_blok_sgemmsp_cost(), fct_blok_sgetrfsp_cost(), fct_blok_spotrfsp_cost(), fct_blok_sscalo_cost(), fct_blok_strsmsp_cost(), fct_blok_zadd_cost(), fct_blok_zgemmsp_cost(), fct_blok_zgetrfsp_cost(), fct_blok_zhetrfsp_cost(), fct_blok_zpotrfsp_cost(), fct_blok_zscalo_cost(), fct_blok_ztrsmsp_cost(), fct_cblk_cadd_cost(), fct_cblk_cgemmsp_cost(), fct_cblk_cgetrfsp_cost(), fct_cblk_chetrfsp_cost(), fct_cblk_cpotrfsp_cost(), fct_cblk_cpxtrfsp_cost(), fct_cblk_csytrfsp_cost(), fct_cblk_dadd_cost(), fct_cblk_dgemmsp_cost(), fct_cblk_dgetrfsp_cost(), fct_cblk_dpotrfsp_cost(), fct_cblk_dsytrfsp_cost(), fct_cblk_sadd_cost(), fct_cblk_sgemmsp_cost(), fct_cblk_sgetrfsp_cost(), fct_cblk_spotrfsp_cost(), fct_cblk_ssytrfsp_cost(), fct_cblk_zadd_cost(), fct_cblk_zgemmsp_cost(), fct_cblk_zgetrfsp_cost(), fct_cblk_zhetrfsp_cost(), fct_cblk_zpotrfsp_cost(), fct_cblk_zpxtrfsp_cost(), fct_cblk_zsytrfsp_cost(), and order_tasks().

◆ order_tasks()

static void order_tasks ( isched_t *  ctx,
struct args_reorder_t *  args 
)
inlinestatic

Order cblks for each process.

This function sorts cblks increasing their cost and process decreasingly their load using priority queue. After that every process has a load nearly equal, except the first one wich has a greater load than others.

Parameters
[in]ctxThe context of the current thread. This provides information about total number of thread used and the rank of the current thread.
[in,out]argsThe argument for reordering functions.

Definition at line 317 of file symbol_reorder.c.

References symbol_matrix_s::cblknbr, symbol_matrix_s::cblktab, cost(), extendint_Add(), symbol_cblk_s::fcolnum, pastix_int_t, pqueueExit(), pqueueInit(), pqueuePop1(), pqueuePush1(), pqueueSize(), symbol_matrix_s::schurfcol, and pastix_data_s::symbmtx.

Referenced by thread_reorder().

◆ thread_reorder()

static void thread_reorder ( pastix_data_t pastix_data,
pastix_int_t  maxdepth,
pastix_int_t levels 
)
inlinestatic

Prepare arguments for parallel subroutines and order cblks.

This function creates array for each process that countains cblks the process has to reorder. These cblks are provided by order_tasks functions. Afterwards, cblks are reordered by reordering functions.

Parameters
[in,out]pastix_dataThe pastix_data providing the scheduler, the symbolic structure, and the ordering providing by Scotch that will be updated with the new rows permutation for each supernode. It will also gives a stopping criterion the reordering of each supernode. The split_level field activates the split level heuristic, dividing distances computations into two stages: for upper and for lower contruibuting supernodes.
[out]levelsThe pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside.
[in]maxdepthThe maximum depth in the elimination tree.

Definition at line 395 of file symbol_reorder.c.

References symbol_matrix_s::cblknbr, extendint_Exit(), extendint_Init(), pastix_data_s::isched, order_tasks(), pastix_int_t, pastix_data_s::symbmtx, and thread_preorder().

Referenced by symbol_reorder().

◆ symbol_reorder()

void symbol_reorder ( pastix_data_t pastix_data,
pastix_int_t  maxdepth,
pastix_int_t levels 
)

Reorder all node.

This function computes the set each cblks, and then call a TSP heuristic to minimize the Hamiltonian Path.

Parameters
[in,out]pastix_dataThe pastix_data providing the scheduler, the symbolic structure, and the ordering providing by Scotch that will be updated with the new rows permutation for each supernode. It will also gives a stopping criterion the reordering of each supernode. The split_level field activates the split level heuristic, dividing distances computations into two stages: for upper and for lower contruibuting supernodes.
[out]levelsThe pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside.
[in]maxdepthThe maximum depth in the elimination tree.

Definition at line 461 of file symbol_reorder.c.

References pastix_data_s::iparm, IPARM_SCHEDULER, pastix_int_t, and thread_reorder().

Referenced by pastixSymbolReordering().

◆ compute_cblklevel()

static pastix_int_t compute_cblklevel ( const pastix_int_t treetab,
const pastix_int_t levels,
pastix_int_t  cblknum 
)
inlinestatic

Compute the level of supernode cblknum, with Scotch treetab.

Parameters
[in]treetabThe pointer to the elimination tree from Scotch.
[in]levelsThe supernode array which contains levels. Used to check if the level was already computed.
[in]cblknumThe supernode for which the level is computed.
Returns
the level of cblknum.

Definition at line 48 of file symbol_reordering.c.

References pastix_int_t.

Referenced by pastixSymbolReordering().

◆ hamming_distance()

static pastix_int_t hamming_distance ( pastix_int_t **  vectors,
pastix_int_t vectors_size,
pastix_int_t  xi,
pastix_int_t  xj,
pastix_int_t  stop 
)
inlinestatic

Compute the distance between two rows of a same supernode.

Parameters
[in]vectorsThe pointer to the sets of contributing supernodes for each row of the current supernode.
[in]vectors_sizeThe pointer to the sizes of each set of contributing supernode, to stop the computation when a row have been totally covered.
[in]xiThe index of the first row.
[in]xjThe index of the second row.
[in]stopThe stop criterion to disregard rows that are far away.
Returns
The distance between rows xi and xj.

Definition at line 101 of file symbol_reordering.c.

References pastix_int_t.

Referenced by symbol_reorder_tsp().

◆ symbol_reorder_tsp()

static void symbol_reorder_tsp ( pastix_int_t  size,
pastix_order_t order,
pastix_int_t  sn_id,
pastix_int_t **  lw_vectors,
pastix_int_t lw_vectors_size,
pastix_int_t **  up_vectors,
pastix_int_t up_vectors_size,
pastix_int_t  stop_criterion 
)
inlinestatic

Reorder rows of a supernode with the nearest insertion TSP heuristic.

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

Parameters
[in]sizeNumber of rows in the current supernode.
[in,out]orderThe pointer to the ordering structure. At exit, this ordering is updated with the new ordering for the current supernode being reordered.
[in]sn_idIdentifier for the current supernode.
[in]lw_vectorsThe pointer to the sets of lower contributing supernodes for each row of the current supernode. Those lower contributing supernodes correspond to supernodes with a level higher than split_level criterion.
[in]lw_vectors_sizeThe pointer to the sizes of each set of lower contributing supernode, to stop the computation when a row have been totally covered.
[in]up_vectorsThe pointer to the sets of upper contributing supernodes for each row of the current supernode. Those upper contributing supernodes correspond to supernodes with a level smaller than split_level criterion.
[in]up_vectors_sizeThe pointer to the sizes of each set of upper contributing supernode, to stop the computation when a row have been totally covered.
[in]stop_criterionThe stop criterion to disregard rows that are far away.

Definition at line 214 of file symbol_reordering.c.

References hamming_distance(), pastix_int_t, pastix_order_s::peritab, and pastix_order_s::rangtab.

Referenced by symbol_reorder_cblk().

◆ symbol_reorder_cblk()

void symbol_reorder_cblk ( const symbol_matrix_t symbptr,
const symbol_cblk_t cblk,
pastix_order_t order,
const pastix_int_t levels,
pastix_int_t depthweight,
pastix_int_t  depthmax,
pastix_int_t  split_level,
pastix_int_t  stop_criterion 
)

Reorder a supernode.

This function computes the set of contributing supernodes for each row, and then call a TSP heuristic to minimize the Hamiltonian Path.

Parameters
[in]symbptrThe pointer to the symbolic structure.
[in]cblkThe pointer to the current supernode being reordered.
[in,out]orderThe ordering providing by Scotch. This ordering will be updated with the new rows permutation for the current supernode.
[out]levelsThe pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside.
[in,out]depthweightThis array provides the number of supernodes corresponding to depth from 1 to depthmax.
[in]depthmaxThe maximum depth in the elimination tree.
[in]split_levelParameter to activate the split level heuristic, dividing distances computations into two stages: for upper and for lower contruibuting supernodes. If a resulting distance for upper supernodes is large enough, the computation is stopped, as long as it will be large taking into account lower contributing supernodes.
[in]stop_criterionThe stop criterion to disregard rows that are far away.

Compute hamming vectors in two subsets:

  • The upper subset contains the cblk with level higher than the split_level in the elimination tree, (or depth lower than levels[cblk])
  • The lower subset contains the cblk with level lower than the split_level in the elimination tree, (or depth higher than levels[cblk])

The delimitation between the lower and upper levels is made such that the upper level represents 17% to 25% of the total number of cblk.

Compute the split_level: We start with the given split_level parameter and we try to correct it to minimize the following iterative process

Definition at line 441 of file symbol_reordering.c.

References symbol_matrix_s::bloktab, symbol_cblk_s::brownum, symbol_matrix_s::browtab, symbol_matrix_s::cblktab, symbol_cblk_s::fcolnum, symbol_blok_s::frownum, symbol_blok_s::lcblknm, symbol_cblk_s::lcolnum, symbol_blok_s::lrownum, pastix_int_t, and symbol_reorder_tsp().

Referenced by sequential_reorder(), thread_preorder_basic_stategy(), and thread_preorder_zigzag_stategy().