Performance Evaluation of a Multi-Zone Application in Different OpenMP Approaches

We describe a performance study of a multi-zone application benchmark implemented in several OpenMP approaches that exploit multi-level parallelism and deal with unbalanced workload. The multi-zone application was derived from the well-known NAS Parallel Benchmarks (NPB) suite that involves flow solvers on collections of loosely coupled discretization meshes. Parallel versions of this application have been developed using the Subteam concept and Workqueuing model as extensions to the current OpenMP. We examine the performance impact of these extensions to OpenMP and compare with hybrid and nested OpenMP approaches on several large parallel systems.     

A Rectangular Finite Volume Element Method for a Semilinear Elliptic Equation

In this paper we extend the idea of interpolated coefficients for semilinear problems to the finite volume element method based on rectangular partition. At first we introduce bilinear finite volume element method with interpolated coefficients for a boundary value problem of semilinear elliptic equation. Next we derive convergence estimate in H ¹-norm and superconvergence of derivative. Finally an example is given to illustrate the effectiveness of the proposed method. This work is supported by Program for New Century Excellent Talents in University of China State Education Ministry, National Science Foundation of China, the National Basic Research Program under the Grant (2005CB321703), the key project of China State Education Ministry (204098), Scientific Research Fund of Hunan Provincial Education Department, China Postdoctoral Science Foundation (No. 20060390894) and China Postdoctoral Science Foundation (No. 20060390894).     

Color Subspaces as Photometric Invariants

Complex reflectance phenomena such as specular reflections confound many vision problems since they produce image ‘features’ that do not correspond directly to intrinsic surface properties such as shape and spectral reflectance. A common approach to mitigate these effects is to explore functions of an image that are invariant to these photometric events. In this paper we describe a class of such invariants that result from exploiting color information in images of dichromatic surfaces. These invariants are derived from illuminant-dependent ‘subspaces’ of RGB color space, and they enable the application of Lambertian-based vision techniques to a broad class of specular, non-Lambertian scenes. Using implementations of recent algorithms taken from the literature, we demonstrate the practical utility of these invariants for a wide variety of applications, including stereo, shape from shading, photometric stereo, material-based segmentation, and motion estimation.     

Analysis of Two-Dimensional Non-Rigid Shapes

Analysis of deformable two-dimensional shapes is an important problem, encountered in numerous pattern recognition, computer vision and computer graphics applications. In this paper, we address three major problems in the analysis of non-rigid shapes: similarity, partial similarity, and correspondence. We present an axiomatic construction of similarity criteria for deformation-invariant shape comparison, based on intrinsic geometric properties of the shapes, and show that such criteria are related to the Gromov-Hausdorff distance. Next, we extend the problem of similarity computation to shapes which have similar parts but are dissimilar when considered as a whole, and present a construction of set-valued distances, based on the notion of Pareto optimality. Finally, we show that the correspondence between non-rigid shapes can be obtained as a byproduct of the non-rigid similarity problem. As a numerical framework, we use the generalized multidimensional scaling (GMDS) method, which is the numerical core of the three problems addressed in this paper.     

Model of Frequency Analysis in the Visual Cortex and the Shape from Texture Problem

This paper addresses the question: at the level of cortical cells present in the primary area V1, is the information sufficient to extract the local perspective from the texture? Starting from a model of complex cells in visual area V1, we propose a biologically plausible algorithm for frequency analysis applied to the shape from texture problem. First, specific log-normal filters are designed in replacement of the classical Gabor filters because of their theoretical properties and of their biological plausibility. These filters are separable in frequency and orientation and they better sample the image spectrum which makes them appropriate for any pattern analysis technique. A method to estimate the local frequency in the image, which discards the need to choose the best local scale, is designed. Based on this frequency analysis model, a local decomposition of the image into patches leads to the estimation of the local frequency variation which is used to solve the problem of recovering the shape from the texture. From the analytical relation between the local frequency and the geometrical parameters, under perspective projection, it is possible to recover the orientation and the shape of the original image. The accuracy of the method is evaluated and discussed on different kind of textures, both regular and irregular, with planar and curved surfaces and also on natural scenes and psychophysical stimuli. It compares favorably to the best existing methods, with in addition, a low computational cost. The biological plausibility of the model is finally discussed.     

Over-Parameterized Variational Optical Flow

A novel optical flow estimation process based on a spatio-temporal model with varying coefficients multiplying a set of basis functions at each pixel is introduced. Previous optical flow estimation methodologies did not use such an over parameterized representation of the flow field as the problem is ill-posed even without introducing any additional parameters: Neighborhood based methods of the Lucas–Kanade type determine the flow at each pixel by constraining the flow to be described by a few parameters in small neighborhoods. Modern variational methods represent the optic flow directly via the flow field components at each pixel. The benefit of over-parametrization becomes evident in the smoothness term, which instead of directly penalizing for changes in the optic flow, accumulates a cost of deviating from the assumed optic flow model. Our proposed method is very general and the classical variational optical flow techniques are special cases of it, when used in conjunction with constant basis functions. Experimental results with the novel flow estimation process yield significant improvements with respect to the best results published so far.     

Multi-Class Segmentation with Relative Location Prior

Multi-class image segmentation has made significant advances in recent years through the combination of local and global features. One important type of global feature is that of inter-class spatial relationships. For example, identifying “tree” pixels indicates that pixels above and to the sides are more likely to be “sky” whereas pixels below are more likely to be “grass.” Incorporating such global information across the entire image and between all classes is a computational challenge as it is image-dependent, and hence, cannot be precomputed. In this work we propose a method for capturing global information from inter-class spatial relationships and encoding it as a local feature. We employ a two-stage classification process to label all image pixels. First, we generate predictions which are used to compute a local relative location feature from learned relative location maps. In the second stage, we combine this with appearance-based features to provide a final segmentation. We compare our results to recent published results on several multi-class image segmentation databases and show that the incorporation of relative location information allows us to significantly outperform the current state-of-the-art.     

On conditional diagnosability and reliability of the BC networks

An n-dimensional bijective connection network (in brief, BC network), denoted by X _n , is an n-regular graph with 2 ⁿ nodes and n2 ^n?1 edges. Hypercubes, crossed cubes, twisted cubes, and Möbius cubes all belong to the class of BC networks (Fan and He in Chin. J. Comput. 26(1):84–90, [2003]). We prove that the super connectivity of X _n is 2n?2 for n≥3 and the conditional diagnosability of X _n is 4n?7 for n≥5. As a corollary of this result, we obtain the super connectivity and conditional diagnosability of the hypercubes, twisted cubes, crossed cubes, and Möbius cubes.     

An adaptive and trustworthy software testing framework on the grid

Grid computing, which is characterized by large-scale sharing and collaboration of dynamic distributed resources has quickly become a mainstream technology in distributed computing and is changing the traditional way of software development. In this article, we present a grid-based software testing framework for unit and integration test, which takes advantage of the large-scale and cost-efficient computational grid resources to establish a testbed for supporting automated software test in complex software applications. Within this software testing framework, a dynamic bag-of-tasks model using swarm intelligence is developed to adaptively schedule unit test cases. Various high-confidence computing mechanisms, such as redundancy, intermediate value checks, verification code injection, and consistency checks are employed to verify the correctness of each test case execution on the grid. Grid workflow is used to coordinate various test units for integration test. Overall, we expect that the grid-based software testing framework can provide efficient and trustworthy services to significantly accelerate the testing process with large-scale software testing.

On scheduling and clustering in hierarchical TH-PPM UWB wireless ad hoc networks

Ultra wideband (UWB) systems are considered as the key wireless infrastructure platforms for efficient short-range communications. In particular, the UWB based mobile computing systems are envisioned to be attractive solutions to various ad hoc networking applications. However, due to UWB’s unique physical characteristics, the traditional resource management schemes for ad hoc networks cannot be applied to UWB based systems directly. In this paper, we consider the bandwidth scheduling problem in a UWB based hierarchical wireless ad hoc network, which is typically used in an enterprise-scale mobile computing environment. Based on the mathematical analysis and the computer simulations, it is demonstrated that our proposed scheduling scheme exhibits close-to-optimal performance governed by the proportional fairness (PF) constraint. Moreover, a novel self-organized clustering method is designed to improve the system throughput while meeting the PF constraint. Simulation results suggest that the proposed clustering method is effective under various system configurations.