Pyramid mappings onto hypercubes for computer vision: Connection machine comparative study

The paper presents a comparative analysis for algorithms that map pyramids onto hypercubes. The analysis is based on some important performance measures from graph theory and actual results from a Connection Machine system CM-2 containing 16K processors. Connection Machine results are presented for pyramid algorithms that compute the perimeter of objects, apply 2-dimensional convolution, and segment images.     

Connected component labelling on the BLITZEN massively parallel processor

This paper presents the implementation of two connected component labelling algorithms on the BLITZEN massively parallel processor that was developed recently for NASA. The topology of BLITZEN is a two-dimensional mesh that can be dynamically configured to also support diagonal data transfers. It is shown that an algorithm based on Levialdi's connected component shrinking process performs much better than a straightforward algorithm for connected component labelling.     

Parallel generation of adaptive multiresolution structures for image processing

In the paper we present an algorithm for creating region-adjacency-graph (RAG) pyramids on TurboNet, an experimental parallel computer system. Each level of these hierarchies of irregular tessellations is generated by independent stochastic processes that adapt the structure of the pyramid to the content of the image. RAGs can be used in multiresolution image analysis to extract connected components from labeled images. The implementation of the algorithm is discussed and performance results are presented for three different communication techniques which are supported by the TurboNet's hybrid architecture. The results indicate that efficient communications are vital to good performance of the algorithm. © 1997 by John Wiley & Sons, Ltd.     

Parallel DSP algorithms on TurboNet: an experimental system with hybrid message-passing/shared-memory architecture

The paper presents several parallel DSP (digital signal processing) algorithms and their performance analysis, targetting a hybrid message-passing and shared-memory architecture that has been built at New Jersey Institute of Technology. The current version of our system contains eight powerful TMS320C40 processors. The algorithms are implemented on our system using message-passing only, shared-memory only, and, if possible, a combination of both of these parallel processing paradigms. Comparisons show that TurboNet's robust, hybrid architecture results in significant performance gains because of the flexibility it introduces.     

Efficient mapping algorithms for a class of hierarchical systems

Proposes techniques for mapping application algorithms onto a class of hierarchically structured parallel computing systems. Multiprocessors of this type are capable of efficiently solving a variety of scientific problems because they can efficiently implement both local and global operations for data in a two-dimensional array format. Among the set of candidate application domains, low-level and intermediate-level image processing and computer vision (IPCV) are characterized by high-performance requirements. Emphasis is given to IPCV algorithms. The importance of the mapping techniques stems from the fact that the current technology cannot be used to build cost-effective and efficient systems composed of very large numbers of processors, so the performance of various systems of lower cost should be investigated. Both analytical and simulation results prove the effectiveness and efficiency of the proposed mapping techniques     

Novel Pipelined Architecture for Efficient Evaluation of the Square Root Using a Modified Non-Restoring Algorithm

The square root is a basic arithmetic operation in image and signal processing. We present a novel pipelined architecture to implement N-bit fixed-point square root operation on an FPGA using a non-restoring pipelined algorithm that does not require floating-point hardware. Pipelining hazards in its hardware realization are avoided by modifying the classic non-restoring algorithm, thus resulting in a 13% improved latency. Furthermore, the proposed architecture is flexible allowing modification as per individual application needs. It is demonstrated that the proposed architecture is approximately four times faster than its popular counterparts and at the same time it consumes 50% less energy for envelope detection at 268 MHz sampling rate.     

A super-programming approach for mining association rules in parallel on PC clusters

PC clusters have become popular in parallel processing. They do not involve specialized interprocessor networks, so the latency of data communications is rather long. The programming models for PC clusters are often different than those for parallel machines or supercomputers containing sophisticated interprocessor communication networks. For PC clusters, load balancing among the nodes becomes a more critical issue in attempts to yield high performance. We introduce a new model for program development on PC clusters, namely, the super-programming model (SPM). The workload is modeled as a collection of super-instructions (SIs). We propose that a set of SIs be designed for each application domain. They should constitute an orthogonal set of frequently used high-level operations in the corresponding application domain. Each SI should normally be implemented as a high-level language routine that can execute on any PC. Application programs are modeled as super-programs (SPs), which are coded using SIs. SIs are dynamically assigned to available PCs at runtime. Because of the known granularity of SIs, an upper bound on their execution time can be estimated at static time. Therefore, dynamic load balancing becomes an easier task. Our motivation is to support dynamic load balancing and code porting, especially for applications with diverse sets of inputs such as data mining. We apply here SPM to the implementation of an a priori-like algorithm for mining association rules. Our experiments show that the average idle time per node is kept very low.     

Parallel LU factorization of sparse matrices on FPGA‐based configurable computing engines

Configurable computing, where hardware resources are configured appropriately to match specific hardware designs, has recently demonstrated its ability to significantly improve performance for a wide range of computation‐intensive applications. With steady advances in silicon technology, as predicted by Moore's Law, Field‐Programmable Gate Array (FPGA) technologies have enabled the implementation of System‐on‐a‐Programmable‐Chip (SOPC or SOC) computing platforms, which, in turn, have given a significant boost to the field of configurable computing. It is possible to implement various specialized parallel machines in a single silicon chip. In this paper, we describe our design and implementation of a parallel machine on an SOPC development board, using multiple instances of a soft IP configurable processor; we use this machine for LU factorization. LU factorization is widely used in engineering and science to solve efficiently large systems of linear equations. Our implementation facilitates the efficient solution of linear equations at a cost much lower than that of supercomputers and networks of workstations. The intricacies of our FPGA‐based design are presented along with tradeoff choices made for the purpose of illustration. Performance results prove the viability of our approach. Copyright © 2004 John Wiley & Sons, Ltd.     

Robust scalability analysis and SPM case studies

Scalability has become an attribute of paramount importance for computer systems used in business, scientific and engineering applications. Although scalability has been widely discussed, especially for pure parallel computer systems, it conveniently focuses on improving performance when increasing the number of computing processors. In fact, the term “scalable” is so much abused that it has become a marketing tool for computer vendors independent of the system’s technical qualifications. Since the primary objective of scalability analysis is to determine how well a system can work on larger problems with an increase in its size, we introduce here a generic definition of scalability. For illustrative purposes only, we apply this definition to PC clusters, a rather difficult subject due to their long communication latencies. Since scalability does not solely depend on the system architecture but also on the application programs and their actual management by the run-time environment, for the sake of illustration, we evaluate scalability for programs developed under the super-programming model (SPM) (Jin and Ziavras in IEEE Trans. Parallel Distrib. Syst. 15(9):783–794, 2004; J. Parallel Distrib. Comput. 65(10):1281–1289, 2005; IEICE Trans. Inf. Syst. E87-D(7):1774–1781, 2004).