High-level parallel programming approaches, such as OpenACC, have recently become popular in complex fluid dynamics research since they are cross-platform and easy to implement. OpenACC is a directive-based programming model that, unlike low-level programming models, abstracts the details of implementation on the GPU. Although OpenACC generally limits the performance of the GPU, this model significantly reduces the work required to port an existing code to any accelerator platform, including GPUs. The purpose of this research is twofold: to investigate the effectiveness of OpenACC in developing a portable and maintainable GPU-accelerated code, and to determine the capability of OpenACC to accelerate large, complex programs on the GPU. In both of these studies, the OpenACC implementation is optimized and extended to a multi-GPU implementation while maintaining a unified code base. OpenACC is shown as a viable option for GPU computing with CFD problems. In the first study, a CFD code that solves incompressible cavity flows is accelerated using OpenACC. Overlapping communication with computation improves performance for the multi-GPU implementation by up to 21%, achieving up to 400 times faster performance than a single CPU and 99% weak scalability efficiency with 32 GPUs. The second study ports the execution of a more complex CFD research code to the GPU using OpenACC. Challenges using OpenACC with modern Fortran are discussed. Three test cases are used to evaluate performance and scalability. The multi-GPU performance using 27 GPUs is up to 100 times faster than a single CPU and maintains a weak scalability efficiency of 95%. / Master of Science / The research and analysis performed in scientific computing today produces an ever-increasing demand for faster and more energy efficient performance. Parallel computing with supercomputers that use many central processing units (CPUs) is the current standard for satisfying these demands. The use of graphics processing units (GPUs) for scientific computing applications is an emerging technology that has gained a lot of popularity in the past decade. A single GPU can distribute the computations required by a program over thousands of processing units. This research investigates the effectiveness of a relatively new standard, called OpenACC, for offloading execution of a program to the GPU. The most widely used standards today are highly complex and require low-level, detailed knowledge of the GPU’s architecture. These issues significantly reduce the maintainability and portability of a program. OpenACC does not require rewriting a program for the GPU. Instead, the developer annotates regions of code to run on the GPU and only has to denote high-level information about how to parallelize the code. The results of this research found that even for a complex program that models air flows, using OpenACC to run the program on 27 GPUs increases performance by a factor of 100 over a single CPU and by a factor of 4 over 27 CPUs. Although higher performance is expected with other GPU programming standards, these results were accomplished with minimal change to the original program. Therefore, these results demonstrate the ability of OpenACC to improve performance while keeping the program maintainable and portable.

Air Quality Models are defined for prediction and simulation of air pollutant concentrations over a certain period of time. The predictions can be used in setting limits for the emission levels of industrial facilities. The input data for the air quality models are very large and encompass various environmental conditions like wind speed, turbulence, temperature and cloud density. Most air quality models are based on advection-diffusion equations. These differential equations are moderately stiff and require appropriate techniques for fast integration over large intervals of time. Implicit time stepping techniques for solving differential equations being unconditionally stable are considered suitable for the solution. However, implicit time stepping techniques impose certain data dependencies that can cause the parallelization of air quality models to be inefficient. The current approach uses Runge Kutta Chebyshev explicit method for solution of advection diffusion equations. It is found that even if the explicit method used is computationally more expensive in the serial execution, it takes lesser execution time when parallelized because of less complicated data dependencies presented by the explicit time-stepping. The implicit time-stepping on the other hand cannot be parallelized efficiently because of the inherent complicated data dependencies. / Master of Science

Proper Orthogonal Decomposition (POD), combined with the Method of Snapshots and Galerkin projection, is a popular method for the model order reduction of nonlinear PDEs. The POD requires the left singular vectors from the singular value decomposition (SVD) of an n-by-m "snapshot matrix" S, each column of which represents the computed state of the system at a given time. However, the direct computation of this decomposition can be computationally expensive, particularly for snapshot matrices that are too large to fit in memory. Hierarchical Approximate POD (HAPOD) (Himpe 2016) is a recent method for the approximate truncated SVD that requires only a single pass over S, is easily parallelizable, and can be computationally cheaper than direct SVD, all while guaranteeing the requested accuracy for the resulting basis. This method processes the columns of S in blocks based on a predefined rooted tree of processors, concatenating the outputs from each stage to form the inputs for the next. However, depending on the selected parameter values and the properties of S, the performance of HAPOD may be no better than that of direct SVD. In this work, we numerically explore the parameter values and snapshot matrix properties for which HAPOD is computationally advantageous over the full SVD and compare its performance to that of a parallelized incremental SVD method (Brand 2002, Brand 2003, and Arrighi2015). In particular, in addition to the two major processor tree structures detailed in the initial publication of HAPOD (Himpe2016), we explore the viability of a new structure designed with an MPI implementation in mind. / Master of Science / Singular Value Decomposition (SVD) provides a way to represent numeric data that breaks the data up into its most important components, as well as measuring how significant each part is. This decomposition is widely used to assist in finding patterns in data and making decisions accordingly, or to obtain simple, yet accurate, representations of complex physical processes. Examples of useful data to decompose include the velocity of water flowing past an obstacle in a river, a large collection of images, or user ratings for a large number of movies. However, computing the SVD directly can be computationally expensive, and usually requires repeated access to the entire dataset. As these data sets can be very large, up to hundreds of gigabytes or even several terabytes, storing all of the data in memory at once may be infeasible. Thus, repeated access to the entire dataset requires that the files be read repeatedly from the hard disk, which can make the required computations exceptionally slow. Fortunately, for many applications, only the most important parts of the data are needed, and the rest can be discarded. As a result, several methods have surfaced that can pick out the most important parts of the data while accessing the original data only once, piece by piece, and can be much faster than computing the SVD directly. In addition, the recent bottleneck in individual computer processor speeds has motivated a need for methods that can efficiently run on a large number of processors in parallel. Hierarchical Approximate POD (HAPOD) [1] is a recently-developed method that can efficiently pick out the most important parts of the data while only accessing the original data once, and which is very easy to run in parallel. However, depending on a user-defined algorithm parameter (weight), HAPOD may return more information than is needed to satisfy the requested accuracy, which determines how much data can be discarded. It turns out that the input weights that result in less extra data also result in slower computations and the eventual need for more data to be stored in memory at once. This thesis explores how to choose this input weight to best balance the amount of extra information used with the speed of the method, and also explores how the properties of the data, such as the size of the data or the distribution of levels of significance of each part, impact the effectiveness of HAPOD.

The chemical master equation, formulated on the Markov assumption of underlying chemical kinetics, offers an accurate stochastic description of general chemical reaction systems on the mesoscopic scale. The chemical master equation is especially useful when formulating mathematical models of gene regulatory networks and protein-protein interaction networks, where the numbers of molecules of most species are around tens or hundreds. However, solving the master equation directly suffers from the so called "curse of dimensionality" issue. This thesis first tries to study the numerical properties of the master equation using existing numerical methods and parallel machines. Next, approximation algorithms, namely the adaptive aggregation method and the radial basis function collocation method, are proposed as new paths to resolve the "curse of dimensionality". Several numerical results are presented to illustrate the promises and potential problems of these new algorithms. Comparisons with other numerical methods like Monte Carlo methods are also included. Development and analysis of the linear Shepard algorithm and its variants, all of which could be used for high dimensional scattered data interpolation problems, are also included here, as a candidate to help solve the master equation by building surrogate models in high dimensions. / Ph. D.

Mathematical models describing the Q-switched laser generation, which is a widely used laser technique for producing short intense pulses of light, belong to the class of semi-nonlinear models where only source terms nonlinearly depend on the solution. Numerical methods for solution of systems of semi-nonlinear partial differential equations have been extensively studied in many papers. Schrödinger-type equations, parabolic-type equations or general diffusion-reaction models arise in nonlinear optics. Such differential problems are solved mainly by finite-difference and Galerkin methods. The convergence analysis is based on the stability analysis of the linearized problems. The construction and theoretical analysis of discrete schemes for one-dimensional problem give a basis for a numerical solution of more general two-dimensional and three-dimensional problems where a diffraction process is taken into account. The two-dimensional problem simulates the dynamics of high-power semiconductor lasers. To solve the problems simulating propagation of photon fluxes in the nonlinear disperse medium, the finite-difference time-domain method is used. However, the major drawback of this method is that the computational domain must be sufficiently large. In order to restrict the computational domain and to solve the problem only in the region of interest, special artificial boundary conditions are investigated. The three-dimensional problem simulates an interaction of counter propagating... [to full text] / Disertacijoje nagrinėjami kai kurių lazerių fizikos ir netiesinės optikos uždavinių skaitinės analizės metodai. Tiriami trys pagrindiniai atvejai: bėgančias plokščias bangas aprašantis vienmatis, bėgančias difraguojančias bangas nagrinėjantis dvimatis ir lazerio pluoštų sąveiką netiesinėje Kero terpėje modeliuojantis trimatis modeliai. Šiuos uždavinius sieja pernešimo diferencialinės lygtys dalinėmis išvestinėmis, aprašančios į priešingas puses sklindančias lazerio bangas. Dvimačiame ir trimačiame uždaviniuose sprendžiamos dalinių išvestinių Šrėdingerio (ang. Schrödinger) tipo diferencialinės lygtys. Šiems matematiniams modeliams sudarytos baigtinių skirtumų schemos, atlikta jų analizė ir pagrindimas. Skaitinių eksperimentų realizacijai sukurti lygiagretieji algoritmai, jie yra būtini atliekant didelių resursų reikalaujančius skaičiavimus. Disertaciją sudaro įvadas, keturi skyriai, rezultatų apibendrinimas, naudotos literatūros ir autoriaus publikacijų disertacijos tema sarašai. Įvadiniame skyriuje aptariama tiriamoji problema, darbo aktualumas, aprašomas tyrimų objektas, formuluojamas darbo tikslas bei uždaviniai, aprašoma tyrimų metodika, darbo mokslinis naujumas, darbo rezultatų praktinė reikšmė, ginamieji teiginiai. Įvado pabaigoje pristatomos disertacijos tema autoriaus paskelbtos publikacijos ir pranešimai konferencijose bei disertacijos struktūra. Pirmasis skyrius skirtas mokslinės literatūros apžvalgai ir supažindinimui su netiesinės optikos sąvokomis bei... [toliau žr. visą tekstą]

Disertacijoje nagrinėjami kai kurių lazerių fizikos ir netiesinės optikos uždavinių skaitinės analizės metodai. Tiriami trys pagrindiniai atvejai: bėgančias plokščias bangas aprašantis vienmatis, bėgančias difraguojančias bangas nagrinėjantis dvimatis ir lazerio pluoštų sąveiką netiesinėje Kero terpėje modeliuojantis trimatis modeliai. Šiuos uždavinius sieja pernešimo diferencialinės lygtys dalinėmis išvestinėmis, aprašančios į priešingas puses sklindančias lazerio bangas. Dvimačiame ir trimačiame uždaviniuose sprendžiamos dalinių išvestinių Šrėdingerio (ang. Schrödinger) tipo diferencialinės lygtys. Šiems matematiniams modeliams sudarytos baigtinių skirtumų schemos, atlikta jų analizė ir pagrindimas. Skaitinių eksperimentų realizacijai sukurti lygiagretieji algoritmai, jie yra būtini atliekant didelių resursų reikalaujančius skaičiavimus. Disertaciją sudaro įvadas, keturi skyriai, rezultatų apibendrinimas, naudotos literatūros ir autoriaus publikacijų disertacijos tema sarašai. Įvadiniame skyriuje aptariama tiriamoji problema, darbo aktualumas, aprašomas tyrimų objektas, formuluojamas darbo tikslas bei uždaviniai, aprašoma tyrimų metodika, darbo mokslinis naujumas, darbo rezultatų praktinė reikšmė, ginamieji teiginiai. Įvado pabaigoje pristatomos disertacijos tema autoriaus paskelbtos publikacijos ir pranešimai konferencijose bei disertacijos struktūra. Pirmasis skyrius skirtas mokslinės literatūros apžvalgai ir supažindinimui su netiesinės optikos sąvokomis bei... [toliau žr. visą tekstą] / Mathematical models describing the Q-switched laser generation, which is a widely used laser technique for producing short intense pulses of light, belong to the class of semi-nonlinear models where only source terms nonlinearly depend on the solution. Numerical methods for solution of systems of semi-nonlinear partial differential equations have been extensively studied in many papers. Schrödinger-type equations, parabolic-type equations or general diffusion-reaction models arise in nonlinear optics. Such differential problems are solved mainly by finite-difference and Galerkin methods. The convergence analysis is based on the stability analysis of the linearized problems. The construction and theoretical analysis of discrete schemes for one-dimensional problem give a basis for a numerical solution of more general two-dimensional and three-dimensional problems where a diffraction process is taken into account. The two-dimensional problem simulates the dynamics of high-power semiconductor lasers. To solve the problems simulating propagation of photon fluxes in the nonlinear disperse medium, the finite-difference time-domain method is used. However, the major drawback of this method is that the computational domain must be sufficiently large. In order to restrict the computational domain and to solve the problem only in the region of interest, special artificial boundary conditions are investigated. The three-dimensional problem simulates an interaction of counter propagating... [to full text]

In the present work we implemented parallel version of a computational fluid dynamics code. This code is based on Discontinuous Galerkin Method (DGM), which is due to its favourable properties suitable for parallelization. In the work we describe the Navier-Stokes equations and their discretization using DGM. We explain the advantages of usage of the DGM and formulate the serial algorithm. Next we focus on the parallel implementation of the algorithm and several particular issues connected to the parallelization. We present the numerical experiments showing the efficiency of the parallel code in the last chapter.

Plusieurs types d’expérimentation existent pour étudier et comprendre les systèmes biologiques. Dans ces travaux, nous nous intéressons à la simulation in silico, c’est-à-dire à la simulation numérique de modèles sur un ordinateur. Les systèmes biologiques sont composés d’entités, à la fois nombreuses et variées, en interaction les unes avec les autres. Ainsi, ils peuvent être modélisés par l’intermédiaire de deux approches complémentaires : l’approche population-centrée et l’approche individu-centrée. Face à la multitude et à la variété des phénomènes composant les systèmes biologiques, il nous semble pertinent de coupler ces deux approches pour obtenir une modélisation mixte. En outre, en raison de la quantité conséquente d’informations que représente l’ensemble des entités et des interactions à modéliser, la simulation numérique des systèmes biologiques est particulièrement coûteuse en temps de calcul informatique. Ainsi, dans ce mémoire, nous proposons des solutions techniques de parallélisation permettant d’exploiter au mieux les performances offertes par les architectures multicoeur et multiprocesseur et les architectures graphiques pour la simulation de systèmes biologiques à base de modélisations mixtes. Nous appliquons nos travaux au domaine de la coagulation du sang et plus particulièrement à l’étude de la cinétique biochimique à l’échelle microscopique ainsi qu’à la simulation d’un vaisseau sanguin virtuel. Ces deux applications nous permettent d’évaluer les performances offertes par les solutions techniques de parallélisation que nous proposons, ainsi que leur pertinence dans le cadre de la simulation des systèmes biologiques. / Several types of experimentation exist to study and understand biological systems. Inthis document, we take an interest in in silico simulation, i.e. numerical simulation ofmodels on a computer. Biological systems are made of many various entities, interactingwith each other. Therefore, they can be modeled by two complementary approaches: thepopulation-based approach and the individual-based one. Because of the multitude anddiversity of the phenomena constituting biological systems, we find the coupling of thesetwo approaches relevant to provide a hybrid modelisation. Moreover, because of the hugequantity of data that the entities and interactions represent, numerical simulation of biologicalsystems is especially computationaly intensive. This is why, in this document, we proposeparallel computing methods to take advantage of the performances offered by multicore andmultiprocessor architectures and by graphical ones for the simulation of biological systemsusing hybrid modelisations. We apply our work to blood coagulation and especially to thestudy of biochemical kinetics at the microscopic scale and the simulation of a virtual bloodvessel. These two applications enable us to assess both the performances obtained by theparallel computing methods we proposed and their relevance for biological systems simulation.

Nesta tese são abordados, de maneira integrada, aspectos de paralelismo em visão natural e artificial, com discussões críticas das diversas áreas relacionadas. O paralelismo é discutido no sistema visual dos primatas, assim como suas principais contribuições e motivações incentivando a incorporação de paralelismo em sistemas de visão artificial. Um dos objetivos principais é fornecer as bases de paralelismo para o desenvolvimento do projeto Cyvis-1, uma proposta do Grupo de Pesquisa em Visão Cibernética (IFSC-USP) para visão versátil, com forte motivação biológica e baseada no córtex visual dos primatas. Para tanto, foi introduzida e implementada a proposta CVMP (Cybernetic Vision Message Passage), um conjunto de ferramentas para o desenvolvimento de aplicações paralelas em visão, tanto para sistemas distribuídos como para máquinas multiprocessadores. Baseada em programação orientada a objetos, interação homem-máquina, engenharia de software e programação visual, a proposta prima pelo desenvolvimento de forma simples e amigável. O CVMP é testado, avaliado e validado quanto a aspectos de funcionalidade e utilização, através da implementação paralela de diversos algoritmos de visão computacional e de processamento de imagens (operadores locais, transformada de Hough e transformada de Fourier, entre outros) os quais, além de ilustrar a utilização da ferramenta, são discutidos em termos de arquitetura e balanceamento de carga. São apresentadas três aplicações reais de sistemas paralelos de visão computacional, implementadas através do CVMP, demonstrando a eficiência da ferramenta, na implementação paralela, na utilização e cooperação de trabalho. Duas destas aplicações (integração de atributos visuais no projeto Cyvis-1 e um modelo de complexidade com base na percepção humana), foram desenvolvidas em conjunto com outros pesquisadores do Grupo de Pesquisa em Visão Cibernética. A terceira aplicação apresenta uma proposta do autor para um sistema automático de reconhecimento de plantas arbóreas (Botânica) / This thesis addresses, in an integrated way, the concept and usage of parallelism in natural and artificial vision. It starts by revising the primate visual system, and discussing how its principles and solutions can be extended to computational systems. One of the main objectives is to supply the parallelism backbone for the development of the Cyvis-1 System, which is a proposal of the Cybernetic Vision Research Group (IFSC-USP) for versatile vision, presenting a strong biological motivation, especially regarding the primate visual cortex. In order to achieve these objectives, the CVMP - Cybernetic Vision Message Passage - had to be developed, representing a set of simple and friendly parallel tools for computer vision applications in distributed and parallel (multiprocessor) systems, which is based on object oriented programming, human-machine interaction, software engineering and visual programming. The CVMP is tested, evaluated and validated with respect to functionality and utilization through the parallel implementation of several algorithms in computer vision and image processing (local operators, Hough transform, Fourier transform, etc.) which, in addition to illustrating the tools, are also discussed as far as their architecture and load balancing is concerned. Three applications of parallel computer vision systems to real situations are presented and implemented by using CVMP, corroborating the effectiveness of the tools in the parallel implementation, usage, and researcher integration. Two such applications (visual attributes integration in Cyvis-1 and a human complexity model) have been developed in collaboration with other researchers at the Cybernetic Vision Research Group. The third application presents the author\'s proposal for an automated system for arboreal plants recognition (Botany)

O crescimento explosivo no número de usuários de Internet levou arquitetos de software a reavaliarem questões relacionadas à escalabilidade de serviços que são disponibilizados em larga escala. Projetar arquiteturas de software que não apresentem degradação no desempenho com o aumento no número de acessos concorrentes ainda é um desafio. Neste trabalho, investigamos o impacto do sistema operacional em questões relacionadas ao desempenho, paralelização e escalabilidade de jogos interativos multi-usuários. Em particular, estudamos e estendemos o jogo interativo, multi-usuário, QuakeWorld, disponibilizado publicamente pela id Software sob a licença GPL. Criamos um modelo de paralelismo para a simulação distribuída realizada pelo jogo e o implementamos no servidor do QuakeWorld com adaptações que permitem que o sistema operacional gerencie de forma adequada a execução da carga de trabalho gerada. / The explosive growth in the number of Internet users made software architects reevaluate issues related to the scalability of services deployed on a large scale. It is still challenging to design software architectures that do not experience performance degradation when the concurrent access increases. In this work, we investigate the impact of the operating system in issues related to performance, parallelization, and scalability of interactive multiplayer games. Particularly, we study and extend the interactive, multiplayer game QuakeWorld, made publicly available by id Software under GPL license. We have created a new parallelization model for Quake\'s distributed simulation and implemented that model in QuakeWorld server with adaptations that allows the operating system to manage the execution of the generated workload in a more convenient way.