Repetitive substructures of two-dimensional arrays have been recently defined and studied in an attempt to parallel some of the analogous developments already known for strings. In the present paper we propose an O (l...
详细信息
Speedup is considered as the criterion of determining whether a parallelalgorithm is optimal. But broadcast-class problems, existing only on parallel computer system, have no sequential algorithms at all. Speedup sta...
详细信息
Speedup is considered as the criterion of determining whether a parallelalgorithm is optimal. But broadcast-class problems, existing only on parallel computer system, have no sequential algorithms at all. Speedup standard becomes invalid here. Through this research on broadcast algorithms under several typical parallel computation models,a model-independent evaluation standard min C2 is developed, which can be not only used to determine an optimal broadcasting algorithm, but also normalized to apply to any parallelalgorithm. As a new idea, min C2 will lead to a new way in this field.
Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant-time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text.
Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant-time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text.
We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a tru...
详细信息
We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of THETA(p) highest priority items and insertions of THETA(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.
We describe an O(log( n )) time with O( n ) processors optimalalgorithm for finding the maximal elements of a set. The model of parallel computation we consider is the CREW-PRAM, i.e. it is the synchronous shared mem...
详细信息
We describe an O(log( n )) time with O( n ) processors optimalalgorithm for finding the maximal elements of a set. The model of parallel computation we consider is the CREW-PRAM, i.e. it is the synchronous shared memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing).
In this paper we present an optimal speedup parallelalgorithm for the measure problem. The measure problem arises in layout verification problems for VLSI designs, in geography, in maintaining architectural databases...
详细信息
In this paper we present an optimal speedup parallelalgorithm for the measure problem. The measure problem arises in layout verification problems for VLSI designs, in geography, in maintaining architectural databases, and in computer graphics. Given R 1 , R 2 , …, R n a list of n iso-oriented rectangles in a plane, the measure problem computes the area of the region R, where R = R 1 ∪ R 2 ∪ ⋯ ∪ R n . The parallelalgorithm presented in this paper is shown to have a tim complexity of O(log n log log n) with O(n/log log n ) processors.
The authors develop a parallelalgorithm sorting n integers, drawn randomly from a polynominal range, on a CRCW PRAM, using n/log n processors in time O(log n) with probability 1-2 super(-bn/log3n), for some b > 0....
详细信息
The authors develop a parallelalgorithm sorting n integers, drawn randomly from a polynominal range, on a CRCW PRAM, using n/log n processors in time O(log n) with probability 1-2 super(-bn/log3n), for some b > 0. The algorithm, called iterated bucket sort, is an improvement over the algorithm given by Chlebus, where the input integer keys were restricted to be of linear magnitude.
The problem to sort integers on a parallel RAM (PRAM) is investigated. An algorithm sorting n integers on n/log n processors in expected time O(log n) is presented. It is a parallel version of the bucket sort. The sim...
详细信息
The problem to sort integers on a parallel RAM (PRAM) is investigated. An algorithm sorting n integers on n/log n processors in expected time O(log n) is presented. It is a parallel version of the bucket sort. The simultaneous resource bounds of this algorithm are asymptotically optimal.
We prove that the parsing problem for bracket context-free languages can be solved in log n time using n /log n processors on a parallel random access machine without write conflicts (P-RAM). On the way we develop a n...
详细信息
We prove that the parsing problem for bracket context-free languages can be solved in log n time using n /log n processors on a parallel random access machine without write conflicts (P-RAM). On the way we develop a new general technique for tree compression based on the bracket structure of the tree.
暂无评论