摘要:

The cost of interprocessor communication has a substantial impact on execution time when implementing parallel algorithms on physical parallel computers. For coarse-grained parallel computers it is important to minimize the number of communication phases, in order to balance cost of communication with local computation time. We present a logp-phase optimal randomized parallel list ranking algorithm and its application to expression evaluation. These techniques address the general issue of model-independent parallel algorithm design.

ISSN:1063-7192    

DOI:10.1080/10637199808947384

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

Numerical solution of elliptic grid generation equations requires iterative solution of large nonlinear algebraic systems, a computationally intensive task. To assist a selection of efficient and robust methods, this paper considers parallel implementations of several iterative grid generation solvers. The methods studied are multicolor SOR. multigrid, and GMRES. They are implemented on the MasPar MP-I, a massively parallel SIMD machine. The experiments suggest that multigrid methods are the most efficient and robust for large problems.

ISSN:1063-7192    

DOI:10.1080/10637199808947385

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

Recently Aklet al. introduced a new model of parallel computation, called BSR (broadcasting with selective reduction) and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for implementation than even EREW PRAM. The model allows constant time solutions to sorting, parallel prefix and other problems. In this paper, we describe constant time solution to the longest common subsequence (LCS) and longest increasing subsequence (LIS) problems using the BSR model. The number of processors used to solve the LCS problem isO(N×M) (whereNandMare the length of the two input sequences). Our BSR solution of the LIS problem needsO(N) processors (whereNis the length of the input sequence). These two solutions use BSR instructions with a constant number of selections. It is an improvement of our former BSR algorithm for the LCS in (Journal of Parallel and Distributed Computing, to appear) which uses 3N+ 3 selections.

ISSN:1063-7192    

DOI:10.1080/10637199808947386

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

We study efficient parallel solutions to the problem of selectingrelements at specified ranks from a set of n arbitrary elements, known asmultiselection, in a hypercube withp<nprocessors. We propose two parallel algorithms based on different approaches, where one requires processors to operate in the SIMD mode, and the other in the MIMD mode. Our SIMD algorithm runs inO(nϵmin{r, logp}) time whenp=n1−rfor any 0<ϵ<1, which is cost-optimal whenr≥p. With the same number of processors, our MIMD algorithm runs inO(nϵlogr) time and is cost-optimal for any values ofr. Both algorithms are more efficient than straightforward solutions and that of direct simulation of the optimal EREW algorithm.

ISSN:1063-7192    

DOI:10.1080/10637199808947387

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

In this paper, the authors present an electromagnetic model suitable to investigate transient performance of electric power substations grounding systems, working in a distributed programming environment. The numerical model, represented by a modified version of the electric field integral equation in frequency domain, is solved by means of the method of moments according to the direct and the iterative numerical formulations. The two computational schemes are described and solved by means or parallel solutions differently grained and oriented to distributed memory computers. Test results, which illustrate the capability of the proposed schemes, are reported and the performances are assessed by using the 128-node Cray T3D architecture.

ISSN:1063-7192    

DOI:10.1080/10637199808947388

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

A direct parallel method called Alternate Quadrant Interlocking Factorization (AQIF);A=WZ, is introduced (Rao,Parallel Algorithms and Applications,4, 1-20, 1994) for the general solution of the linear systemAx=b. The matricesWandZare closed under multiplication and inversion. In this paper AQIF is used with partition method for the solution of the banded linear system. The AQIF of the coefficient matrix in each block has the properties that when A is banded with the semibandwidth β, the space generated byei, en−I+11≤i≤β, is invariant under the transformationW, so is invariant under the transformationW−1, whereejdenotesndimensional unit vector with I injth position and 0's elsewhere and the solution process with the coefficient matrixZproceeds from the first and last unknowns towards middle ones. These properties of AQIF help us to decouple the partitioned systems for the parallel execution once ‘reduced system’ is solved.

ISSN:1063-7192    

DOI:10.1080/10637199808947389

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor