Search

We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP type model. We first describe a simple version which requires, with high probability, log(3p)+log ln(n)=O(logp+log logn) communication rounds (h-relations withh=O(n/p)) andO(n/p)) local computation. We then outline an improved version that requires high probability, onlyr⩽(4k+6) log(2/3p)+8=O(k logp) communication rounds wherek=min{i⩾0 |ln(i+1)n⩽(2/3p)2i+1}. Notek

In this paper, we present optimal parallel algorithms for optical clustering on a mesh-connected computer.Optical clustering is a clustering technique based on the principal of optical resolution, and is of particular interest in picture analysis. The algorithms we present are based on the application of parallel algorithms in computational geometry and graph theory. In particular, we show that given a setS ofN points in the Euclidean plane, the following problems can be solved in optimal\(O\left( {\sqrt N } \right)\) time on a mesh-connected computer of sizeN. 1. Determine the optical clusters ofS with respect to a given separation parameter. 2. Given an interval [a, b] representing the number of optical clusters desired in the clustering ofS, determine the range of the separation parameter that will result in such an optical clustering.

Consider an×n binary image. Given a directionD, the parallel visibility problem consists of determining for each pixel of the image the portion that is visible (i.e., not obstructed by any other black pixel of the image) in directionD from infinity. A related problem, referred to as point visibility, is to compute for each pixel the portion that is visible from a given pointp. In this paper, we deriveO(logn) time SIMD algorithms for each of these two problems on the hypercube, where one processor is assigned to every pixel of the image. Since the worst case communication distance of two processors in an 2-processor hypercube is 2 logn, it follows that both of the above algorithms are asymptotically optimal.

The time complexity of searching a sorted list ofn elements in parallel on a coarse grained network of diameterD and consisting ofN processors (wheren may be much larger thanN) is studied. The worst case period and latency of a sequence of pipeline search operation are easity seen to be Ω(logn−logN) and Ω(D+logn−logN), respectively. Since forn=N1+Ω(1) the worst-case period is Ω(logn) (which can be achieved by a single processor), coarse-grained networks appear to be unsuitable for the search problem. By contrast, it is demonstrated using standard queuing theory techniques that a constant expected period can be achieved provided thatn=O(N2N).