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... | |
|
inlinestatic |
Sequential version for reordering.
This algorithm reorders cblks. (Sequential version).
[in,out] | pastix_data | The 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] | levels | The pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside. |
[in] | maxdepth | The 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().
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)
[in] | ctx | The context of the current thread. This provides information about total number of thread used and the rank of the current thread. |
[in,out] | args | The 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().
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)
[in] | ctx | The context of the current thread. This provides information about total number of thread used and the rank of the current thread. |
[in,out] | args | The 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().
|
inlinestatic |
Function called by each thread.
This function select and call a strategy to reorder cblks. (Parallel version)
[in] | ctx | The context of the current thread. This provides information about total number of thread used and the rank of the current thread. |
[in,out] | args | The 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().
|
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.
[in] | cblk | The cblk we want to compute the cost. |
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().
|
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.
[in] | ctx | The context of the current thread. This provides information about total number of thread used and the rank of the current thread. |
[in,out] | args | The 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().
|
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.
[in,out] | pastix_data | The 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] | levels | The pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside. |
[in] | maxdepth | The 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().
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.
[in,out] | pastix_data | The 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] | levels | The pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside. |
[in] | maxdepth | The 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().
|
inlinestatic |
Compute the level of supernode cblknum, with Scotch treetab.
[in] | treetab | The pointer to the elimination tree from Scotch. |
[in] | levels | The supernode array which contains levels. Used to check if the level was already computed. |
[in] | cblknum | The supernode for which the level is computed. |
Definition at line 48 of file symbol_reordering.c.
References pastix_int_t.
Referenced by pastixSymbolReordering().
|
inlinestatic |
Compute the distance between two rows of a same supernode.
[in] | vectors | The pointer to the sets of contributing supernodes for each row of the current supernode. |
[in] | vectors_size | The pointer to the sizes of each set of contributing supernode, to stop the computation when a row have been totally covered. |
[in] | xi | The index of the first row. |
[in] | xj | The index of the second row. |
[in] | stop | The stop criterion to disregard rows that are far away. |
Definition at line 101 of file symbol_reordering.c.
References pastix_int_t.
Referenced by symbol_reorder_tsp().
|
inlinestatic |
Reorder rows of a supernode with the nearest insertion TSP heuristic.
See reordering paper: http://epubs.siam.org/doi/10.1137/16M1062454.
[in] | size | Number of rows in the current supernode. |
[in,out] | order | The pointer to the ordering structure. At exit, this ordering is updated with the new ordering for the current supernode being reordered. |
[in] | sn_id | Identifier for the current supernode. |
[in] | lw_vectors | The 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_size | The pointer to the sizes of each set of lower contributing supernode, to stop the computation when a row have been totally covered. |
[in] | up_vectors | The 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_size | The pointer to the sizes of each set of upper contributing supernode, to stop the computation when a row have been totally covered. |
[in] | stop_criterion | The 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().
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.
[in] | symbptr | The pointer to the symbolic structure. |
[in] | cblk | The pointer to the current supernode being reordered. |
[in,out] | order | The ordering providing by Scotch. This ordering will be updated with the new rows permutation for the current supernode. |
[out] | levels | The pointer to the levels structure, giving the level of each supernode in the elimination tree. To be computed inside. |
[in,out] | depthweight | This array provides the number of supernodes corresponding to depth from 1 to depthmax. |
[in] | depthmax | The maximum depth in the elimination tree. |
[in] | split_level | Parameter 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_criterion | The stop criterion to disregard rows that are far away. |
Compute hamming vectors in two subsets:
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().