This paper first presents two implementations of parallel Gaussian elimination using MPI, one uses cyclic data mapping and pipelined point-to-point communication, the other one uses blocked data mapping and MPI collec...
详细信息
ISBN:
(纸本)0769517315
This paper first presents two implementations of parallel Gaussian elimination using MPI, one uses cyclic data mapping and pipelined point-to-point communication, the other one uses blocked data mapping and MPI collective communication. Then, theoretical performance analysis for the two implementations is given, and the impacts of different data distribution and communication methods are compared.
In the following paper a two-dimensional parallel algorithm FDTD is presented. It uses a decomposition of a space domain into sub-areas. The shapes of the dielectrics are approximated by the groups of rectangles, desc...
详细信息
ISBN:
(纸本)0769517315
In the following paper a two-dimensional parallel algorithm FDTD is presented. It uses a decomposition of a space domain into sub-areas. The shapes of the dielectrics are approximated by the groups of rectangles, described by coordinates. In addition, the parallel algorithm was equipped in the Specific Absorption Rate and Temperature Increases calculation modules. The paper also contains the results of the efficiency research into two types of the connection topology of the computation nodes. The computations were made on a homogeneous cluster of personal computers.
Summary form only given. We show a parallel algorithm using a rectangle greedy matching technique which requires a linear number of processors and O(log(M)log(n)) time on the PRAM EREW model. The algorithm is suitable...
详细信息
The ROI (Region Of Interest) matching problem is defined and its application to endoscopic diagnosis is shown. Two kinds of matching procedures (ire considered: random search and simulation anneuling ones. The suitabl...
详细信息
ISBN:
(纸本)0769517307;0769517315
The ROI (Region Of Interest) matching problem is defined and its application to endoscopic diagnosis is shown. Two kinds of matching procedures (ire considered: random search and simulation anneuling ones. The suitable sequential and parallel algorithms are proposed and their suitability for ROI identification is discussed.
A new parallel algorithm that solve a dynamic programming paradigm is proposed. It has the time complexity, of O(n) and uses (n-1)n/2 processors. A MPI implementation is used to test the algorithm.
ISBN:
(纸本)0769517315
A new parallel algorithm that solve a dynamic programming paradigm is proposed. It has the time complexity, of O(n) and uses (n-1)n/2 processors. A MPI implementation is used to test the algorithm.
In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the...
详细信息
ISBN:
(纸本)3540438645
In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) and with n processors. This represents a useful improvement since most practical situations satisfy H = O(log n).
We present a significant improvement for parallel integer sorting. On the EREW (exclusive read exclusive write) PRAM our algorithm sorts n integers in the range {0, 1,..., m 1} in time O(log n) with O(n(q) (log n) ove...
详细信息
ISBN:
(纸本)0898714346
We present a significant improvement for parallel integer sorting. On the EREW (exclusive read exclusive write) PRAM our algorithm sorts n integers in the range {0, 1,..., m 1} in time O(log n) with O(n(q) (log n) over bar /k) operations using word length k log( m + n), where 1 less than or equal to k less than or equal to log n. In this paper we present the following four variants of our algorithm. (1) The first variant sorts integers in {0, 1,..., m - 1} in time O(log n) and in linear space with O(n) operations using word length log m log n. (2) The second variant sorts integers in {0, 1,..., n - 1} in time O ( log n) and in linear space with O(n rootlog n) operations using word length log n. (3) The third variant sorts integers in {0, 1,..., m - 1} in time O(log(3)/(2)n) and in linear space with O(n rootlog n) operations using word length log(m + n). (4) The fourth variant sorts integers in {0, 1,..., m - 1} in time O(log n) and space O(nm(epsilon)) with O(n rootlog n) operations using word length log( m + n). Our algorithms can then be generalized to the situation where the word length is k log( m + n), 1 less than or equal to k less than or equal to log n.
Multiprocessor architectures with few but powerful processors gain more and more popularity. In this paper we describe a parallel iterative algorithm to perform randomization for a continuous time Markov, chain with a...
详细信息
ISBN:
(纸本)0769515975
Multiprocessor architectures with few but powerful processors gain more and more popularity. In this paper we describe a parallel iterative algorithm to perform randomization for a continuous time Markov, chain with a Kronecker representation on a shared memory architecture. The Kronecker representation is modified for a parallel matrix-vector multiplication with a fast multiplication scheme and no write conflicts on iteration vectors. The proposed technique is applied on a model of a workstation cluster for dependability analysis, corresponding computations are performed on two multiprocessor architectures, a Sun enterprise and a SGI Origin 2000 to measure its performance.
Let T e an edge-weighted tree. A p-core of T is a set of p mutually disjoint paths in T that minimizes the sum of the distances of all vertices in T from any of the p paths, where p greater than or equal to 1 is an in...
详细信息
Let T e an edge-weighted tree. A p-core of T is a set of p mutually disjoint paths in T that minimizes the sum of the distances of all vertices in T from any of the p paths, where p greater than or equal to 1 is an integer. In this paper, an O(n) time algorithm is proposed for the case p = 2, where n is the number of vertices in T. Our algorithm improves the two O(n(2)) time algorithms previously proposed by Becker and Perl Discrete Appl. Math., 11 (1985), pp. 103-113]. With some modi cations, the proposed algorithm can e implemented on the EREW PRAM in O (log(2) n) time using O (n log n) work.
We consider the problem of constructing binary heaps on constant degree networks performing compare-exchange operations only. The heap data structure, introduced by William and Williams [Comm. ACM 7 (6) (1964) 347-348...
详细信息
We consider the problem of constructing binary heaps on constant degree networks performing compare-exchange operations only. The heap data structure, introduced by William and Williams [Comm. ACM 7 (6) (1964) 347-348], has many applications and, therefore, has been intensively studied in sequential and parallel context. In particular, Brodal and Pinotti [Theoret. Comput. Sci. 250 (2001) 235-245] have recently presented two families of comparator networks: the first of depth 4 log N and the second of size O(N log log N) for constructing binary heaps of size N. In this note, we give an new construction of such a network with the running time improved to 3 log N. Moreover, the network has a novel property of being 3-periodic, that is, for each unit of time i the same sets of operations are performed in units i and i + 3. Then we argue that our construction is optimal with respect to the length of the period, that is, we prove that there is no 2-periodic network that is able to build a binary heap in sublinear time. Finally, we show that our construction can be used to decrease also the depth of the networks with O(N log log N) size. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论