Solving large-scale sparse linear systems is a critical problem in scientific and engineering computing. Partial differential equations can solve problems in many fields. They can be transformed into large-scale linea...
详细信息
ISBN:
(数字)9781510651890
ISBN:
(纸本)9781510651890;9781510651883
Solving large-scale sparse linear systems is a critical problem in scientific and engineering computing. Partial differential equations can solve problems in many fields. They can be transformed into large-scale linear systems with a series of methods, and the parallel solution of tridiagonal linear systems is one of them. The solution of linear systems is very time-consuming in most of the problems, accounting for more than half of the total time. Load balancing can reduce process time for waiting and improves computational efficiency, and it is the focus of many algorithms. The article is based on Stone's proposed recursive doubling algorithm, an improved algorithm for solving tridiagonal linear systems using the full-recursive-doubling communication model and the Mobiu transform. The improved algorithm can calculate the million-dimensional linear systems. Numerical experiments show that compared with ordinary parallel algorithms, the improved algorithm shows up to 2x improvement than the original version, and some results even show up to 3x. In addition, the load-balancing performance has been greatly improved, and the time difference of the processes is 1/7 of the original version. The improved algorithm has a good load balancing, and the running time of each process is not much different, avoiding process waiting and resource wastage.
The mean-time-between-failure of current high-performance computer systems is much shorter than the running times of many computational applications, whereas those applications are the main workload for those systems....
详细信息
ISBN:
(纸本)9783540768364
The mean-time-between-failure of current high-performance computer systems is much shorter than the running times of many computational applications, whereas those applications are the main workload for those systems. Currently, checkpoint/restart is the most commonly used scheme for such applications to tolerate hardware failures. But this scheme has its performance limitation when the number of processors becomes much larger. In this paper, we propose a novel fault-tolerant parallel algorithm FPAPR. First, we introduce the basic idea of FPAPR. Second, we specify the details of how to implement a FPAPR program by using two NPB kernels as examples. Third, we theoretically analyze the overhead of FPAPR, and find out that the overhead of FPAPR decreases with the increase of the number of processors. At last, the experimental results on a 512-CPU cluster show the overhead introduced by the algorithm is very small.
Mining frequent itemsets is a crucial issue in data mining applications. The complexity of the problem has been shown as NP-hard. parallel techniques are widely used to improve the efficiency of mining algorithms. A n...
详细信息
ISBN:
(纸本)9781934272084
Mining frequent itemsets is a crucial issue in data mining applications. The complexity of the problem has been shown as NP-hard. parallel techniques are widely used to improve the efficiency of mining algorithms. A novel and powerful parallel algorithm for mining maximal frequent itemsets, called P-MinMax, is proposed in this paper, which is based on its serial version MinMax. The new algorithm decomposes the search space by prefix-based equivalence classes, distributes work among the processors by complete inclusive relation between equivalence class gene itemsets and selectively duplicates databases in such a way that each processor can compute the frequent itemsets independently. These techniques eliminate the need for synchronization, drastically cutting down the I/O overhead. The analysis and experimental results demonstrate the superb efficiency of the approach in comparison with the previous work.
In this paper, a parallel algorithm with iterative form for solving finite element equation is presented. Based on the iterative solution of linear algebra equations, the parallel computational steps are introduced in...
详细信息
In this paper, a parallel algorithm with iterative form for solving finite element equation is presented. Based on the iterative solution of linear algebra equations, the parallel computational steps are introduced in this method. Also by using the weighted residual method and choosing the appropriate weighting functions, the finite element basic form of parallel algorithm is deduced. The program of this algorithm has been realized on the ELXSI-6400 parallel computer of Xi'an Jiaotong University. The computational results show the operational speed will be raised and the CPU time will be cut down effectively. So this method is one kind of effective parallel algorithm for solving the finite element equations of large-scale structures.
Given an unreliable communication network, we aim to find a most reliable source (MRS) on the network, which maximizes the expected number of nodes that are reachable from it. Although the problem of finding an MRS on...
详细信息
ISBN:
(纸本)9783642226151
Given an unreliable communication network, we aim to find a most reliable source (MRS) on the network, which maximizes the expected number of nodes that are reachable from it. Although the problem of finding an MRS on general graphs is #P-hard, it is tractable in several types of sparse graphs. The ring-tree graph is such a kind of sparse graph that not only has the capability of failure tolerance but also holds an underlying tree topology which facilitates network administration. In this paper, we are concerned with unreliable general ring-tree graphs in which each edge has an independent operational probability while all nodes are immune to failures. We first design a complementary dynamic programming algorithm and then develop a parallel algorithm based on the underlying tree for finding an MRS on the network.
We consider 2D and 3D models dealing with the transport of suspended particles. The approximation of 2D and 3D models that describe the transport of suspended particles is considered on the example of the two-dimensio...
详细信息
ISBN:
(纸本)9783030816919;9783030816902
We consider 2D and 3D models dealing with the transport of suspended particles. The approximation of 2D and 3D models that describe the transport of suspended particles is considered on the example of the two-dimensional diffusion-convection equation. We use discrete analogs of convective and diffusion transfer operators on the assumption of partial filling of cells. The geometry of the computational domain is described based on the filling function. We solve the problem of transport of suspended particles using a difference scheme that is a linear combination of the Upwind and the Standard Leapfrog difference schemes with weight coefficients obtained from the condition of minimization of the approximation error. The scheme is designed to solve the problem of transfer of impurities for large grid Peclet numbers. We have developed some parallel algorithms for the solution of this problem on multiprocessor systems with distributed memory. The results of numerical experiments give us grounds to draw conclusions about the advantages of 3D models of transport of suspended particles over 2D ones.
In the paper, the preconditioner of linear systems is directly extented to the solutions of block-tridiagonal equations. And by corresponding parallel processing, a parallel algorithm of two stage iterative method for...
详细信息
ISBN:
(纸本)9781846260612
In the paper, the preconditioner of linear systems is directly extented to the solutions of block-tridiagonal equations. And by corresponding parallel processing, a parallel algorithm of two stage iterative method for solving block-tridiagonal linear equations is presented. According to theoretical analysis, a sufficient condition of the new algorithm convergence is given. Finally, the results of numerical experiments on HP rx2600 cluster indicate that the algorithm is feasible and effective.
In view of the FP-Growth algorithm needs to establish huge FP-Tree to take the massive memories, when is confronted with very huge database, its algorithm obviously insufficient in efficiency. This article unified FP-...
详细信息
ISBN:
(纸本)9783642274510
In view of the FP-Growth algorithm needs to establish huge FP-Tree to take the massive memories, when is confronted with very huge database, its algorithm obviously insufficient in efficiency. This article unified FP-Growth and parallel algorithm, proposed one kind association rule parallel algorithm based on the FP-Growth, this algorithm in the FP-Growth algorithm foundation, with the aid of parallel algorithm's thought that carried on the database resolution as well as the FP-tree tree the division reasonable combination, In the task allocation, the load stabilization, has done the research, the duty rational distribution, the combination, has achieved the good load stabilization, raised the algorithm speed, this algorithm is suitable in the large-scale database carries on the data mining, compared with former algorithm had the remarkable enhancement in the efficiency.
In order to solve the system load imbalanced problem of the synchronized parallel algorithm on unconstrained optimization problems,improve the speed of solving *** relaxation asynchronous
ISBN:
(纸本)9780769544151
In order to solve the system load imbalanced problem of the synchronized parallel algorithm on unconstrained optimization problems,improve the speed of solving *** relaxation asynchronous
Let G be a connected graph with n vertices. A spanning tree of G is an acyclic subgraph of G that has n vertices and n - 1 edges. In this paper, we propose a simple optimal parallel algorithm for constructing a spanni...
详细信息
Let G be a connected graph with n vertices. A spanning tree of G is an acyclic subgraph of G that has n vertices and n - 1 edges. In this paper, we propose a simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph in O (log n) time with O (n / log n) processors on the EREW PRAM computational model.
暂无评论