Labeling Schemes for Dynamic Tree Networks

Distance labeling schemes are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute the distance between any two vertices directly from their labels (without using any additional information). As applications for distance labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. The current paper considers the problem on dynamic trees, and proposes efficient distributed schemes for it. The paper first presents a labeling scheme for distances in the dynamic tree model, with amortized message complexity O(log² n) per operation, where n is the size of the tree at the time the operation takes place. The protocol maintains O(log² n) bit labels. This label size is known to be optimal even in the static scenario. A more general labeling scheme is then introduced for the dynamic tree model, based on extending an existing static tree labeling scheme to the dynamic setting. The approach fits a number of natural tree functions, such as distance, separation level, and flow. The main resulting scheme incurs an overhead of an O(log n) multiplicative factor in both the label size and amortized message complexity in the case of dynamically growing trees (with no vertex deletions). If an upper bound on n is known in advance, this method yields a different tradeoff, with an O(log² n/log log n) multiplicative overhead on the label size but only an O(log n/log log n) overhead on the amortized message complexity. In the fully dynamic model the scheme also incurs an increased additive overhead in amortized communication, of O(log² n) messages per operation.     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

Efficient Graph-Theoretic Algorithms on a Linear Array with a Reconfigurable Pipelined Bus System

We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n ²) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. [7] have been considered to be the most efficient on the LARPBS model till now. Their algorithm [7] for these two problems require O(log n) time and O(n ³/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n ²) processors. No previous algorithm was known for these latter problems on the LARPBS.     

Analysis of Multi-Sort Algorithm on Multi-Mesh of Trees (MMT) architecture

Various sorting algorithms using parallel architectures have been proposed in the search for more efficient results. This paper introduces the Multi-Sort Algorithm for Multi-Mesh of Trees (MMT) Architecture for N=n ⁴ elements with more efficient time complexity compared to previous architectures. The shear sort algorithm on Single Instruction Multiple Data (SIMD) mesh model requires \(4\sqrt{N}+O\sqrt{N}\) time for sorting N elements, arranged on a \(\sqrt{N}\times \sqrt{N}\) mesh, whereas Multi-Sort algorithm on the SIMD Multi-Mesh (MM) Architecture takes O(N ^1/4) time for sorting the same N elements, which proves that Multi-Sort is a better sorting approach. We have improved the time complexity of intrablock Sort. The Communication time complexity for 2D Sort in MM is O(n), whereas this time in MMT is O(log?n). The time complexity of compare–exchange step in MMT is same as that in MM, i.e., O(n). It has been found that the time complexity of the Multi-Sort on MMT has been improved as on Multi-Mesh architecture.     

Medial axis transform on mesh-connected computers with hyperbus broadcasting

To represent a region of a digital image as the union of maximal upright squares contained in the region is called the medial axis transform. In this paper, we present anO(logn) time parallel algorithm for the medial axis transform of ann×n binary image on an SIMD mesh-connected computers with hyperbus broadcasting usingn ³ processors.     

Parallel computer vision on Polymorphic Torus architecture

Polymorphic Torus is a novel interconnection network for SIMD massively parallel computers, able to support effectively both local and global communication. Thanks to this characteristic, Polymorphic Torus is highly suitable for computer vision applications, since vision involves local communication at the low-level stage and global communication at the intermediate- and high-level stages. In this paper we evaluate the performance of Polymorphic Torus in the computer vision domain. We consider a set of basic vision tasks, namely,convolution, histogramming, connected component labeling, Hough transform, extreme point identification, diameter computation, andvisibility, and show how they can take advantage of the Polymorphic Torus communication capabilities. For each basic vision task we propose a Polymorphic Torus parallel algorithm, give its computational complexity, and compare such a complexity with the complexity of the same task inmesh, tree, pyramid, and hypercube interconnection networks. In spite of the fact that Polymorphic Torus has the same wiring complexity as mesh, the comparison shows that in all of the vision tasks under examination it achieves complexity lower than or at most equal to hypercube, which is the most powerful among the interconnection networks considered.     

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in O(log n) time using O(n/log n) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be found in O(log n) time using O(n/log n) processors.     

On Parallel Selection and Searching in Partial Orders: Sorted Matrices

Parallel algorithms for the problems of selection and searching on sorted matrices are formulated. The selection algorithm takesO(lognlog lognlog*n) time withO(n/lognlog*n) processors on an EREW PRAM. This algorithm can be generalized to solve the selection problem on a set of sorted matrices. The searching algorithm takesO(log logn) time withO(n/log logn) processors on a Common CRCW PRAM, which is optimal. We show that no algorithm using at mostnlog^cnprocessors,c≥ 1, can solve the matrix search problem in time faster than Ω(log logn) and that Ω(logn) steps are needed to solve this problem on any model that does not allow concurrent writes.     

Representation of Edmonds' Algorithm for Finding Optimum Graph Branching on Associative Parallel Processors

In the paper, an efficient parallel implementation of Edmonds' algorithm is suggested for finding optimum graph branching on an abstract model of the SIMD type with vertical data processing (STAR machine). For this, associative parallel algorithms for finding critical circuit and its contraction, as well as for unfolding embedded critical circuits, are constructed for directed weighted graphs represented as a list of arcs and their weights. It is shown that the execution of Edmonds' algorithm on a STAR machine requires O(nlogn) time, where nis the number of graph vertexes. Basic advantages of the parallel implementation of Edmonds' algorithm compared to its implementation on sequential computers are discussed.     

Efficient parallel solutions to some geometric problems

This paper presents new algorithms for solving some geometric problems on a shared memory parallel computer, where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location. The algorithms are quite different from known sequential algorithms, and are based on the use of a new parallel divide-and-conquer technique. One of our results is an O(log n) time, O(n) processor algorithm for the convex hull problem. Another result is an O(log n log log n) time, O(n) processor algorithm for the problem of selecting a closest pair of points among n input points.     

An optimal parallel algorithm for computing cut vertices and blocks on interval graphs

In this paper, a parallel algorithm is presented to find all cut-vertices and blocks of an interval graph. If the list of sorted end points of the intervals of an interval graph is given then the proposed algorithm takes O(log n) time and O(n/log n) processors on an EREW PRAM, if the sorted list is not given then the time and processors complexities are respectively O(log n) and O(n).     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to beO(log logn) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) andO(logn · log logn) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel timeO(log logn) for the CRCW PRAM andO(logn) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before.For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time ofO(log logn) on the CRCW PRAM, withO(n) expected number of processors only.Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential spaceO(logn · log logn) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.This research was supported by National Science Foundation Grant DCR-85-03251 and Office of Naval Research Contract N00014-80-C-0647.This research was partially supported by the National Science Foundation Grants MCS-83-00630, DCR-8503497, by the Greek Ministry of Research and Technology, and by the ESPRIT Basic Research Actions Project ALCOM.     

An efficient distributed algorithm for finding all hinge vertices in networks

Let G=(V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v∈V is called a hinge vertex if there exist two vertices in V\{v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n ²) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.     

An algorithm for merging meaps

Summary We present an algorithm to merge priority queues organized as heaps. The worst case number of comparisons required to merge two heaps of sizes k and n is O(log(n)*log(k)). The algorithm requires O(k) +log(n)*log (k)) data movements if heaps are implemented using arrays and O(log(n)*log(k)) for a pointer-based implementation. Previous algorithms require either O(n+k) data movements and comparisons, or O(k*log(log(n+k))) comparisons and O(k*log(n+k)) data movements. The algorithm presented in this paper improves on the previous algorithms for the case when k>log(n).This work was done while the authors were at McGill University, Montréal, Canada     

具有O(n)消息复杂度的协调检查点设置算法

协调检查点设置及回卷恢复技术作为一种有效的容错手段,已广泛地运用在集群等并行/分布计算机系统中.为了进一步降低协调检查点设置的时间和空间开销,提出了一种基于消息计数的协调检查点设置算法.该算法无须对底层消息通道的FIFO特性进行假设,并使同步阶段引入的控制消息复杂度由通常的O(n²)降低到O(n),有效地提高了系统的效率和扩展性.     

The Hough Transform on a Reconfigurable Multi-Ring Network

A novel reconfigurable network referred to as the Reconfigurable Multi-Ring Network (RMRN) is described. The RMRN is shown to be a truly scalable network, in that each node in the network has a fixed degree of connectivity and the reconfiguration mechanism ensures a network diameter of O(log₂N) for an N-processor network. Algorithms for the 2-D mesh and the SIMD n-cube are shown to map very elegantly onto the RMRN. Basic message passing and reconfiguration primitives for the SIMD RMRN are designed which could be used as building blocks for more complex parallel algorithms. The RMRN is shown to be a viable architecture for image processing and computer vision problems via the parallel computation of the Hough transform. The parallel implementation of the Y-angle Hough transform of an N × N image is showed to have a asymptotic complexity of O(Y log₂Y + log₂N) on the SIMD RMRN with O(N²) processors. This compares favorably with the O(Y + log₂N) optimal algorithm for the same Hough transform on the MIMD n-cube with O(N²) processors.     

A new scheme for the deterministic simulation of PRAMs in VLSI

A deterministic scheme for the simulation of (n, m)-PRAM computation is devised. Each PRAM step is simulated on a bounded degree network consisting of a mesh-of-trees (MT) of siden. The memory is subdivided inn modules, each local to a PRAM processor. The roots of the MT contain these processors and the memory modules, while the otherO(n ²) nodes have the mere capabilities of packet switchers and one-bit comparators. The simulation algorithm makes a crucial use of pipelining on the MT, and attains a time complexity ofO(log² n/log logn). The best previous time bound wasO(log² n) on a different interconnection network withn processors. While the previous simulation schemes use an intermediate MPC model, which is in turn simulated on a bounded degree network, our method performs the simulation directly with a simple algorithm.This work has been supported in part by Ministero della Pubblica Istruzione of Italy under a research grant.     

A fast algorithm for point-location in a finite element mesh

An algorithm for the point-location problem in 2D finite element meshes as a special case of plane straight-line graphs (PSLG) is presented. The element containing a given point P is determined combining a quadtree data structure to generate a quaternary search tree and a local search wave using adjacency information. The preprocessing construction of the search tree has a complexity ofO(n·log(n)) and requires only pointer swap operations. The query time to locate a start element for local search isO(log(n)) and the final point search by ‘point-in-polygon’ tests is independent of the total number of elements in the mesh and thus determined in constant time. Although the theoretical efficiency estimates are only given for quasi-uniform meshes, it is shown in numerical examples, that the algorithm performs equally well for meshes with extreme local refenement.     

Efficiently computing geodesic offsets on triangle meshes by the extended Xin–Wang algorithm

Geodesic offset curves are important for many industrial applications, such as solid modeling, robot-path planning, the generation of tool paths for NC machining, etc. Although the offset problem is well studied in classical differential geometry and computer-aided design, where the underlying surface is sufficiently smooth, very few algorithms are available for computing geodesic offsets on discrete representation, in which the input is typically a polyline curve restricted on a piecewise linear mesh. In this paper, we propose an efficient and exact algorithm to compute the geodesic offsets on triangle meshes by extending the Xin–Wang algorithm of discrete geodesics. We define a new data structure called parallel-source windows, and extend both the “one angle one split” and the filtering theorem to maintain the window tree. Similar to the original Xin–Wang algorithm, our extended algorithm has an O(n) space complexity and an O(n²logn) asymptotic time complexity, where n is the number of vertices on the input mesh. We tested our algorithm on numerous real-world models and showed that our algorithm is exact, efficient and robust, and can be applied to large scale models with complicated geometry and topology.