作者：
Wilmoth, Richard G.NASA
Langley Res Ctr Div Space Syst Aerothermodynam Branch Hampton VA 23665 USA
A method for executing a direct simulation Monte Carlo (DSMC) analysis using parallel processing is described. The method is based on using domain decomposition to distribute the work load among multiple processors, a...
详细信息
A method for executing a direct simulation Monte Carlo (DSMC) analysis using parallel processing is described. The method is based on using domain decomposition to distribute the work load among multiple processors, and the DSMC analysis is performed completely in parallel. Message passing is used to transfer molecules between processors and to provide the synchronization necessary for the correct physical simulation. Benchmark problems are described for testing the method, and results are presented that demonstrate the performance on two commercially available multicomputers. The results show that reasonable parallel speedup and efficiency can be obtained if the problem is sized properly to the number of processors. It is projected that, with a massively parallel system, performance exceeding that of current supercomputers is possible.
In this paper, we consider the problem of constructing a Voronoi diagram in L1(L-infinity) metric for a set of n points in the Cartesian plane on a mesh-connected computer. An O(square-root n) parellel algorithm on a ...
详细信息
In this paper, we consider the problem of constructing a Voronoi diagram in L1(L-infinity) metric for a set of n points in the Cartesian plane on a mesh-connected computer. An O(square-root n) parellel algorithm on a square-root n x square-root n mesh-connected computer is given for solving that problem. This is the first solution on a square-root n x square-root n MCC to achieve an asymptotically optimal theta(square-root n) running time for L1(L-infinity) metric.
This paper presents a parallel algorithm for sorting on any graph with a Hamiltonian path and 1-factorization. For an n-cube the algorithm is equivalent to the sequential balanced sorting network of Dowd, Perl, Rudolp...
详细信息
This paper presents a parallel algorithm for sorting on any graph with a Hamiltonian path and 1-factorization. For an n-cube the algorithm is equivalent to the sequential balanced sorting network of Dowd, Perl, Rudolph, and Saks. The application of this algorithm to other networks is discussed.
Givennitems, a parallel algorithm for generating all then! permutations is presented. The computational model used is a linear array which consists ofnidentical processing elements with a simple structure. One permuta...
详细信息
Givennitems, a parallel algorithm for generating all then! permutations is presented. The computational model used is a linear array which consists ofnidentical processing elements with a simple structure. One permutation is produced at each other time step. The elapsed time to produce a permutation is independent of the integern. The basic idea used is the iterative method and the exchange of two consecutive components in an existing permutation. The design procedures of this algorithm are considered in detail. The ranking and unranking functions of the required permutations are also discussed.
We show that the same basic recurrence can be used to solve a number of classical problems from linear algebra and graph theory, including instances of the algebraic path problem, matrix multiplication, matrix triangu...
详细信息
We show that the same basic recurrence can be used to solve a number of classical problems from linear algebra and graph theory, including instances of the algebraic path problem, matrix multiplication, matrix triangularization, and matrix transpose, and we give a simple mapping of the recurrence onto a unidirectional linear array. Qualitative advantages to programming linear arrays using this approach include uniformity of design, simplicity of programming, and scalability to larger problems. The major disadvantage is that the resulting algorithms are not necessarily optimal.
The nearest neighbor (NN) classification schemes have been popular in pattern recognition because of their efficiency and simplicity. The computation of distances of a testing pattern to the training patterns is very ...
详细信息
The nearest neighbor (NN) classification schemes have been popular in pattern recognition because of their efficiency and simplicity. The computation of distances of a testing pattern to the training patterns is very time-consuming. This paper proposes several parallel algorithms for nearest neighbor classification on two different types of SIMD machines. One type of SIMD machine has parallel shared memory modules. An alignment network is used to connect the processors and the memory modules. The data storage schemes and two different procedures on this machine type are presented. The other type of machines employs only a distributed memory system and an interconnection network. The data distribution and communication issues are discussed. For a problem with N(p) training patterns and N(f) features, comparing the distances from a testing pattern to all training patterns takes O(N(p)N(f)) time on a sequential machine. The distance computation and comparison can be performed in parallel. The proposed algorithms on a parallel machine with Q processing elements (PEs) take approximately O(N(p)N(f)/Q) time.
We present a parallel algorithm which computes recursively, in increasing order, the complete generalized eigendecompositions of the successive subpencils contained in a maximum size Hermitian Toeplitz generalized eig...
详细信息
We present a parallel algorithm which computes recursively, in increasing order, the complete generalized eigendecompositions of the successive subpencils contained in a maximum size Hermitian Toeplitz generalized eigenproblem. At each order a number of independent, structurally identical, nonlinear problems are solved in parallel, facilitating fast implementation. The multiple and clustered minimum eigenvalue cases are treated in detail. In the application of our algorithm to narrowband array processing in colored noise, the direction-of-arrival containing eigenspace information is provided recursively in order. This permits estimation of the angles of arrival for subsequent orders, facilitating early estimation of the number of sources as well as verification of results obtained at previous orders.
Most current thinning algorithms use only small windows (templates) due to the heavy computation load associated with large template size. However, the lack of global information leads to severe shape distortion and m...
详细信息
Most current thinning algorithms use only small windows (templates) due to the heavy computation load associated with large template size. However, the lack of global information leads to severe shape distortion and misclassification. We develop a new variable resolution method to solve this problem. The proposed algorithm, which is parallel in nature, uses a 9 x 9 window with a high resolution 3 x 3 center and low resolution periphery. The resolution is reduced by a ratio of 9 : 2 in the periphery. Thus the complexity of our method is less than twice that of a method using 4 x 4 windows. Our method resembles the human visual system which has a high resolution fovea and low resolution periphery. The advantage of the proposed algorithm over two well-known algorithms is demonstrated using several input characters.
In this paper a systolic algorithm is presented for the Simplex algorithm as used in Linear Programming applications. In addition, to reduce computer storage requirements, a revised form of the algorithm is considered...
详细信息
In this paper a systolic algorithm is presented for the Simplex algorithm as used in Linear Programming applications. In addition, to reduce computer storage requirements, a revised form of the algorithm is considered for systolic array implementation using the product form of the inverse.
Forming the transitive closure of a binary relation (or directed graph) is an important part of many algorithms. When the relation is represented by a bit matrix, the transitive closure can be efficiently computed in ...
详细信息
Forming the transitive closure of a binary relation (or directed graph) is an important part of many algorithms. When the relation is represented by a bit matrix, the transitive closure can be efficiently computed in parallel in a systolic array. Here we propose two novel ways of computing the transitive closure of an arbitrarily big graph on a systolic array of fixed size. The first method is a simple partitioning of a well-known systolic algorithm for computing the transitive closure. The second is a block-structured algorithm. This algorithm is suitable for execution on a systolic array that can multiply fixed size bit matrices and compute transitive closure of graphs with a fixed number of nodes. The algorithm is, however, not limited to systolic array implementations;it works on any parallel architecture that can perform these bit matrix operations efficiently. The shortest path problem, for directed graphs with weighted edges, can also be solved in the same manner, devised above, as the transitive closure is computed.
暂无评论