摘要:

We present a fast parallel algorithm for finding the blocks or biconnected components of an undirected graphG = (V,E) havingnvertices and m edges. Our techniques arc based on partitioning the vertex setVinto adjacency-level sets using information contained in the distance matrixDof the graph. LettDandpDbe the time and number of processors, respectively, for the computation of the distance matrix of a graphGon a CRCW-PRAM computational model. We show that the location of all cut vertices and bridges of a graph can be done in timeO(logδ + tD) by usingO(n m/td) processors, where δ is the maximum degree of a vertex inG. Based on these results, we define a digraphGdand we prove certain properties on its distance matrix leading to a parallel block-finding algorithm running in timeO(logδ + tD) withO(n m/tD) processors on the same computational model. We also show that other connectivity-related problems can be efficiently solved using distance matrices.

ISSN:1063-7192    

DOI:10.1080/10637199608915561

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

All the parallel discrete event simulation algorithms developed so far have been designed to suit a specific parallel model (e.g., a PRAM model, a MP-RAM model, etc.). This paper presents several versions of conservative parallel discrete event simulation algorithms developed around a unifying model for general purpose parallel computer design and programming, namely around the Bulk Synchronous Parallel (BSP) model. The new algorithms are analysed in terms of the BSP model parameters and the effectiveness of simulators based on these algorithms is evaluated. The performance achieved even for a loosely coupled distributed system is comparable with that reported in previous research work, while the generality of the BSP model provides portability to the new approaches.

ISSN:1063-7192    

DOI:10.1080/10637199608915562

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

Monte Carlo algorithms for solving boundary value problems for elliptic differential equations are studied. In particular two Monte Carlo numerical algorithms are considered. The first one is so-called grid-walk (GW) algorithm, white the second one is grid-free (GF) algorithm. The first algorithm uses a discretisation of the problem on a mesh and solves the linear algebraic system, which approximates the original problem. The second algorithm uses an integral representation for the problem. For the studied algorithms a new data parallel approach is applied. It is shown that the numerical solution of partial differential equations, can be efficiently addressed in a functional language. These algorithms have been implemented in parallel on a MIMD-machine with distributed memory. Experimental results that they behave well and that due to small amount of communication a linear speedup is possible.

ISSN:1063-7192    

DOI:10.1080/10637199608915563

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

Ordering clones from a genomic library into physical maps of whole chromosomes presents a central computational problem in genetics. Chromosome reconstruction via clone ordering is shown to be isomorphic to the NP-completeOptimal Linear Orderingproblem. Massively parallel algorithms for simulated annealing based on Markov chain distribution are proposed and applied to the problem of chromosome reconstruction via clone ordering. Perturbation methods and problem-specific annealing heuristics arc proposed and described. These algorithms are implemented on a 2048 processor MasPar MP-2 system which is an SIMD 2-D toroidal mesh architecture. Convergence, speedup and scalability characteristics of the various algorithms are analyzed and discussed. Results indicate that for an optimal clone ordering, a single Markov chain of solution states should not be distributed across more than two adjoining processing elements (PE's) on the MasPar MP-2.

ISSN:1063-7192    

DOI:10.1080/10637199608915564

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

The philosophy of multisplitting methods is the replacement of a large-scale linear or nonlinear problem by a set of smaller subproblems, each of which can be solved locally and independently in parallel by taking advantage of well-tested sequential algorithms. Because of this formulation most compute-intensive operations can be calculated independently and the algorithms are highly parallel. In continuation of our earlier work we utilize a new parameter-free formulation of linearly constrained convex minimization problems to obtain a parallel algorithm of multisplitting type. Numerical results both serial and parallel are reported which demonstrate its efficiency and which also show that it compares favorably to our earlier parameter-dependent approach.

ISSN:1063-7192    

DOI:10.1080/10637199608915565

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

A novel method, binary countdown transformation, for generating integer compositions in parallel is proposed. Based on this method, an optimal and highly adaptive parallel algorithm for generating all compositions of integernis presented. The algorithm runs onpprocessors on a simple SIMD model requiring neither shared memory nor interconnection network and has a worst-case time complexity ofO(n2n−1/p), 1 ≤ p ≤ 2n−1. All the compositions generated are in lexicographic order. The proposed algorithm is superior to those built on generating combinations and set partitions.

ISSN:1063-7192    

DOI:10.1080/10637199608915566

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper presents a parallel algorithm for finding the centers and medians of graphs. The computational model used is a shared memory single instruction stream, multiple data stream computer which is more commonly known as the parallel random access machine. The design of the parallel algorithm is based on the growing-by-doubling paradigm. Assuming that the graph consists ofnnodes, the proposed parallel algorithm can be implemented inO(log2n) time withO(n2n/logn) processors when no write-conflict is allowed by the computational model. On the other hand, the algorithm can be implemented inO(log n(loglogn)) time withO(n2n/loglogn) processors when the computational model allows write-conflict. In case of write-conflict, it is assumed that all the processors involved in the concurrent-write operation must attempt to write the same value.

ISSN:1063-7192    

DOI:10.1080/10637199608915567

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper describes the numerical solution of heat transfer problems using cellular automata. While traditional methods offer high performance on uniprocessor machines, their performance is limited on distributed memory multiprocessors by communication bottlenecks caused by the interdependence of the equations. Using a cellular automata formulation, these bottlenecks can be avoided, and performance greater than that obtained by parallelizing traditional algorithms can be achieved. This paper gives an overview of the cellular automata paradigm and specific examples of solutions to a hyperbolic and a parabolic problem. The accuracy of the method is verified by comparisons of the results with analytical solutions and with results produced by other techniques.

ISSN:1063-7192    

DOI:10.1080/10637199608915568

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

In this paper the algorithms of the multisplitting parallel PE Iterative Method for linear systems of the formAx = ƒare proposed, whenAis block tridiagonal matrix. The convergence of these iterative methods is analyzed, whenAis anMmatrix orHmatrix. The resulting MPPE method has been tested on a CHALLENGE-L computer. Numerical examples indicates that the new method is very efficient, since the parallel computation can be applied.

ISSN:1063-7192    

DOI:10.1080/10637199608915569

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

Horner's algorithm of evaluating a polynomial is studied and formulated as a matrix equationAx = c, with a special bidiagonalA.Decoupling algorithm proposed by Kowalik and Kumar [5] for solving bidiagonal systems is simplified and modified by showing that only two stages of three stage algorithm is satisfactory to be used to evaluate polynomials. Some numerical results are presented and discussed. It has been seen that the results are comparable with those of Dorn's [1].

ISSN:1063-7192    

DOI:10.1080/10637199608915570

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor