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.

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.

Aplicações têm tradicionalmente utilizado o paradigma de programação sequencial. Com a recente expansão da computação paralela, em particular os processadores multinúcleo e ambientes distribuídos, esse paradigma tornou-se um obstáculo para a utilização dos recursos disponíveis nesses sistemas, uma vez que a maior parte das aplicações tornam-se restrita à execução sobre um único núcleo de processamento. Nesse sentido, este trabalho de mestrado introduz uma abordagem para paralelizar programas sequenciais de forma automática e transparente, diretamente sobre o código-binário, de forma a melhor utilizar os recursos disponíveis em computadores multinúcleo. A abordagem consiste na desmontagem (disassembly) de aplicações Intel x86 e sua posterior tradução para uma linguagem intermediária. Em seguida, são produzidos grafos de fluxo e dependências, os quais são utilizados como base para o particionamento das aplicações em unidades paralelas. Por fim, a aplicação é remontada (assembly) e traduzida novamente para a arquitetura original. Essa abordagem permite a paralelização de aplicações sem a necessidade de esforço suplementar por parte de desenvolvedores e usuários. / Traditionally, computer programs have been developed using the sequential programming paradigm. With the advent of parallel computing systems, such as multi-core processors and distributed environments, the sequential paradigm became a barrier to the utilization of the available resources, since the program is restricted to a single processing unit. To address this issue, we introduce a transparent automatic parallelization methodology using a binary rewriter. The steps involved in our approach are: the disassembly of an Intel x86 application, transforming it into an intermediary language; analysis of this intermediary code to obtain flow and dependency graphs; partitioning of the application into parallel units, using the obtained graphs and posterior reassembly of the application, writing it back to the original Intel x86 architecture. By transforming the compiled application software, we aim at obtaining a program which can explore the parallel resources, with no extra effort required either from users or developers.

A reconfiguração de redes é uma técnica utilizada para alterar topologias de redes por meio da mudança dos estados das chaves normalmente aberta e normalmente fechada. Essa técnica é muito utilizada para tratar problemas relacionados ao excesso de perdas ôhmicas em uma rede elétrica. Tais perdas representam um custo considerável no faturamento das empresas distribuidoras. O problema de redução de perdas via reconfiguração de redes pode ser modelado como um problema de otimização combinatória, em que se deve determinar a combinação de estados de chaves que correspondem a configuração radial da rede com menor nível de perdas. De modo a lidar com esse problema por reconfiguração da redes, diversas técnicas computacionais têm sido propostas. Dentre essas técnicas, estruturas de dados eficientes, como a Representação nó-profundidade (RNP), viabilizam a modelagem radial dos sistemas de distribuição (SDs) e o uso combinado com métodos de otimização possibilitam uma redução do espaço de busca de soluções consequentemente pode-se obter melhores soluções. Para otimizar a capacidade de processamento, este trabalho propõe tratar o problema de redução de perdas em SDs via reconfiguração de redes em aceleradores de hardware utilizando da arquitetura de hardware paralelizada em FPGA baseada na RNP (HP-RNP) proposta em (GOIS, 2011). Assim, um problema combinatório é tratado em aceleradoras de hardware reduzindo significativamente o custo computacional devido ao alto grau de paralelismo no processo de busca por soluções. Nesse sentido, foi proposto neste trabalho a extensão da HP-RNP, a partir de modificações no barramento de comunicação da arquitetura original para o envio e recebimentos dos dados que representam os SDs de forma mais eficiente. Além disso, o problema de redução de perdas por reconfiguração de redes foi mapeado em um problema de floresta geradora mínima com restrição de grau (dc-MSFP), a partir de uma aproximação que faz uso de uma heurística de pesos, em que informações relacionadas com grandezas elétricas e características topológicas da rede são transformadas em pesos. A partir da extensão da HP-RNP e do mapeamento do problema em um dc-MSFP, foi possível obter soluções de qualidade (próximas da ótima) em tempo significativamente reduzido quando comparado às outras abordagens. / Network reconfiguration is a technique used to change network topologies by changing the normally open and normally closed switches states. This technique is widely used to problems related to the excess of ohmic losses in distribution companies. Such losses represent a considerable cost in the distribution companies. The problem of network reconfiguration can be modeled as a combinatorial optimization problem, in which the combination of switches states that represent the configuration of the network with the lowest level of losses must be determined. To deal with these problems by network reconfiguration, several computational techniques have been proposed. Among these techniques, efficient data structures, such as the Node-Depth Encoding (NDE), enable the radial modeling of the distribution systems and the combined use of the NDE with optimization methods allow the reduction of the search space of the solutions. In order to optimize the processing capacity, this work proposes to deal with the loss minimization problem in Distribution Systems (DSs) by network reconfiguration using the Hardware Parallelized NDE (HP-NDE) proposed in (GOIS, 2011) to accelerate the network reconfiguration. Thus, a combinatorial problem is addressed in hardware accelerators, reducing significantly the computational cost due to the high degree of the parallelism in the process of search of the solution search. In this context, it was proposed the extension of the HP-NDE, from modifications in the communication bus of the original HP-NDE to send and receive more efficiently the data that represent the DSs. Moreover, the problem of loss reduction was mapped in a minimum spanning forest problem with degree constraint (dc-MSFP), by using an approximation that use a weights heuristic based on the information of the electrical magnitudes and topological characteristics of the network. From the extension of the HP-RNP and the mapping of the problem in a dc-MSFP, it was possible to obtain solutions of the good quality (close to optimal) in a time significantly reduced when compared to the other approaches.

A reconfiguração de redes é uma técnica utilizada para alterar topologias de redes por meio da mudança dos estados das chaves normalmente aberta e normalmente fechada. Essa técnica é muito utilizada para tratar problemas relacionados ao excesso de perdas ôhmicas em uma rede elétrica. Tais perdas representam um custo considerável no faturamento das empresas distribuidoras. O problema de redução de perdas via reconfiguração de redes pode ser modelado como um problema de otimização combinatória, em que se deve determinar a combinação de estados de chaves que correspondem a configuração radial da rede com menor nível de perdas. De modo a lidar com esse problema por reconfiguração da redes, diversas técnicas computacionais têm sido propostas. Dentre essas técnicas, estruturas de dados eficientes, como a Representação nó-profundidade (RNP), viabilizam a modelagem radial dos sistemas de distribuição (SDs) e o uso combinado com métodos de otimização possibilitam uma redução do espaço de busca de soluções consequentemente pode-se obter melhores soluções. Para otimizar a capacidade de processamento, este trabalho propõe tratar o problema de redução de perdas em SDs via reconfiguração de redes em aceleradores de hardware utilizando da arquitetura de hardware paralelizada em FPGA baseada na RNP (HP-RNP) proposta em (GOIS, 2011). Assim, um problema combinatório é tratado em aceleradoras de hardware reduzindo significativamente o custo computacional devido ao alto grau de paralelismo no processo de busca por soluções. Nesse sentido, foi proposto neste trabalho a extensão da HP-RNP, a partir de modificações no barramento de comunicação da arquitetura original para o envio e recebimentos dos dados que representam os SDs de forma mais eficiente. Além disso, o problema de redução de perdas por reconfiguração de redes foi mapeado em um problema de floresta geradora mínima com restrição de grau (dc-MSFP), a partir de uma aproximação que faz uso de uma heurística de pesos, em que informações relacionadas com grandezas elétricas e características topológicas da rede são transformadas em pesos. A partir da extensão da HP-RNP e do mapeamento do problema em um dc-MSFP, foi possível obter soluções de qualidade (próximas da ótima) em tempo significativamente reduzido quando comparado às outras abordagens. / Network reconfiguration is a technique used to change network topologies by changing the normally open and normally closed switches states. This technique is widely used to problems related to the excess of ohmic losses in distribution companies. Such losses represent a considerable cost in the distribution companies. The problem of network reconfiguration can be modeled as a combinatorial optimization problem, in which the combination of switches states that represent the configuration of the network with the lowest level of losses must be determined. To deal with these problems by network reconfiguration, several computational techniques have been proposed. Among these techniques, efficient data structures, such as the Node-Depth Encoding (NDE), enable the radial modeling of the distribution systems and the combined use of the NDE with optimization methods allow the reduction of the search space of the solutions. In order to optimize the processing capacity, this work proposes to deal with the loss minimization problem in Distribution Systems (DSs) by network reconfiguration using the Hardware Parallelized NDE (HP-NDE) proposed in (GOIS, 2011) to accelerate the network reconfiguration. Thus, a combinatorial problem is addressed in hardware accelerators, reducing significantly the computational cost due to the high degree of the parallelism in the process of search of the solution search. In this context, it was proposed the extension of the HP-NDE, from modifications in the communication bus of the original HP-NDE to send and receive more efficiently the data that represent the DSs. Moreover, the problem of loss reduction was mapped in a minimum spanning forest problem with degree constraint (dc-MSFP), by using an approximation that use a weights heuristic based on the information of the electrical magnitudes and topological characteristics of the network. From the extension of the HP-RNP and the mapping of the problem in a dc-MSFP, it was possible to obtain solutions of the good quality (close to optimal) in a time significantly reduced when compared to the other approaches.

Aplicações têm tradicionalmente utilizado o paradigma de programação sequencial. Com a recente expansão da computação paralela, em particular os processadores multinúcleo e ambientes distribuídos, esse paradigma tornou-se um obstáculo para a utilização dos recursos disponíveis nesses sistemas, uma vez que a maior parte das aplicações tornam-se restrita à execução sobre um único núcleo de processamento. Nesse sentido, este trabalho de mestrado introduz uma abordagem para paralelizar programas sequenciais de forma automática e transparente, diretamente sobre o código-binário, de forma a melhor utilizar os recursos disponíveis em computadores multinúcleo. A abordagem consiste na desmontagem (disassembly) de aplicações Intel x86 e sua posterior tradução para uma linguagem intermediária. Em seguida, são produzidos grafos de fluxo e dependências, os quais são utilizados como base para o particionamento das aplicações em unidades paralelas. Por fim, a aplicação é remontada (assembly) e traduzida novamente para a arquitetura original. Essa abordagem permite a paralelização de aplicações sem a necessidade de esforço suplementar por parte de desenvolvedores e usuários. / Traditionally, computer programs have been developed using the sequential programming paradigm. With the advent of parallel computing systems, such as multi-core processors and distributed environments, the sequential paradigm became a barrier to the utilization of the available resources, since the program is restricted to a single processing unit. To address this issue, we introduce a transparent automatic parallelization methodology using a binary rewriter. The steps involved in our approach are: the disassembly of an Intel x86 application, transforming it into an intermediary language; analysis of this intermediary code to obtain flow and dependency graphs; partitioning of the application into parallel units, using the obtained graphs and posterior reassembly of the application, writing it back to the original Intel x86 architecture. By transforming the compiled application software, we aim at obtaining a program which can explore the parallel resources, with no extra effort required either from users or developers.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-07-28T12:46:53Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_diogotc_final.pdf: 7303783 bytes, checksum: f9959e8bb63b91d247de9903c2484d35 (MD5) / Made available in DSpace on 2016-07-28T12:46:53Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_diogotc_final.pdf: 7303783 bytes, checksum: f9959e8bb63b91d247de9903c2484d35 (MD5) Previous issue date: 2016-01-29 / Esta tese apresenta uma metodologia de paralelização híbrida aplicada ao Método dos Elementos Discretos (DEM - Discrete Element Method) que combina MPI e OpenMP com o intuito de melhoria de desempenho computacional. A metodologia utiliza estratégias de decomposição de domínio visando a distribuição do cálculo de modelos de larga escala em um cluster. A técnica proposta também particiona a carga de trabalho de cada subdomínio entre threads. Este procedimento adicional visa obter maiores desempenhos computacionais através do ajuste de utilização de mecanismos de troca de mensagens entre processos e paralelização por threads. O objetivo principal da técnica é reduzir os elevados tempos de comunicação entre processos em ambientes computacionais de memória compartilhada tais como os processadores modernos. A divisão de trabalho por threads emprega a curva de preenchimento de espaço de Hilbert (HSFC) visando a melhoria de localidade dos dados e evitando custos computacionais (overheads) resultantes de ordenações constantes para o vetor de partículas. As simulações numéricas apresentadas permitem avaliar os métodos de decomposição de domínio, técnicas de particionamento, mecanismos de controle de acesso à memória, dentre outros. Algoritmos distintos de particionamento e diferentes estratégias de solução paralela são abordados para ambientes computacionais de memória distribuída, compartilhada ou para um modelo híbrido que envolve os dois ambientes. A metodologia desenvolvida e a ferramenta computacional utilizada nas implementações realizadas, o software DEMOOP, fornecem recursos que podem ser aplicados em diversos problemas de engenharia envolvendo modelos de partículas em larga escala. Nesta tese alguns destes problemas são abordados, em especial aqueles relacionados com fluxo de partículas em rampas, em funis de descarga e em cenários reais de deslizamento de terra. Os resultados mostram que as estratégias de execução híbridas atingem, em geral, melhores desempenhos computacionais que aqueles que se baseiam unicamente em troca de mensagens. A técnica de paralelização híbrida desenvolvida também obtém um bom controle de balanço de carga entre threads. Os estudos de caso apresentados apresentam boa escalabilidade e eficiências paralelas. O método proposto permite uma execução configurável de modelos numéricos do DEM e introduz uma estratégia combinada que melhora localidade dos dados e um balanceamento de carga iterativo. / This thesis introduces a methodology of hybrid parallelization applied to the Discrete Element Method (DEM) that combines MPI and OpenMP to improve computational performance. The methodology uses domain decomposition strategies to distribute the computation of large-scale models in a cluster. It also partitions the workload of each subdomain among threads. This additional procedure aims to reach higher computational performance by adjusting the usage of message passing artifacts and threads. The main objective is to reduce the expensive communications between processes in computer resources of shared memory such as modern processors. The work division by threads employs Hilbert Space Filling Curves (HSFC) in order to improve data-locality and to avoid the overhead caused by the dynamical sorting of the particles array. Presented numerical simulations allow to evaluate several domain decomposition schemes, partitioning methods, mechanisms of memory access control, among others. The work investigate distinct schemes of parallel solution for both distributed and shared memory environments. The method and the computational tool employed, the software DEMOOP, provide applied resources for several engineering problems involving large scale particle models. Some of these problems are presented on this thesis, such as the particle flows that happen on inclined ramps, discharge hoppers and real scenarios of landslides. The results shows that the hybrid executions reach better computational performance than those based on message passing only, including a good control of load balancing among threads. Case studies present good scalability and parallel efficiencies. The proposed approach allows a configurable execution of numerical models and introduces a combined scheme that improves data-locality and an iterative workload balancing.

Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))

Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))

Submitted by Maicon Juliano Schmidt (maicons) on 2015-03-30T11:51:21Z No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) / Made available in DSpace on 2015-03-30T11:51:21Z (GMT). No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) Previous issue date: 2014-01-31 / Nenhuma / Este trabalho apresenta um algoritmo de otimização baseado na metaheurística dos Sistemas Imunológicos Artificiais, princípios de Teoria dos Jogos, Co-evolução e Paralelização. Busca-se a combinação adequada dos conceitos de Teoria dos Jogos, Co-evolução e Paralelização aplicados ao algoritmo AISO (Artificial Immune System Optimization) para resolução do Problema de Alocação de Berços (PAB). Dessa maneira, o algoritmo é formalizado a partir das técnicas citadas, formando o PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Inicialmente, foram realizados experimentos visando à sintonia dos parâmetros empregados nas diferentes versões da ferramenta desenvolvida. Com base nas melhores configurações identificadas, foram realizados experimentos de avaliação através da solução de um conjunto de instâncias do PAB. Os resultados obtidos permitiram a indicação da versão co-evolutiva associada à teoria dos jogos como a melhor para solução do problema em estudo. / This paper presents an optimization algorithm based on metaheuristic of Artificial Immune Systems, principles of Game Theory, Co-evolution and parallelization. The objective is find the appropriate combination of the concepts of Game Theory, Co-evolution and Parallelization applied to AISO algorithm (Artificial Immune System Optimization) for solving the Berth Allocation Problem (BAP). Thus, the algorithm is formalized from the above mentioned techniques, forming the PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Initially, experiments aiming to tune the parameters were performed using different versions of the tool developed. Based on the identified best settings, evaluation experiments were carried out by solving a set of instances of the PAB. The results obtained allowed the appointment of co-evolutionary version associated with game theory as the best solution to the problem under study.