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.     

Mesh of Linear Arrays for Template Matching

This paper presents the architecture and the implementation of template matching on a 3-D piece-wise regular processor space that forms a two-dimensional array of linear systolic arrays. Template matching can be considered as a 2-D convolution of an image of sizeN × Nwith a kernel of sizer× r. Conventional high-speed implementations use 2-D systolic arrays of sizeO(r²) which compute inO(N²) time. The drawback of this solution is that the size of the processor array follows on the size of the convolution kernel. This does not permit the allocation of more processors in order to meet the real-time requirements. With the approach used in this paper, the size of the processor array may be extended up toO(sr²), 1 ≤s≤N, thereby accomplishing the calculations inO(N²/s) time. In the case whens=r, ther × rmesh of 1-D systolic arrays of sizeO(r) is yielded. The piecewise regularity of the 3-D processor array allows also easy physical realization.     

Optimal Computing the Chessboard Distance Transform on Parallel Processing Systems

Thedistance transform(DT) is an image computation tool which can be used to extract the information about the shape and the position of the foreground pixels relative to each other. It converts a binary image into a grey-level image, where each pixel has a value corresponding to the distance to the nearest foreground pixel. The time complexity for computing the distance transform is fully dependent on the different distance metrics. Especially, the more exact the distance transform is, the worse execution time reached will be. Nowadays, quite often thousands of images are processed in a limited time. It seems quite impossible for a sequential computer to do such a computation for the distance transform in real time. In order to provide efficient distance transform computation, it is considerably desirable to develop a parallel algorithm for this operation. In this paper, based on the diagonal propagation approach, we first provide anO(N²) time sequential algorithm to compute thechessboard distance transform(CDT) of anN×Nimage, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. Following the mapping as proposed by Lee and Horng, the algorithm for the medial axis transform is also efficiently derived. The medial axis transform of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. The proposed parallel algorithms are composed of a set of prefix operations. In each prefix operation phase, only increase (add-one) operation and minimum operation are employed. So, the algorithms are especially efficient in practical applications.     

A fault tolerant massively parallel processing architecture

This paper presents two massively parallel processing architectures suitable for solving a wide variety of algorithms of divide-and-conquer type for problems such as the discrete Fourier transform, production systems, design automation, and others. The first architecture, called the Chain-structured Butterfly ARchitecture (CBAR), consists of a two-dimensional array of N = L · (log₂(L) + 1) processing elements (PE) organized as L levels of log₂(L) + 1 stages, and which has the butterfly connection between PEs in consecutive stages with straight-through feedback between PEs in the last and first stages. This connection system has the desirable property of allowing thousands of PEs to be connected with O(N) connection cost, O(log₂(N/log₂N)) communication paths, and a small number (=4) of I/O ports per PE. However, this architecture is not fault tolerant. We, therefore, propose a second architecture, called the REconfigurable Chain-structured Butterfly ARchitecture (RECBAR), which is a modified version of the CBAR. The RECBAR possesses all the desirable features of the CBAR, with the number of I/O ports per PE increased to six, and uses O((log₂N)/N) overhead in PEs and approximately 50% overhead in links to achieve single-level fault tolerance. Reliability improvements ofthe RECBAR over the CBAR are studied. This paper also presents a distributed diagnostic and structuring algorithm for the RECBAR that enables the architecture to detect faults and structure itself accordingly within 2 · log₂(L) + 1 time steps, thus making it a truly fault tolerant architecture.     

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log²n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)²) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.     

Computing the subset partial order for dense families of sets

We give an algorithm to compute the subset partial order (called the subset graph) for a family F of sets containing k sets with N elements in total and domain size n. Our algorithm requires O(nk²/logk) time and space on a Pointer Machine. When F is dense, i.e. N=Θ(nk), the algorithm requires O(N²/log²N) time and space. We give a construction for a dense family whose subset graph is of size Θ(N²/log²N), indicating the optimality of our algorithm for dense families. The subset graph can be dynamically maintained when F undergoes set insertions and deletions in O(nk/logk) time per update (that is sub-linear in N for the case of dense families). If we assume words of b?k bits, allow bits to be packed in words, and use bitwise operations, the above running time and space requirements can be reduced by a factor of blog(k/b+1)/logk and b²log(k/b+1)/logk respectively.     

A Truncation Method for Computing Walsh Transforms with Applications to Image Processing

We present a method called the Truncation method for computing Walsh-Hadamard transforms of one- and two-dimensional data. In one dimension, the method uses binary trees as a basis for representing the data and computing the transform. In two dimensions, the method uses quadtrees (pyramids), adaptive quad-trees, or binary trees as a basis. We analyze the storage and time complexity of this method in worst and general cases. The results show that the Truncation method degenerates to the Fast Walsh Transform (FWT) in the worst case, while the Truncation method is faster than the Fast Walsh Transform when there is coherence in the input data, as will typically be the case for image data. In one dimension, the performance of the Truncation method for N data samples is between O(N) and O(N log₂N), and it is between O(N²) and O(N² log₂N) in two dimensions. Practical results on several images are presented to show that both the expected and actual overall times taken to compute Walsh transforms using the Truncation method are less than those required by a similar implementation of the FWT method.     

Parallel tree contraction and prefix computations on a large family of interconnection topologies

The derivation of the prefixes of a given sequence (prefix computation) and the fast reduction of a tree to a single node (tree contraction) are two useful primitives for many applications on parallel computers. It is well known that certain special cases of the two problems can be solved efficiently on the hypercube. Here we extend this result to a large family of parallel computers. The family of parallel computers are based on a novel interconnection scheme called thegeneralized Fibonacci cube that encompasses both the hypercube and the second-order Fibonacci cube in [8]. Specifically, we show that thek-th order Fibonacci tree of sizeN can be reduced to a single node inO(logN) steps on ak-th order Fibonacci cube withN nodes (processors). Assuming thatO(logN) data items are on each of theN processors, we also show that the prefixes can be computed inO(logN) steps on thek-th order Fibonacci cube.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

A new quantum claw-finding algorithm for three functions

Fork functionsf ₁, ...f _k, ak-tuple (x ₁, ...x _k) such thatf ₁(x ₁)=...=f _k(x _k) is called a claw off ₁, ...,f _k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the numberM of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requiresO(N ^7/8 logN) queries to find a claw, but our algorithm requiresO(N ^3/4 logN) queries ifM ≤ √N andO(N ^7/12 M ^1/3 logN) queries otherwise. Thus, our algorithm is more efficient ifM≤N ^7/8. Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Akinori Kawachi: Received B.Eng. and M.Info. from Kyoto University in 2000 and 2002, respectively. His research interests are quantum computation and distributed computation.     

A SimpleO(log N) Time Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs

Maximal outerplanar graphs constitute an important class of graphs, often encountered in various applications, e.g., computational geometry, robotics, etc. In this paper, we propose a parallel algorithm for testing the isomorphism of maximal outerplanar graphs. Given the ordered adjacency lists of the two graphs, the proposed algorithm tests their isomorphism inO(log N) time usingNprocessors, for graphs withNnodes on an EREW shared memory model, as well as on a hypercube arhitecture. When the adjacency matrices of the graphs are given, this algorithm can be redesigned onN²processors to run inO(log N) time.     

Efficient and exact quantum compression

We present a divide and conquer based algorithm for optimal quantum compression/decompression, using O(n(log⁴n)log log n) elementary quantum operations. Our result provides the first quasi-linear time algorithm for asymptotically optimal (in size and fidelity) quantum compression and decompression. We also outline the quantum gate array model to bring about this compression in a quantum computer. Our method uses various classical algorithmic tools to significantly improve the bound from the previous best known bound of O(n³) for this operation.     

A Nonoblivious Bus Access Scheme Yields an Optimal Partial Sorting Algorithm

This paper focuses on a linear array ofnnodes withmultiple shared busesas a practically feasible model for parallel processing. Letkbe the number of shared buses. A nonoblivious scheme for mutually exclusive access tokshared buses is proposed. The effectiveness of the scheme is demonstrated by proposing an algorithm for solving a partial sort problem, which can be efficiently executed on the array according to the scheme. Thepartial sort problemwith parametermis the problem of sorting a subsetS′ of a given setS, whereS′ is the set of elements less than or equal to themth smallest element inS. Ifm= 1, then it is solved by an algorithm for finding the smallest element inS, and ifm=n, then it is solved by adapting normal sorting algorithm. The time complexity (9m/k) log₂log₂n+ 3.467[formula]+O(m/k+ (n/k)^1/4) of the proposed algorithm matches a lower bound Ω ([formula]+m/k) with respect tonandk, ifmis small enough to satisfym=O([formula]/log logn).     

Coarse-Grained Parallel Geometric Search

We present a parallel algorithm for solving thenext element search problemon a set of line segments, using a BSP-like model referred to as thecoarse grained multicomputer(CGM). The algorithm requiresO(1) communication rounds (h-relations withh=O(n/p)),O((n/p) log n) local computation, andO((n/p) log p) memory per processor, assumingn/p⩾p. Our result implies solutions to the point location, trapezoidal decomposition, and polygon triangulation problems. A simplified version for axis-parallel segments requires onlyO(n/p) memory per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri (Int. J. Comput. Geom. Appl.6(1996), 487–506), our algorithm is based on a distributed implementation of segment trees which are of sizeO(n log n). This paper improves onop. cit.in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require onlyO((n/p) log n) local computation instead ofO(log p*(n/p) log n). (3) The algorithms require onlyO((n/p) log p) local memory instead ofO((n/p) log n).     

Computing the Map of Geometric Minimal Cuts

In this paper we consider the following problem of computing a map of geometric minimal cuts (called MGMC problem): Given a graph G=(V,E) and a planar rectilinear embedding of a subgraph H=(V _H ,E _H ) of G, compute the map of geometric minimal cuts induced by axis-aligned rectangles in the embedding plane. The MGMC problem is motivated by the critical area extraction problem in VLSI designs and finds applications in several other fields. In this paper, we propose a novel approach based on a mix of geometric and graph algorithm techniques for the MGMC problem. Our approach first shows that unlike the classic min-cut problem on graphs, the number of all rectilinear geometric minimal cuts is bounded by a low polynomial, O(n ³). Our algorithm for identifying geometric minimal cuts runs in O(n ³logn(loglogn)³) expected time which can be reduced to O(nlogn(loglogn)³) when the maximum size of the cut is bounded by a constant, where n=|V _H |. Once geometric minimal cuts are identified we show that the problem can be reduced to computing the L _∞ Hausdorff Voronoi diagram of axis aligned rectangles. We present the first output-sensitive algorithm to compute this diagram which runs in O((N+K)log² NloglogN) time and O(Nlog² N) space, where N is the number of rectangles and K is the complexity of the Hausdorff Voronoi diagram. Our approach settles several open problems regarding the MGMC problem.     

Systolic arrays for multidimensional discrete transforms

An active area of research in supercomputing is concerned with mapping certain finite sums, such as discrete Fourier transforms, onto arrays of processors. This paper presents systolic mapping techniques that exploit the parallelism inherent in discrete Fourier transforms. It is established that, for anM-dimensional signal, parallel executions of such transforms are closely related to mappings of an (M + 1)-dimensional finite vector space into itself. Three examples of such parallel schemes are then described for the discrete Fourier transform of a two-dimensional finite extent sequence of sizeN ₁ ×N ₂. The first is a linear array ofN ₁ +N ₂ – 1 processors and takesO(N ₁ N ₂) steps. The second is anN ₁ ×N ₂ rectangular array of processors and takesO(N ₁ +N ₂) steps, and the third is a hexagonal array which usesN ₁ N ₂ + (N ₂ – 1)(N ₁ +N ₂ – 1) processors andO(N ₁ +N ₂) steps. All three mappings are optimal in that they achieve asymptotically the highest speedup possible over the sequential execution of the same transform, and can easily be generalized to higher dimensions.     

TDM Hypercube and TWDM Mesh Optical Interconnections

We propose the time division multiplexed hypercube (TDM-cube) and the time/wavelength division multiplexed mesh (TWDM-mesh). The TDM-cube is an extension of the earlier work by Thompson on the dilated slipped banyan network, DSB. While the DSB(N) provides the complete connection among N users in O(N) time via the time division multiplexing, the TDM-cube(N) implements the binary hypercube interconnection among N users in O(log₂ N) time. The TWDM-mesh(n²) uses a DSB(n), and combines the TDM and WDM. Like the Bus-Mesh, it requires at most 2 hops to send a packet from one node to any other node. The TWDM-mesh has a much higher network throughput than the Bus-Mesh. Both the TDM-cube and TWDM-mesh require only one fixed-wavelength transmitter/receiver per node, and they have a simple column control and dilated operation. The performance in terms of scalability, delay, and throughput is considered.     

A novel constant degree and constant congestion DHT scheme for peer-to-peer networks

1 Introduction and related work In recent years, peer-to-peer computing has attracted significant attention from both industry field and academic field[1-3]. The core component of many proposed peer-to- peer systems is the distributed hash table (DHT) schemes[4,5] that use a hash table-like interface to publish and look up data objects. Many proposed DHT schemes[6-15] are based on some traditional interconnection to- pology: Chord[6], Tapestry[7,8], Pastry[9] are based on hypercube topolog…     

Matching with don't-cares and a small number of mismatches

In matching with don't-cares and k mismatches we are given a pattern of length m and a text of length n, both of which may contain don't-cares (a symbol that matches all symbols), and the goal is to find all locations in the text that match the pattern with at most k mismatches, where k is a parameter. We present new algorithms that solve this problem using a combination of convolutions and a dynamic programming procedure. We give randomized and deterministic solutions that run in time O(nk²logm) and O(nk³logm), respectively, and are faster than the most efficient extant methods for small values of k. Our deterministic algorithm is the first to obtain an O(polylog(k)⋅nlogm) running time.