We study a class of simple algorithms for concurrently computing the connected components of an n-vertex, m-edge graph. Our algorithms are easy to implement in either the COMBINING CRCW pram or the MPC computing model...
详细信息
We study a class of simple algorithms for concurrently computing the connected components of an n-vertex, m-edge graph. Our algorithms are easy to implement in either the COMBINING CRCW pram or the MPC computing model. For two related algorithms in this class, we obtain Theta(lgn) step and Theta(m lgn) work bounds.(1) For two others, we obtain O(lg(2) n) step and O(m lg(2) n) work bounds, which are tight for one of them. All our algorithms are simpler than related algorithms in the literature. We also point out some gaps and errors in the analysis of previous algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.
We present a more efficient CREW pram algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2, ... , n(1/2)} in O(log n)(3/2)/log log n) time and O(n(log n/ log log n)(1/2)) operations. It also sort...
详细信息
We present a more efficient CREW pram algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2, ... , n(1/2)} in O(log n)(3/2)/log log n) time and O(n(log n/ log log n)(1/2)) operations. It also sorts n integers in {0, 1, 2, ..., n - 1} in 0 ((log n)(3/2)/log log n) time and O (n(log n/log log n)1/2 log log log n) operations. Previous best algorithm [15] on both cases has time complexity O(log n) but operation complexity O (n(log n)(1/2)).
The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X,Y of the set U such tha...
详细信息
The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X,Y of the set U such that X = {X-1, X-2,..., X-x} and Y = {Y-1, Y-2,...;Y-y } and determine a new partition Z = {Z(1), Z(2),..., Z(z)} such that each Z(c) epsilon Z is a common non-empty subset of some X-a epsilon X and some Y-b epsilon Y and Z is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O(t (n) + log n) parallel time using max{n/log n, p(n)} processors, where t(n) denotes the running time of a parallel stable sorting algorithm that uses p(n) processors on an EREW pram. This result depends on t(n) and p(n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW pram. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O(log n log (n/log n)) parallel time using n/log n processors on an EREW pram. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm.
The Dandelion-like codes are eight bijections between labeled trees and strings of node labels. The literature contains optimal sequential algorithms for these bijections, but no parallel algorithms have been reported...
详细信息
The Dandelion-like codes are eight bijections between labeled trees and strings of node labels. The literature contains optimal sequential algorithms for these bijections, but no parallel algorithms have been reported. In this paper the first parallel encoding and decoding algorithms for Dandelion-like codes are presented. Namely, a unique encoding algorithm and a unique decoding algorithm, which when properly parameterized, can be used for all Dandelion-like codes, are designed. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW pram is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading. (c) 2010 Elsevier Inc. All rights reserved.
All students at our high school are required to take at least one course in Computer Science prior to their junior year. They are also required to complete a year-long senior project associated with a specific in-hous...
详细信息
ISBN:
(纸本)9781605588858
All students at our high school are required to take at least one course in Computer Science prior to their junior year. They are also required to complete a year-long senior project associated with a specific in-house laboratory, one of which is the Computer Systems Lab. To prepare students for this experience the lab offers elective courses at the post-AP Computer Science level. Since the early 1990s one of these electives has focused on parallel computing. The course enrolls approximately 40 students each year for two semesters of instruction. The lead programming language is C and topics include a wide array of industry-standard and experimental tools. Since the 2007-2008 school year we have included a unit on parallel algorithmic thinking (PAT) using the Explicit Multi-Threading (XMT) system [11, 12]. We describe our experiences using this system after self-studying the approach from a publicly available tutorial. Overall, this article provides significant evidence regarding the unique teachability of the XMT PAT approach, and advocates using it broadly in Computer Science education.
This is a theoretical study of partially occluded one-dimensional images. Here, we consider ''valid" images composed from a given set of objects, where some objects appearing in the image may be partially...
详细信息
This is a theoretical study of partially occluded one-dimensional images. Here, we consider ''valid" images composed from a given set of objects, where some objects appearing in the image may be partially obstructed by others. A CRCW pram algorithm is presented here for validating a one-dimensional image x of length n over a set of k objects of equal length in O(log logn) time with linear work, where k is a fixed integer. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
The aim of this paper is to describe a CREW-pram optimal algorithm which converts a regular expression of size s into its Glushkov automaton in O(logs) time using O(s(2)/log s) processors. This algorithm makes use of ...
详细信息
The aim of this paper is to describe a CREW-pram optimal algorithm which converts a regular expression of size s into its Glushkov automaton in O(logs) time using O(s(2)/log s) processors. This algorithm makes use of the star-normal form of an expression as defined by Bruggemann-Klein (1993) and is based on the sequential algorithm due to Ziadi et al. (1997) which computes an original representation of Glushkov automaton in O(s) time. (C) 1999-Elsevier Science B.V. All rights reserved.
A bipartite graph G = (V, W, E) is called convex if the vertices in W can be ordered in such a way that the elements of W adjacent to any vertex nu is an element of V form an interval (i.e. a sequence consecutively nu...
详细信息
A bipartite graph G = (V, W, E) is called convex if the vertices in W can be ordered in such a way that the elements of W adjacent to any vertex nu is an element of V form an interval (i.e. a sequence consecutively numbered vertices). Such a graph can be represented in a compact form that requires O(n) space, where n = max{\V\, \W\}. Given a convex bipartite graph G in the compact form Dekel and Sahni designed an O(log(2)(n))-time, n-processor EREW pram algorithm to compute a maximum matching in G, We show that the matching produced by their algorithm can be used to construct optimally in parallel a maximum set of independent vertices. Our algorithm runs in O(log n) time with nl log n processors on an Arbitrary CRCW pram.
We present an optimal O(log log n) time algorithm on the CRCW pram which tests whether a square array, A, of size n × n, is superprimitive. If A is not superprimitive, the algorithm returns the quasiperiod, i.e.,...
详细信息
A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers [1..s]. For an input of size n, it runs in O(log log log s) time and O(n) work (which is optimal). A fast...
详细信息
A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers [1..s]. For an input of size n, it runs in O(log log log s) time and O(n) work (which is optimal). A faster algorithm is presented for the special case s = n;it runs in O(log* n) time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CRCW pram). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the OMEGA(log log n) time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348-355]. The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with s = n, thus giving an 0 (log* n) time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time.
暂无评论