This thesis investigates the feasibility of using fluid flow as a deformable model for segmenting vessels in 2D and 3D medical images. Exploiting fluid flow in vessel segmentation is biologically plausible since vessels naturally provide the medium for blood transportation. Fluid flow can be used as a basis for powerful vessel segmentation because streaming fluid regions can merge and split providing topological adaptivity. In addition, the fluid can also flow through small gaps formed by imaging artifacts building connections between disconnected areas. In our study, due to their simplicity, parallelism, and low computational cost compared to other fluid simulation methods, linearized shallow water equations (LSWE) are used. The method developed herein is validated using synthetic data sets, two clinical datasets, and publicly available simulated datasets which contain Magnetic Resonance Angiography (MRA) images, Magnetic Resonance Venography (MRV) images and retinal angiography images. Depending on image size, one to two order of magnitude speed ups are obtained with developed parallel implementation using Nvidia Compute Unified Device Architecture (CUDA) compared to single-core and multicore CPU implementation.

The emergence of heterogeneous and many-core architectures presents a unique opportunity to deliver order of magnitude performance increases to high performance applications by matching certain classes of algorithms to specifically tailored architectures. However, their ubiquitous adoption has been limited by a lack of programming models and management frameworks designed to reduce the high degree of complexity of software development inherent to heterogeneous architectures. This dissertation introduces Harmony, an execution model for heterogeneous systems that draws heavily from concepts and optimizations used in processor micro-architecture to provide: (1) semantics for simplifying heterogeneity management, (2) dynamic scheduling of compute intensive kernels to heterogeneous processor resources, and (3) online monitoring driven performance optimization for heterogeneous many core systems. This work focuses on simplifying development and ensuring binary portability and scalability across system configurations and sizes.

The FPGA GPU architecture proposed in this thesis was motivated by underserved markets for graphics processing that desire flexibility, long-term device availability, scalability, certifiability, and high reliability. These markets of industrial, medical, and avionics applications often are forced to rely on the latest GPUs that were actually designed for gaming PCs or handheld consumer devices. The architecture for the GPU in this thesis was crafted specifically for an FPGA and therefore takes advantage of its capabilities while also avoiding its limitations. Previous work did not specifically exploit the FPGA's structures and instead used FPGA implementations merely as an integration platform prior to proceeding on to a final ASIC design. The target of an FPGA for this architecture is also important because its flexibility and programmability allow the GPU's performance to be scaled or supplemented to fit unique application requirements. This tailoring of the architecture to specific requirements minimizes power consumption and device cost while still satisfying performance, certification, and device availability requirements. To demonstrate the feasibility of the flexible FPGA GPU architectural concepts, the architecture is applied to an avionics application and analyzed to confirm satisfactory results. The architecture is further validated through the development of extensions to support more comprehensive graphics processing applications. In addition, the breadth of this research is illustrated through its applicability to general-purpose computations and more specifically, scientific visualizations.

<p>Shape-Based matching (SBM) is a known method for 2D object recognition that is rather robust against illumination variations, noise, clutter and partial occlusion.</p><p>The objects to be recognized can be translated, rotated and scaled.</p><p>The translation of an object is determined by evaluating a similarity measure for all possible positions (similar to cross correlation).</p><p>The similarity measure is based on dot products between normalized gradient directions in edges.</p><p>Rotation and scale is determined by evaluating all possible combinations, spanning a huge search space.</p><p>A resolution pyramid is used to form a heuristic for the search that then gains real-time performance.</p><p>For SBM, a model consisting of normalized edge gradient directions, are constructed for all possible combinations of rotation and scale.</p><p>We have avoided this by using (bilinear) interpolation in the search gradient map, which greatly reduces the amount of storage required.</p><p>SBM is highly parallelizable by nature and with our suggested improvements it becomes much suited for running on a GPU.</p><p>This have been implemented and tested, and the results clearly outperform those of our reference CPU implementation (with magnitudes of hundreds).</p><p>It is also very scalable and easily benefits from future devices without effort.</p><p>An extensive evaluation material and tools for evaluating object recognition algorithms have been developed and the implementation is evaluated and compared to two commercial 2D object recognition solutions.</p><p>The results show that the method is very powerful when dealing with the distortions listed above and competes well with its opponents.</p>

The understanding of molecular effects in nanoscale environments is becoming increasingly relevant for various emerging fields. These include spectroscopy for molecular identification as well as in finding molecules for energy harvesting. Theoretical quantum chemistry has been increasingly useful to address these phenomena to yield an understanding of these effects. In the first part of this dissertation, we study the chemical effect of surface-enhanced Raman scattering (SERS). We use quantum chemistry simulations to study the metal-molecule interactions present in these systems. We find that the excitations that provide a chemical enhancement contain a mixed contribution from the metal and the molecule. Moreover, using atomistic studies we propose an additional source of enhancement, where a transition metal dopant surface could provide an additional enhancement. We also develop methods to study the electrostatic effects of molecules in metallic environments. We study the importance of image-charge effects, as well as field-bias to molecules interacting with perfect conductors. The atomistic modeling and the electrostatic approximation enable us to study the effects of the metal interacting with the molecule in a complementary fashion, which provides a better understanding of the complex effects present in SERS. In the second part of this dissertation, we present the Harvard Clean Energy project, a high-throughput approach for a large-scale computational screening and design of organic photovoltaic materials. We create molecular libraries to search for candidates structures and use quantum chemistry, machine learning and cheminformatics methods to characterize these systems and find structure-property relations. The scale of this study requires an equally large computational resource. We rely on distributed volunteer computing to obtain these properties. In the third part of this dissertation we present our work related to the acceleration of electronic structure methods using graphics processing units. This hardware represents a change of paradigm with respect to the typical CPU device architectures. We accelerate the resolution-of-the-identity Moller-Plesset second-order perturbation theory algorithm using graphics cards. We also provide detailed tools to address memory and single-precision issues that these cards often present.

An assembled algorithm for pricing American options with absolute, discrete dividends using adaptive lattice methods is described. Considerations for hardware-conscious programming on both CPU and GPU platforms are discussed, to provide a foundation for the investigation of several approaches for deploying the program onto GPU architectures. The performance results of the approaches are compared to that of a central processing unit reference implementation, and to each other. In particular, an approach of designating subtrees to be calculated in parallel by allowing multiple calculation of overlapping elements is described. Among the examined methods, this attains the best performance results in a "realistic" region of calculation parameters. A fifteen- to thirty-fold improvement in performance over the CPU reference implementation is observed as the problem size grows sufficiently large.

This work is dedicated to the theoretical and numerical study of nonlinear phononic crystals. The studied nonlinearities are those due to the second (quadratic) and third (cubic) order elastic constants of the materials that constitute the crystals. Nonlinear effects are studied by the means of finite element methods, used to simulate the propagation of an elastic wave through the crystals. A first research project concerns the study of a bone structure, namely the dispersion of elastic waves in a structure composed of collagen and hydroxy apatite alternate constituent layers. Simulations showed that it exists a strong link between bones hydration and their ability to dissipate the energy. The second study relates to an elastic resonator. A structure composed of steel inclusions in a silica matrix shows a switch behavior when the cubic nonlinearities of steel are taken into account. This strong nonlinear effect appears when the amplitude of the incident wave reaches a threshold. A full analytical model is provided. The last study demonstrates the design of composite materials with both strong cubic nonlinearities and weak quadratic nonlinearities. The derivation of the mixing laws of the elastic parameters of a nonlinear material inside a linear one is performed up to order three. Equations show a strong amplification of the nonlinear parameters of the material for some concentrations. Numerical simulations allow to conclude that the above mentioned resonator can be produced. For this thesis, an innovative tool based on the Discontinuous Galerkin (DG) finite element method is developed for the simulation of elastic wave propagation, in linear and nonlinear systems and in finite and semi-infinite media. The implementation of this DG code for 2D and 3D simulations benefits from the efficient exploitation of modern computer infrastructure (GPU units, clusters) using the property of massive parallelization of DG algorithms. This thesis is part of a joint agreement for an international Ph.D. degree between École Centrale de Lille and the Materials Science and Engineering department of the University of Arizona at Tucson. Ce travail porte sur l'étude théorique et numérique des cristaux phononiques non-linéaires. Les non-linéarités étudiées sont celles dues aux constantes élastiques d'ordre deux (quadratiques) et trois (cubiques) des matériaux constituant les cristaux. Les effets non-linéaires sont étudiés grâce á des méthodes d'éléments finis en simulant la propagation d'une onde élastique á travers les cristaux. Un premier projet de recherche a porté sur l'étude d'une structure osseuse, et plus spécifiquement sur la dispersion des ondes élastiques dans une structure constituée d'une alternance de couches de collagène et d'hydroxy apatite. Les simulations montrent qu'il existe un lien étroit entre l'hydratation des os et leur capacité à dissiper l'énergie. La seconde étude réalisée concerne un résonateur élastique. Une structure constituée d'inclusions d'acier dans de la silice présente un comportement de commutateur (switch) lorsque les non-linéarités cubiques de l'acier sont prises en compte. Cet effet fortement non-linéaire apparaît lorsque l'amplitude de l'onde incidente dépasse un certain seuil. Un modèle analytique complet est fourni. La dernière étude réalisée montre la conception de matériaux composites possédant de fortes non-linéarités cubiques mais de faibles non-linéarités quadratiques. La dérivation des lois de mélange des paramètres élastiques d'un matériau non-linéaire dans un matériau linéaire est effectuée à l'ordre trois. Les équations montrent une forte amplification des paramètres non-linéaires du matériau résultant pour certaines concentrations. Les simulations permettent de conclure que le résonateur mentionné ci-dessus peut effectivement étre réalisé. Pour cette thèse, un outil numérique innovant basé sur la méthode des éléments finis de type Galerkin Discontinu (DG) est développé pour la simulation de la propagation d'ondes élastiques, dans des systèmes linéaires et non-linéaires et dans des milieux finis et semi-infinis. L'implémentation de ce code DG pour des simulations 2D et 3D tire parti des infrastructures de calcul actuelles (processeurs graphiques, clusters) grâce à la propriété de parallélisation massive des algorithmes DG. Cette thèse s'est déroulée dans le cadre d'une cotutelle entre l'École Centrale de Lille et le département de Science et ingénierie des matériaux de l'Université d'Arizona, à Tucson.

Challenging science requirements and complex space missions are driving the need for fast and robust space trajectory design and simulation tools. The main aim of this thesis is to develop new and improved high performance algorithms and solution techniques for commonly encountered problems in astrodynamics. Five major problems are considered and their state-of-the art algorithms are systematically improved. Theoretical and methodological improvements are combined with modern computational techniques, resulting in increased algorithm robustness and faster runtime performance. The five selected problems are 1) Multiple revolution Lambert problem, 2) High-fidelity geopotential (gravity field) computation, 3) Ephemeris computation, 4) Fast and accurate sensitivity computation, and 5) High-fidelity multiple spacecraft simulation. The work being presented enjoys applications in a variety of fields like preliminary mission design, high-fidelity trajectory simulation, orbit estimation and numerical optimization. Other fields like space and environmental science to chemical and electrical engineering also stand to benefit.

Susidūrimų paieška - tai dviejų ar daugiau objektų susikirtimo radimas. Praktikoje susidūrimų paieška taikoma šiose srityse: kompiuteriniuose žaidimuose, netiesinėje baigtinių elementų analizėje, dalelių hidrodinamikoje, daugiafunkcinės dinamikos analizėje, įvairiose fizikos simuliacijose ir kt. Egzistuoja daugybė susidūrimų paieškos algoritmų, iš kurių populiariausi yra erdvinio skaidymo, hierarchinio struktūrizavimo ir atrinkimo bei rūšiavimo metodai. Šiame darbe yra tiriamas šių algoritmų veikimas ant CPU (Central processing unit) ir ant GPU (Graphics processing unit), analizuojami susidūrimų paieškos nustatymo būdai bei nagrinėjamos pasirinktų algoritmų veikimo spartinimo galimybės panaudojant CUDA (Compute Unified Device Architecture) technologiją. Ši technologija yra Nvidia sukurta nauja duomenų apdorojimo architektūra išnaudojanti grafinio procesoriaus resursus bendro pobūdžio skaičiavimams. Darbe iškeltų tikslų pasiekimui yra realizuotos kelios bazinės algoritmų versijos, jų pritaikymo lygiagretiems skaičiavimams galimybės ir taip pat atliekami bazinių algoritmų laiko, reikalingo skaičiavimams atlikti, grafinio procesoriaus atminties sąnaudos bei įvairių veikimo laiką įtakojančių faktorių tyrimai. Darbo pabaigoje aptariami lygiagretaus programavimo privalumai pritaikant nagrinėjamai temai. Šiame darbe atlikti tyrimai parodė, jog perduodant skaičiavimus į GPU pasiekiamas 200 kartų didesnis nagrinėjamų algoritmų našumas negu atliekant skaičiavimus naudojant CPU. / Collision detection is a well-studied and active research field where the main problem is to determine if one or more objects collide with each other in 3D virtual space. Collision detection is an issue affecting many different fields of study, including computer animation, physical-based simulation, robotics, video games and haptic applications. There is a big variety of collision detection algorithms of witch spatial subdivision, octree and sort and sweep are three of them. In this document we provide a short summary of collision detection algorithms, but the main focus will be on analyzing and increasing their performance working on CPU (orig. Central processing unit) and GPU (orig. Graphics processing unit) separately by making use of CUDA (orig.Compute Unified Device Architecture) technology. This technology is a part of Nvidia, witch helps the use of graphics processor for general-purpose computation. Main goal of this research is achieved by performing analysis of implemented spatial subdivision, octree and sort and sweep algorithms. This analysis consists of both general performance, parallelization performance and various performance affecting factors analyses. At the end of the document, the advantages of parallel programming adapted to the present subject are discussed.

Dans ce travail, méthodes d'estimation basées sur des images, également connu sous le nom de méthodes directes, sont étudiées qui permettent d'éviter l'extraction de caractéristiques et l'appariement complètement. L'objectif est de produire pose 3D précis et des estimations de la structure. Les fonctions de coût présenté minimiser l'erreur du capteur, car les mesures ne sont pas transformés ou modifiés. Dans la caméra photométrique estimation de la pose, rotation 3D et les paramètres de traduction sont estimées en minimisant une séquence de fonctions de coûts à base d'image, qui sont des non-linéaires en raison de la perspective projection et la distorsion de l'objectif. Dans l'image la structure basée sur le raffinement, d'autre part, de la structure 3D est affinée en utilisant un certain nombre de vues supplémentaires et un coût basé sur l'image métrique. Les principaux domaines d'application dans ce travail sont des reconstitutions d'intérieur, la robotique et la réalité augmentée. L'objectif global du projet est d'améliorer l'image des méthodes d'estimation fondées, et pour produire des méthodes de calcul efficaces qui peuvent être accueillis dans des applications réelles. Les principales questions pour ce travail sont : Qu'est-ce qu'une formulation efficace pour une image 3D basé estimation de la pose et de la structure tâche de raffinement ? Comment organiser calcul afin de permettre une mise en œuvre efficace en temps réel ? Quelles sont les considérations pratiques utilisant l'image des méthodes d'estimation basées sur des applications telles que la réalité augmentée et la reconstruction 3D ?