An option is a financial instrument which derives its value from an underlying asset. There are a wide range of options traded today. Some are simple and plain, like the European options, while others are very difficult to evaluate. Both buyers and sellers continue to look for efficient algorithms and faster technology to price options for profit. In this thesis, I will first map the PSO parameters to the parameters in the option pricing problem. Then, I extend this to study pricing of complex chooser option. Further, I design a parallel algorithm that avails of the inherent concurrency in PSO while searching for a optimum solution. For implementation of my algorithm I used graphics processor unit (GPU). Analyzing the characteristics of PSO and option pricing, I propose a strategy to normalize some of the PSO parameters that helps in better understanding the sensitivity of various parameters on option pricing results.

This thesis focuses on improving the user experience for computer vision-based Augmented Reality (AR) applications on smartphones. The first part shows our proposed methods to enhance image binarisation. This improves the marker detection results in mobile AR applications. The comparisons of the original ARToolKit binarization method, our proposed histogram-based automatic thresholding and our histogram equalization based thresholding show that the histogram-based automatic thresholding produces a relatively better result under extreme and normal lighting conditions but slightly reduces the ARToolKit framerate. The second part introduces a new fast painterly rendering algorithm which produces an immersive experience for mobile AR users. The proposed algorithm has low complexity and achieves a real-time performance on smartphones. In addition, this study has carried out a preliminary experiment comparing mobile GPU-based image processing algorithms with CPU-based equivalent on smartphones. The result indicates that the GPU-based implementations perform better than the CPU when processing relatively large sized images.

This thesis describes two new techniques for enhancing the rendering quality of cartoon characters in toon-shading applications. The proposed methods can be used to improve the output quality of current cel shaders. The first technique which uses 2D image-based algorithms, enhances the silhouettes of the input geometry and reduces the computer generated artefacts. The silhouettes are found by using the Sobel filter and reconstructed by Bezier curve fitting. The intensity of the reconstructed silhouettes is then modified to create a stylised appearance. In the second technique, a new hair model based on billboarded particles is introduced. This method is found to be particularly useful for generating toon-like specular highlights for hair, which are important in cartoon animations. The whole rendering framework is implemented in C++ using the OpenGL API. OpenGL extensions and GPU programming are used to take the advantage of the functionalities of currently available graphics hardware. The programming of graphics hardware is done using Cg, a high level shader language.

This thesis presents the application of graphics processing unit (GPU) based parallel computing technique to speed up electromagnetic transients (EMT) simulation of large power systems. GPUs support extra computing capability to handle gaming and animation related applications in the desktop computers. GPUs can be used for general-purpose computations, such as EMT simulation. Traditionally, EMT simulation tools are implemented on the CPUs, where simulation is performed in a sequential manner. Hence, with the increase in network size, there is a drastic increase in simulation times. This research shows that the use of GPU computing considerably reduces the total simulation time. This thesis proposes parallelized algorithm for EMT simulations on the GPU, and demonstrates the algorithm by simulating large power systems. Total computation times for GPU computing, using 'compute unified device architecture' (CUDA)-based C programming are compared with the total computation times for the sequential implementations on the CPU using ANSI-C programming for systems of various sizes and types. Special parallel processing techniques are implemented to model various power system components such as transmission lines, generators, etc. An advanced technique to implement parallel matrix-vector multiplication on the GPU is implemented, which shows a significant performance gain in the simulation. A sparsity-based technique for the inverse admittance matrix is implemented in this simulation process to ignore the multiplications involving zeros. A typical power electronic subsystem is also implemented in this simulation process, which had not been implemented in the literature so far for the GPU platforms. GPU computing-based simulation of large power networks with many power electronic subsystems has shown a massive performance gain compared to conventional sequential simulations with and without the sparsity technique. Finally, in this research work, the effect of granularity on the speedup of simulation was investigated. Granularity is defined as the ratio of the number of transmission lines used to interconnect various subsystems to the total size of the network. It should be noted that dividing a network into smaller subsystems requires additional transmission lines. Simulation results show that there is a negative impact on the overall performance gain of simulation with the use of excessive transmission lines in the test systems.

This thesis describes a new approach to accelerate the simulation of the steady-state response of nonlinear circuits using the Harmonic Balance (HB) technique. The approach presented in this work focuses on direct factorization of the sparse Jacobian matrix of the HB nonlinear equations using a Graphics Processing Unit (GPU) platform. This approach exploits the heterogeneous structure of the Jacobian matrix. The computational core of the proposed approach is based on developing a block-wise version of the KLU factorization algorithm, where scalar arithmetic operations are replaced by block-aware matrix operations. For a large number of harmonics, or excitation tones, or both the Block-KLU (BKLU) approach effectively raises the ratio of floating-point operations to other operations and, therefore, becomes an ideal vehicle for implementation on a GPU-based platform. Motivated by this fact, a GPU-based Hybrid Block KLU framework is developed to implement the BKLU. The proposed approach in this thesis is named Hybrid-BKLU. The Hybrid-BKLU is implemented in two parts, on the host CPU and on the graphic card’s GPU, using the OpenCL heterogeneous parallel programming language. To show the efficiency of the Hybrid-BKLU approach, its performance is compared with BKLU approach performing HB analysis on several test circuits. The Hybrid-BKLU approach yields speedup by up to 89 times over conventional BKLU on CPU.

An option is a financial instrument which derives its value from an underlying asset. There are a wide range of options traded today. Some are simple and plain, like the European options, while others are very difficult to evaluate. Both buyers and sellers continue to look for efficient algorithms and faster technology to price options for profit. In this thesis, I will first map the PSO parameters to the parameters in the option pricing problem. Then, I extend this to study pricing of complex chooser option. Further, I design a parallel algorithm that avails of the inherent concurrency in PSO while searching for a optimum solution. For implementation of my algorithm I used graphics processor unit (GPU). Analyzing the characteristics of PSO and option pricing, I propose a strategy to normalize some of the PSO parameters that helps in better understanding the sensitivity of various parameters on option pricing results.

Artists have been using brush strokes to generate abstractions and interpretations of the world they view, however this process is very time consuming. Many recent and diverse techniques attempt to mimic the process on a computer that an artist would go through to generate a painting; an area of research is a ectionately nick-named "painterly rendering". These applications emulate the effects of an artist's handiwork with dramatically less time invested in the process. I present a method to adapt painterly rendering for real-time simulations or video games, such that the images may appear to have been painted by hand. The work described in this document focuses on three problem areas posed for a real-time solution for painterly-rendering: brush stroke generation, temporal coherence between frames and performance. The solution presented here intends to solve these three fundamental issues with the intent to layer these methods on top of real-time applications using current generation consumer hardware. / Graduate

In this thesis we have presented an implementation of soft Multi Input Multi Output (MIMO) detection, single tree search algorithm on Graphics Processing Units (GPUs). We have compared its performance on different GPUs and a Central Processing Unit (CPU). We have also done a performance study of iterative decoding algorithms. We have shown that by increasing the number of outer iterations error rate performance can be further improved. GPUs are specialized devices specially designed to accelerate graphics processing. They are massively parallel devices which can run thousands of threads simultaneously. Because of their tremendous processing power there is an increasing interest in using them for scientific and general purpose computations. Hence companies like Nvidia, Advanced Micro Devices (AMD) etc. have started their support for General Purpose GPU (GPGPU) applications. Nvidia came up with Compute Unified Device Architecture (CUDA) to program its GPUs. Efforts are made to come up with a standard language for parallel computing that can be used across platforms. OpenCL is the first such language which is supported by all major GPU and CPU vendors. MIMO detector has a high computational complexity. We have implemented a soft MIMO detector on GPUs and studied its throughput and latency performance. We have shown that a GPU can give throughput of up to 4Mbps for a soft detection algorithm which is more than sufficient for most general purpose tasks like voice communication etc. Compare to CPU a throughput increase of ~7x is achieved. We also compared the performances of two GPUs one with low computational power and one with high computational power. These comparisons show effect of thread serialization on algorithms with the lower end GPU's execution time curve shows a slope of 1/2. To further improve error rate performance iterative decoding techniques are employed where a feedback path is employed between detector and decoder. With an eye towards GPU implementation we have explored these algorithms. Better error rate performance however, comes at a price of higher power dissipation and more latency. By simulations we have shown that one can predict based on the Signal to Noise Ratio (SNR) values how many iterations need to be done before getting an acceptable Bit Error Rate (BER) and Frame Error Rate (FER) performance. Iterative decoding technique shows that a SNR gain of ~1:5dB is achieved when number of outer iterations is increased from zero. To reduce the complexity one can adjust number of possible candidates the algorithm can generate. We showed that where a candidate list of 128 is not sufficient for acceptable error rate performance for a 4x4 MIMO system using 16-QAM modulation scheme, performances are comparable with the list size of 512 and 1024 respectively.

<p>Detta examensarbete undersöker en befintilig teknik för att simulera rök med ett partikelsystem. Tekniken utvecklas och implementeras så att beräkningar av partiklars nya positioner sker på både en CPU och en GPU. Arbetet gör undersökningar baserat på tidseffektivitet och visar att simulering av röken sker snabbare, när beräkningarna av partiklars nya positioner görs på GPU’n, istället för CPU’n.</p>

En Computación Gráfica uno de los conceptos más importantes es el \emph{Rendering}, definido como el proceso que a partir de los datos de una escena tridimensional genera una imagen en una ventana de visualización en 2 dimensiones. El rendering siempre se ha enfocado en generar imágenes fotorrealistas, aunque para diversas aplicaciones y escenarios se desea una imagen abstracta y/o estilizada. El proceso que puede generar ese tipo de imágenes es llamado Rendering No Fotorrealista, o NPR por sus siglas en inglés (Non Photorealistic Rendering). El NPR integra conceptos de Computación Gráfica y de Geometría Diferencial, y puede aplicarse en visualización científica e ilustración técnica, con el fin de destacar áreas o contornos de los objetos que son de interés para el observador; en la producción de imágenes que imiten medios tradicionales como la pintura o la acuarela; y en la generación de imágenes que imiten dibujos animados, entre otras áreas. En esta memoria se diseña e implementa un marco de trabajo (framework en inglés) para Computación Gráfica que permite desarrollar técnicas NPR y de rendering tradicional. El diseño del marco de trabajo contempla el estudio de los puntos comunes de diferentes técnicas de NPR y de las áreas asociadas, y, siguiendo el paradigma de la Orientación a Objetos, define distintas componentes internas que pueden ser extendidas para implementar técnicas de NPR y de rendering tradicional. La implementación se realiza en el lenguaje de programación C++ utilizando bibliotecas de código abierto o compatibles con código abierto: se utilizan la biblioteca gráfica OpenGL y el lenguaje Cg para comunicarse con los procesadores de la tarjeta de vídeo (GPU). El marco de trabajo incluye técnicas ya implementadas: para el rendering tradicional se implementaron graficadores de Gouraud y de Phong, mientras que para las técnicas NPR se implementaron graficadores de dibujado animado (Cel-Shading) y de modelos de tonos (Gooch Shading). Se implementaron extractores de líneas de interés (Siluetas y Contornos Sugestivos), así como una clase abstracta que permite definir nuevos tipos de líneas a extraer. La demostración de estas implementaciones se realiza mediante una aplicación de prueba que permite cargar modelos tridimensionales estáticos y animados; los resultados obtenidos se muestran mediante imágenes de los modelos tridimensionales cargados en la aplicación de prueba. Finalmente se realiza una discusión sobre el trabajo futuro, sobre las posibles líneas de investigación a seguir en estudios de post-grado y sobre el uso del marco de trabajo para implementar técnicas de rendering no NPR. Se concluye que el marco de trabajo se puede utilizar para el desarrollo de técnicas NPR y de rendering tradicional, que su desempeño es adecuado para el rendering en tiempo real para escenas tridimensionales de tamaño medio y que puede ser utilizado en aplicaciones reales.