The numerical solution of 3D linear elasticity equations is considered. The problem is described by a coupled system of second order elliptic partial differential equations. This system is discretized by trilinear par...
详细信息
ISBN:
(纸本)3540006087
The numerical solution of 3D linear elasticity equations is considered. The problem is described by a coupled system of second order elliptic partial differential equations. This system is discretized by trilinear parallelepipedal finite elements. The Preconditioned Conjugate Gradient iterative method is used for solving of the large-scale linear algebraic systems arising after the Finite Element Method (FEM) discretization of the problem. Displacement decomposition technique is applied at the first step to construct a preconditioner using the decoupled block-diagonal part of the original matrix. Then circulant block-factorization is used for preconditioning of the obtained block-diagonal matrix. Both preconditioning techniques, displacement decomposition and circulant block-factorization, are highly parallelizable. A parallel algorithm is invented for the proposed preconditioner. The theoretical analysis of the execution time shows that the algorithm is highly efficient for coarse-grain parallel computer systems. A portable parallel FEM code based on MPI is developed. Numerical tests for real-life engineering problems in computational geomechanics are performed on a number of modern parallel computers: Cray T3E, Sunfire 6800, and Beowulf cluster. The reported speed-up and parallel efficiency well illustrate the parallel features of the proposed method and its implementation.
This paper presents a set of benchmarks and metrics for performance reporting in explicit state parallel model checking algorithms. The benchmarks are selected for controllability, and the metrics are chosen to measur...
详细信息
We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n-vertex graph the algorithm runs in o((log n)(1+epsilon)) expected time for any epsilon > 0 and p...
详细信息
We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n-vertex graph the algorithm runs in o((log n)(1+epsilon)) expected time for any epsilon > 0 and performs linear expected work. This is the first linear-work, polylog-time algorithm on the EREW PRAM for this problem. This also gives parallel algorithms that perform expected linear work on two general-purpose models of parallel computation-the QSM and the BSP.
A parallel propagation algorithm was applied to the decoding of convolutional codes. The performance of the algorithm was demonstrated by a numerical method similar to the density evaluation.
A parallel propagation algorithm was applied to the decoding of convolutional codes. The performance of the algorithm was demonstrated by a numerical method similar to the density evaluation.
We describe a parallel model-checking algorithm for the fragment of the μ-calculus that allows one alternation of minimal and maximal fixed-point operators. This fragment is also known as L2μ. Since LTL and CTL* can...
详细信息
At the Center for Computational Electromagnetics at the University of Illinois, we recently solved a very-large-scale electromagnetic scattering problem. We computed the bistatic radar cross-section of a full-size air...
详细信息
At the Center for Computational Electromagnetics at the University of Illinois, we recently solved a very-large-scale electromagnetic scattering problem. We computed the bistatic radar cross-section of a full-size aircraft at 8 GHz, involving the solution of a dense matrix equation with nearly 10.2 million unknowns. We regarded this as the "ultimate test" of a massively parallel implementation of the Multilevel Fast Multipole Algorithm (MLFMA), called ScaleME. In this paper, we narrate the technical difficulties faced and the experience gained from a very informal point of view. We shall describe the various methods developed for surmounting each of the obstacles.
We discuss the efficient implementation of a collective operation called reduce-scatter, which is defined in the MPI standard. The reduce-scatter is equivalent to the combination of a reduction on vectors of length n ...
详细信息
We discuss the efficient implementation of a collective operation called reduce-scatter, which is defined in the MPI standard. The reduce-scatter is equivalent to the combination of a reduction on vectors of length n with a scatter of the resulting n-vector to all processors. We describe the implementation issues and the performance characterization of two recently proposed algorithms for the reduce-scatter that have been proven to be highly efficient in theory under the assumption of fully connected parallel system. A performance comparison with existing mainstream implementations of the operation is presented which confirms the practical advantage of the new algorithms. Experiments show that the two algorithms have different characteristics which make them complementary in providing a performance gain over standard algorithms. Our study has been carried out on two different platforms: an SP2 and a Myrinet interconnected cluster of Pentium PRO. However, most of the results reported here are not specific for either MPI or the platforms used, and they hold in general for any message passing programming system. (C) 2003 Elsevier B.V. All rights reserved.
The central contribution of this work is SAMBA (Single Application, Multiple Load Balancing), a framework for the development of parallel SPMD (single program, multiple data) applications with load balancing. This fra...
详细信息
The central contribution of this work is SAMBA (Single Application, Multiple Load Balancing), a framework for the development of parallel SPMD (single program, multiple data) applications with load balancing. This framework models the structure and the characteristics common to different SPMD applications and supports their development. SAMBA also contains a library of load balancing algorithms. This environment allows the developer to focus on the specific problem at hand. Special emphasis is given to the identification of appropriate load balancing strategies for each application. Three different case studies were used to validate the functionality of the framework: matrix multiplication, numerical integration, and a genetic algorithm. These applications illustrate its ease of use and the relevance of load balancing. Their choice was oriented by the different load imbalance factors they present and by their different task creation mechanisms. The computational experiments reported for these case studies made possible the validation of SAMBA and the comparison, without additional reprogramming costs, of different load balancing strategies for each of them. The numerical results and the elapsed times measurements show the importance of using an appropriate load balancing algorithm and the associated reductions that can be achieved in the elapsed times. They also illustrate that the most suitable load balancing strategy may vary with the type of application and with the number of available processors. Besides the support to the development of SPMD applications, the facilities offered by SAMBA in terms of load balancing play also an important role in terms of the development of efficient parallel implementations. (C) 2003 Elsevier Science B.V. All rights reserved.
An AB 2 operation is known as an efficient basic operation for public key cryptosystems over GF(2(m)), and various systolic arrays for performing AB(2) operations have already been proposed using a standard basis repr...
详细信息
An AB 2 operation is known as an efficient basic operation for public key cryptosystems over GF(2(m)), and various systolic arrays for performing AB(2) operations have already been proposed using a standard basis representation. However, these circuits have certain shortcomings for cryptographic application due to their high circuit complexity and long latency. Therefore, further research on an efficient AB(2) multiplication circuit is still needed. Accordingly, the authors present a new AB(2) algorithm and its systolic realisations in GF(2(m)). First, a new algorithm is proposed based on the MSB-first scheme using a standard basis representation. Thereafter, bitparallel and bit-serial systolic power multipliers are derived that exhibit a lower hardware complexity and smaller latency than conventional approaches. In addition, since the proposed architectures incorporate simplicity, regularity, modularity, and pipelinability, they are well suited to VLSI implementation and can be easily applied as a basic architecture for computing an inverse/ division operation and in crypto-processor chip design.
This paper solves the NP problem of DNA string matching using heuristics and parallelism. The current methods for approximate matching are merely different versions of dynamic programming. Dynamic programming is O(n2)...
详细信息
ISBN:
(纸本)1892512416
This paper solves the NP problem of DNA string matching using heuristics and parallelism. The current methods for approximate matching are merely different versions of dynamic programming. Dynamic programming is O(n2), and does not consider one of the most important areas in technology: parallelism. The proposed algorithm uses parallelism to solve approximate matching. It has a best-case time complexity of O(n), and has better performance in practice than dynamic programming.
暂无评论