This paper presents efficient and portable implementations of a useful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique which makes use of the SNF and a variant o...
详细信息
This paper presents efficient and portable implementations of a useful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique which makes use of the SNF and a variant of the conventional connected components algorithm which we call δ-Connected Components. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The image segmentation algorithm makes use of an efficient connected components algorithm based on a novel approach for parallel merging. The algorithms have been coded in SPLIT-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results are consistent with the theoretical analysis (and provide the best known execution times for segmentation, even when compared with machine-specific implementations.) Our test data include difficult images from the Landsat Thematic Mapper (TM) satellite data.
parallel parenthesis-matching algorithm has in the past been used to design parallel algorithms for generation of computation tree forms and parsing. In this paper we present a parallel parenthesis-matching algorithm....
详细信息
We consider two difference schemes that describe the convective-diffusion transfer and settling of multifractional suspensions in coastal systems. The first is based on an explicit-implicit scheme with reduced cost of...
详细信息
Redundancy is a basic technique for achieving fault tolerance, but the overhead introduced by redundancy may degrade system's performance. In this paper, we propose efficient replication based algorithms for fault...
详细信息
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP*, that rewards blo...
详细信息
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP*, that rewards blockwise communication, and use Valiant's notion of 1-optimality. Intuitively, a 1-optimal parallel algorithm for p processors achieves speed-up close to p. We consider the Multisearch Problem: Assume a strip in 2D to be partitioned into m segments. Given n query points in the strip, the task is to locate, for each query, its segment. For m less than or equal to n greater than or equal to p we present a deterministic BSP* algorithm that is 1-optimal, if n/p greater than or equal to log(2)n. For m>n greater than or equal to p, we present a randomized BSP* algorithm that is 1-optimal with high probability, if m less than or equal to 2(p) and n/p greater than or equal to log(3)n. Both results hold for a wide range of BSP* parameters where the range becomes larger with growing input size n. We further report on implementation work. Previous parallel algorithms for Multisearch were far away from being 1-optimal in our model and did not consider blockwise communication. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM algorithms are spec...
详细信息
External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation. In the past, several attempts have been made to relate the large body of work on parallel algorithms to EM, but with limited success. The combination of EM computing, on multiple disks, with multiprocessor parallelism has been posted as a challenge by the ACM Working Group on Storage I/O for Large-Scale Computing. In this paper we provide a simulation technique which produces efficient parallel EM algorithms from efficient BSP-like parallel algorithms. The techniques obtained can accommodate one or multiple processors on the EM target machine, each with one or more disks, and they also adapt to the disk blocking factor of the target machine. When applied to existing BSP-like algorithms, our simulation technique produces improved parallel EM algorithms for a large number of problems.
In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimal T(n) * P(n) products, where T(n) is the time complexity and P(n) is the number of ...
详细信息
In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimal T(n) * P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.
In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in...
详细信息
In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular is property, and more efficiently in parallel ii at least one matrix satisfies the consecutive Is property. Graphs which have identification matrices satisfying the consecutive Is property include, among others, proper interval graphs and doubly convex bipartite graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms.
作者：
ALNUWEIRI, HMKUMAR, VKPEEB-244
Department of Electrical Engineering Systems University of Southern California Los Angeles USA
We present processor-time optimal parallel algorithms for several problems on n x n digitized image arrays, on a mesh-connected array having p processors and a memory of size O(n2) words. The number of processors p ca...
详细信息
We present processor-time optimal parallel algorithms for several problems on n x n digitized image arrays, on a mesh-connected array having p processors and a memory of size O(n2) words. The number of processors p can vary over the range [1, n3/2] while providing optimal speedup for these problems. The class of image problems considered here includes labeling the connected components of an image;computing the convex hull, the diameter, and a smallest enclosing box of each component;and computing all closest neighbors. Such problems arise in medium-level vision and require global operations on image pixels. To achieve optimal performance, several efficient data-movement and reduction techniques are developed for the proposed organization.
This paper presents very fast parallel algorithms for approximate edge coloring. Let log((1)) n = log n, log((k)) n = log(log((k-1)) n), and log*(n) = min{k \ log((k)) n /log(c/4) log*(n)])2 colors in O(log log*(n)) t...
详细信息
This paper presents very fast parallel algorithms for approximate edge coloring. Let log((1)) n = log n, log((k)) n = log(log((k-1)) n), and log*(n) = min{k \ log((k)) n < 1}. It is shown that a graph with n vertices and in edges can he edge colored with (2[log(1/4)log*(n)])(c) ([/log(c/4) log*(n)])2 colors in O(log log*(n)) time using O(m + n) processors on the EREW PRAM, where Delta is the maximum vertex degree of the graph and c is an arbitrarily large constant. It is also shown that the graph can he edge colored using at most [4 Delta (1+4/log log log*(Delta)) log(1/2) log*(Delta )1 colors in O(log Delta log log*(Delta)/log log log* (Delta) + log log*(n)) time using O(m + n) processors on the same model. O 2001 Elsevier Science B.V. All rights reserved.
暂无评论