Choosing transmitter locations among alternatives optimally in a radio network, regarding a known area, to guarantee a stipulated quality of service (QOS), is tackled by coarse-grained parallel genetic algorithms, whi...
详细信息
ISBN:
(纸本)0780372689
Choosing transmitter locations among alternatives optimally in a radio network, regarding a known area, to guarantee a stipulated quality of service (QOS), is tackled by coarse-grained parallel genetic algorithms, which maximize the coverage while reduce the number of utilized transmitters. An exclusive local search operator is raised, and the impacts of neighbor topologies are compared. Simulations on a dedicated cluster demonstrate that our local search operator is very effective, in the meantime, increasing the neighbor number of subpopulations will ameliorate optimization quality.
This paper surveys new trends recently introduced in the most commonly occurring problems of linear algebra which will have a significant impact on all aspects of scientific computation and software development as it ...
详细信息
This paper surveys new trends recently introduced in the most commonly occurring problems of linear algebra which will have a significant impact on all aspects of scientific computation and software development as it comes under pressure from the increasing advancement from parallel computing technology in its transition from sequential to parallel algorithmic techniques during the next decade. Topics will include direct methods for dense matrices and alternating group explicit methods. The computational analyses of the proposed strategies are presented which demonstrate that limited parallelism by using explicit block (2 x 2, 3 x 3) schemes can be effective in reducing data storage accesses in shared memory and communication in distributed parallel computer systems.
For a positive integer c, a c-vertex-ranking of a graph G = (V, E) is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels > i leaves connected components, ...
详细信息
For a positive integer c, a c-vertex-ranking of a graph G = (V, E) is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. The c-vertex-ranking problem is to find a c-vertex-ranking of a given graph using the minimum number of ranks. In this paper we give an optimal parallel algorithm for solving the c-vertex-ranking problem on trees in O (log(2) n) time using linear number of operations on the EREW PRAM model. (C) 2004 Elsevier B.V. All rights reserved.
A parallel quaternion-based dissipative particle dynamics (QDPD) program has been developed in Fortran to study the flow properties of complex fluids subject to shear. The parallelization allows for simulations of gre...
详细信息
A parallel quaternion-based dissipative particle dynamics (QDPD) program has been developed in Fortran to study the flow properties of complex fluids subject to shear. The parallelization allows for simulations of greater size and complexity and is accomplished with a parallel link-cell spatial (domain) decomposition using MPI. The technique has novel features arising from the DPD formalism, the use of rigid body inclusions spread across processors, and a sheared boundary condition. A detailed discussion of our implementation is presented, along with results on two distributed memory architectures. A parallel speedup of 24.19 was obtained for a benchmark calculation on 27 processors of a distributed memory cluster.
We present the first space and time optimal parallel algorithm for the pairwise sequence alignment problem, a fundamental problem in computational biology. This problem can be solved sequentially in O(mn) time and O(m...
详细信息
We present the first space and time optimal parallel algorithm for the pairwise sequence alignment problem, a fundamental problem in computational biology. This problem can be solved sequentially in O(mn) time and O(m + n) space, where m and n are the lengths of the sequences to be aligned. The fastest known parallel space-optimal algorithm for pairwise sequence alignment takes optimal O(m+n/p) space, but suboptimal O(m+n)(2)/p) time, where p is the number of processors. On the other hand, the most space economical time-optimal parallel algorithm takes O(mn/p) time, but O(m+n/p) space. We close this gap by presenting an algorithm that achieves both time and space optimality, i.e. requires only O(m+n/p) space and O(mn/p) time. We also present an experimental evaluation of the proposed algorithm on an IBM xSeries cluster. Although presented in the context of full sequence alignments, our algorithm is applicable to other alignment problems in computational biology including local alignments and syntenic alignments. It is also a useful addition to the range of techniques available for parallel dynamic programming.
A black-box methodology of a parallel generation of adaptive anisotropic meshes is described. A control of mesh adaptation, important for robustness and flexibility, may effect parallel properties of the methodology. ...
详细信息
A black-box methodology of a parallel generation of adaptive anisotropic meshes is described. A control of mesh adaptation, important for robustness and flexibility, may effect parallel properties of the methodology. This is demonstrated with a 3D example.
A common statistical problem is that of finding the median element in a set of data. This paper presents an efficient randomized high-level parallel algorithm for finding the median given a set of elements distributed...
详细信息
A common statistical problem is that of finding the median element in a set of data. This paper presents an efficient randomized high-level parallel algorithm for finding the median given a set of elements distributed across a parallel machine. In fact, our algorithm solves the general selection problem that requires the determination of the element of rank k, for an arbitrarily given integer k. Our general framework is an SPMD distributed-memory programming model that is enhanced by a set of communication primitives. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The algorithms have been coded in the message-passing standard MPI, and our experimental results from the IBM SP-2 illustrate the scalability and efficiency of our algorithm and improve upon all the related experimental results known to the author. The main contributions of this paper are (1) New techniques for speeding the performance of certain randomized algorithms, such as selection, which are efficient with likely probability. (2) A new, practical randomized selection algorithm (UltraFast) with significantly improved convergence. (C) 2004 Elsevier Inc. All rights reserved.
Paper presents a wavelet based, high performance image denoising scheme implemented in a parallel virtual machine (PVM) environment. Performance of generalized cross validation (GCV) based threshold selection scheme i...
详细信息
Paper presents a wavelet based, high performance image denoising scheme implemented in a parallel virtual machine (PVM) environment. Performance of generalized cross validation (GCV) based threshold selection scheme is poorer from CPU time viewpoint when implemented sequentially. In contrast to the traditional parallel approaches, which rely on specialized parallel machines, the present work explores the potential of distributed systems for parallelism. The master/slave model is adopted for control of machines. In this paper the performance of GCV based thresholding algorithm is presented in PVM environment. The proposed algorithm outperforms Donoho and Johnstone's Universal and SureSrink thresholding scheme in most of the test cases. The present investigation validates suitability of GCV thresholding scheme from parallel implementation viewpoint. (C) 2003 Elsevier Inc. All rights reserved.
This paper presents a new network-flow formulation for the problem of predicting 3D protein structures using threading. Several integer-programming models based on this formulation are proposed and compared. These mod...
详细信息
This paper presents a new network-flow formulation for the problem of predicting 3D protein structures using threading. Several integer-programming models based on this formulation are proposed and compared. These models allow for an efficient decomposition and for the application of a parallel branch-and-cut algorithm, significantly reducing the running time. The efficiency of our approach has been confirmed by extensive computational experiments.
Let T = (V, E) be an edge-weighted tree with \V\ = n vertices embedded in the Euclidean plane. Let E denote the set of all points on the edges of T. Let X and Y be two subsets of E and let r be a positive real number....
详细信息
Let T = (V, E) be an edge-weighted tree with \V\ = n vertices embedded in the Euclidean plane. Let E denote the set of all points on the edges of T. Let X and Y be two subsets of E and let r be a positive real number. A subset D subset of or equal to X is an X/Y/r-dominating set if every point in Y is within distance r of a point in D. The X/Y/r-dominating set problem is to find an X/Y/r-dominating set D* with minimum cardinality. Let p greater than or equal to 1 be an integer. The X/Y/p-center problem is to find a subset C* subset of or equal to X of p points such that the maximum distance of any point in Y from C* is minimized. Let X and Y be either V or E. In this paper, efficient parallel algorithms on the EREW PRAM are first presented for the X/Y/r-dominating set problem. The presented algorithms require O(log(2) n) time for all cases of X and Y. parallel algorithms on the EREW PRAM are then developed for the X/Y/p-center problem. The presented algorithms require O(log(3) n) time for all cases of X and Y. Previously, sequential algorithms for these two problems had been extensively studied in the literature. However, parallel solutions with polylogarithmic time existed only for their special cases. The algorithms presented in this paper are obtained by using an interesting approach which we call the dependency-tree approach. Our results are examples of parallelizing sequential dynamic-programming algorithms by using the approach.
暂无评论