Este trabalho utiliza o problema subset-sum (SSP) como estudo de caso, com o objetivo de analisar a complexidade de paralelização em Unidades de Processamento Gráficas (GPU). O SSP foi escolhido por pertencer à classe dos problemas NP-Completo, possuir grande necessidade de memória e não ter cálculo de ponto flutuante, além de ser amplamente estudado na área acadêmica devido a sua importância prática e teórica. Estas características representam um desafio para paralelização em GPUs, pelo fato de serem especialistas em cálculos de ponto flutuante e por possuir pouca quantidade de memória em relação ao grande número de núcleos. Basicamente, são apresentados 3 novos algoritmos, implementados em linguagem CUDA C, com baixo consumo de memória: somente , onde , é a capacidade da mochila e é a quantidade de itens, ao invés de do paradigma de Bellman, referentes aos algoritmos do estado da arte implementados na mesma arquitetura. Esta característica permite um ganho significativo na quantidade de instâncias solucionáveis, além do melhor tempo computacional. Para uma variedade de benchmarks, obteve-se bons valores de speed-up em relação aos melhores resultados práticos conhecidos até agora. Isto foi possível graças a um novo método para a solução do SSP, permitindo sua computação em tempo e mesmo espaço, caso processadores sejam utilizados.

Esta dissertação apresenta o PMPI, uma implementação do padrão MPI em plataformas heterogêneas. Diferentemente de outras implementações de MPI, o PMPI permite que a aplicação paralela seja realizada num sistema multi-plataforma, e que programas em linguagens de programação diferentes participem da mesma computação. PMPI é construído sobre o Dotnet Framework. Com o PMPI, os nós de processamento chamam funções MPI que são executadas transparentemente em outros nós participantes da computação paralela pela rede de comunicação. O PMPI pode atravessar múltiplos domínios administrativos distribuídos geograficamente. Para os programadores, o grid se parece como uma computação MPI local. O modelo de computação é indistinguível da computação MPI padrão. Esta dissertação estuda a implementação de PMPI com o Microsoft Dotnet Framework e com o MONO para prover uma biblioteca que suporta ambiente de multi-linguagens de programação e multi-plataformas. São analisados os resultados obtidos dos testes executados em sistemas heterogêneos usando PMPI. Os resultados obtidos mostram que a implementação PMPI é uma solução viável, possuindo várias vantagens que ainda podemos explorar melhor. / This dissertation describes PMPI, an implementation of the MPI standard on a heterogeneous platform. Unlike other MPI implementations, PMPI permits MPI computation to run on a multiplatform system. In addition, PMPI permits programs executing on different nodes to be written in different programming languages. PMPI is build on the top of Dotnet framework. With PMPI, nodes call MPI functions that are transparently executed on the participating nodes across the network. PMPI can span multiple administrative domains distributed geographically. To programmers, the grid looks like a local MPI computation. The model of computation is indistinguishable from that of standard MPI computation. This dissertation studies the implementation of PMPI with Microsoft Dotnet framework and MONO Dotnet framework to provide a common layer for a multiprogramming language multiplatform MPI library. Results obtained from tests running PMPI on a heterogeneous system are analyzed. The obtained results show that PMPI implementation is feasible and has many advantages that can be explored.

Esse trabalho propõe uma solução de um Data Warehouse distribuído para implementação de um sistema de CRM, Customer Relationship Management, com o objetivo de uso no ambiente bancário possibilitando que ações de relacionamento com clientes sejam planejadas e implementadas. É proposta uma arquitetura para implementação de um Data Warehouse em ambiente distribuído, utilizando programação paralela. Com o aumento no volume de dados armazenados nos Data Warehouse, as arquiteturas tradicionais exigem processadores e sistemas de entrada e saída cada vez mais robustos em termos de desempenho. Isso fica mais bem caracterizado quando são executadas procuras complexas (Ad hoc). A utilização de ambientes distribuídos em conjunto com programação paralela é uma alternativa para redução de custo e aumento de desempenho. É apresentada, aqui, uma proposta de arquitetura de Data Warehouse distribuído, integrado ao uso de programação paralela. / This lecture proposes a solution for Data Warehouse in an distributed environment for implementation of a CRM, Customer Relationship Management in a banking system. It\'s possible to create, plan and implement relationship actions with clients. Architecture is proposed for implementation of a Data Warehouse in a distributed environment, using parallel programming. With the increase of volume of data stored in Data Warehouse, the traditional architectures needs high performance in terms of processors and input and output systems. This kind of problem is well characterized when high complex queries (Ad hoc) is performed. Using distributed environment, together with parallel programming is a good choice to increase the performance and reduce cost. It\'s presented, here, a proposal for architecture of distributed Data Warehouse, integrated with the use of parallel programming.

O Tanque de Provas Numérico (TPN) é um laboratório pioneiro em hidrodinâmica aplicada e fruto de uma colaboração entre a indústria brasileira de petróleo (PETROBRAS S.A.) e as principais instituições de pesquisa do país. Seu principal objetivo é atuar como parceiro da indústria offshore e de petróleo, colaborando para a obtenção da autossuficiência da produção nacional de petróleo como uma poderosa ferramenta para projeto e análise de sistemas flutuantes de produção de óleo e gás. O coração do TPN é um cluster de computadores SMP que é hoje um dos maiores agrupamentos do Brasil para fins de pesquisa. Um dos focos de atenção do TPN é a aplicação do Moving Particles Semi-implicit Method (MPS) na exploração de soluções para muitos problemas de Engenharia. Por trabalhar sem a necessidade do uso de malhas (método tradicional Euleriano), o método tem diversas aplicações na simulação de corpos flutuantes e na hidrodinâmica aplicada, sendo atualmente utilizado para realização de estudos sobre a influência do movimento de ondas em navios; simulações de fenômenos que envolvem fragmentações; superfícies livres; grandes deformações; dinâmica de fluidos em condições extremas, como é o caso em processos prospecção do petróleo onde muitas vezes é difícil e economicamente inviável fazer ensaios físicos. Devido ao grande número de partículas utilizadas na simulação de sistemas complexos pelo método MPS, é necessário aproveitar de forma eficiente os recursos computacionais disponíveis para a análise de modelos com o refinamento adequado às aplicações práticas. Com tera-FLOPS disponíveis na rede cluster do TPN para modelagem computacional, há uma grande necessidade de uma solução computacional paralela altamente escalonável que, além disto, seja fácil de manutenção e extensibilidade. Dentro desta linha de pesquisa, foi desenvolvida uma solução com essas características através do emprego de modernas técnicas de engenharia de software. / The Numerical Offshore Tank (TPN) is a pioneer laboratory in applied hydrodynamics and result of collaboration between the Brazilian oil (Petrobras SA) and the major research institutions in the country. Its main purpose is to act as a partner of industry and offshore oil, contributing to the achievement of self-sufficiency of domestic oil production as a powerful tool for design and analysis of floating production systems for oil and gas. The heart of TPN is a cluster of SMP computers that is now one of the largest groupings of Brazil for research purposes. One focus of attention of TPN is the application of Moving Particles Semi-implicit Method (MPS) in exploring solutions to many engineering problems. By working without the use of mesh (Eulerian traditional method), the method has several applications in the simulation of floating bodies and applied hydrodynamics, currently being used for studies on the influence of the movement of ships in waves; simulations of phenomena involving fragmentation; free surfaces, large deformations; fluid dynamics in extreme conditions, as is the case in processes where petroleum exploration is often difficult and uneconomical to do physical tests. Due to the high number of particles used in the simulation of complex systems by the MPS method, it is necessary to efficiently take advantage of the computational resources available for the analysis of models with the refinement suitable for practical applications. With tera-FLOPS available in the TPN network cluster for computational modeling, there is a great need for a parallel highly scalable solution which, moreover, must be easy maintenance and extensibility. Within this line of research, we developed a solution with these characteristics through the use of modern software engineering techniques.

Empresas estão procurando reduzir seus custos e aumentar seu desempenho e competitividade. Neste cenário de redução de custos, a logística colaborativa pode ser uma aliada. Numa rede complexa, onde embarcadores muitas vezes nem sabem da existência de outros embarcadores com demandas complementares, existe um potencial de sinergia e redução de custos através da diminuição de deslocamentos de veículos sem carga, ou seja, deslocamentos para reposicionar os veículos. Visando essa redução, o Problema de Cobertura de Rotas (PCR), que tem como objetivo cobrir rotas no mínimo custo, une as demandas de frete de vários embarcadores e tenta minimizar os deslocamentos sem cargas (reposicionamentos), reduzindo assim o custo total de toda a rede dos embarcadores envolvidos. Esta pesquisa propõe um modelo e uma heurística para resolver, em grande escala através de programação paralela, uma expansão do PCR. / Companies are looking to reduce costs and improve performance and competitiveness. In this cost-cutting scenario, collaborative logistics can be an ally. In a complex network where shippers often do not know of the existence of other shippers with complementary demands, there is potential for synergy and cost savings by reducing unloaded travelling of vehicles, i.e, the distance and time to reposition the vehicles\'. Towards that reduction, the Lane Covering Problem (LCP), which aims to cover at least cost routeslinks the various shippers\' demands of freight and tries to minimize operations without loads (repositioning), thus reducing the total cost of the entire network for involved shippers. This research proposes a model and an heuristic to solve, in large-scale through parallel programming, an expansion of the PCR.

Este trabalho aborda alguns conceitos e definições de processamento paralelo, que são aplicados a paralelização automática, e também às análises e condições para as dependências dos dados, de modo a aplicarmos os métodos de paralelização: Hiperplano, Transformação Unimodular, Alocação de Dados Sem Comunicação e Particionamento & Rotulação. Desta forma, transformamos um programa seqüencial em seu equivalente paralelo. Utilizando-os em um sistema de memória distribuída com comunicação através da passagem de mensagem MPI (Message-Passing Interface), e obtemos algumas métricas para efetuarmos as avaliações/comparações entre os métodos. / This work invoke some concepts and definitions about parallel processing, applicable in the automatic parallelization, and also the analysis and conditions for the data dependence, in order to apply the methods for parallelization: Hyperplane, Unimodular Transformation, Communication-Free Data Allocation and Partitioning & Labeling. On this way, transform a sequential program into an equivalent parallel one. Applying these programs on the distributed-memory system with communication through message-passing MPI (Message-Passing Interface), and we obtain some measurements for the evaluations/comparison between those methods.

Orientador: Alexandro José Baldassin / Banca: Daniel Carlos Guimarães Pedronette / Banca: Márcio Merino Fernandes / Resumo: Memória Transacional (Transactional Memory - TM) possibilita que programadores utilizem-se do conceito de transação na escrita de código concorrente. Nesse contexto, uma transação pode ser entendida como um bloco de instruções que é executado atomicamente e de forma isolada, ou seja, os estados intermediários no processamento de uma transação não são vistos pelas demais. Embora inicialmente confinada ao ambiente acadêmico, TM está se tornando cada vez mais popular. Prova disto é a adição de hardware transacional aos novos processadores da Intel e IBM, além de suporte para codificação de transações provido por compiladores como o GCC. A grande vantagem do modelo transacional é o maior nível de abstração fornecido ao programador, facilitando a escrita de programas concorrentes e evitando erros de sincronização famosos causados pelas travas (locks), como o deadlock. Infelizmente, o suporte em software para execução de transações ainda não provê desempenho muito bom. Em particular, o código transacional, produzido por compiladores e o sistema de tempo de execução associado, ainda pode ser considerado ineficiente. Nesta dissertação é realizado um estudo atualizado sobre a geração de código transacional do compilador GCC com o objetivo de encontrar a razão da deficiência de desempenho do compilador. O trabalho feito indica que uma das principais fontes de ineficiência são as barreiras de leitura e escrita inseridas pelo compilador. O problema dessa instrumentação acontece quando o... / Abstract: Transactional Memory (TM) allows programmers to utilize the concept of transaction for writing concurrent code. In this context, a transactioncan be extended as a block of instructions that is executed atomically and isolated, that is, the intermediate states of the processing of a transaction can not be seen by the other transactions. Although initially confined to the academic field, TM is becoming more popular. An evidence of this is the addition of transactional hardware to the new processors from Intel and IBM, as well as the support for transactional code provided by compilers such as GCC. The biggest advantage to the transactional model is the bigger level of abstraction provided to the programmer, making the process of writing parallel code easier, as well as avoiding famous synchronization errors caused by traditional locks, such as the deadlock problem. Unfortunately, the software support for execution of transaction still does not provide a good performance. In particular, transactional code, produced by compilers and the associated runtime system, can still be considered inefficient. This thesis performs an up-to-date study of the GCC transactional code generation and with the objective to find where the main performance losses are coming from. The study done indicates that one of the main sources of inefficiency is the read and write barriers inserted by the compiler. The problem of this instrumentation is that the compiler cannot determine, at compile time, if a ... / Mestre

Um problema que vem se tornando habitual em análise geoestatística é a quantidade crescente de observações. Em tais casos é comum que estimadores usualmente utilizados não possam ser empregados devido a dificuldades numéricas. Esta tese têm por objetivo propor um novo estimador para massivas observações em geoestatística: o estimador subsemble espacial. O estimador subsemble espacial seleciona várias subamostras, espacialmente estruturadas, do conjunto completo de dados. Cada subamostra estima com facilidade os parâmetros do modelo e as estimativas resultantes são ponderadas através de um subconjunto de validação. Em estudos simulados, compara-se a metodologia proposta com outros métodos e os resultados apresentam sua acurácia e rapidez. Além disso, uma aplicação em um banco de dados reais, com 11.000 observações, confirma essas características. / A problem that is becoming common in geostatistical analysis is the growing number of observations. In such cases, common estimators cannot be used due to numerical difficulties. This thesis proposes a new estimator for massive observations in geostatistics: the spatial subsemble estimator. The estimator selects small spatially structured subset of observations. The model parameters are estimated easily with each subsample, and the resulting estimates are weighted by a subset of validation. We compare the spatial subsemble with competing alternatives showing that it is faster and accurate. In addition, we present an application in a real database with 11000 observations.

Orientadora: Letícia Rodrigues Bueno / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2013

Made available in DSpace on 2014-06-11T19:30:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-04-27Bitstream added on 2014-06-13T19:40:30Z : No. of bitstreams: 1 ferro_m_dr_rcla_parcial.pdf: 557493 bytes, checksum: fcae382eb9a89592e907d3171f912924 (MD5) Bitstreams deleted on 2015-05-04T12:07:27Z: ferro_m_dr_rcla_parcial.pdf,Bitstream added on 2015-05-04T12:07:58Z : No. of bitstreams: 1 000713741.pdf: 1451277 bytes, checksum: 241fb4d825af417c9645365b1885c071 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / As formigas Attini são destacadas pragas agrícolas e invertebrados modelos em estudos em genômica, metagenômica, sistemática e evolução molecular. Tais estudos têm gerado milhares de sequências nucleotídicas, cuja análise demanda o uso de diferentes programas de Bioinformática em processamentos automatizados. Pensando nisso, foram desenvolvidos protocolos para análises de ESTs e de bibliotecas de sequências ITS e 16S obtidas de formigas Attini. Foi desenvolvida uma arquitetura baseada no padrão MVC e J2EE responsável por todos os processos cliente-servidor. Os protocolos foram implementados na forma de pipelines em que cada componente é um serviço web em REST acoplado a arquitetura desenvolvida. bESTscan realiza a anotação de sequências EST transcriptômicas, 16Scan e ITScan realizam análises de ecologia microbiana, para bactérias (sequências 16S) e para fungos (sequências ITS) respectivamente, bem como identifica as sequências através de pesquisas em bancos de dados públicos. O sistema computacional desenvolvido automatiza a anotação de sequências para um pequeno volume de sequências como as obtidas por Sanger ou para grande volume de dados como as geradas por Sequenciadores de Nova Geração, reduzindo o tempo de processamento e facilitando a análise dos resultados. Todos os pipelines desenvolvidos foram validados com sequências de Attini, obtidas por Sanger e Illumina, geradas a partir de diferentes projetos do nosso laboratório e estão disponíveis na web nos endereços http://evol.rc.unesp.br/lem/?q=bioinformatics / The Attini ants are agricultural pests and invertebrate models for studies on genomics, metagenomics, molecular systematics and evolution. These studies have generated thousands of nucleotide sequences whose analysis requires the use of different Bioinformatics tools and automated processing. We developed automated sequence annotation protocols for ESTs and ITS and 16S libraries analysis for Attini ants. We developed an architecture model based on J2EE and MVC patterns which is responsible for all client-server processes and each tool in the pipeline is a REST web service coupled in the architecture model developed. The bESTscan pipeline to perform the EST transcriptome annotation, 16Scan e ITScan realize microbial ecology studies for both, bacteria (16S sequences) and for fungi (ITS sequences), as well as identify sequences through public databases. The computer system developed automates the annotation for both a small volume of sequences obtained by Sanger and for a large number of data generated by the Next Generation Sequencers (NGS), reducing processing time and with high performance. Pipelines were developed and validated using sequences Sanger and Illumina generated with different projects from our laboratory and are available at http://evol.rc.unesp.br/lem/?q=bioinformatics