Consider a set P of points in the plane sorted by x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The pr...
详细信息
Consider a set P of points in the plane sorted by x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The proximate point problem is to determine all the proximate points in P. Our main contribution is to propose optimal parallel algorithms for solving instances of size n of the proximate points problem. We begin by developing a work-time optimal algorithm running in O(log log n) time and using n/loglogn Common-CRCW processors. We then go on to show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. In addition to being work-time optimal, our EREW algorithm turns out to also be lime-optimal. Our second main contribution is to show that the proximate points problem finds interesting, and quite unexpected, applications to digital geometry and image processing. As a first application, we present a work-time optimal parallel algorithm for finding the convex hull of a set of n points in the plane sorted by x-coordinate;this algorithm runs in O(log log n) time using n/loglogn Common-CRCW processors. We then show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. Next, we show that the proximate points algorithms afford us work-time optimal (resp. time-optimal) parallel algorithms for various fundamental digital geometry and image processing problems. Specifically, we show that the Voronoi map, the Euclidean distance map, the maximal empty circles, the largest empty circles, and other related problems involving a binary image of size n x n can be solved in O(log log n) time using n(2)/loglogn Common-CRCW processors or in O(log n) time using n(2)/EREW processors.
This paper considers a variety of geometric problems based in description of the loir er envelope function, on input sets of size n using a coarse grained multicomputer model consisting of p processors with Omega(n/p)...
详细信息
This paper considers a variety of geometric problems based in description of the loir er envelope function, on input sets of size n using a coarse grained multicomputer model consisting of p processors with Omega(n/p) local memory each (i.e., Omega(n/p) memory cells of Theta(log n) bits apiece), where the processors are connected to an arbitrary interconnection network. We give an efficient scaleable parallel algorithm for computation of the lower envelope and use this algorithm to obtain efficient solutions for a variety of geometric problems, including the minimization of the Hausdorff distance between two finite sets on the real line when one is subject to translation;the Common Intersection Problem for vertically convex planar polygons;and several problems in Dynamic Computational Geometry: in which we consider geometric questions for systems of moving objects. All of the algorithms presented are scaleable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addition to the practicality imparted by scaleability, these algorithms are easy to implement in that all required communications can be achieved by a small number of calls to standard global routing operations. (C) 1998 Academic Press.
This paper considers a variety of geometric pattern recognition problems on input sets of size n using a coarse grained multicomputer model consisting of p processors with Omega(n/p) local memory each (i.e., Omega(n/p...
详细信息
This paper considers a variety of geometric pattern recognition problems on input sets of size n using a coarse grained multicomputer model consisting of p processors with Omega(n/p) local memory each (i.e., Omega(n/p) memory cells of Theta(log n) bits apiece), where the processors are connected to an arbitrary interconnection network. It introduces efficient scalable parallel algorithms for a number of geometric problems including the rectangle finding problem, the maximal equally spaced collinear points problem, and the point set pattern matching problem. All of the algorithms presented are scalable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addition to the practicality imparted by scalability, these algorithms are easy to implement in that all required communications can be achieved by a small number of calls to standard global routing operations. (C) 1999 Academic Press.
Global optimization is playing an increasing role in physics, chemistry, and biophysical chemistry. One of the most important applications of global optimization is to find the global minima of the potential energy of...
详细信息
Global optimization is playing an increasing role in physics, chemistry, and biophysical chemistry. One of the most important applications of global optimization is to find the global minima of the potential energy of molecules or molecular assemblies, such as crystals. The solution of this problem typically requires huge computational effort. Even the fastest processor available is not fast enough to carry out this kind of computation in real time for the problems of real interest, e.g., protein and crystal structure prediction. One way to circumvent this problem is to take advantage of massively parallel computing. In this paper, we provide several examples of parallel implementations of global optimization algorithms developed in our laboratory. All of these examples follow the master/worker approach. Most of the methods are parallelized on the algorithmic (coarse-grain) level and one example of fine-grain parallelism is given, in which the function evaluation itself is computationally expensive. All parallel algorithms were initially implemented on an IBM/SP2 (distributed-memory) machine. In all cases, however, message passing is handled through the standard Message Passing Interface (MPI);consequently the algorithms can also be implemented on any distributed- or shared-memory system that runs MPI. The efficiency of these implementations is discussed. (C) 2000 Elsevier Science B.V. All rights reserved.
A constant-time algorithm for labeling the connected components of an N x N image on a reconfigurable network of N3 processors is Presented. The main contribution of the algorithm is a novel constant-time technique fo...
详细信息
A constant-time algorithm for labeling the connected components of an N x N image on a reconfigurable network of N3 processors is Presented. The main contribution of the algorithm is a novel constant-time technique for determining the minimum-labeled PE in each component. The number of processors used by the algorithm can be reduced to N2+(1/d), for any 1 less-than-or-equal-to d less-than-or-equal-to log N, if O(d) time is allowed.
作者：
Kapralski, AUniversity of Aizu
Computer Software Department Mathematical Foundations of Computer Science Laboratory Aizu-wakamatsu 965-80 Japan JP
The problem of finding the shortest path between the given terminal points s and t within a given planar figure F is considered. The approach contains basic methodology developed for any parallel or distributed system...
详细信息
The problem of finding the shortest path between the given terminal points s and t within a given planar figure F is considered. The approach contains basic methodology developed for any parallel or distributed system. The 2D scene or the edge of F are represented in the n Cartesian coordinate system (n-CCS). Several algorithms for the shortest path are given, each one to be applied in specified circumstances depending on the exact machine model or on additional information concerning geometrical properties of the figure. If these algorithms are implemented in a parallel depth search machine (PDSM), then the shortest path can be computed in time O(1). The maximum number of processors used is 0(n). The given methodology can also be adapted for producing an approximate solution when the shortest path is approximated by polygonal lines.
The high intensity of research and modeling in fields of mathematics, physics, biology and chemistry requires new computing resources. For the big computational complexity of such tasks computing time is large and cos...
详细信息
The high intensity of research and modeling in fields of mathematics, physics, biology and chemistry requires new computing resources. For the big computational complexity of such tasks computing time is large and costly. The most efficient way to increase efficiency is to adopt parallel principles. Purpose of this paper is to present the issue of parallel computing with emphasis on the analysis of parallel systems, the impact of communication delays on their efficiency and on overall execution time. Paper focuses is on finite algorithms for solving systems of linear equations, namely the matrix manipulation (Gauss elimination method, GEM). algorithms are designed for architectures with shared memory (open multiprocessing, openMP), distributed-memory (message passing interface, MPI) and for their combination (MPI + openMP). The properties of the algorithms were analytically determined and they were experimentally verified. The conclusions are drawn for theory and practice.
We present the first parallel algorithms that decide strong and branching bisimilarity in linear time. More precisely, if a transition system has n states, m transitions and |Act| action labels, we introduce an algori...
详细信息
We present the first parallel algorithms that decide strong and branching bisimilarity in linear time. More precisely, if a transition system has n states, m transitions and |Act| action labels, we introduce an algorithm that decides strong bisimilarity in O(n + |Act|) time on max(n, m) processors and an algorithm that decides branching bisimilarity in O(n + |Act|) time using up to max(n(2), m, |Act|n) processors.
Several recent papers have introduced asynchronous shared memory parallel models in an attempt to discover how removing the assumption of synchronization of processor steps may alter the parallel complexities of probl...
详细信息
Several recent papers have introduced asynchronous shared memory parallel models in an attempt to discover how removing the assumption of synchronization of processor steps may alter the parallel complexities of problems. Preliminary work has resulted in the development and analysis of algorithms for a few specific problems. The best known general technique for transforming synchronous algorithms into asynchronous ones has been to synchronize all processors after each step of a synchronous computation. This results in the time complexity being multiplied by a factor that may be logarithmic in the number of processors, where time is defined to be the expected maximum numbers of steps taken by any processor, with respect to several families of distributions on processor schedules. Here we give a transformation technique that forms an asynchronous algorithm that runs in O(t + log p) time using p processors from any synchronous algorithm that runs in O(t) time on a p-processor CROW PRAM. This result can be extended to more general classes of synchronous algorithms. The technique yields an O(log p) time algorithm for p-input sorting, making possible the simulation of algorithms that run on the PRIORITY CRCW PRAM. (C) 1995 Academic Press, Inc.
EEG-classification is necessary, for instance, to test the hearing of babies and to adapt hearing aids. A CPU-time of 3 hours is necessary for these classifications on serial computers like CYBER 845. This is too long...
详细信息
EEG-classification is necessary, for instance, to test the hearing of babies and to adapt hearing aids. A CPU-time of 3 hours is necessary for these classifications on serial computers like CYBER 845. This is too long to do examinations systematically. We have reduced the CPU-time for these classifications on the DAP. The result is that the DAP needs only 6 minutes CPU-time for the classifications with 8 attributes instead of 4 attributes used in the serial case.
暂无评论