Efficient parallel processing of image contours

Describes two parallel algorithms for ranking the pixels on a curve in O (log N) time using either an EREW or CREW PRAM model. The algorithms accomplish this with N processors for a √N×√N image. After applying such an algorithm to an image, it is possible to move the pixels from a curve into processors having consecutive addresses. This is important because one can subsequently apply many algorithms to the curve (such as piecewise linear approximation algorithms or point in polygon tests) using segmented scan operations (i.e. parallel prefix operations). Scan operations can be executed in logarithmic time on many interconnection networks, such as hypercube, tree, butterfly, and shuffle exchange machines as well as on the EREW PRAM. The algorithms were implemented on the hypercube structured Connection Machine, and various performance tests were conducted     

Designing efficient parallel algorithms on mech-connected computerswith multiple broadcasting

Semigroup and prefix computations on two-dimensional mesh-connected computers with multiple broadcasting (2-MCCMBs) are studied. Previously, only square 2-MCCMBs with N processing elements were considered for semigroup computations of N data items, and O(N^1/6) time was required. It is found that square machines are not the best form for semigroup computations, and an O(N^1/8)-time algorithm is derived on an N^5/8×N^3/8 rectangular 2-MCCMB. This time complexity can be further reduced to O(N^1/9) if fewer processing elements are used. Parallel algorithms for prefix computations with the same time complexities are derived     

Odd even shifts in SIMD hypercubes

A linear-time algorithm is developed to perform all odd (even) length circular shifts of data in an SIMD (single-instruction-stream, multiple-data-stream) hypercube. As an application, the algorithm is used to obtain an O(M²+log N) time and O(1) memory per processor algorithm to compute the two-dimensional convolution of an N×N image and an M×M template on an N² processor SIMD hypercube. This improves the previous best complexity of O(M² log M+log N)     

Parallel algorithms for hierarchical clustering and clustervalidity

Parallel algorithms on SIMD (single-instruction stream multiple-data stream) machines for hierarchical clustering and cluster validity computation are proposed. The machine model uses a parallel memory system and an alignment network to facilitate parallel access to both pattern matrix and proximity matrix. For a problem with N patterns, the number of memory accesses is reduced from O(N ³) on a sequential machine to O(N²) on an SIMD machine with N PEs     

Convolution on mesh connected multicomputers

An efficient parallel algorithm is presented for convolution on a mesh-connected computer with wraparound. The algorithm does not require a broadcast feature for data values, as assumed by previously proposed algorithms. As a result, the algorithm is applicable to both SIMD and MIMD meshes. For an N×N image and a M×M template, the previous algorithms take O (M²q) time on an N×N mesh-connected multicomputer (q is the number of bits in each entry of the convolution matrix). The algorithms have complexity O(M²r), where r=max {number of bits in an image entry, number of bits in a template entry}. In addition to not requiring a broadcast capability, these algorithms are faster for binary images     

Latin squares for parallel array access

A parallel memory system for efficient parallel array access using perfect latin squares as skewing functions is discussed. Simple construction methods for building perfect latin squares are presented. The resulting skewing scheme provides conflict free access to several important subsets of an array. The address generation can be performed in constant time with simple circuitry. The skewing scheme can provide constant time access to rows, columns, diagonals, and N^1/2 ×N^1/2 subarrays of an N× N array with maximum memory utilization. Self-routing Benes networks can be used to realize the permutations needed between the processing elements and the memory modules. Two skewing schemes that provide conflict free access to three-dimensional arrays are also discussed. Combined with self-routing Benes networks, these schemes provide efficient access to frequently used subsets of three-dimensional arrays     

Serial and parallel algorithms for the medial axis transform

An O(n²) time serial algorithm is developed for obtaining the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log² n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n²) processors. Two problems associated with the MAT, the area and perimeter reporting problem, are studied. An O(log n) time hypercube algorithm is developed for both of them, where n is the number of squares in the MAT, and the algorithms use O(n²) processors     

An algorithm for finding a common structure shared by a family ofstrings

An algorithm is presented for extracting and localizing a common structure in a family of strings with time complexity O(N² L² log₂ L) where N is the number of strings and L their maximum length. The method could be extended to two-dimensional image analysis. This structure appears as alignments of words which are similar but not necessarily identical and which occur approximately at the same location in all the strings. The method works in two successive stages. First, a fast algorithm is used for drawing up a directory of exactly repeated patterns appearing in a given majority of strings. Second, the algorithm constructs recursively anchoring patterns by a divide-and-conquer strategy and converges on a maximum number of alignments. This algorithm has been applied to find common a priori unknown features in families of biological macromolecules, with quite good results. One of these families included 23 strings of about 100 characters each. Each characteristic structure has been achieved within less than one minute on a MULTIX-DPS8 system     

A novel discrete relaxation architecture

The discrete relaxation algorithm (DRA) is a computational technique that enforces arc consistency (AC) in a constraint satisfaction problem (CSP). The original sequential AC-1 algorithm suffers from O(n³m³) time complexity, and even the optimal sequential AC-4 algorithm is O (n²m²) for an n-object and m-label DRA problem. Sample problem runs show that these algorithms are all too slow to meet the need for any useful, real-time CSP applications. A parallel DRA5 algorithm that reaches a lower bound of O(nm) (where the number of processors is polynomial in the problem size) is given. A fine-grained, massively parallel hardware computer architecture has been designed for the DRA5 algorithm. For practical problems, many orders of magnitude of efficiency improvement can be reached on such a hardware architecture     

On the number of digital straight line segments

A closed-form expression has been reported in the literature for L_N, the number of digital line segments of length N that correspond to lines of the form y=ax+β, O⩽α, β<1. The authors prove an asymptotic estimate for L_N that might prove useful for many applications, namely, L_N=N ³/π²+O(N² log N). An application to an image registration problem is given     

Parallel binary search

Two arrays of numbers sorted in nondecreasing order are given: an array A of size n and an array B of size m, where n<m. It is required to determine, for every element of A, the smallest element of B (if one exists) that is larger than or equal to it. It is shown how to solve this problem on the EREW PRAM (exclusive-read exclusive-write parallel random-access machine) in O(logm logn/log log m) time using n processors. The solution is then extended to the case in which fewer than n processors are available. This yields an EREW PRAM algorithm for the problem whose cost is O(n log m, which is O(m)) for n⩽m/log m. It is shown how the solution obtained leads to an improved parallel merging algorithm     

A VLSI constant geometry architecture for the fast Hartley andFourier transforms

An application-specific architecture for the parallel calculation of the decimation in time and radix 2 fast Hartley (FHT) and Fourier (FFT) transforms is presented. A real sequence with N=2ⁿ data items is considered as input. The system calculates the FHT and the FFT in n and n+1 stages. respectively. The modular and regular parallel architecture is based on a constant geometry algorithm using butterflies of four data items and the perfect unshuffle permutation. With this permutation, the mapping of the algorithm in VLSI technology is simplified and the communications among processors are minimized. Organization of the processor memory based on first-in, first-out (FIFO) queues facilitates a systolic data flow and permits the implementation in a direct way of the complex data movements and address sequences of the transforms. This is accomplished by means of simple multiplexing operations, using hardwired control. The total calculation time is (Nlog₂N)/4Q cycles for the FHT and N(1+log₂N)/4Q cycles for the FFT, where Q is the number of processors ( Q= 2^q, Q⩽N/4)     

Fast image labeling using local operators on mesh-connectedcomputers

A new parallel algorithm is proposed for fat image labeling using local operators on image pixels. The algorithm can be implemented on an n×n mesh-connected computer such that, for any integer k in the range [1, log (2n)], the algorithm requires Θ(kn¹k/) bits of local memory per processor and takes Θ(kn) time. Bit-serial processors and communication links can be used without affecting the asymptotic time complexity of the algorithm. The time complexity of the algorithm has very small leading constant factors, which makes it superior to previous mesh computer labeling algorithms for most practical image sizes (e.g. up to 4096×4096 images). Furthermore, the algorithm is based on using stacks that can be realized using very fast shift registers within each processing element     

Efficient algorithms for selection of recovery points in tree taskmodels

Efficient solutions to the problem of optimally selecting recovery points are developed. The solutions are intended for models of computation in which task precedence has a tree structure and a task may fail due to the presence of faults. An algorithm to minimize the expected computation time of the task system under a uniprocessor environment has been developed for the binary tree model. The algorithm has time complexity of O(N₂), where N is the number of tasks, while previously reported procedures have exponential time requirements. The results are generalized for an arbitrary tree model     

Two-dimensional convolution on a pyramid computer

An algorithm for convolving a k×k window of weighting coefficients with an n×n image matrix on a pyramid computer of O(n²) processors in time O(logn+k²), excluding the time to load the image matrix, is presented. If k=Ω (√log n), which is typical in practice, the algorithm has a processor-time product O(n ² k²) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two {0, 1}-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state     

A processor-time-minimal systolic array for transitive closure

Using a directed acyclic graph (DAG) model of algorithms, the authors focus on processor-time-minimal multiprocessor schedules: time-minimal multiprocessor schedules that use as few processors as possible. The Kung, Lo, and Lewis (KLL) algorithm for computing the transitive closure of a relation over a set of n elements requires at least 5n-4 parallel steps. As originally reported. their systolic array comprises n² processing elements. It is shown that any time-minimal multiprocessor schedule of the KLL algorithm's dag needs at least n²/3 processing elements. Then a processor-time-minimal systolic array realizing the KLL dag is constructed. Its processing elements are organized as a cylindrically connected 2-D mesh, when n=0 mod 3. When n≠0 mod 3, the 2-D mesh is connected as a torus     

Optimal broadcasting on the star graph

The star graph has been show to be an attractive alternative to the widely used n-cube. Like the n-cube, the star graph possesses rich structure and symmetry as well as fault tolerant capabilities, but has a smaller diameter and degree. However, very few algorithms exists to show its potential as a multiprocessor interconnection network. Many fast and efficient parallel algorithms require broadcasting as a basic step. An optimal algorithm for one-to-all broadcasting in the star graph is proposed. The algorithm can broadcast a message to N processors in O(log₂ N) time. The algorithm exploits the rich structure of the star graph and works by recursively partitioning the original star graph into smaller star graphs. In addition, an optimal all-to-all broadcasting algorithm is developed     

An optimal implementation of broadcasting with selective reduction

A model of parallel computation called broadcasting with selective reduction (BSR) can be viewed as a concurrent-read concurrent-write (CRCW) parallel random access machine (PRAM) with one extension. An additional type of concurrent memory access is permitted in BSR, namely the BROADCAST instruction by means of which all N processors may gain access to all M memory locations simultaneously for the purpose of writing. At each memory location, a subset of the incoming broadcast data is selected and reduced to one value finally stored in that location. For several problems, BSR algorithms are known which require fewer steps than the corresponding best-known PRAM algorithms, using the same number of processors. A circuit is introduced to implement the BSR model, and it is shown that, in size and depth, the circuit presented is of the same order as an optimal circuit implementing the PRAM. Thus, if it is reasonable to assume that CRCW PRAM instructions execute in constant time, the assumption of a constant time BROADCAST instruction is no less reasonable     

Comments on `Parallel algorithms for hierarchical clustering andcluster validity'

In the above-titled paper (ibid., vol.12, no.11, p.1088-92, Nov. 1990), parallel implementations of hierarchical clustering algorithms that achieve O(n²) computational time complexity and thereby improve on the baseline of sequential implementations are described. The latter are stated to be O( n³), with the exception of the single-link method. The commenter points out that state-of-the-art hierarchical clustering algorithms have O(n²) time complexity and should be referred to in preference to the O(n³ ) algorithms, which were described in many texts in the 1970s. Some further references in the parallelizing of hierarchic clustering algorithms are provided     

Parallel evaluation of attribute grammars

Examines the generation of parallel evaluators for attribute grammars, targeted to shared-memory MIMD computers. Evaluation-time overhead due to process scheduling and synchronization is reduced by detecting coarse-grain parallelism (as opposed to the naive one-process-per-node approach). As a means to more clearly expose inherent parallelism, it is shown how to automatically transform productions of the form X→Y X into list-productions of the form X→Y⁺. This transformation allows for many simplifications to be applied to the semantic rules, which can expose a significant degree of inherent parallelism, and thus further increase the evaluator's performance. Effectively, this constitutes an extension of the concept of attribute grammars to the level of abstract syntax