Parallel directed graph algorithms on directional processor arrays with reconfigurable bus systems

Processors arrays with reconfigurable bus systems (abbreviated to PARBS) have been received a lot of attention in the last decade, and many undirected graph algorithms with constant time complexity have been proposed on PARBS. However, for a directed graph, it will be proved that connecting PARBS in the way proposed for undirected graphs generates paths which do not exist in the directed graph. This result may lead to incorrect solution for directed graph problems. Therefore, in this paper, a model named D-PARBS (Directional PARBS) is proposed for eliminating the non-existent paths. This model can be used to correctly identifying redundant arcs on directed graphs in constant time. Furthermore, by modifying the D-PARBS architecture, constant time algorithms with O(n ³) processors are developed to solve topological sort, transitive closure, cyclic graph checking, and strongly connected component problems on directed graphs. Chi-Jung Kuo: He is currently an operation officer of the Information Processing Department in the Taipei Branch of Bangkok Bank. His research interests include parallel processing and graph theory. He received his B.S. and M.S. degree in Information Management from National Taiwan University of Science and Technology in 1993 and 1995, respectively. He was a teacher in the Chin Min Junior College from 1995 to 1996. Chiun-Chieh Hsu, Ph.D.: He is currently a full professor of Information Management Department at National Taiwan University of Science and Technology. His current research interests include fault-tolerant computing, parallel and distributed processing, networks, and graph theory. He received his B.E., M.E., and Ph.D. degrees all in Electrical Engineering from National Taiwan University in 1983, 1987, and 1990, respectively. He worked as a software and firmware design engineer of Research and Development in Acer Computer Company from 1983 to 1985. Wei-Chen Fang: He received the BS degree in MIS from Tamkang University and the MS degree in Information Management from National Taiwan University of Science and Technology. Currently, he is a Ph.d student and works as an assistant researcher with the Advanced Technology research group for Chunghwa Telecommunication Laboratory. His research interests include multi-processor architecture, fault-tolerant computing, and parallel and distributed processing.     

Macro-programmable reconfigurable stream processor for collaborative manufacturing systems

Growing demand for high speed processing of streamed data (e.g. video-streams, digital signal streams, communication streams, etc.) in the advanced manufacturing environments requires the adequate cost-efficient stream-processing platforms. Platforms based on the embedded microprocessors often cannot satisfy performance requirements due to limitations associated with the sequential nature of data execution process. During the last decade, development and prototyping of the above embedded platforms has started moving towards utilization of the Field Programmable Gate Array (FPGA) devices. However, the programming of an application to the FPGA based platform became an issue due to relatively complicated hardware design process. The paper presents an approach which allows simplification of the application programming process by utilization of: (i) the uniformed FPGA platform with the dynamically reconfigurable architecture, (ii) a programming technique based on a temporal partitioning of the application in segments which can be described in terms of macro-operators (function specific virtual components). The paper describes the concept of the approach, presents the analytical investigation and experimental verification of the cost-effectiveness of the proposed platform comparing to the platforms based on sequential micro-processors. It is also shown that the approach can be beneficially utilized in collaborative design and manufacturing.     

Performance Prediction of the Hough Transform

Based on hree different implementation schemes,this paper strongly demonstrates that the performance of the Hough transform depends crucially on its implementation sceme when it is used for line detection.Moreover,the obtained results can be used as a theoretical basis to predict the performance of the Hough transform as well as to eliminate the noise in Hough space coming from image noise.     

Constant time algorithms for the transitive closure and somerelated graph problems on processor arrays with reconfigurable bussystems

The transitive closure problem in O(1) time is solved by a new method that is far different from the conventional solution method. On processor arrays with reconfigurable bus systems, two O (1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional n×n×n processor array with a reconfigurable bus system, and the other is designed on a two-dimensional n²×n² processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O(1) time transitive closure algorithms, many other graph problems are solved in O(1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs     

Fast and processor efficient parallel matrix multiplicationalgorithms on a linear array with a reconfigurable pipelined bus system

We present efficient parallel matrix multiplication algorithms for linear arrays with reconfigurable pipelined bus systems (LARPBS). Such systems are able to support a large volume of parallel communication of various patterns in constant time. An LARPBS can also be reconfigured into many independent subsystems and, thus, is able to support parallel implementations of divide-and-conquer computations like Strassen's algorithm. The main contributions of the paper are as follows. We develop five matrix multiplication algorithms with varying degrees of parallelism on the LARPBS computing model; namely, MM₁, MM ₂, MM₃, and compound algorithms C₁(ϵ)and C₂(δ). Algorithm C₁(ϵ) has adjustable time complexity in sublinear level. Algorithm C₂(δ) implies that it is feasible to achieve sublogarithmic time using σ(N³) processors for matrix multiplication on a realistic system. Algorithms MM₃, C₁(ϵ), and C₂(δ) all have o(𝒩³) cost and, hence, are very processor efficient. Algorithms MM₁, MM₃, and C₁(ϵ) are general-purpose matrix multiplication algorithms, where the array elements are in any ring. Algorithms MM₂ and C₂(δ) are applicable to array elements that are integers of bounded magnitude, or floating-point values of bounded precision and magnitude, or Boolean values. Extension of algorithms MM ₂ and C₂(δ) to unbounded integers and reals are also discussed     

快速随机Hough变换多圆检测算法

随机Hough变换是检测圆的一种有效方法,但在处理多圆复杂图像时随机采样带来的大量无效累积会导致计算量过大。文中提出一种基于随机Hough变换的快速多圆检测算法,除去三类噪声点,通过随机采样到的一点按照一定规则搜索另外两点来确定候选圆,用原始图像对候选圆进行证据积累以判断是否为真圆。理论分析和实验结果表明：该算法较其他算法能更快地检测出图像中的多个圆,具有较好的应用价值。     

基于Hough变换的圆形物体的检测

Hough变换在图像处理中占有重要地位,但本身具有存储空间大、计算时间长的缺点。利用圆的几何特性,针对Hough变换的缺点进行改进,并将其应用到图像中存在多个圆的情况。实验表明:该算法能较好地减少存储空间,并降低计算时间,同时,能很好地对图像中多个圆进行检测。     

An optimal and processor efficient parallel sorting algorithm on a linear array with a reconfigurable pipelined bus system

Optical interconnections attract many engineers and scientists’ attention due to their potential for gigahertz transfer rates and concurrent access to the bus in a pipelined fashion. These unique characteristics of optical interconnections give us the opportunity to reconsider traditional algorithms designed for ideal parallel computing models, such as PRAMs. Since the PRAM model is far from practice, not all algorithms designed on this model can be implemented on a realistic parallel computing system. From this point of view, we study Cole’s pipelined merge sort [Cole R. Parallel merge sort. SIAM J Comput 1988;14:770–85] on the CREW PRAM and extend it in an innovative way to an optical interconnection model, the LARPBS (Linear Array with Reconfigurable Pipelined Bus System) model [Pan Y, Li K. Linear array with a reconfigurable pipelined bus system—concepts and applications. J Inform Sci 1998;106;237–58]. Although Cole’s algorithm is optimal, communication details have not been provided due to the fact that it is designed for a PRAM. We close this gap in our sorting algorithm on the LARPBS model and obtain an O(log N)-time optimal sorting algorithm using O(N) processors. This is a substantial improvement over the previous best sorting algorithm on the LARPBS model that runs in O(log N log log N) worst-case time using N processors [Datta A, Soundaralakshmi S, Owens R. Fast sorting algorithms on a linear array with a reconfigurable pipelined bus system. IEEE Trans Parallel Distribut Syst 2002;13(3):212–22]. Our solution allows efficiently assign and reuse processors. We also discover two new properties of Cole’s sorting algorithm that are presented as lemmas in this paper.     

Inherent bias and noise in the hough transform

Considering the Hough transformation as a linear imaging process recasts certain well-known problems, provides a useful vocab-ulary, and possibly indicates a source of applicable literature on the behavior of the Hough transformation in various forms of noise. A consideration of the analytic form of peaks in parameter space sets the stage for the idea of using complementary (negative) votes to cancel off-peak positive votes in parameter space, thus sharpening peaks and reducing bias.     

Constant-time algorithm for computing the Euclidean distance maps of binary images on 2D meshes with reconfigurable buses

The computation of Euclidean distance maps (EDM), also called Euclidean distance transform, is a basic operation in computer vision, pattern recognition, and robotics. Fast computation of the EDM is needed since most of the applications using the EDM require real-time computation. It is shown in L. Chen and H.Y.H. Chuang [Information Processing Letters, 51, pp. 25–29 (1994)] that a lower bound Ω(n²) is required for any sequential EDM algorithm due to the fact that in any EDM algorithm each of the n² pixels has to be scanned at least once. Recently, many parallel EDM algorithms have been proposed to speedup its computation. Chen and Chuang proposed an algorithm for computing the EDM on an n×n mesh in O(n) time [L. Chen and H.Y.H. Chuang Parallel Computing, 21, pp. 841–852 (1995)]. Clearly, the VLSI complexities of both the sequential and the mesh algorithm described in L. Chen and H.Y.H. Chuang [Parallel Computing, 21, pp. 841–852 (1995)] are AT²=O(n⁴), where A is the VLSI layout area of the design and T is the computation time using area A when implemented in VLSI. In this paper, we propose a new and faster parallel algorithm for computing the EDM problem on the reconfigurable VLSI mesh model. For the same problem, our algorithm runs in O(1) time on a two-dimensional n²×n² reconfigurable mesh. We show that the VLSI complexity of our algorithm is the same as those of the above sequential algorithm and the mesh algorithm, while it uses much less time. To our best knowledge, this is the first constant-time EDM algorithm on any parallel computational model.     

An extension to the randomized hough transform exploiting connectivity

Finding global curve segments in an image is an important task. For such a task, a new branch of Hough Transform algorithms, called probabilistic Hough Transforms, has been actively developed in recent years. One of the first was a new and efficient probabilistic version of the Hough Transform for curve detection, the Randomized Hough Transform (RHT). In this paper, a novel extension of the RHT, called the Connective Randomized Hough Transform (CRHT), is suggested to improve the RHT for line detection in complex and noisy pictures. The CRHT method combines the ability of the Hough Transform for global feature extraction with curve fitting techniques by exploiting the connectivity of local edge image points. Tests demonstrate the high speed and low memory usage of the CRHT, as compared both to the Standard Hough Transform and the basic RHT.     

Contribution to the prediction of performances of the hough transform

Exact predictions of the performances of the Hough detection of straight lines in two-dimensional images are presented for rectangular and circular retinas, in Cartesian and normal parameterization, in the case of noisy signals. Detection of circles, under the same assumptions, is discussed. The limits of adaptive quantization to reduce intrinsic noise are presented, and it is shown that a signal processing approach is especially convenient to measure the performances of a detector based on the Hough transform.     

Randomised hough transform with error propagation for line and circle detection

In this paper, we introduce a new Randomised Hough Transform aimed at improving curve detection accuracy and robustness, as well as computational efficiency. Robustness and accuracy improvement is achieved by analytically propagating the errors with image pixels to the estimated curve parameters. The errors with the curve parameters are then used to determine the contribution of pixels to the accumulator array. The computational efficiency is achieved by mapping a set of points near certain selected seed points to the parameter space at a time. Statistically determined, the seed points are points that are most likely located on the curves and that produce the most accurate curve estimation. Further computational advantage is achieved by performing progressive detection. Examples of detection of lines using the proposed technique are given in the paper. The concept can be extended to non-linear curves such as circles and ellipses. ID="A1"Correspondance and offprint requests to: Q. Ji, Department of Electrical, Computer and Systems Engineering, Rensselaer Polytechnic Institute, Troy, NY 12180, USA. E-mail: qji@ecse.rpi.edu     

Computer vision algorithms on reconfigurable logic arrays

Computer vision algorithms are natural candidates for high performance computing systems. Algorithms in computer vision are characterized by complex and repetitive operations on large amounts of data involving a variety of data interactions (e.g., point operations, neighborhood operations, global operations). In this paper, we describe the use of the custom computing approach to meet the computation and communication needs of computer vision algorithms. By customizing hardware architecture at the instruction level for every application, the optimal grain size needed for the problem at hand and the instruction granularity can be matched. A custom computing approach can also reuse the same hardware by reconfiguring at the software level for different levels of the computer vision application. We demonstrate the advantages of our approach using Splash 2-a Xilinx 4010-based custom computer     

可重构数据流SPJ查询处理器的研究

数据流的实时处理需要很高的处理速度,一种解决方法是使用协处理器。然而协处理器硬布线是不变的,查询不断变化使其一定时间内综合性能达不到最优。为提高数据流处理速度和资源利用率,采用了可重构的数据流SPJ查询处理器,在具备选择、投影和连接三种查询模块及相应指令集的基础上,根据输入查询的查询树调用相应的模块自适应对FPGA编程,改变自身的硬布线,实现数据流的处理。通过大量实验验证了处理器不仅正确,而且具备高速度和灵活性。     

A reconfigurable bus structure for multiprocessors with bandwidth reuse

Shared bus is one of the most popular communication media for tightly coupled multiprocessing environments. However, a shared bus can provide only limited bandwidth, a fact that limits its usability. In this paper we propose a re-configurable bus structure with both temporal and spatial/spectral bandwidth expansion and describe a method for reusing part of the bandwidth available from temporal and spatial/spectral bandwidth expansion without introducing any buffering delay. Two polynomial time algorithms are developed to optimally reconfigure the bus under the design constraints for a given traffic pattern. For one algorithm the architecture is geared to obtain low average system response time. The other algorithm minimizes the system response time on a different architecture that is designed to reduce the disparity of response time among different nodes. We have compared the performance of reconfigured buses with that of the traditional slotted buses for uniform and localized traffic patterns and found that the reconfigured bus outperforms the traditional slotted bus substantially in most practical scenarios.