Abstract:

Diffraction, particularly of X-rays, is a powerful technique for the investigation of structure, microstructure and dynamical properties of matter. In order to link theoretical methods, like Molecular Dynamics and other atomistic approaches, and diffraction experiments we developed a new software for calculating the powder diffraction pattern of nano-sized objects on the GPUs. The software, soon to be made available under GPL license, allows the use of GPUs on different hosts for a direct (brute-force) computation of the Debye scattering equation.

(L Geliso, C. L. Azanza Ricardo, M. Leoni and P. Scardi: “Real-space calculation of powder diffraction patterns on graphics processing units”, Journal of Applied Crystallography 43:647-653, 2010. [DOI])

Abstract:

Data stream processing applications such as stock exchange data analysis, VoIP streaming, and sensor data processing pose two conflicting challenges: short per-stream latency — to satisfy the milliseconds-long, hard real-time constraints of each stream, and high throughput — to enable efficient processing of as many streams as possible. High-throughput programmable accelerators such as modern GPUs hold high potential to speed up the computations. However, their use for hard real-time stream processing is complicated by slow communications with CPUs, variable throughput changing non-linearly with the input size, and weak consistency of their local memory with respect to CPU accesses. Furthermore, their coarse grain hardware scheduler renders them unsuitable for unbalanced multi-stream workloads.

We present a general, efficient and practical algorithm for hard real-time stream scheduling in heterogeneous systems. The algorithm assigns incoming streams of different rates and deadlines to CPUs and accelerators. By employing novel stream schedulability criteria for accelerators, the algorithm finds the assignment which simultaneously satisfies the aggregate throughput requirements of all the streams and the deadline constraint of each stream alone.

Using the AES-CBC encryption kernel, we experimented extensively on thousands of streams with realistic rate and deadline distributions. Our framework outperformed the alternative methods by allowing 50% more streams to be processed with provably deadline-compliant execution even for deadlines as short as tens milliseconds. Overall, the combined GPU-CPU execution allows for up to 4-fold throughput increase over highly-optimized multi-threaded CPU-only implementations.

( Uri Verner, Assaf Schuster and Mark Silberstein, “Processing data streams with hard real-time constraints on heterogeneous systems”, ICS’11, to appear)

Read the rest of this entry »

Abstract:

In this paper, we present the design of Power Flow algorithm that has enhanced performance on the Graphics Processing Unit (GPU) using Compute Unified Device Architecture (CUDA). This work investigates the performance of optimized CPU versions of Newton-Raphson (Polar form) and Gauss-Jacobi power flow algorithms, highlights the approach used to reduce the computation time by performing these studies on massively parallel GPU cores. Simulations results demonstrate the significant acceleration of the GPU version compared to its CPU variant, thus reducing processing time making them suitable for real-time online dispatching purposes.

(Singh, J. and Aruni, I.: “Accelerating Power Flow studies on Graphics Processing Unit”, Proceedings of the Annual IEEE India Conference 2010 (INDICON), pp 1-5, Dec. 2010. [DOI])

Abstract:

We present a computational method of coupling average interpolating wavelets with high-order finite volume schemes and its implementation on heterogeneous computer architectures for the simulation of multiphase compressible flows. The method is implemented to take advantage of the parallel computing capabilities of emerging heterogeneous multicore/multi-GPU architectures. A highly efficient parallel implementation is achieved by introducing the concept of wavelet blocks, exploiting the task-based parallelism for CPU cores, and by managing asynchronously an array of GPUs by means of OpenCL. We investigate the comparative accuracy of the GPU and CPU based simulations and analyze their discrepancy for two-dimensional simulations of shock-bubble interaction and Richtmeyer–Meshkov instability. The results indicate that the accuracy of the GPU/CPU heterogeneous solver is competitive with the one that uses exclusively the CPU cores. We report the performance improvements by employing up to 12 cores and 6 GPUs compared to the single-core execution. For the simulation of the shock-bubble interaction at Mach 3 with two million grid points, we observe a 100-fold speedup for the heterogeneous part and an overall speedup of 34.

(Rossinelli D., Hejazialhosseini B., Spampinato D., Koumoutsakos P.: “Multicore/Multi-GPU Accelerated Simulations of Multiphase Compressible Flows Using Wavelet Adapted Grids”, SIAM Journal of Scientific Computing 33:512-540, 2011 [DOI])

Abstract:

The paper discusses a fast implementation of the conjugate gradient iterative method with E-field multilevel preconditioner applied to solving real symmetric and sparse systems obtained with vector finite element method. In order to accelerate computations, a graphics processing unit (GPU) was used and significant speed-up (2.61 fold) was achieved comparing to a central processing unit (CPU) based approach. These results indicate that performance of electromagnetic simulations can be significantly improved thereby enabling full wave optimization of microwave components in more manageable time.

(A. Dziekonski, A. Lamecki and M. Mrozowski: “GPU Acceleration of Multilevel Solvers for Analysis of Microwave Components With Finite Element Method”, IEEE Microwave and Wireless Components Letters 21(1) pp.1-3, Jan. 2011. [DOI])

Abstract:

Proteins, nucleic acids, and small molecules form a dense network of molecular interactions in a cell. The architecture of molecular networks can reveal important principles of cellular organization and function, similarly to the way that protein structure tells us about the function and organization of a protein. Protein complexes are groups of proteins that interact with each other at the same time and place, forming a single multimolecular machine. Functional modules, in contrast, consist of proteins that participate in a particular cellular process while binding each other at a different time and place.

A protein-protein interaction network is represented as proteins are nodes and interactions between proteins are edges. Protein complexes and functional modules can be identified as highly interconnected subgraphs and computational methods are now inevitable to detect them from protein interaction data. In addition, High-throughput screening techniques such as yeast two-hybrid screening enable identification of detailed protein-protein interactions map in multiple species. As the interaction dataset increases, the scale of interconnected protein networks increases exponentially so that the increasing complexity of network gives computational challenges to analyze the networks. Read the rest of this entry »

Abstract:

We examine the problem of segmenting foreground objects in live video when background scene textures change over time. In particular, we formulate background subtraction as minimizing a penalized instantaneous risk functional yielding a local on-line discriminative algorithm that can quickly adapt to temporal changes. We analyze the algorithms convergence, discuss its robustness to non-stationarity, and provide an efficient non-linear extension via sparse kernels. To accommodate interactions among neighboring pixels, a global algorithm is then derived that explicitly distinguishes objects versus background using maximum a posteriori inference in a Markov random field (implemented via graph-cuts). By exploiting the parallel nature of the proposed algorithms, we develop an implementation that can run efficiently on the highly parallel Graphics Processing Unit (GPU). Empirical studies on a wide variety of datasets demonstrate that the proposed approach achieves quality that is comparable to state-of-the-art off-line methods, while still being suitable for real-time video analysis (75 fps on a mid-range GPU).

(Li Cheng, M. Gong, D. Schuurmans, and T. Caelli: “Real-time Discriminative Background Subtraction”. IEEE Transactions on Image Processing, 2011, to appear. [DOI] [Sources & Info])

The Parallel Processing for Imaging Applications conference, part of IS&T/SPIE’s Electronic Imaging conference, was held on January 24–25 in San Francisco. The conference had a large number of GPU papers (SPIE digital library link):

• Using a commercial graphical processing unit and the CUDA programming language to accelerate scientific image processing applications by Broussard and Ives
• GPGPU real-time texture analysis framework by Akhloufi et al.
• A parallel implementation of 3D Zernike moment analysis by Berjón et al.
• Visualization assisted by parallel processing by Lange et al.
• GPU color space conversion by Chase and Vondran
• Acceleration of the Retinex algorithm for image restoration by GPGPU/CUDA by Wang and Huang
• Video transcoding using GPU accelerated decoder by Hsu
• Real-time image deconvolution on the GPU by Klosowski and Krishnan
• GPU-completeness: theory and implications by Lin
• A parallel error diffusion implementation on a GPU by Zhang et al.
• Evaluation of CPU and GPU architectures for spectral image analysis algorithms by Fresse et al.
• Real-time 3D flash ladar imaging through GPU data processing by Wong et al.
• Advanced MRI reconstruction toolbox with accelerating on GPU by Wu et al.
• Accelerating image recognition on mobile devices using GPGPU by López et al.
• A GPU accelerated PDF transparency engine by Recker et al.

Abstract:

We implemented a GPU based parallel code to perform Monte Carlo simulations of the two dimensional q-state Potts model. The algorithm is based on a checkerboard update scheme and assigns independent random number generators to each thread (one thread per spin). The implementation allows to simulate systems up to ~10^9 spins with an average time per spin flip of 0.147ns on the fastest GPU card tested, representing a speedup up to 155x, compared with an optimized serial code running on a standard CPU. The possibility of performing high speed simulations at large enough system sizes allowed us to provide a positive numerical evidence about the existence of metastability on very large systems based on Binder’s criterion, namely, on the existence or not of specific heat singularities at spinodal temperatures different of the transition one.

(Ezequiel E. Ferrero, Juan Pablo De Francesco, Nicolás Wolovick and Sergio A. Cannas: “q-state Potts model metastability study using optimized GPU-based Monte Carlo algorithms”. [arXiv:1101.0876] [code and additional information])

Abstract:

Although trivial background subtraction (BGS) algorithms (e.g. frame differencing, running average…) can perform quite fast, they are not robust enough to be used in various computer vision problems. Some complex algorithms usually give better results, but are too slow to be applied to real-time systems. We propose an improved version of the Extended Gaussian mixture model that utilizes the computational power of Graphics Processing Units (GPUs) to achieve real-time performance. Experiments show that our implementation running on a low-end GeForce 9600GT GPU provides at least 10x speedup. The frame rate is greater than 50 frames per second (fps) for most of the tests, even on HD video formats.

(Vu Pham, Phong Vo, Vu Thanh Hung and Le Hoai Bac: “GPU Implementation of Extended Gaussian Mixture Model for Background Subtraction”. IEEE International Conference on Computing and Communication Technologies, Research, Innovation, and Vision for the Future (RIVF), 2010. [DOI] [code and additional information])