Sparse LU factorization is a critical kernel in scientific computing and engineering applications. A better nonzero pattern of sparse matrixes can accelerate LU factorization by reordering. Traditionally it's diff...
详细信息
The use of binary decision diagrams (BDDs) has proliferated in numerous fields. When a system criterion is formulated in form of a Boolean function, its BDD is constructed. Each node in the BDD is further mapped into ...
详细信息
The use of binary decision diagrams (BDDs) has proliferated in numerous fields. When a system criterion is formulated in form of a Boolean function, its BDD is constructed. Each node in the BDD is further mapped into another form to be exploited in the system analysis. However, the cost of the resultant mapping form is directly related to the BDD size which can be effectively reduced through applying proper variable reordering followed by applying reduction rules that preserve the fidelity of the BDD in correctly representing the input Boolean function. Although several algorithms have been proposed in the literature to find the optimal order of variables in the BDD, the scalability of such algorithms is a serious barrier when it comes to complex systems with exponential explosion in the possible number of orders in the search space. Furthermore, solely exploring the search space in BDD reordering is not sufficient since better permutations might be obtained with slight tuning of the candidate solutions. Thus, a sufficient degree of equilibrium between exploration and exploitation should be preserved during the evolution of the reordering algorithm. In this article, we propose a BDD optimizer driven by either genetic algorithm (GA) or swarm engines. The proposed GA-based BDD reordering optimizer iteratively processes an essentially large population with a randomized mixing of low destructive crossover/mutation operators. The proposed swarm-based optimizer, on the other hand, maps a vector of real numbers into a permutation to further construct its companion BDD. The generation of the next vector is guided by recent parameter and parameter-less swarm algorithms that are armed with effective mechanisms to simultaneously conduct exploration and exploitation. Experimental results show that our proposed optimizer effectively reduces the resultant BDD size for input Boolean functions with almost linear computational complexity. Furthermore, it has been found that exploiti
Binary Decision Diagrams (BDDs) have become the state -of -art data structures in numerous fields, wherein, small-sized BDDs are required to reduce the companion cost. Since BDD size is sensitive to the order of varia...
详细信息
Binary Decision Diagrams (BDDs) have become the state -of -art data structures in numerous fields, wherein, small-sized BDDs are required to reduce the companion cost. Since BDD size is sensitive to the order of variables for the Boolean function in use, evolutionary algorithms have been extensively exploited to solve the BDD reordering problem which is provably an NP-hard problem. However, getting trapped in a local minima is more likely as the population gets homogeneous during the evolution of the algorithm. This paper compares various diversity measures correlated to BDDs and studies the impact of different crossover and mutations used in the Genetic algorithm (GA) on those diversity measures. Thereafter, we propose an enhanced GA-based reordering algorithm for BDD, wherein, the chosen diversity measure is calculated per generation to steer the application of proper variation operators, in such a way that an acceptable level of equilibrium between exploration and exploitation is preserved. Finally, we utilize a new heuristic Cyclic Crossover (HCX) that further improves the performance of the proposed algorithm following the fitness value. Experimental results on public benchmarks show that our proposed algorithm outperforms other algorithms from the literature when switching between HCX and swap mutation operators is made following the measured diversity metric.
As blockchain technology garners increased adoption, permissioned blockchains like Hyperledger Fabric emerge as a popular blockchain system for developing scalable decentralized applications. Nonetheless, parallel exe...
详细信息
ISBN:
(数字)9789819708628
ISBN:
(纸本)9789819708611;9789819708628
As blockchain technology garners increased adoption, permissioned blockchains like Hyperledger Fabric emerge as a popular blockchain system for developing scalable decentralized applications. Nonetheless, parallel execution in Fabric leads to concurrent conflicting transactions attempting to read and write the same key in the ledger simultaneously. Such conflicts necessitate the abortion of transactions, thereby impacting performance. The mainstream solution involves constructing a conflict graph to reorder the transactions, thereby reducing the abort rate. However, it experiences considerable overhead during scenarios with a large volume of transactions or high data contention due to capture dependencies between each transaction. Therefore, one critical problem is how to efficiently order conflicting transactions during the ordering phase. In this paper, we introduce an optimized reordering algorithm designed for efficient concurrency control. Initially, we leverage key dependency instead of transaction dependency to build a conflict graph that considers read/write units as vertices and intra-transaction dependency as edges. Subsequently, a key sorting algorithm generates a serializable transaction order for validation. Our empirical results indicate that the proposed key-based reordering method diminishes transaction latency by 36.3% and considerably reduces system memory costs while maintaining a low abort rate compared to benchmark methods.
Jacobian-free Newton Krylov (JFNK) is an attractive method to solve nonlinear equations in the nuclear engineering community, and has been successfully applied to steady-state neutron diffusion k-eigenvalue problems a...
详细信息
Jacobian-free Newton Krylov (JFNK) is an attractive method to solve nonlinear equations in the nuclear engineering community, and has been successfully applied to steady-state neutron diffusion k-eigenvalue problems and multi-physics coupling problems. Preconditioning technique plays an important role in the JFNK algorithm, significantly affecting its computational efficiency. The key point is how to automatically construct a high-quality preconditioning matrix that can improve the convergence rate and perform the preconditioning matrix factorization efficiently and robustly. A reordering-based ILU(k) preconditioner is proposed to achieve the above objectives. In detail, the finite difference technique combined with the coloring algorithm is utilized to automatically construct a preconditioning matrix with low computational cost. Furthermore, the reordering algorithm is employed for the ILU(k) to reduce the additional non-zero elements and pursue robust computational performance. A 2D LRA neutron steady-state benchmark problem is used to evaluate the performance of the proposed preconditioning technique, and a steady-state neutron diffusion k-eigenvalue problem with thermal-hydraulic feedback is also utilized as a supplement. The results show that coloring algorithms can automatically and efficiently construct the preconditioning matrix. The computational efficiency of the FDP with coloring could be about 60 times higher than that of the preconditioner without the coloring algorithm. The reordering-based ILU(k) preconditioner shows excellent robustness, avoiding the effect of the fill-in level k choice in incomplete LU factorization. Moreover, its performances under different fill-in levels are comparable to the optimal computational cost with natural ordering.
Finding appropriate permutations of rows and columns of a matrix may help users to see hidden patterns in datasets. This paper presents a set of binarization-based matrix reordering algorithms able to reveal some patt...
详细信息
ISBN:
(纸本)9781467389426
Finding appropriate permutations of rows and columns of a matrix may help users to see hidden patterns in datasets. This paper presents a set of binarization-based matrix reordering algorithms able to reveal some patterns in a quantitative data set. In these algorithms, matrix binarization converts a matrix into a set of binary ones, from which the algorithms calculate desired groups of similar rows and columns. PQR trees provide a linear order of rows and columns that obey these groups as much as possible. These algorithms use mean or median filter as smoothing techniques to minimize data noise in intermediate matrix permutation steps. They also use feature vectors or thresholding for defining binarization thresholds in intermediate steps. Our experiments with synthetic matrices revealed that our algorithms are competitive with other matrix reordering algorithms in terms of quality of reordering (Moore stress) and runtime. We observed that our set of algorithms is suitable to reveal Circumplex pattern with all tested noise ratios, and other data canonical patterns with low noise ratio.
Many sparse matrix computations can be speeded up if the matrix is first reordered. reordering was originally developed for direct methods but it has recently become popular for improving the cache locality of paralle...
详细信息
ISBN:
(纸本)9781479955008
Many sparse matrix computations can be speeded up if the matrix is first reordered. reordering was originally developed for direct methods but it has recently become popular for improving the cache locality of parallel iterative solvers since reordering the matrix to reduce bandwidth and wavefront can improve the locality of reference of sparse matrix-vector multiplication (SpMV), the key kernel in iterative solvers. In this paper, we present the first parallel implementations of two widely used reordering algorithms: Reverse Cuthill-McKee (RCM) and Sloan. On 16 cores of the Stampede supercomputer, our parallel RCM is 5.56 times faster on the average than a state-of-the-art sequential implementation of RCM in the HSL library. Sloan is significantly more constrained than RCM, but our parallel implementation achieves a speedup of 2.88X on the average over sequential HSL-Sloan. reordering the matrix using our parallel RCM and then performing 100 SpMV iterations is twice as fast as using HSL-RCM and then performing the SpMV iterations;it is also 1.5 times faster than performing the SpMV iterations without reordering the matrix.
A vectorial implementation of dynamic optimal power now (DOPF) including wind farms was presented. The vectorization of DOPF was established by arranging the control variables and state variables according to the vari...
详细信息
ISBN:
(纸本)9787506292214
A vectorial implementation of dynamic optimal power now (DOPF) including wind farms was presented. The vectorization of DOPF was established by arranging the control variables and state variables according to the variable types and time intervals. The asynchronous generators in wind farms were modeled in Q-V formulation. A step-controlled primal-dual interior point framework (SCIPM) with upper and lower inequality constrains was adopted to solve this DOPF model. The gradient and Hessian matrices of each time interval had relative non-zeros position with the admittance matrix, which was constant during iterations. Hence a sparse data structure and memory allocation strategy was utilized to accelerate the construction of KKT system. The effect of ramping rates and generation contract constrains on solving KKT system was analyzed in detail. Through computation statistics, it is confirmed that approximate minimum degree (AMD) reordering algorithm is most efficient with only ramping rate constrains, and column approximate minimum degree (COLAMD) reordering algorithm is most efficient with both ramping rate and generation contract constrains. Numerical simulations on test systems ranging in size from 14 to 1040 buses over 12-96 time intervals validate the correctness and efficiency of the proposed method. Vectorization technique with step-controlled primal-dual interior point method improves the calculation speed and convergence performance of DOPF.
State estimation base on a nonlinear programming model is presented (NLSE), which is applied the vectorization mode. We choose the L2 norm estimation as object. The nonlinear programming with equality constraint intro...
详细信息
ISBN:
(纸本)9787506292214
State estimation base on a nonlinear programming model is presented (NLSE), which is applied the vectorization mode. We choose the L2 norm estimation as object. The nonlinear programming with equality constraint introduced slack variables, can guarantee the robust of the algorithm and dispose the convergence problem. The symmetric coefficient matrix of correction equation can be used by apply the AMD reordering algorithm and LDLT algorithm on the solution, which can speed up the calculation striking. The whole model of nonlinear state estimation applies vectorization form, so the complexity extent is simplified and both versatility and maintainability of code are improved. Numerical simulations use IEEE14, IEEE57, IEEE118, IEEE300, N1047 system to validate the correctness of the proposed model and method.
State estimation base on a nonlinear programming model is presented（NLSE）,which is applied the vectorization *** order to treated the derivation simplify we choose the L2 norm estimation,that is the least square est...
详细信息
State estimation base on a nonlinear programming model is presented（NLSE）,which is applied the vectorization *** order to treated the derivation simplify we choose the L2 norm estimation,that is the least square estimation,which can guarantee the robust of the *** nonlinear programming with equality constraint,which was introduce slack variables.A simple objective function with slack variables substitutes the traditional least square estimation's target *** symmetric coefficient matrix of correction equation can be used by apply the AMD reordering algorithm and LDL algorithm on the solution,which can speed up the calculation *** simulations validate the correctness of the proposed model and method.
暂无评论