ISSN:1063-7192    

DOI:10.1080/10637199408915403

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Data parallelism, in which the same operation is performed on many elements of an n-dimensional array, is one of the most powerful methods of extracting parallelism in scientific computation. One form of data parallelism involves defining a sequence of parallel wavefronts of a computation. Each wavefront consists of an (n - l)-dimcnsional subarray of the evaluated array and all wavefront elements are evaluated simultaneously. Different wavefronts result in different performance, so the question arises how to determine the wavefronts that result in the minimum computation time. Wavefront determination should define also allocation of wavefront elements to processors.

ISSN:1063-7192    

DOI:10.1080/10637199408915404

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We present load balancing, selection, and sorting algorithms for the star and pancake networks. Let Xnbe an n-star or n-pancake with p = n! processors with N elements distributed evenly among (he processors such that each processor holds at most [N/p] elements, N ≥ n!. Our selection algorithm selects the κth smallest element on Xnin O((N/P))loglogp + (logN/p)n3logn) time. The sorting algorithm sorts the N elements on Xnin 0((N/p)nlogp + log(N/p)n4log2n) time. This new sorting algorithm is asymptotically faster than the previously fastest known algorithm when N = ω((n log2+δn)p) = ω((log p)(loglog p)1+δp), i.e., when N = O(p1+ε), for any δ > 0 and ε > 0. A main component of the sorting algoriihm is a procedure for balancing the load among all the processors in each of the two networks. This procedure runs in O(nM + n3logn) lime, where M is the maximum load among all the processors in the network.

ISSN:1063-7192    

DOI:10.1080/10637199408915405

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Efficient parallel algorithms for finding an optimal path-shaped or tree-shaped facility with a specified size in a tree network are presented. Four kinds of optimization criteria are considered: minimizing/maximizing distancesum/eccentricity. There are eight cases when considering facility shapes and optimization criteria. Parallel algorithms for finding a minimum/maximum distancesum path were presented in [9]. The other six cases are studied in this paper. Two of these six cases can be solved optimally in linear Time x Processor complexity. For the problem of finding a maximum distancesum tree, the algorithm presented in this paper is the first polynomial time solution under a reasonable assumption.

ISSN:1063-7192    

DOI:10.1080/10637199408915406

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We present a new parallel best-first Branch and Bound algorithm designed for distributed memory machines. Starting from an axiomatization of the Branch and Bound pardigm, we develop the notion of fringes in the Branch and Bound tree which correspond to sets of equivalent problems. The algorithm proposed in this paper evaluates these sets of problems in parallel, during each phase of its execution. These computationally intensive phases alternate with control phases where synchronization and information exchange between processors lakes place. We use a probabilistic model for predicting the performances of this algorithm. Finally, we discuss the performances obtained on MIMD-DM multiprocessors for the asymmetric non-Euclidean Traveling Salesman Problem.

ISSN:1063-7192    

DOI:10.1080/10637199408915407

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Finitely inductive (Fl) sequences are a class of sequences, finite or infinite, which are amenable to a certain mathematical representation which has direct significance to pattern recognition and string matching. Pattern recognition using the Fl technique first transforms known patterns into function table(s) byfactoring, and then uses the function table(s) to match an input pattern byfollowing. Factoring is done off line and only once for each pattern. The sequential time for matching two sequences depends only upon the length of the input sequence. In this paper, we propose cost-optimal (i.e., efficient) parallel algorithms for Fl sequence processing. These algorithms include parallelfactoring and followingby bucket packing on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. The proposed algorithms also have implications to parallel integer sorting.

ISSN:1063-7192    

DOI:10.1080/10637199408915408

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We show that the notoriously difficult problem of finding the minimum number of paths that cover the vertices of a graph can be solved efficiently for cographs. Our result implies that for this class of graphs finding a hamiltonian path and a hamiltonian cycle can be solved efficiently in parallel. Specifically, with ann-vertcx cographGrepresented by its parse tree as input, our algorithm determines the number of paths in a minimum path cover in O(logn) time usingn/lognprocessors in the EREW-PRAM; we also exhibit all the paths in a minimum path cover of G inO(log2n) lime usingn/lognprocessors in the EREW-PRAM. Our result significantly improves on the state of the art.

ISSN:1063-7192    

DOI:10.1080/10637199408915409

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Determining the parallel complexity of maximum cardinality matching in bipartite graphs is one of the most famous open problems in parallel algorithm design. The problem is known to be in RNC, but all known fast (polylogarithmic running time) parallel algorithms that find maximum cardinality matchings require the use of random numbers. Moreover, they are based on matrix algebra, so they are inherently inefficient for sparse graphs. Therefore, we are interested in the problem of finding an approximate maximum cardinality matching. The parallel matching algorithm of Goldberg, Plotkin and Vaidya (FOCS 1988) can be modified so that it runs in O(a2log3n) time on an EREW PRAM with n + m processors and finds a matching of size (1 - 1/a)p when given a graph with n vertices, m edges, and a maximum cardinality matching of size p. The resulting algorithm is deterministic.

ISSN:1063-7192    

DOI:10.1080/10637199408915410

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We focus on differences inherent in the design and implementation of non-numeric parallel algorithms on MIMD and SIMD architectures. We take as our prototypical examples time-space optimal merging and sorting routines. Our representative MIMD and SIMD machines are the Sequent Symmetry S81 and the Connection Machine CM-2, respectively. In addition to the contrast provided by their differing execution philosophies, this choice of machines allows us to compare results from both shared-memory and distributed-memory models.

ISSN:1063-7192    

DOI:10.1080/10637199408915411

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper we present an array based network analyzer for Broadband Integrated Services Digital Networks. The analyzer is laid as a linear array processor. We describe the implementation of the analyzer's functions on the array processor. Apart the real-time application, the importance of this study becomes more apparent by the fact that, the resulting design can be implemented on configurable gate array and be attached to a microprocessor. Nevertheless, it is also possible to use the analyser array in combination with commercially available hardware to debug the network equipment in the development phase.

ISSN:1063-7192    

DOI:10.1080/10637199408915412

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor