Let T=(V, E) be a tree with vertex set V and edge set E. Let n=|V|. Each e/spl isin/E has a non-negative length. In this paper, we first present an algorithm on the CREW PRAM for solving the V/V/r-dominating set probl...
详细信息
ISBN:
(纸本)0769517609
Let T=(V, E) be a tree with vertex set V and edge set E. Let n=|V|. Each e/spl isin/E has a non-negative length. In this paper, we first present an algorithm on the CREW PRAM for solving the V/V/r-dominating set problem on T, where r/spl ges/0 is a real number. The algorithm requires O(log/sup 2/ n) time using O(n log n) work. Applying this algorithm as a procedure for testing feasibility, the V/V/p-center problem on the CREW PRAM is solved in O(log/sup 2/ n) time using O(n log/sup 2/ n) work, where p/spl ges/1 is an integer. Previously, He and Yesha had proposed algorithms on the CREW PRAM for special cases of the V/V/r-dominating set and the V/V/p-center problems, in which r is an integer and the lengths of all edges are 1. Their V/V/r-dominating set algorithm requires O(log n log log n) time using O(n log n log log n) work; and their V/V/p-center algorithm requires O(log/sup 2/ n log log n) time using O(n log/sup 2/ n log log n) work. As compared with He and Yesha's results, ours are more general and more efficient from the aspect of work.
It is presented in this work new parallel algorithms to train a multilayer perceptron network using the error backpropagation algorithm. An analysis of the different paralleling strategies used is shown and aspects su...
详细信息
It is presented in this work new parallel algorithms to train a multilayer perceptron network using the error backpropagation algorithm. An analysis of the different paralleling strategies used is shown and aspects such as-task definition and communications profile were taken into account. An application in image compression illustrates the capacity of these new procedures when compared to the classical approach and to other parallel implementations.
By means of an abstract model of the SIMD type with vertical data processing (the STAR-machine), we present a simple associative parallel algorithm for finding tree paths in undirected graphs. We study applications of...
详细信息
By means of an abstract model of the SIMD type with vertical data processing (the STAR-machine), we present a simple associative parallel algorithm for finding tree paths in undirected graphs. We study applications of this algorithm to update minimum spanning trees in undirected graphs, to determine maximum flow values in a multiterminal network, and to find a fundamental set of circuits with respect to a given spanning tree. These algorithms are given as the corresponding STAR procedures whose correctness is proved and time complexity is evaluated.
In this paper we present new parallel versions of sequential Goertzel and Reinsch algorithms for calculating trigonometric sums. The new algorithms use a recently introduced, very efficient BLAS-based algorithm for so...
详细信息
In this paper we present new parallel versions of sequential Goertzel and Reinsch algorithms for calculating trigonometric sums. The new algorithms use a recently introduced, very efficient BLAS-based algorithm for solving linear recurrence systems with constant coefficients. To achieve their portability across different shared-memory parallel architectures, the algorithms have been implemented in Fortran 77 and OpenMP We also present experimental results performed on a two processor Pentium III computer running under Linux operating system with Atlas as an efficient implementation of BLAS. The new algorithms are up to 60-90% faster than the equivalent sequential Goertzel and Reinsch algorithms, even on one processor.
We develop parallel algorithms for pricing a class of multidimensional financial derivatives employing a binomial lattice approach. We describe the algorithms, explain their complexities, and study their performance. ...
详细信息
We develop parallel algorithms for pricing a class of multidimensional financial derivatives employing a binomial lattice approach. We describe the algorithms, explain their complexities, and study their performance. The limitations posed by the problem size on the recursive algorithm and the solution to overcome this problem by an iterative algorithm are explained through experimental results using MPI. We first present analytical results for the number of computations and communications for both the algorithms. Since the number of nodes in a recombining lattice grows linearly with the problem size, it is feasible to price long-dated options using a recombining lattice. We have extended our algorithm to handle derivatives with many underlying assets and shown that the multi-asset derivatives offer a better problem for parallel computation. This is very important for the finance industry since long-dated derivatives with many underlying assets are common in practice.
In a cellular network, the base stations are not necessarily uniformly distributed, and their corresponding cell sizes are not necessarily the same. For example, a cell in a well-populated city cell is usually smaller...
详细信息
In a cellular network, the base stations are not necessarily uniformly distributed, and their corresponding cell sizes are not necessarily the same. For example, a cell in a well-populated city cell is usually smaller than a cell in a rural area. To study a cellular network with non-uniform cell sizes, one approach is to use a virtual cellular network with a uniform cell size such that each virtual cell contains at most one base station. This paper has proposed parallel algorithms for meshes with multiple broadcasting to construct virtual mesh and honeycomb cellular networks for non-uniformly distributed base stations. The constructed virtual cellular networks are optimal in the sense that their corresponding uniform cell sizes reach the largest possible. The algorithms run in O(log n) time on a mesh with multiple broadcasting of size n/spl times/n to construct optimal virtual mesh and honeycomb cellular networks for n non-uniformly distributed base stations. Furthermore, those algorithms are time-optimal.
Expressed sequence tags, ESTs, are DNA molecules experimentally derived from expressed portions of genes. Clustering of ESTs is essential for gene recognition and understanding important genetic variations such as tho...
详细信息
Expressed sequence tags, ESTs, are DNA molecules experimentally derived from expressed portions of genes. Clustering of ESTs is essential for gene recognition and understanding important genetic variations such as those resulting in diseases. In this paper, we present the design and development of a parallel software system for EST clustering. To our knowledge, this is the first such effort to address the problem of EST clustering in parallel. The novel features of our approach include 1) design of space efficient algorithms to keep the space requirement linear in the size of the input data set, 2) a combination of algorithmic techniques to reduce the total work without sacrificing the quality of EST clustering, and 3) use of parallel processing to reduce the run-time and facilitate the clustering of large datasets. Using a combination of these techniques, we report the clustering of 81,414 Arabidopsis ESTs in under 2.5 minutes on a 64-processor IBM SP, a problem that is estimated to take 9 hours of run-time with a state-of-the-art software, provided the memory required to run the software can be made available.
We present the transformational derivations of several efficient, scalable, message-passing parallel algorithms from clear functional specifications. The starting algorithms rely on some commonly used combinatorial li...
详细信息
We present the transformational derivations of several efficient, scalable, message-passing parallel algorithms from clear functional specifications. The starting algorithms rely on some commonly used combinatorial list generator functions such as tails, inits, splits and cp (Cartesian product) for generating useful intermediate results. This paper provides generic parallel algorithms for efficiently implementing a small library of useful combinatorial list generator functions. It also provides a framework for relating key higher order functions such as map, reduce, and scan with communicating processes with different configurations. The parallelisation of many interesting functional algorithms can then be systematically synthesized by taking an "off the shelf" parallel implementation of the list generator and composing it with appropriate parallel implementations of instances of higher order functions. Efficiency in the final message-passing algorithms is achieved by exploiting data parallelism, for generating the intermediate results in parallel;and functional parallelism, for processing intermediate results in stages such that the output of one stage is simultaneously input to the next one. This approach is then illustrated with a number of case studies which include: testing whether all the elements of a given list are distinct, the maximum segment sum problem, the minimum distance of two sets of points, and rank sort. In each case we progress from a quadratic time initial functional specification of the problem to a linear time parallel message-passing implementation which uses a linear number of communicating sequential processes. Bird-Meertens Formalism is used to concisely carry out the transformations.
暂无评论