Image processing pipelines are ubiquitous. Every image captured by a camera and every image uploaded on social networks like Google+or Facebook is processed by a pipeline. Applications in a wide range of domains like computational photography, computer vision and medical imaging use image processing pipelines. Many of these applications demand high-performance which requires effective utilization of modern architectures. Given the proliferation of camera enabled devices and social networks optimizing these emerging workloads has become important both at the data center and the embedded device scales. An image processing pipeline can be viewed as a graph of interconnected stages which process images successively. Each stage typically performs one of point-wise, stencil, sam-pling, reduction or data-dependent operations on image pixels. Individual stages in a pipeline typically exhibit abundant data parallelism that can be exploited with relative ease. However, the stages also require high memory bandwidth preventing effective uti-lization of parallelism available on modern architectures. The traditional options are using optimized libraries like OpenCV or to optimize manually. While using libraries precludes optimization across library routines, manual optimization accounting for both parallelism and locality is very tedious. Inthisthesis,wepresentthedesignandimplementationofPolyMage,adomain-specific language and compiler for image processing pipelines. The focus of the system is on au-tomatically generating high-performance implementations of image processing pipelines expressed in a high-level declarative language. We achieve such automation with: • tiling techniques to improve parallelism and locality by introducing redundant computation, v a model-driven fusion heuristic which enables a trade-off between locality and re-dundant computations, and anautotuner whichleveragesthefusionheuristictoexploreasmallsubsetofpipeline implementations and find the best performing one. Our optimization approach primarily relies on the transformation and code generation ca-pabilities of the polyhedral compiler framework. To the best of our knowledge, this is the first model-driven compiler for image processing pipelines that performs complex fusion, tiling, and storage optimization fully automatically. We evaluate our framework on a modern multicore system using a set of seven benchmarks which vary widely in structure and complexity. Experimental results show that the performance of pipeline implementations generated by our approach is: • up to 1.81× better than pipeline implementations manually tuned using Halide, a state-of-the-art language and compiler for image processing pipelines, • on average 5.39× better than pipeline implementations automatically tuned using Halide and OpenTuner, and • on average 3.3× better than naive pipeline implementations which only exploit par-allelism without optimizing for locality. We also demonstrate that the performance of PolyMage generated code is better or compa-rable to implementations using OpenCV, a state-of-the-art image processing and computer vision library.

Neste trabalho, modela-se a ocorrência de contaminação de um aquífero hipotético por derramamento de substância tóxica e analisa-se a solução de descontaminação baseada na retirada do contaminante através de bombeamento feito por poços de extração. O projeto do sistema de remediação envolve a escolha do número de poços a serem instalados, suas localizações e vazões de modo a maximizar a quantidade de poluente extraída e ao mesmo tempo minimizar o custo total do sistema. A busca da solução ótima é feita de forma automática, através de um sistema paralelo de otimização por simulação numérica, composto por três subsistemas: (a) simulador numérico - resolve numericamente o modelo matemático do aquífero contaminado; (b) otimizador automático - implementa o método dos algoritmos genéticos para busca das localizações e vazões ótimas dos poços de extração; (c)sistema computacional distribuído - gerencia a distribuição e a execução paralela das simulações numéricas. Foram feitos experimentos em vários ambientes computacionais: homogêneo, heterogêneo, em grande escala, usando máquinas não dedicadas, interligadas por rede local e ambiente de grade, e seus resultados demonstram a aplicabilidade da metodologia. / In this dissertation, a hypothetical aquifer that has been contaminated by the dumping of toxic substances is modeled. The remediation strategy considered is based on withdrawal, which requires the removal of contaminated groundwater from the aquifer by pumping. The design of such a system involves the choice of the number of extracting wells to be installed, their locations and pumping rates,with the goal of maximizing the amount of contaminant extracted, while minimizing the cost of the system. To find the optimal solution, a numerical simulation optimization parallel system is used, which is composed by three subsystems: (a) numerical simulator - numerically solves the mathematical model ofthe contaminated aquifer; (b) optimizer - implements the genetic algorithm method to search for optimal locations and pumping rates for the extracting wells; (c)distributed computing system - manages the distribuition and parallel execution of the numerical simulations. Experiments were done in many different computational environments: homogeneous, heterogeneous, in large scale, using non dedicated computers, connected via local network, and computational grids, and their results demonstrate the methodologys applicability.

Made available in DSpace on 2015-05-08T14:59:57Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3935872 bytes, checksum: 5a4c90590e53b3ea1d71bbe61a628b56 (MD5) Previous issue date: 2014-07-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The aim of this work is to study the non-local means algorithm and propose techniques to optimize and implement this algorithm for its application in real-time. Two alternatives are suggested for implementation. The first deals with the development of an accelerator card for computers, which has a PCI bus containing specialized hardware that implements the NLM filter. The second implementation uses densely GPU multiprocessor environment, which exists in the parent video. Both proposals significantly accelerates the NLM algorithm, while maintains the same visual quality of traditional software implementations, enabling real-time use. Image denoising is an important area for digital image processing. Recently, its use is becoming more popular due to improvements of of the new acquisition equipments and, thus, the increase of image resolution that favors the occurrence of such perturbations. It is widely studied in the fields of image processing, computer vision and predictive maintenance of electrical substations, motors, tires, building facilities, pipes and fittings, focusing on reducing the noise without removing details of the original image. Several approaches have been proposed for filtering noise. One of such approaches is the non-local method called Non-Local Means (NLM), which uses the entire image rather than local information and stands out as the state of the art. However, a problem in this method is its high computational complexity, which turns its application almost impossible in real time applications, even for small images / O propósito deste trabalho é estudar o algoritmo non-local means(NLM) e propor técnicas para otimizar e implementar o referido algoritmo visando sua aplicação em tempo real. Ao todo são sugeridas duas alternativas de implementação. A primeira trata do desenvolvimento de uma placa aceleradora para computadores que possuam Barramento PCI, contendo um hardware especializado que implementa o Filtro NLM. A segunda implementação utiliza o ambiente densamente multiprocessado GPU, existente nas controladoras de vídeo. As duas propostas aceleraram significativamente o algoritmo NLM, mantendo a mesma qualidade visual das implementações tradicionais em software, tornando possível sua utilização em tempo real. A filtragem de ruídos é uma área importante para o processamento digital de imagens, sendo cada vez mais utilizada devido as melhorias dos novos equipamentos de captação, e o consequente aumento da resolução da imagem, que favorece o aparecimento dessas perturbações. Ela é amplamente estudada nos campos de tratamento de imagens, visão computacional e manutenção preditiva de subestações elétricas, motores, pneus, instalações prediais, tubos e conexões, focando em reduzir os ruídos sem que se remova os detalhes da imagem original. Várias abordagens foram propostas para filtragem de ruídos, uma delas é o método não-local, chamado de Non-Local Means (NLM), que não só utiliza as informações locais, mas a imagem inteira, destaca-se como o estado da arte, porém, há um problema neste método, que é a sua alta complexidade computacional, que o torna praticamente inviável de ser utilizado em aplicações em tempo real, até mesmo para imagens pequenas

Nesta tese é apresentado um novo workflow de simulação para avaliar o desempenho do balanceamento de carga dinâmico baseado em sobre-decomposição aplicado a aplicações paralelas iterativas. Seus objetivos são realizar essa avaliação com modificações mínimas da aplicação e a baixo custo em termos de tempo e de sua necessidade de recursos computacionais. Muitas aplicações paralelas sofrem com desbalanceamento de carga dinâmico (temporal) que não pode ser tratado a nível de aplicação. Este pode ser causado por características intrínsecas da aplicação ou por fatores externos de hardware ou software. Como demonstrado nesta tese, tal desbalanceamento é encontrado mesmo em aplicações cujo código não aparenta qualquer dinamismo. Portanto, faz-se necessário utilizar mecanismo de balanceamento de carga dinâmico a nível de runtime. Este trabalho foca no balanceamento de carga dinâmico baseado em sobre-decomposição. No entanto, avaliar e ajustar o desempenho de tal técnica pode ser custoso. Isso geralmente requer modificações na aplicação e uma grande quantidade de execuções para obter resultados estatisticamente significativos com diferentes combinações de parâmetros de balanceamento de carga Além disso, para que essas medidas sejam úteis, são usualmente necessárias grandes alocações de recursos em um sistema de produção. Simulated Adaptive MPI (SAMPI), nosso workflow de simulação, emprega uma combinação de emulação sequencial e replay de rastros para reduzir os custos dessa avaliação. Tanto emulação sequencial como replay de rastros requerem um único nó computacional. Além disso, o replay demora apenas uma pequena fração do tempo de uma execução paralela real da aplicação. Adicionalmente à simulação de balanceamento de carga, foram desenvolvidas técnicas de agregação espacial e rescaling a nível de aplicação, as quais aceleram o processo de emulação. Para demonstrar os potenciais benefícios do balanceamento de carga dinâmico com sobre-decomposição, foram avaliados os ganhos de desempenho empregando essa técnica a uma aplicação iterativa paralela da área de geofísica (Ondes3D). Adaptive MPI (AMPI) foi utilizado para prover o suporte a balanceamento de carga dinâmico, resultando em ganhos de desempenho de até 36.58% em 288 cores de um cluster Essa avaliação também é usada pra ilustrar as dificuldades encontradas nesse processo, assim justificando o uso de simulação para facilitá-la. Para implementar o workflow SAMPI, foi utilizada a interface SMPI do simulador SimGrid, tanto no modo de emulação, como no de replay de rastros. Para validar esse simulador, foram comparadas execuções simuladas (SAMPI) e reais (AMPI) da aplicação Ondes3D. As simulações apresentaram uma evolução do balanceamento de carga bastante similar às execuções reais. Adicionalmente, SAMPI estimou com sucesso a melhor heurística de balanceamento de carga para os cenários testados. Além dessa validação, nesta tese é demonstrado o uso de SAMPI para exploração de parâmetros de balanceamento de carga e para planejamento de capacidade computacional. Quanto ao desempenho da simulação, estimamos que o workflow completo é capaz de simular a execução do Ondes3D com 24 combinações de parâmetros de balanceamento de carga em 5 horas para o nosso cenário de terremoto mais pesado e 3 horas para o mais leve. / In this thesis we present a novel simulation workflow to evaluate the performance of dynamic load balancing with over-decomposition applied to iterative parallel applications at low-cost. Its goals are to perform such evaluation with minimal application modification and at a low cost in terms of time and of resource requirements. Many parallel applications suffer from dynamic (temporal) load imbalance that can not be treated at the application level. It may be caused by intrinsic characteristics of the application or by external software and hardware factors. As demonstrated in this thesis, such dynamic imbalance can be found even in applications whose codes do not hint at any dynamism. Therefore, we need to rely on runtime dynamic load balancing mechanisms, such as dynamic load balancing based on over-decomposition. The problem is that evaluating and tuning the performance of such technique can be costly. This usually entails modifications to the application and a large number of executions to get statistically sound performance measurements with different load balancing parameter combinations. Moreover, useful and accurate measurements often require big resource allocations on a production cluster. Our simulation workflow, dubbed Simulated Adaptive MPI (SAMPI), employs a combined sequential emulation and trace-replay simulation approach to reduce the cost of such an evaluation Both sequential emulation and trace-replay require a single computer node. Additionally, the trace-replay simulation lasts a small fraction of the real-life parallel execution time of the application. Besides the basic SAMPI simulation, we developed spatial aggregation and applicationlevel rescaling techniques to speed-up the emulation process. To demonstrate the real-life performance benefits of dynamic load balance with over-decomposition, we evaluated the performance gains obtained by employing this technique on a iterative parallel geophysics application, called Ondes3D. Dynamic load balancing support was provided by Adaptive MPI (AMPI). This resulted in up to 36.58% performance improvement, on 288 cores of a cluster. This real-life evaluation also illustrates the difficulties found in this process, thus justifying the use of simulation. To implement the SAMPI workflow, we relied on SimGrid’s Simulated MPI (SMPI) interface in both emulation and trace-replay modes.To validate our simulator, we compared simulated (SAMPI) and real-life (AMPI) executions of Ondes3D. The simulations presented a load balance evolution very similar to real-life and were also successful in choosing the best load balancing heuristic for each scenario. Besides the validation, we demonstrate the use of SAMPI for load balancing parameter exploration and for computational capacity planning. As for the performance of the simulation itself, we roughly estimate that our full workflow can simulate the execution of Ondes3D with 24 different load balancing parameter combinations in 5 hours for our heavier earthquake scenario and in 3 hours for the lighter one.

O objetivo deste trabalho é estudar algoritmos paralelos para a solução de problemas de Mecânica dos Sólidos, Mecânica dos Fluídos e Interação Fluido-Estrutura empregando o Método dos Elementos Finitos para uso em configurações de memória distribuída e compartilhada. Dois processos para o particionamento da estrutura de dados entre os processadores e divisão de tarefas foram desenvolvidos baseados na aplicação do método de particionamento em faixas e do método da bissecção coordenada recursiva não sobre a geometria da malha mas sim diretamente sobre o sistema de equações, através de reordenações nodais para minimização da largura da banda. Para ordenar a comunicação entre os processadores, foi desenvolvido um algoritmo simples e genérico baseado em uma ordenação circular e alternada que permite a organização eficiente dos processos mesmo em cenários nos quais cada processador precisa trocar dados com todos os demais. Os algoritmos selecionados foram todos do tipo iterativo, por sua adequabilidade ao paralelismo de memória distribuída. Foram desenvolvidos códigos paralelos para o Método dos Gradientes Conjugados utilizado em problemas de Mecânica dos Sólidos, para o esquema explícito de Taylor-Galerkin com um passo e iterações utilizado na simulação de escoamentos compressíveis em regime transônico e supersônico, para o esquema explícito de Taylor- Galerkin com 2 passos para simulação de escoamentos incompressíveis em regime subsônico e para interação fluído-estrutura usando o esquema explícito de dois passos para o fluído e o método implícito de Newmark no contexto do método de estabilização α-Generalizado para a estrutura, com acoplamento particionado. Numerosas configurações foram testadas com problemas tridimensionais utilizando elementos tetraédricos e hexaédricos em clusters temporários e permanentes, homogêneos e heterogêneos, com diferentes tamanhos de problemas, diferentes números de computadores e diferentes velocidades de rede. / Analysis and development of distributed memory parallel algorithms for the solution of Solid Mechanics, Fluid Mechanics and Fluid-Structure Interaction problems using the Finite Element Method is the main goal of this work. Two process for mesh partitioning and task division were developed, based in the Stripwise Partitioning and the Recursive Coordinate Bisection Methods, but applied not over the mesh geometry but over the resultant system of equations through a nodal ordering algorithm for system bandwidth minimization. To schedule the communication tasks in scenarios where each processor must exchange data with all others in the cluster, a simple and generic algorithm based in a circular an alternate ordering was developed. The algorithms selected to be parallelized were of iterative types due to their suitability for distributed memory parallelism. Parallel codes were developed for the Conjugate Gradient Method ( for Solid Mechanics analysis), for the explicit one-step scheme of Taylor-Galerkin method (for transonic and supersonic compressible flow analysis), for the two-step explicit scheme of Taylor-Galerkin method (for subsonic incompressible flow analysis) and for a Fluid-Structure Interaction algorithm using a coupling model based on a partitioned scheme. Explicit two-step scheme of Taylor-Galerkin were employed for the fluid and the implicit Newmark algorithm for the structure. Several configurations were tested for three-dimensional problems using tetrahedral and hexahedral elements in uniform and nonuniform clusters and grids, with several sizes of meshes, numbers of computers and network speeds.

É notório que o emprego de unidades de processamento gráfico (GPU) pode acelerar significativamente métodos numéricos de aplicações científicas. Para suportar essa nova tecnologia, é necessário que programas sejam readaptados, exigindo flexibilidade do código. Nesse trabalho, é apresentada a arquitetura de um programa de elementos finitos (MEF) para a análise de estruturas, com suporte ao processamento em GPU. A orientação a objetos é usada para guiar o desenvolvimento e modelar o código em uma estrutura flexível. A escalabilidade do programa é dada pela extensão de suas funcionalidades através de componentes carregados em tempo de execução. Para ilustrar a robustez do código, o software é aplicado para o estudo de dinâmica estrutural, considerando aspectos complexos de não linearidade de material (plasticidade) e geometria (grandes deslocamentos). A acurácia do código é verificada através da comparação com problemas conhecidos da literatura e com as soluções MEF comerciais (ABAQUS). As comparações mostraram uma boa concordância nos resultados. O speedup da GPU é analisado em relação aos tempos de CPU do próprio programa, sendo observado ganhos de desempenho de até 10 vezes. / It has been recognized that the adoption of graphics processing units (GPU) can significantly boost numerical methods in scientific applications. In order to support such technology, it is necessary to readapt the program, which requires code flexibility. In this work, it is presented the architecture of a finite element (FEM) analysis program for structural analysis with GPU support. Object-oriented design is used to guide development and to build code into a flexible structure. Program scalability is achieved by extensibility of its features, provided by run-time loaded components. In order to demonstrate code robustness, the software is directed to the study of structural dynamics, considering complex non-linear aspects of material (plasticity) and geometry (large displacements). Code accuracy is checked by comparing with known literature problems and with commercial solver packages (ABAQUS). The comparison shows good agreement in the results. The GPU code speedup is analysed against timings of CPU program code, where it is observed performance gain up to 10 times.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-07-04T17:30:00Z No. of bitstreams: 1 raphaelpereiracordeiro.pdf: 17027543 bytes, checksum: 91ef68c2021ff4c93dc8b4fe66217cf2 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-08-08T13:42:41Z (GMT) No. of bitstreams: 1 raphaelpereiracordeiro.pdf: 17027543 bytes, checksum: 91ef68c2021ff4c93dc8b4fe66217cf2 (MD5) / Made available in DSpace on 2017-08-08T13:42:41Z (GMT). No. of bitstreams: 1 raphaelpereiracordeiro.pdf: 17027543 bytes, checksum: 91ef68c2021ff4c93dc8b4fe66217cf2 (MD5) Previous issue date: 2017-03-10 / A modelagem computacional é uma ferramenta útil no estudo de diversos fenômenos complexos, como o comportamento eletro-mecânico do coração em condições normais e patológicas, sendo importante para o desenvolvimento de novos medicamentos e métodos de combate às doenças cardíacas. A alta complexidade de processos biofísicos se traduz em complexos modelos matemáticos e computacionais, o que faz com que simulações cardíacas necessitem de um grande poder computacional para serem executadas. Logo, o estado da arte em simuladores cardíacos é implementado para ser executado em arquiteturas paralelas. Este trabalho apresenta a implementação e avaliação de um método com dados e kernel agregados, método este utilizado para reduzir o tempo de computação de códigos que executam em ambientes computacionais compostos de múltiplas unidades de processamento gráfico (Graphics Processing Unit ou simplesmente GPUs). Este método foi testado na computação de uma importante parte da simulação da eletrofisiologia do coração, a resolução das equações diferenciais ordinárias (EDOs), resultando em uma redução pela metade do tempo necessário para a sua resolução, quando comparado com o esquema onde este método não foi implementado. Com o uso da técnica proposta neste trabalho, o tempo total de execução das simulações cardíacas foi reduzido em até 25%. / Computational modeling is a useful tool to study many distinct and complex phenomena, such as to describe the electrical and mechanical behavior of the heart, under normal and pathological conditions. The high complexity of the associated biophysical processes translates into complex mathematical and computational models. This, in turn, translates to cardiac simulators that demand a lot of computational power to be executed. Therefore, most of the state-of-the-art cardiac simulators are implemented to run in parallel architectures. In this work a new coalesced data and kernel scheme is evaluated. Its objective is to reduce the execution costs of cardiac simulations that run on multi-GPU environments. The new scheme was tested for an important part of the simulator, the solution of the systems of Ordinary Differential Equations (ODEs). The results have shown that the proposed scheme is very effective. The execution time to solve the systems of ODEs on the multi-GPU environment was reduced by half, when compared to a scheme that does not implemented the proposed data and kernel coalescing. As a result, the total execution time of cardiac simulations was 25% faster.

In this paper we present two hierarchically preconditioned methods for the fast solution of mesh equations that approximate 2D-elliptic boundary value problems on unstructured quasi uniform triangulations. Based on the fictitious space approach the original problem can be embedded into an auxiliary one, where both the hierarchical grid information and the preconditioner by decomposing functions on it are well defined. We implemented the corresponding Yserentant preconditioned conjugate gradient method as well as the BPX-preconditioned cg-iteration having optimal computational costs. Several numerical examples demonstrate the efficiency of the artificially constructed hierarchical methods which can be of importance in the industrial engineering, where often only the nodal coordinates and the element connectivity of the underlying (fine) discretization are available.

Synthetic antenna aperture (SAR) is a pulses focusing airborne radar which can achieve high resolution radar image. A number of image process algorithms have been developed for this kind of radar, but the calculation burden is still heavy. So the image processing of SAR is normally performed “off-line”. The Fast Factorized Back Projection (FFBP) algorithm is considered as a computationally efficient algorithm for image formation in SAR, and several applications have been implemented which try to make the process “on-line”. CELL Broadband Engine is one of the newest multi-core-processor jointly developed by Sony, Toshiba and IBM. CELL is good at parallel computation and floating point numbers, which all fit the demands of SAR image formation. This thesis is going to implement FFBP algorithm on CELL Broadband Engine, and compare the results with pre-projects. In this project, we try to make it possible to perform SAR image formation in real-time.

Bayesian inference for stochastic volatility models using MCMC methods highly depends on actual parameter values in terms of sampling efficiency. While draws from the posterior utilizing the standard centered parameterization break down when the volatility of volatility parameter in the latent state equation is small, non-centered versions of the model show deficiencies for highly persistent latent variable series. The novel approach of ancillarity-sufficiency interweaving has recently been shown to aid in overcoming these issues for a broad class of multilevel models. In this paper, we demonstrate how such an interweaving strategy can be applied to stochastic volatility models in order to greatly improve sampling efficiency for all parameters and throughout the entire parameter range. Moreover, this method of "combining best of different worlds" allows for inference for parameter constellations that have previously been infeasible to estimate without the need to select a particular parameterization beforehand. / Series: Research Report Series / Department of Statistics and Mathematics