One of the frequently used models for a synchronous parallel computer is that of a parallelrandomaccess machine, where each processor can read from and write into a common randomaccess memory. Different processors ...
详细信息
One of the frequently used models for a synchronous parallel computer is that of a parallelrandomaccess machine, where each processor can read from and write into a common randomaccess memory. Different processors may read the same memory location at the same time, but simultaneous writing is disallowed. We show that even if we allow nonuniform algorithms, an arbitrary number of processors, and arbitrary instruction sets, Ω(logn)
This paper is concerned with parallel random access machines (PRAMs), where each processor can read from and write into a common randomaccess memory. Different processors may read the same memory location at a time, ...
详细信息
This paper is concerned with parallel random access machines (PRAMs), where each processor can read from and write into a common randomaccess memory. Different processors may read the same memory location at a time, but only one processor is allowed to write into it (the CREW model). Suppose f is a Boolean function of n variables. Let CREW(f) be the number of steps required by CREW PRAMs to compute function f. It has been proved that CREW(f) greater-than-or-equal-to log(b) crit(f), where b almost-equal-to 4.79 and crit(f) is the critical complexity of f (see [S. Cook, C. Dwork, and R. Reischuk, SIAM J. Comput., 15 (1986), pp. 87-97]). It was proved by Parberry and Pei Yuan Yan [SIAM J. Comput., 20 (1991), pp. 88-99] that the same holds for b = 4. It follows that the time required by the logical "or" of n variables is at least log4 n. This paper presents an essentially different method of estimating PRAM complexity of Boolean functions. Let n(f) be the number of inputs x is-an-element-of {0, 1}n for which f(x) = 1. Let i(f) = max{j:2j\n(f)}. Then CREW(f) greater-than-or-equal-to log(c) (n - i(f)), where c almost-equal-to 2.618. Thanks to this result, the time complexity of the logical "or" of n variables is determined exactly. This in turn allows better estimations of time complexity of the threshold functions to be obtained. Another corollary is that for sorting n arbitrary keys, PRAMs require time, which can be determined up to five steps.
The effect of relaxing the assumption of a fixed memory word-size is investigated. It is shown that this can lead to faster algorithms. A model in which the processors can view the memory as made up of as ″small″ wo...
详细信息
The effect of relaxing the assumption of a fixed memory word-size is investigated. It is shown that this can lead to faster algorithms. A model in which the processors can view the memory as made up of as ″small″ words (of contiguous bits) as deemed necessary is proposed.
This paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [G], and the COMMON PRAM [K]. Improving the trivial and seemingly optimalO(log...
详细信息
This paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [G], and the COMMON PRAM [K]. Improving the trivial and seemingly optimalO(logn) simulation, we show that one step of a PRIORITY machine can be simulated byO(logn/(log logn)) steps of a COMMON machine with the same number of processors (and more memory). We further prove that this is optimal, if processor communication is restricted in a natural way.
Shared memory models of parallel computation (e.g., parallel RAMs) that allow simultaneous read/write access are very natural and already widely used for parallel algorithm design. The various models differ from each ...
详细信息
Shared memory models of parallel computation (e.g., parallel RAMs) that allow simultaneous read/write access are very natural and already widely used for parallel algorithm design. The various models differ from each other in the mechanism by which they resolve write conflicts. To understand the effect of these communication primitives on the power of parallelism, we extensively study the relationship between four such models that appear in the literature, and prove nontrivial separations and simulation results among them.
Let A be a sorted array of n numbers and B a sorted array of m numbers, both in nondecreasing order, with n less than or equal to m. We consider the problem of determining, for each element A(j), j = 1, 2, ..., n, the...
详细信息
Let A be a sorted array of n numbers and B a sorted array of m numbers, both in nondecreasing order, with n less than or equal to m. We consider the problem of determining, for each element A(j), j = 1, 2, ..., n, the unique element B(i), 0 less than or equal to i less than or equal to m, such that B(i) less than or equal to A(j) < B(i + 1) (with B(0) = -infinity and B(m + 1) = +infinity). We present an efficient parallel algorithm for solving this problem in O(log m) time using O(n log(m/n)/log m) EREW PRAM processors. Our algorithm improves the previously known results on either the time or processor complexity, and enables us to solve several other problems optimally on the EREW PRAM.
A new model of computation called the B-PRAM, which is a PRAM augmented with reconfigurable buses that provide additional channels of communication, is proposed. It is proved that the OR of n bits can be computed on a...
详细信息
A new model of computation called the B-PRAM, which is a PRAM augmented with reconfigurable buses that provide additional channels of communication, is proposed. It is proved that the OR of n bits can be computed on an EREW B-PRAM in O(1) time, thus showing that the addition of reconfgurable buses makes the model strictly more powerful than the CREW PRAM. Bounds for sorting n m=O(log n) - bit numbers (integer sorting) are also obtained.
作者：
REISCHUK, RUniv Bielefeld
Fakultaet fuer Mathematik Bielefeld West Ger Univ Bielefeld Fakultaet fuer Mathematik Bielefeld West Ger
Probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes wit...
详细信息
Probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes with high probability in constant time and the sorting tree in time O(logn)
暂无评论