Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2012. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-04-11T12:42:16Z No. of bitstreams: 1 2012_DanielSundfeldLima.pdf: 2274332 bytes, checksum: 03f64cd52764929edc5ad78619656562 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-05-20T14:40:19Z (GMT) No. of bitstreams: 1 2012_DanielSundfeldLima.pdf: 2274332 bytes, checksum: 03f64cd52764929edc5ad78619656562 (MD5) / Made available in DSpace on 2013-05-20T14:40:19Z (GMT). No. of bitstreams: 1 2012_DanielSundfeldLima.pdf: 2274332 bytes, checksum: 03f64cd52764929edc5ad78619656562 (MD5) / O alinhamento múltiplo de sequências biológicas é um problema muito importante em Biologia Molecular, pois permite que sejam detectadas similaridades e diferenças entre um conjunto de sequências. Esse problema foi provado NP-Difícil e, por essa razão, geralmente algoritmos heurísticos são usados para resolvê-lo. No entanto, a obtenção da solucão ótima é bastante desejada e, por essa razão, existem alguns algoritmos exatos que solucionam esse problema para um número reduzido de sequências. Dentre esses algoritmos, destaca-se o método exato Carrillo-Lipman, que permite reduzir o espaço de busca utilizando um limite inferior e superior. Mesmo com essa redução, o algoritmo com Carrillo-Lipman executa-se em tempo exponencial. Com o objetivo de acelerar a obtenção de resultados, plataformas computacionais de alto desempenho podem ser utilizadas para resolver o problema do alinhamento múltiplo. Dentre essas plataformas, destacam-se as Unidades de Processamento Gráfico (GPU) devido ao seu potencial para paralelismo massivo e baixo custo. O objetivo dessa dissertação de mestrado é propor e avaliar uma estratégia paralela para execução do algoritmo Carrillo-Lipman em GPU. A nossa estratégia permite a exploração do paralelismo em granularidade na, onde o espaço de busca é percorrido por várias threads em um cubo tridimensional, divido em janelas de processamento que são diagonais projetadas em duas dimensões. Os resultados obtidos com a comparação de conjuntos de 3 sequências reais e sintéticas de diversos tamanhos mostram que speedups de até 8,60x podem ser atingidos com a nossa estratégia. ______________________________________________________________________________ ABSTRACT / Multiple Sequence Alignment is a very important problem in Molecular Biology since it is able to detect similarities and di erences in a set of sequences. This problem has been proven NP-Hard and, for this reason, heuristic algorithms are usually used to solve it. Nevertheless, obtaining the optimal solution is highly desirable and there are indeed some exact algorithms that solve this problemfor a reduced number of sequences. Carrillo-Lipman is a well-known exact algorithmfor the Multiple Sequence Alignment problemthat is able to reduce the search space by using inferior and superior bounds. Even with this reduction, the Carrillo-Lipman algorithm executes in exponential time. High Performance Computing (HPC) Platforms can be used in order to produce results faster. Among the existing HPC platforms, GPUs (Graphics Processing Units) are receiving a lot of attention due to their massive parallelism and low cost. The goal of this MsC dissertation is to propose and evaluate a parallel strategy to execute the Carrillo-Lipman algorithm in GPU. Our strategy explores parallelism at ne granularity, where the search space is a tridimensional cube, divided on processing windows with bidimensional diagonals, explored by multiple threads. The results obtained when comparing several sets of 3 real and synthetic sequences show that speedups of 8.60x can be obtained with our strategy.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2006. / Submitted by Érika Rayanne Carvalho (carvalho.erika@ymail.com) on 2009-10-15T01:45:32Z No. of bitstreams: 1 DissertacaoMestrado Leonardo Nunes da Silva.pdf: 1605735 bytes, checksum: cd1350cb41219363224dc8d8c3d3f2e5 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2009-11-24T14:20:22Z (GMT) No. of bitstreams: 1 DissertacaoMestrado Leonardo Nunes da Silva.pdf: 1605735 bytes, checksum: cd1350cb41219363224dc8d8c3d3f2e5 (MD5) / Made available in DSpace on 2009-11-24T14:20:22Z (GMT). No. of bitstreams: 1 DissertacaoMestrado Leonardo Nunes da Silva.pdf: 1605735 bytes, checksum: cd1350cb41219363224dc8d8c3d3f2e5 (MD5) Previous issue date: 2006-12-07 / Na área de processamento paralelo existem dois paradigmas principais de programação: Memória Compartilhada e Troca de Mensagens. Cada um deles é adequado a uma arquitetra de hardware específica. No entanto, existem arquiteturas de multiprocessadores para as quais o mapeamento para um desses paradigmas não é tão simples. Clusters de SMP, por exemplo, são construídos com máquinas de memória compartilhada, conectadas através de uma rede de interconexão. Aplicações para clusters de SMP podem ser programadas para utilizar troca de mensagens entre todos os processadores. Mas existe a possibilidade de um melhor desempenho se utilizado um modelo híbrido de comunicação com troca de informações por memória compartilhada dentro do nó SMP e troca de informações por mensagens entre os nós. Nesse trabalho foi desenvolvido e avaliado um modelo híbrido de programação para uma aplicação na área de engenharia mecânica baseada no método dos elementos finitos. O objetivo desse trabalho é avaliar esse modelo e comparar seu desempenho com uma versão pura, por troca de mensagens, da aplicação. ___________________________________________________________________________________ ABSTRACT / In the area of parallel processing there are two major programming paradigms: Shared Memory and Message Passing. Each of them fits into a specific physical model, but there are multiprocessor architectures whose mapping to one of these paradigms is not so simple. SMP clusters, for example, are built by connecting some shared memory machines through an interconnection network. Applications on SMP clusters can be programmed to use message passing among all processors. However, it’s possible to achieve better performance using a hybrid model with shared memory communication inside SMP nodes and message passing communication between them. In this work, a hybrid model was used to develop an engineering application based on the Finite Element Method in order to evaluate this model and to compare its performance with a pure message passing version of the same application.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2006. / Submitted by Kathryn Cardim Araujo (kathryn.cardim@gmail.com) on 2009-11-13T12:07:06Z No. of bitstreams: 1 2006_RobertaRibeiroFerreira.pdf: 1012527 bytes, checksum: 0f8b6c0ad04b7092c4a0d6a3c623f831 (MD5) / Approved for entry into archive by Tania Milca Carvalho Malheiros(tania@bce.unb.br) on 2009-11-13T13:42:12Z (GMT) No. of bitstreams: 1 2006_RobertaRibeiroFerreira.pdf: 1012527 bytes, checksum: 0f8b6c0ad04b7092c4a0d6a3c623f831 (MD5) / Made available in DSpace on 2009-11-13T13:42:12Z (GMT). No. of bitstreams: 1 2006_RobertaRibeiroFerreira.pdf: 1012527 bytes, checksum: 0f8b6c0ad04b7092c4a0d6a3c623f831 (MD5) Previous issue date: 2006-07-27 / Na área das Engenharias muitos problemas complexos de soluções extremamente trabalhosas e normalmente impossíveis de serem resolvidos por métodos analíticos exigem soluções numéricas. O método dos elementos finitos (MEF) é uma abordagem para solução destes problemas encontrados em análise de estruturas, fluídos, eletromagnetismo, modelagem de circuitos integrados, biomédica e transferência de calor que necessitam processamento de alto desempenho e trabalham com grandes volumes de dados. A computação paralela aparece como uma alternativa viável para a obtenção do desempenho necessário para a solução de problemas através do MEF e a utilização de clusters, como alternativa para a obtenção deste desempenho a baixo custo, se comparados a outros sistemas de computação paralela. Contudo, em ambientes heterogêneos, para que o paralelismo seja explorado eficientemente é fundamental uma distribuição balanceada da carga de trabalho. Para isto, se faz necessário o conhecimento detalhado dos custos de execução e comunicação envolvidos no processamento da aplicação paralela, nas diferentes máquinas do ambiente. Este trabalho tem como objetivo caracterizar o desempenho, através de medições de tempo de execução detalhadas, de um código paralelo para um problema de análise estrutural modelado pelo método dos elementos finitos e resolvido pelo método dos gradientes conjugados (MGC), em um ambiente heterogêneo de PCs. Através dos resultados obtidos com as medições detalhadas, foi possível estabelecer um balanceamento de carga empírico para o ambiente heterogêneo, mostrando a viabilidade da utilização deste ambiente para a execução do código paralelo do método dos elementos finitos. _________________________________________________________________________________________ ABSTRACT / There are many complex problems of extremely difficult solutions in engineering area. These complex problems are usually impossible to be resolved for analytic methods and then they demand numeric solutions. The Finite Elements Method (FEM) is an approach for the solution of these problems found in analysis of structures, fluids, electromagnetism, assembling of integrated circuits, biomedical and transfer of heat, that need high performance processing and work with great volumes of data. The parallel computing appears as a viable alternative for obtaining the necessary performance for the solution of problems through the FEM and the use of cluster appears as an alternative for obtaining this performance processing at a low cost, if compared with the other systems of parallel computing. However, in heterogeneous environments, for an efficiently exploration of the parallelism, it is fundamental a balanced distribution of the work load. For this, it is necessary the knowledge of the execution costs and the communication involved in the processing of the parallel application, in the different machines of the environment. This work has as objective to characterize the performance of a parallel code for a problem of structural analysis modeled by the Finite Elements Method and solved by the Conjugated Gradients Method, in a heterogeneous environment. Through the results obtained with the detailed measurements, it was possible to establish an empiric load balancing for the heterogeneous environment, showing the viability of the use of this environment for the execution of the parallel code of the Finite Elements Method.

Apesar do aumento constante da largura de banda das tecnologias de rede de computadores as aplicações de processamento paralelo ainda necessitam de uma latência de comunicação mais baixa que a oferecida. Este aspecto não tem sido contemplado por estas tecnologias de rede pois está relacionado à maneira como o sistema operacional utiliza-se dos recursos do hardware com relação aos dados enviados pelas aplicações dos usuários. Neste trabalho apresentamos um estudo da técnica para diminuição desta latência e as características necessárias para implementação deste tipo de sistemas, incluindo mecanismos de transferência de dados, técnicas para tradução de endereços, proteção, transferência de controle, grau de confiabilidade e implementação de \"Multicasting\". Apresentamos também o estudo de um sistema já implementado, chamado M-VIA, comparando seu desempenho com o TCP/IP tradicional. / Despite the constant bandwidth increase in computer networks parallel processing tasks still require a lower communication latency than offered. This necessity has not been addressed by these network technologies because it is related to how operating systems use hardware resources to send user data through network. In this work we present strategies to lower latency and the requirements to implement these systems, including data transfer mechanisms, address translation , security, control transfer, reliability and \"Multicasting\" deployment . We also present a ready to use system, M-VIA, comparing it to traditional TCP/IP performance.

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.

A Transformada Distância é uma importante ferramenta para o processamento de imagens digitais. A partir dela podemos calcular a dimensão fractal e obter o esqueleto de um objeto. Estas operações são muito importantes na análise de formas e no reconhecimento de padrões. Porém poucas são as implementações em hardware específico para este processamento. Neste trabalho apresentamos a implementação de arquiteturas paralelas para a determinação da Transformada Distância e para a geração de esqueletos baseados no algoritmo de Dilatação Exata e Propagação de Rótulos. Propomos também uma implementação do algoritmo utilizando a biblioteca MPI para o processamento paralelo. / Distance Transform is an important tool for digital imaging processing. Using the Distance Transform it is possible to evaluate the fractal dimension and skeletons of objects. Fractal dimension and skeletons are very important in shape analysis and pattern recognition operations, few are the hardware implementation for these operations. In this work we present a parallel implementation based on the exact dilation and label propagation for the evaluation of the Distance Transform and skeletons generation. We also propose an algorithm implementation using the MPI library for parallel processing.

Este trabalho apresenta uma ferramenta orientada ao objeto para o monitoramento de cargas em sistemas paralelos. O desenvolvimento desta ferramenta surgiu com o intuito de facilitar a programação paralela em sistemas distribuídos como NOWs, Networks of Workstations , e Grids computacionais, pois este tipo de programação é bem mais difícil do que a seqüencial e, por isso, desestimula novos programadores a desenvolver aplicações paralelas. Dentre as razões que tornam a programação paralela difícil destaca-se o balanceamento de cargas em que se quer maximizar a utilização dos recursos computacionais do sistema distribuído. Outro motivo para o programador de aplicações paralelas se preocupar com balanceamento de cargas é o desempenho, que é drasticamente afetado com o desequilíbrio de cargas do sistema. Com relação ao tempo em que as decisões de rebalanceamento de cargas são tomadas, os algoritmos de distribuição de cargas podem ser estáticos, realizados em tempo de compilação, ou dinâmicos, efetuados em tempo de execução. Embora o algoritmo estático não gere sobrecarga em tempo de execução na distribuição de carga, o dinâmico é a melhor escolha, pois se adapta bem em qualquer situação. Assim, o sistema de monitoramento de cargas surge como uma ferramenta de auxílio ao programador que deseje implementar algoritmos de balanceamento dinâmico de cargas nas suas aplicações paralelas, provendo informações de como os recursos computacionais do sistema distribuído estão sendo utilizados. / This work presents an object oriented tool for load monitoring in parallel systems. This tool was developed with intention to easy the parallel programming in distributed systems like NOWs (Networks of Workstations) and Computational Grids, because this type of programming is more difficult than the sequential and, therefore, it does not stimulate new programmers to develop parallel softwares. One of the most important reasons why parallel programming is difficult is the worry about load balancing where the purpose is to maximize the use of the computational resources of the distributed system. Another reason for the programmer of parallel softwares to worry about load balancing is the performance, which is drastically affected with the load imbalance of the system. With respect to the time where the decisions of load balancing are made, the load distribution algorithms can be static, done at compilation time, or dynamic, done at execution time. Although the static algorithm does not generate overhead at execution time, the dynamic one is a better choice, because it adapts well to any situation. Thus, the monitoring system appears as a tool to aid the programmer who desires to implement dynamic load balancing algorithms in his or her parallel softwares, providing information on how the computational resources of the distributed system are being used.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / A aplicaÃÃo de nuvens computacionais para oferecer serviÃos de ComputaÃÃo de Alto Desempenho (CAD) à um assunto bastante discutido no meio acadÃmico e industrial. Esta dissertaÃÃo està inserida no contexto do projeto de uma nuvem computacional para o desenvolvimento e execuÃÃo de aplicaÃÃes de CAD baseadas em componentes paralelos, doravante denominada nuvem de componentes. Um dos principais desafios na sua utilizaÃÃo consiste no suporte à programaÃÃo paralela, tarefa bastante suscetÃvel à erros, pois tais erros podem levar, ao longo do desenvolvimento, a problemas de sincronizaÃÃo de processos, que podem causar abortamento da execuÃÃo e a produÃÃo de dados incorretos, bem como a problemas relacionados ao uso ineficiente dos recursos computacionais. à importante que tais problemas sejam tratados no caso de aplicaÃÃes de longa duraÃÃo cujo respeito a um cronograma para obtenÃÃo de resultados à crÃtico, aplicaÃÃes estas bastante comuns no contexto de CAD. Uma possÃvel soluÃÃo para tais problemas consiste na verificaÃÃo do comportamento e das propriedades dos componentes na nuvem, antes que seja feita a sua execuÃÃo, tornando possÃvel que os usuÃrios dos componentes da nuvem saibam se um componente pode ser utilizado com seguranÃa em sua aplicaÃÃo. Nesse cenÃrio, o uso de mÃtodos formais surge como uma alternativa atraente. A contribuiÃÃo desta dissertaÃÃo consiste em um processo de derivaÃÃo e verificaÃÃo de propriedades de componentes na nuvem. Tal processo envolve a especificaÃÃo formal do comportamento dos componentes por meio de contratos descritos pela linguagem Circus. EntÃo, atravÃs de um processo de refinamento e traduÃÃo tendo como ponto de partida o contrato, chega-se à implementaÃÃo de um componente para execuÃÃo sobre uma plataforma de computaÃÃo paralela. AtravÃs desse processo, torna-se possÃvel oferecer garantias aos desenvolvedores em relaÃÃo ao comportamento dos componentes no contexto de suas aplicaÃÃes. Para a prova de conceito, o processo à aplicado sobre a especificaÃÃo "papel-e-caneta" de dois benchmarks do NAS Parallel Benchmarks, IS e CG, bastante difundidos na Ãrea de CAD. / The use of cloud computing to offer High Performance Computing (HPC) services has been widely discussed in the academia and industry. In this respect, this dissertation is included in the context of designing a cloud computing platform for the development of component-based parallel computing applications, referred as cloud of components. Many important challenges about using the cloud of components relate to parallel programming, an error-prone task due to synchronization issues, which may lead to abortion and production of incorrect data during execution of applications, and the inefficient use of computational resources. These problems may be very relevant in the case of long running applications with tight timelines to obtain critical results, quite common in the context of HPC. One possible solution to these problems is the formal analysis of the behavior of the components of an application through the cloud services, before their execution. Thus, the users of the components may know if a component can be safely used in their application. In this scenario, formal methods becomes useful. In this dissertation, it is proposed a process for specification and derivation of parallel components implementation for the cloud of components. This process involves the formal specification of the components behavior through contracts described using the Circus formal specification language. Then, through a refinement and translation process, which takes the contract as a start point, one may produce an implementation of a component that may execute on a parallel computing platform. Through this process, it becomes possible to offer guarantees to developers about the components behavior in their applications. To validate the proposed idea, the process is applied to contracts that have been described based on two benchmarks belonging to the NAS Parallel Benchmarks, widely adopted in HPC for evaluate the performance of parallel programming and computing platforms.

Manipuladores paralelos apresentam inércia reduzida, o que lhes permite alcançar altas acelerações e melhor eficiência energética. Porém, frequentemente seu espaço de trabalho possui desempenho pouco uniforme. De fato, a presença de singularidades paralelas é um forte limitante para essa arquitetura robótica. A redundância de atuação já é conhecida como uma alternativa para essa questão. Enquanto que a redundância cinemática ainda não possui consequências claras. Um manipulador com esse tipo de redundância apresenta um número de graus de liberdade do end-effector menor que o número de graus de liberdade do mecanismo como um todo. Considerando essa lacuna, o objetivo desse mestrado é analisar a influência da redundância cinemática no desempenho de manipuladores paralelos através de simulações e testes experimentais. Tal estudo não é trivial, uma vez que com o maior número de atuadores e graus de liberdade, é adicionada também inércia ao sistema. Foram definidas métricas para avaliar o quão favorável é uma dada posição e, com elas, estratégias de resolução de redundância foram analisadas. A estratégia principal proposta se compõe por duas etapas. No primeiro passo, é definida uma movimentação na qual a posição a cada instante é ótima segundo uma dada métrica de desempenho multiobjetivo. Isso resulta em um movimento de referência que em geral possui altas acelerações. Na segunda etapa, aplica-se uma otimização global, procurando manter um compromisso de proximidade com o movimento de referência e com os níveis de aceleração. Além deste, foram aplicados diversos métodos de otimização local (onde a cinemática inversa é resolvida para cada instante isoladamente) e uma estratégia global truncada. Essas opções foram comparadas numericamente e experimentalmente, trazendo uma resposta objetiva da influência da redundância cinemática no manipulador paralelo. A campanha experimental foi realizada em uma protótipo construído no Laboratório de Dinâmica da Escola de Engenharia de São Carlos. Esse protótipo consiste em um manipulador paralelo planar com 6 graus de liberdade, tendo assim, até 3 graus de redundância para a movimentação no plano. Têm-se 6 motores rotativos para atuá-los, sendo 3 deles acoplados a guias lineares com fusos para obtenção de atuação linear. O acionamento ou não destas guias define o grau de redundância do sistema, garantindo a versatilidade do protótipo. / As a consequence of their reduced inertia, parallel manipulators present superior energetic efficiency and they are able to reach high accelerations. Nevertheless, their workspace has a poorly uniform performance. Indeed, the presence of parallel singularities is a strong limitant for this kind of robots. On the one hand, actuation redundancy is well-known as a good choice in an effort to solve this issue. On the other hand, kinematic redundancy still have unclear consequences on this matter. A kinematically redundant manipulator presents an end-effector with fewer degrees of freedom than the mechanism as a whole. Considering this gap, the objective of this research is to analyze the influence of kinematic redundancy on the performance of parallel manipulators through simulations and experimental tests. This issue turns out to be complex, once traveling actuators sum additional inertia to the system. Metrics are defined in order to evaluate how favourable is a given position, and redundancy resolution strategies are analyzed using them. The main proposed strategy is composed of two steps. In the first one, a movement is defined so that the position for each instant is optimum for a given multiobjective performance metric. This procedure delivers a refererence movement which generally presents high accelerations. On the second step, a global optimization is applied, seeking for a trade-off between the proximity to the reference and the acceleration levels. In addition, several local methods (which resolve the inverse kinematics for each instant independently) and one truncated global strategy were addressed. These configurations were compared numerically and experimentally, delivering a objective analysis of the influence of kinematic redundancy on the performance of the parallel manipulator. The experimental campaign was executed with a physical prototype built at the São Carlos School of Engineering. This is a planar manipulator with 6 degrees of freedom, consequently presenting up to 3 degrees of redundancy. The mechanism is actuated by 6 rotating motors, of which 3 are coupled to leadscrews, resulting in linear actuators. These leadscrews can be locked, defining different degrees of redundancy and granting the versatility of the prototype.

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.