An algorithm for finding a shortest path between each pair of nodes of a positive arc weighted graph on a shared memory model of a single instruction-stream multiple data-stream computer is proposed. The time complexi...
详细信息
An algorithm for finding a shortest path between each pair of nodes of a positive arc weighted graph on a shared memory model of a single instruction-stream multiple data-stream computer is proposed. The time complexity of the algorithm is of O(log d . log n), where d and n denote the diameter and the number of nodes of the graph, respectively. At most, O(n3) processors are required to achieve this time bound.
In this paper, we present a parallel algorithm for solving the all-pairs vertical segment visibility reporting (SVR) problem. Given a set S = {S0, S1,...,S(n-1)} of disjoint vertical segments in the plane, the SVR pro...
详细信息
In this paper, we present a parallel algorithm for solving the all-pairs vertical segment visibility reporting (SVR) problem. Given a set S = {S0, S1,...,S(n-1)} of disjoint vertical segments in the plane, the SVR problem asks for the determination and reporting of all the distinct visibility pairs. Our algorithm solves the SVR problem in O(log n) time using O(n log n) space and O(n) processors on an EREW PRAM (Exclusive Read Exclusive Write parallel Random Access Machine) computational model.
Cell dynamics simulation (CDS) is a very promising approach to model dynamic processes in block copolymer systems at the mesoscale level. It is difficult to implement a real time and experimental-scale simulation with...
详细信息
Cell dynamics simulation (CDS) is a very promising approach to model dynamic processes in block copolymer systems at the mesoscale level. It is difficult to implement a real time and experimental-scale simulation with traditional serial algorithms because of the expensive computation. A parallel, spatial decomposition-based algorithm for large-scale CDS is proposed. With the efficient strategy of domain decomposition and the fast method of neighbouring points location, we greatly reduce the calculating and communicating cost. The numerical results indicate that the proposed parallel algorithm can provide an efficient procedure for computer simulation of block copolymer systems of experimental size.
The author presents a parallel algorithm for finding a maximum 2-chain edge packing of an undirected graph G = (V, E). It runs in O(log n) time using O(n + m) processors on a CRCW PRAM, where n = !V! and m = !E!.
The author presents a parallel algorithm for finding a maximum 2-chain edge packing of an undirected graph G = (V, E). It runs in O(log n) time using O(n + m) processors on a CRCW PRAM, where n = !V! and m = !E!.
A simple parallel algorithm for the evaluation of polynomials written in the Chebyshev form is introduced. By this method only 2 inverted right perpendicularlog(2)(p - 2)inverted left perpendicular + inverted right pe...
详细信息
A simple parallel algorithm for the evaluation of polynomials written in the Chebyshev form is introduced. By this method only 2 inverted right perpendicularlog(2)(p - 2)inverted left perpendicular + inverted right perpendicularlog(2) pinverted left perpendicular + 4inverted right perpendicularN/pinverted left perpendicular - 7 steps on p processors are needed to evaluate a Chebyshev series of degree N. Theoretical analysis of the efficiency is performed and some numerical examples on a CRAY T3D are shown.
High accuracy surface modeling (HASM) has been proved to be a superior method for surface simulation compared to classical interpolation methods. However, the fact that HASM is time consuming combined with its depende...
详细信息
High accuracy surface modeling (HASM) has been proved to be a superior method for surface simulation compared to classical interpolation methods. However, the fact that HASM is time consuming combined with its dependence on its driving field restricts its application in large area problems. This research develops a modified HASM which can get rid of the driving field in the surface simulation, and the parallel version of the modified HASM is also proposed with the purpose of improving its computational efficiency. Light detection and ranging (LIDAR) data are used as an optimum constraint to construct digital elevation model (DEM). Tests show that the modified HASM can perform surface simulation successfully without the driving field. And it also shows that the simulation accuracy of the modified HASM is almost the same as the old HASM and the classical interpolation methods when the sampling rate is larger than 0.5 %, while the modified HASM shows significantly increased simulation accuracy as the sampling rate decreases. This characteristic indicates that the modified HASM no longer relies on the driving field in the surface simulation. And it also improves the simulation accuracy compared to the old HASM and the classical interpolation methods. Tests of parallel efficiency show that the master-slave mode used in the parallel algorithm obtains a satisfactory result, indicating that the HASM can be applied to surface simulation of large area problems. And it also shows that the modified HASM would have great potential where applied in high-resolution DEM and digital surface model (DSM) construction from LIDAR data.
Some testing results on DAWNING-1000, Paragon and workstation cluster are described in this paper. On the home-made parallel system DAWNING-1000 with 32 computational processors, the practical performance of 1.117 Gfl...
详细信息
Some testing results on DAWNING-1000, Paragon and workstation cluster are described in this paper. On the home-made parallel system DAWNING-1000 with 32 computational processors, the practical performance of 1.117 Gflops and 1.58 Gflops has been measured in solving a dense linear system and doing matrix multiplication, respectively. The scalability is also investigated. The importance of designing efficient parallel algorithms for evaluating parallel systems is emphasized.
This paper parallelizes the embedding strategy for mapping any two-dimensional grid into its optimal hypercube with minimal dilation. The parallelization allows each hypercube node to independently determine, in const...
详细信息
This paper parallelizes the embedding strategy for mapping any two-dimensional grid into its optimal hypercube with minimal dilation. The parallelization allows each hypercube node to independently determine, in constant time, which grid node it will simulate and the communication paths it will take to reach the hypercube nodes which simulate its grid-neighbors. The paths between grid-neighbors are chosen in such a way as to curb the congestion at each hypercube node and across each hypercube edge. Explicity, the node congestion for our embedding is at most 6 (one above optimal), while the edge congestion is at most 5.
This paper presents a general purpose algorithm for solving the Unfriendly Beehive Game. The proposed algorithm will utilize an artificial neural network to solve the problem. The neural network will use a simple part...
详细信息
This paper presents a general purpose algorithm for solving the Unfriendly Beehive Game. The proposed algorithm will utilize an artificial neural network to solve the problem. The neural network will use a simple partial differential (motion) equation expressed in terms of its natural constraints. Each constraint within the equation represents a simple connection to an artificial neuron. Each connection strength (or synaptic strength) is weighted by multiplicative constants and summed together. The result is an input that is adjusted in the direction that decreases the error or conflict. Using this information, the system derives a simple binary state output in an attempt to solve the puzzle. Given an overall time slot in which to resolve all conflicts, the system iteratively strives to arrive at the state of the global minimum. The proposed algorithm will be able to solve a variety of real-world problems, including: facility layouts for maximizing productivity and safety, classroom assignment for minimizing pupil conflict, crop and plant placement for maximizing yields, and chemical placement within shipping boxes to reduce the possibility of chemical interactions.
Let C = {c1,...,c(m)} be a family of subsets of a finite set S = {1,..., n}, a subset S' of S is a co-hitting set if S' contains no element of C as a subset. By using an O ( (log n) 2) time EREW PRAM algorithm...
详细信息
Let C = {c1,...,c(m)} be a family of subsets of a finite set S = {1,..., n}, a subset S' of S is a co-hitting set if S' contains no element of C as a subset. By using an O ( (log n) 2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show that a maximal co-hitting set for S can be computed on an EREW PRAM in time O (alphabeta (log (n + m))2) using 0 (n2m) processors, where alpha = max{\c(i)\\i = 1,...,n} and beta =max{\d(j)\\ j = 1,...n} with d(j)={c(i)\j is-an-element-of c(i)}. This implies that if alphabeta = O((log(n+m))k) then the problem is solvable in NC.
暂无评论