Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers

This paper presents several algorithms for solving problems using massively parallel SIMD hypercube and shuffle-exchange computers. The algorithms solve a wide variety of problems, but they are related because they all use a common strategy. Specifically, all of the algorithms use a divide-and-conquer approach to solve a problem withN inputs using a parallel computer withP processors. The structural properties of the problem are exploited to assure that fewer thanN data items are communicated during the division and combination steps of the divide-and-conquer algorithm. This reduction in the amount of data that must be communicated is central to the efficiency of the algorithm.This paper addresses four problems, namely the multiple-prefix, data-dependent parallel-prefix, image-component-labeling, and closest-pair problems. The algorithms presented for the data-dependent parallel-prefix and closest-pair problems are the fastest known whenN P and the algorithms for the multiple-prefix and image-component-labeling problems are the fastest known whenN is sufficiently large with respect toP.This work was supported in part by our NSF Graduate Fellowship.     

SUSAN structure preserving filtering for mesh denoising

Motivated by the impressive effect of the SUSAN operator for low level image processing and its usage simplicity, we extend it to denoise the 3D mesh. We use the angle between the normals on the surface to determine the SUSAN area; each point has associated itself with the SUSAN area that is has a similar continuity feature to the point. The SUSAN area avoids the feature to be taken as noise effectively, so the SUSAN operator gives the maximal number of suitable neighbors with which to take an average, whilst no neighbors from unrelated regions are involved. Thus, the entire structure can be preserved. We also extend the SUSAN operator to two-ring neighbors by a squared umbrella-operator to improve the surface smoothness with little loss of detailed features. Details of the SUSAN structure preserving noise reduction algorithm are discussed along with the test results in this paper.     

Fast mean filtering technique (FMFT)

This article presents a novel method for mean filtering that reduces the required number of additions and eliminates the need for division altogether. The time reduction is achieved using basic store-and-fetch operations and is irrespective of the image or neighbourhood size. This method has been tested on a variety of greyscale images and neighbourhood sizes with promising results. These results indicate that the relative time requirement reduces with increase in image size. The method's efficiency also improves significantly with increase in neighbourhood size thereby making it increasingly useful when dealing with large images.     

基于System Generator的快速中值滤波算法设计与实现

针对传统中值滤波算法比较运算量大、处理效率低、无法满足实时性的问题,以中值滤波原理为基础,对滤波排序算法和实现方案进行了研究,提出了一种基于System Generator的快速中值滤波算法。该算法通过两次行、列排序将3×3窗口中9个像素取中值简化为3个像素的排序运算,使得单窗口查找中值的比较次数由传统排序算法的36次最少降到了14次。结合System Generator系统建模工具,将处理速度提升到传统方法的近6倍,达到了快速抑制噪声的目的,满足了图像实时处理的要求。     

基于向量图分析的自适应滤波快速算法

对自适应滤波算法进行了讨论,提出了基于向量图分析的快速算法.该方法与目前所有自适应滤波算法不同,将数学中的几何分析方法引入到自适应滤波的研究中,通过探讨最小均方(LMS)算法的向量图结构及其算法收敛的几何特征,在基于几何分析的基础上,寻找有效的快速算法.仿真结果表明了所获算法的有效性及优越性,从而为自适应滤波算法的研究开辟了另一条新的途径.     

边界重叠图象的一种快速拼接算法

针对边界部分有重叠的图象,提出了一种基于网络的快速对准算法,并通过平滑因子对图象实现了无缝拼接。     

Parallel computers for region-level image processing

It is well known that parallel computers can be used very effectively for image processing at the pixel level, by assigning a processor to each pixel or block of pixels, and passing information as necessary between processors whose blocks are adjacent. This paper discusses the use of parallel computers for processing images at the region level, assigning a processor to each region and passing information between processors whose regions are related. The basic difference between the pixel and region levels is that the regions (e.g. obtained by segmenting the given image) and relationships differ from image to image, and even for a given image, they do not remain fixed during processing. Thus, one cannot use the standard type of cellular parallelism, in which the set of processors and interprocessor connections remain fixed, for processing at the region level. Reconfigurable cellular computers, in which the set of processors that each processor can communicate with can change during a computation, are more appropriate. A class of such computers is described, and general examples are given illustrating how such a computer could initially configure itself to represent a given decomposition of an image into regions, and dynamically reconfigure itself, in parallel, as regions merge or split.     

Efficient algorithms for computing two nearest-neighbor problems on a rap

This paper makes an improvement of computing two nearest-neighbor problems of images on a reconfigurable array of processors (RAP) by increasing the bus width between processors. Based on a base-n system, a constant time algorithm is first presented for computing the maximum/minimum of N log N-bit unsigned integers on a RAP using N processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Then, two basic operations such as image component labeling and border following are also derived from it. Finally, these algorithms are used to design two constant time algorithms for the nearest neighbor black pixel and the nearest neighbor component problems on an N^1/2 × N^1/2 image using N^1/2 × N^1/2 processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.     

A new impulse detection and filtering method for removal of wide range impulse noises

A new impulse detection and filtering algorithm is proposed for restoration of images that are highly corrupted by impulse noise. It is based on the minimum absolute value of four convolutions obtained by one-dimensional Laplacian operators. The proposed algorithm can effectively remove the impulse noise with a wide range of noise density and produce better results in terms of the qualitative and quantitative measures of the images even at noise density as high as 90%. Extensive simulations show that the proposed algorithm provides better performance than many of the existing switching median filters in terms of noise suppression and detail preservation.     

Fast parallel algorithms for graph similarity and matching

This paper addresses the problem of global graph alignment on supercomputer-class clusters. We define the alignment of two graphs, as a mapping of each vertex in the first graph to a unique vertex in the second graph so as to optimize a given similarity-based cost function.¹ Using a state of the art serial algorithm for the computation of vertex similarity scores called Network Similarity Decomposition (NSD), we derive corresponding parallel formulations. Coupling this parallel similarity algorithm with a parallel auction-based bipartite matching technique, we obtain a highly efficient and scalable graph matching pipeline. We validate the performance of our integrated approach on a large parallel platform and on diverse graph instances (including Protein Interaction, Wikipedia and Web networks). Experimental results demonstrate that our algorithms scale to large machine configurations (thousands of cores) and problem instances, enabling the alignment of networks of sizes two orders of magnitude larger than reported in the current literature.     

中值滤波与各向异性扩散相结合的医学图像滤波方法

医学图像的滤波处理,须保留具有重要诊断意义的边缘细节信息。针对Perona-Malik(PM)各向异性扩散模型遇到强噪声则失效和扩散门限参数K依靠经验选取的不足,提出了一种改进的各向异性扩散算法。将PM算法与中值滤波结合,用经过中值滤波平滑后的梯度模代替原始图像的梯度模,以控制扩散的过程。应用自适应扩散门限(当前邻域内梯度的绝对偏差中值(MAD))和迭代终止准则,提高算法鲁棒性和效率。实验分别对超声心动图、CT图像和Lena图像进行去噪处理,用峰值信噪比(PSNR)和边缘保持能力EPI作为评价标准。实验结果表明,改进算法优于PM算法和Catte-PM方法,在提高信噪比的同时保留了图像的细节信息,可以更好地满足医学图像的使用要求。     

Construction of optimal algorithms for mass computations in digital filtering problems

Theoretical results are reviewed that are concerned with the construction of speed-optimal parallel-pipeline algorithms for mass calculations in solving filtering problems. The optimality is proved in the corresponding classes of algorithms equivalent in terms of information graphs. The effectiveness of using the developed algorithmic constructions for filtering problems is investigated. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 3–14, July–August 2008.     

基于多抽样率滤波实现离散Gabor展开与变换的快速并行算法

Gabor变换在信号处理领域一直被认为是一十分有用的时频分析工具,却因Gabor变换算法的高计算复杂性而限制了其实时应用.本文基于多抽样率滤波原理,设计了分析和综合滤波器组分别用于实现离散Gabor变换与展开,从而提出了全新的离散Gabor展开与变换快速并行算法.所设计的分析和综合滤波器组中的每一并行通道具有一致的结构并能够利用快速Fourier变换(FFT)及其逆变换(IFFT)减小计算量.每一并行通道计算复杂性非常小,只取决于输入离散信号的长度及Gabor频率抽样点数,并且每一并行通道计算复杂性不会随Gabor变换过抽样率增加而增大.本文对所提出的并行算法的计算复杂性进行了分析并与目前主要的离散Gabor展开与变换并行算法进行了比较,结果表明所提出基于多抽样率滤波实现离散Gabor展开与变换的并行算法对实时信号处理十分有利.     

Propagation algorithms for framing rectangle construction

Given a binary image containing a connected component, parallel propagation algorithms are presented for constructing upright and 45°-tilted framing rectangles around the component in time proportional to the sum of the dimensions of these rectangles. The algorithms make use of properties of geodesics connecting pairs of points in the component to iteratively fill in the region to the desired shape.     

Practical aspects and experiences Scalable massively parallel algorithms for computational nanoelectronics

There is at present a worldwide effort to overcome the technological barriers to nanoelectronics. Microscopic simulation can significantly enhance our understanding of the physics of nanoscale structures, and constitutes a valuable tool for designing nanoelectronic functional devices. In nanodevices, novel physics effects are used to attain logic functionality which conventional technology can not achieve. Therefore it is necessary to develop quantum-transport simulation methods which include novel physical effects. Moreover, simulation of realistic nanodevices require enormous computing resource, necessitating parallel supercomputing. In this paper, we present massively parallel algorithms for simulating large-scale nanoelectronic networks based on the single-electron tunneling effect, which is arguably the quantum effect of greatest significance to nanoelectronic technology. A MIMD implementation of our simulation algorithm is carried out on a 64-processor nCUBE 2, and a SIMD implementation is carried out on a 16,384-processor MasPar MP-1. By exploiting massive parallelism, both parallel implementations achieve very high parallel efficiency and nearly linear scalability. The result of this work is that we are able to simulate large-scale nanoelectronic network, within a reasonable time period, which would be impractical on conventional workstations.     

Fast parallel algorithms for discrete Gabor expansion and transform based on multirate filtering

The Gabor transform has long been recognized as a very useful tool for the joint time and frequency analysis in signal processing.Its real time applications,however,were limited due to the high computational complexity of the Gabor transform algorithms.In this paper,some novel and fast parallel algorithms for the finite discrete Gabor expansion and transform are presented based on multirate filtering.An analysis filter bank is designed for the finite discrete Gabor transform(DGT)and a synthesis filter bank is designed for the finite discrete Gabor expansion(DGE).Each of the parallel channels in the two filter banks has a unified structure and can apply the FFT and the IFFT to reduce its computational load.The computational complexity of each parallel channel does not change as the oversampling rate increases.In fact,it is very low and depends only on the length of the input discrete signal and the number of the Gabor frequency sampling points.The computational complexity of the proposed parallel algorithms is analyzed and compared with that of the major existing parallel algorithms for the finite DGT and DGE.The results indicate that the proposed parallel algorithms for the finite DGT and DGE based on multirate filtering are very attractive for real time signal processing.     

Parallelizing implicit algorithms for time-dependent problems by parabolic domain decomposition

Applications of the multidomain Local Fourier Basis method [1], for the solution of PDEs on parallel computers are described. The present approach utilizes, in an explicit way, the rapid (exponential) decay of the fundamental solutions of elliptic operators resulting from semi-implicit discretizations of parabolic time-dependent problems. As a result, the global matching relations for the elemental solutions are decoupled into local interactions between pairs of solutions in neighboring domains. Such interactions require only local communications between processors with short communication links. Thus the present algorithm overcomes the global coupling, inherent both in the use of the spectral Fourier method and implicit time discretization scheme.This research is supported partly by a grant from the French-Israeli Binational Foundation for 1991–1992.     

一种适于串行机实现的图像并行细化算法

为解决现有的图像并行细化算法在串行机上的高效实现问题 ,首先提出了一种 4× 4邻域二值图像的双字节图像编码方案 ,由于在该方案中将每个 4× 4邻域的像素用一个双字节的整数来表示 ,从而将基于整个邻域 16个像素的细化处理转化为一个双字节整数的读、写和比较运算的问题 ;然后在此基础上提出了一种可在串行机上实现的并行细化算法。实验证明 ,该算法适用于当前通用的各种基于模板匹配的并行细化算法 ,其不仅可以取得完全相同的细化结果 ,而且可以大幅度提高图像细化过程在串行机上的执行速度 ;最后简要讨论了该算法利用 PC机中的 MMX技术来进一步提高并行粒度和运算效率方面所具有的潜力     

Parallel Newton-Krylov-Schwarz algorithms for the three-dimensional Poisson-Boltzmann equation in numerical simulation of colloidal particle interactions

We investigate fully parallel Newton-Krylov-Schwarz (NKS) algorithms for solving the large sparse nonlinear systems of equations arising from the finite element discretization of the three-dimensional Poisson-Boltzmann equation (PBE), which is often used to describe the colloidal phenomena of an electric double layer around charged objects in colloidal and interfacial science. The NKS algorithm employs an inexact Newton method with backtracking (INB) as the nonlinear solver in conjunction with a Krylov subspace method as the linear solver for the corresponding Jacobian system. An overlapping Schwarz method as a preconditioner to accelerate the convergence of the linear solver. Two test cases including two isolated charged particles and two colloidal particles in a cylindrical pore are used as benchmark problems to validate the correctness of our parallel NKS-based PBE solver. In addition, a truly three-dimensional case, which models the interaction between two charged spherical particles within a rough charged micro-capillary, is simulated to demonstrate the applicability of our PBE solver to handle a problem with complex geometry. Finally, based on the result obtained from a PC cluster of parallel machines, we show numerically that NKS is quite suitable for the numerical simulation of interaction between colloidal particles, since NKS is robust in the sense that INB is able to converge within a small number of iterations regardless of the geometry, the mesh size, the number of processors. With help of an additive preconditioned Krylov subspace method NKS achieves parallel efficiency of 71% or better on up to a hundred processors for a 3D problem with 5 million unknowns.