摘要:

Two constant time algorithms, which are based on the reflexive transitive closure of a directed graph, are proposed for computing dominators and dominator tree of a flow graph respectively. The parallel computation model used is a reconfigurable array of processors. A reconfigurable array of processors is defined to be an array of processors connected to a reconfigurable bus system whose configuration can be dynamically changed. Other applications that are based on the proposed algorithms are also solved in a constant time respectively. These problems include finding the back edges in a flow graph, recognizing the acyclic directed graph, recognizing the reducible flow graph, finding the natural loops, and finding the inner loop.

ISSN:1063-7192    

DOI:10.1080/10637199408962522

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In many scientific fields, three dimensional surfaces must be reconstructed from a given collection of its surface points. Applications for surface reconstruction exist in medical research and diagnosis as well as in design intensive disciplines. Fuchs, Kedem, and Uselton and Keppel show that surface reconstruction via triangulation can be reduced to the problem of finding a path in a toroidal graph. This paper presents a parallel algorithm to find the minimum cost acceptable path in anmbyntoroidal graph. We then show an implementation of the parallel algorithm on a parallel architecture, using a message passing approach. Results are shown, along with suggestions for future enhancements.

ISSN:1063-7192    

DOI:10.1080/10637199408962523

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

This paper describes the usage of feed-forward artificial neural networks, for the implementation of a variety of iterative methods of numerical linear algebra for solving linear systems of equations. Extensions to matrix based iterative procedures are also presented and the application of those iterative methods in neural network training algorithms is discussed. Finally, some experimented results are presented, comparing the various methods discussed.

ISSN:1063-7192    

DOI:10.1080/10637199408962524

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper we present fast parallel algorithms for finding the cutpoints and bridges of an undirected graph G = (V,E) havingnvertices. We start with the notion of partitioning a graph in a set of (mutually disjoint) adjacency-level sets, and we propose a parallel algorithm which computes these sets in time O(logL) using L · H · n2processors on a CRCW-PRAM, where L < n and H < n. Based on the properties of the adjacency-level sets, we formulate parallel algorithms which locate all cutpoints and bridges of an undirected graph in constant time O(1) by using no more than L · H · n2processors on a CRCW-PRAM computational model.

ISSN:1063-7192    

DOI:10.1080/10637199408962525

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this study, we introduce the weak precedence constrained (WPC) problem and present a two-stage approach for its allocation in a homogenous distributed architecture. The performance of the two-stage algorithm is compared with that of a simulated annealing algorithm through experimental results. The two-stage algorithms outperform the simulated annealing algorithm significantly based on a given performance measure. A detailed description of the two-stage approach proposed in [22] is given here.

ISSN:1063-7192    

DOI:10.1080/10637199408962526

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper the parallel solution of a block diagonal bordered system of linear equations is presented. Block Gaussian elimination is used to solve the system, and the implementation of the concurrent algorithm is carried out using a general purpose harness for parallel execution calledExDaTa. This harness allows the execution of a data- and function-partitioned (MIMD) program to achieve flexible partitioning strategies and programming simplicity

ISSN:1063-7192    

DOI:10.1080/10637199408962527

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

If we consider the knowledge of the insertion points of the items and one sorted sequence into another as solving the problem of merging two sequences, the merging of two sequences and the searching for multiple (sorted) values in a sequence can be considered as twin problems. Both, which we shall call the multiple ranking problem, can be phrased as determining the insertion or location point of one sequence in other

ISSN:1063-7192    

DOI:10.1080/10637199408962528

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Mathematical structures associated with parallel computations are considered. We introduce the notion of perpendicular computations. Compositions of the parallel and perpendicular computations of funaion evaluations, decompositions of linear operators acting in Banach spaces are discussed. Such perpendicular computations for nonlinear operator equations as localization of roots by computing rotation of a vector field and separation of branches in neighbourhoods of branch points are demonstrated.

ISSN:1063-7192    

DOI:10.1080/10637199408962529

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We consider analogies between statistic mechanical approach and computational algorithm description. The notion of algorithm entropy is introduced to characterize measure of potential parallelism and compare algorithms. The value of entropy for some couple of algorithms is evaluated (ordinary block matrix multiplication and Strassen's algorithm, LU decomposition and QIF, particle-particle and particle-mesh algorithms). We discuss thermodynamical approach to the algorithm description in the frame of which one can discover self-organization phenomenon in massively parallel algorithms.

ISSN:1063-7192    

DOI:10.1080/10637199408962530

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We present two new parallel algorithms for exact (error-free) solution of a system of linear equations on a distributed-memory multiprocessor. The exact solution is obtained using the congruence technique which consists of two steps: First, the system of linear equations is converted to systems of linear congruence equations with respect to several prime moduli, and each of these systems is solved on a separate processor. Then, these solutions are combined using the mixed-radix conversion algorithm to obtain the exact solution. The first step is completely (embarrassingly) parallel with no communication requirements among the processors. We improve our previous work and describe two efficient parallel algorithms for the second step. We present the results of our experiments on an Intel iPSC/860 with 8 processors. A linear system of dimension 128 with integer entries as large as 10577is solved in about 195 seconds on 8 processors with an efficiency of 99.76%.

ISSN:1063-7192    

DOI:10.1080/10637199408962531

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor