Com o crescente aumento das funcionalidades dos circuitos integrados, existe um aumento consequente da complexidade do projeto dos mesmos. O fluxo de projeto de circuitos integrados inclui em um de seus passos o roteamento, que consiste em criar fios que interconectam as células do circuito. Devido à complexidade, o roteamento é dividido em global e detalhado. O roteamento global de circuitos VLSI é uma das tarefas mais complexas do fluxo de síntese física, sendo classificado como um problema NP-completo. Neste trabalho, além de realizar um levantamento de trabalhos que utilizam as principais técnicas de paralelismo com o objetivo de acelerar o processamento do roteamento global, foram realizadas análises nos arquivos de benchmark do ISPD 2007/08. Com base nestas análises foi proposto um método que agrupa as redes para então verificar a existência de dependência de dados em cada grupo. Esta verificação de dependência de dados, que chamamos neste trabalho de colisor, tem por objetivo, criar fluxos de redes independentes umas das outras para o processamento em paralelo, ou seja, ajudar a implementação do roteamento independente de redes. Os resultados demonstram que esta separação em grupos, aliada com a comparação concorrente dos grupos, podem reduzir em 67x o tempo de execução do colisor de redes se comparada com a versão sequencial e sem a utilização de grupos. Também foi obtido um ganho de 10x ao comparar a versão com agrupamentos sequencial com a versão paralela. / With the increasing of the functionality of integrated circuits, there is a consequent increase in the complexity of the design. The IC design flow includes the routing in one of its steps, which is to create wires that interconnect the circuit cells. Because of the complexity, routing is divided into global and detailed. The global routing of VLSI circuits is one of the most complex tasks in the flow of physical synthesis and it's classified as an NP-complete problem. In this work, a parallel computing techniques survey was applied to the VLSI global routing in order to accelerate the global routing processing analyzes. This analyzes was performed on the ISPD 2007/08 benchmark files. We proposed a method that groups the networks and then check for data dependence in each group based on these analyzes. This data dependency checking, we call this checking of collider, aims to create flow nets independent of each other for processing in parallel, or help implement the independent routing networks. The results demonstrate that this separation into groups, together with the competitor comparison of groups, can reduce 67x in the collider networks runtime compared with the sequential release and without the use of groups. It was also obtained a gain of 10x when comparing the version with sequential clusters with the parallel version.

Este trabalho teve como finalidade a implementação de um método para a paralelização parcial de programas, escritos na linguagem funcional, SISAL utilizando as bibliotecas do padrão MPI (Message Passing Interface). Para tal, propusemos a transformação dos programas SISAL através do particionamento do loop paralelo forall, através do método de particionamento slice e a utilização do modelo de implementação do paralelismo SPMD (Single Program Multiple Data) no estilo de programas mestre/escravo. A validação de nossa proposta foi obtida através da realização de testes onde foram comparados os resultados obtidos com os programas originais e os programas com as alterações propostas / This work describes a method for the partial parallelization of SISAL programs into programs with calls to MPI routines. We focused on the parallelization of the forall loop (through slicing of the index range). The generated code is a master/slave SPMD program. The work was validated through the compilation of some simple SISAL programs and comparison of the results with an unmodified version

Este trabalho tem o intuito de fazer uso do processamento paralelo na análise não linear de cascas pelo método dos elementos finitos. O elemento finito de casca é obtido com o acoplamento de um elemento de placa e um de chapa. O elemento de placa utiliza formulação de Kirchhof (DKT) para placas delgadas e o elemento de chapa faz uso da formulação livre (FF), introduzindo um grau de liberdade rotacional nos vértices. A análise não-linear com plasticidade utiliza o modelo de plasticidade associada com algoritmo de integração explícito, modelo de escoamento de von Mises com integração em camadas (modelo estratificado), para materiais isotrópicos. A implementação em paralelo é realizada em um sistema com memória distribuída e biblioteca de troca de mensagens PVM (Parallel Virtual Machine). O procedimento não-linear é completamente paralelizado, excetuando a impressão final de resultados. As etapas que constituem o método dos elementos finitos, matriz de rigidez da estrutura e resolução do sistema de equações lineares são paralelizadas. Para o cálculo da matriz de rigidez utiliza-se um algoritmo com decomposição de domínio explícito. Para resolução do sistema de equações lineares utiliza-se o método dos gradientes conjugados com implementação em paralelo. É apresentada uma breve revisão bibliográfica sobre o paralelismo, com comentários sobre perspectivas em análise estrutural / This work aims at using parallel processing for nonlinear analysis of shells through finite element method. The shell finite element is obtained by coupling a plate element with a membrane one. The plate element uses Kirchhoff’s formulation (DKT) for thin plates and the membrane element makes use of the free formulation (FF), introducing a rotational degree of freedom at the vertexes. Nonlinear plastic analysis uses associated plasticity model with explicit integration algorithm, von Mises yelding model with layer integration (stratified model) for isotropic materials. Parallel implementation is done on a distributed memory system and message exchange library PVM (Parallel Virtual Machine). Nonlinear procedure is completely parallelised, but final printing of results. The finite element method steps, structural stifness matrix and solution of the linear equation system are parallelised. An explicit domain decomposition algorithm is used for the stifness matrix evaluation. To solve the linear equation system, one uses conjugated gradients method, with parallel implementation. A brief bibliography about parallelism is presented, with comments on structural analysis perspectives

Com o crescente aumento das funcionalidades dos circuitos integrados, existe um aumento consequente da complexidade do projeto dos mesmos. O fluxo de projeto de circuitos integrados inclui em um de seus passos o roteamento, que consiste em criar fios que interconectam as células do circuito. Devido à complexidade, o roteamento é dividido em global e detalhado. O roteamento global de circuitos VLSI é uma das tarefas mais complexas do fluxo de síntese física, sendo classificado como um problema NP-completo. Neste trabalho, além de realizar um levantamento de trabalhos que utilizam as principais técnicas de paralelismo com o objetivo de acelerar o processamento do roteamento global, foram realizadas análises nos arquivos de benchmark do ISPD 2007/08. Com base nestas análises foi proposto um método que agrupa as redes para então verificar a existência de dependência de dados em cada grupo. Esta verificação de dependência de dados, que chamamos neste trabalho de colisor, tem por objetivo, criar fluxos de redes independentes umas das outras para o processamento em paralelo, ou seja, ajudar a implementação do roteamento independente de redes. Os resultados demonstram que esta separação em grupos, aliada com a comparação concorrente dos grupos, podem reduzir em 67x o tempo de execução do colisor de redes se comparada com a versão sequencial e sem a utilização de grupos. Também foi obtido um ganho de 10x ao comparar a versão com agrupamentos sequencial com a versão paralela. / With the increasing of the functionality of integrated circuits, there is a consequent increase in the complexity of the design. The IC design flow includes the routing in one of its steps, which is to create wires that interconnect the circuit cells. Because of the complexity, routing is divided into global and detailed. The global routing of VLSI circuits is one of the most complex tasks in the flow of physical synthesis and it's classified as an NP-complete problem. In this work, a parallel computing techniques survey was applied to the VLSI global routing in order to accelerate the global routing processing analyzes. This analyzes was performed on the ISPD 2007/08 benchmark files. We proposed a method that groups the networks and then check for data dependence in each group based on these analyzes. This data dependency checking, we call this checking of collider, aims to create flow nets independent of each other for processing in parallel, or help implement the independent routing networks. The results demonstrate that this separation into groups, together with the competitor comparison of groups, can reduce 67x in the collider networks runtime compared with the sequential release and without the use of groups. It was also obtained a gain of 10x when comparing the version with sequential clusters with the parallel version.

Made available in DSpace on 2014-06-12T15:54:52Z (GMT). No. of bitstreams: 2 arquivo2015_1.pdf: 2391415 bytes, checksum: 09ab851c629f8ccc9ea982e2c53f53b3 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / A recente evolução na arquitetura dos dispositivos lógicos programáveis, como os FPGAs (Field Programmable Gate Array), associada à demanda por desempenho exigida em aplicações de computação científica, despertou a atenção de projetistas de supercomputadores que têm investido na criação de plataformas híbridas, associando processadores de propósito geral a co-processadores baseados em FPGAs, em busca de melhores níveis de aceleração. Uma arquitetura que incorpore um ou mais processadores de propósito geral e FPGAs num link de alta velocidade é chamada computador reconfigurável de alto desempenho. Este tipo de configuração requer, em geral, uma alta largura de banda entre o processador e o FPGA, necessário para que os ganhos com a execução em hardware superem o gargalo na comunicação. O sucesso dessas plataformas depende de características como: recursos presentes no FPGA, disponibilidade de memória na arquitetura, largura de banda e capacidade de escalabilidade das mesmas. Ao mesmo tempo, uma análise adequada do problema e um particionamento hardware/software eficiente, são necessários. Neste caso, processos com características de controle devem ser executados no processador de propósito geral e a computação intensiva deve ser executada em FPGA, onde podem ser exploradas características como paralelismo de execução e reuso de dados. Neste trabalho, são estudadas as principais características de alguns dos computadores reconfiguráveis de alto desempenho existentes. Além disso, como estudo de caso, é apresentada a análise e desenvolvimento de uma das importantes operações da computação científica: a multiplicação de matrizes, objetivando uma das plataformas estudadas, a plataforma RASC (Reconfigurable Application-Specific Computing), desenvolvida pela Silicon Graphics. A arquitetura proposta no estudo de caso visa, a partir da análise do problema e da avaliação dos recursos disponíveis na plataforma alvo, a obtenção de melhores resultados de desempenho quando comparado à execução em plataformas convencionais, baseadas em processadores de propósito geral. Para tanto, características como paralelismo e o reuso de dados são exploradas. A partir do projeto desenvolvido, é apresentado um modelo para avaliação de desempenho do multiplicador que pode ser aplicado às demais plataformas estudadas

Made available in DSpace on 2014-06-12T15:03:44Z (GMT). No. of bitstreams: 2 arquivo2323_1.pdf: 3871578 bytes, checksum: 7e9177d6650f3b741144b1d9ea52512c (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / O objetivo deste trabalho foi o estudo de sepultamentos humanos localizados no sítio arqueológico da antiga igreja da Sé em Salvador, na Bahia, e que apresentavam colares de contas de culturas religiosas de origem africana. O contexto arqueológico em que se encontraram esses vestígios levou, após a análise, à hipótese de práticas rituais derivadas de sistemas religiosos que coexistiram paralelamente. Para verificar essa hipótese, buscou-se, inicialmente, comprovar a relação entre as referidas contas e a religiosidade africana. Assim, consultaram-se especialistas em culturas africanas, (professor Waldeloir Rego), que pela característica das contas certificou essa relação. Utilizou-se ainda a iconografia de contas dedicadas aos orixás, a partir de imagens encontradas em catálogos fotográficos, e no acervo do Museu afro-brasileiro da Universidade Federal da Bahia. Soma-se a estas fontes referencias bibliográficas. A análise da pesquisa arqueológica que gerou este trabalho, pela localização estratigráfica dos sepultamentos, aponta para uma cronologia entre os séculos XVIII e XIX. Considera-se também as fontes documentas que possibilitaram a pesquisa. Finaliza-se o trabalho demonstrando que a presença destes vestígios arqueológicos no contexto apresentado explica-se pela dualidade religiosa em que viveram os negros escravizados na cidade de Salvador do referido período. Aponta-se, especialmente, para uma análise dos conceitos de sincretismo e paralelismo religioso e seus desdobramentos no plano pessoais e institucionais

En el área de Ingeniería de Procesos abundan los problemas de optimización no lineales. En busca de formulaciones más realistas ha aumentado la exigencia de un modelado riguroso. Como complejidades incorporadas, al aumento de la cantidad de variables continuas y restricciones no lineales se le suman la presencia de variables binarias. En muchos casos los problemas se resuelven mediante la relajación de variables y condiciones, así generando subproblemas no lineales cuya resolución se realiza a través de aproximaciones lineales y cuadráticas. La pregunta formulada en esta tesis es la siguiente ¿Podemos lograr eficiencia sin tener que relajar el problema? Es decir ¿podemos conseguir soluciones del modelo original en tiempos razonables? En esta tesis proponemos explotar el Método del Gradiente Espectral Proyectado (SPG) mediante su refundación a partir del paradigma paralelo. El SPG es un método de optimización global no monótono para problemas de programación no lineal, con características diferentes a las exhibidas por los métodos clásicos de gradiente proyectado. La no monotonicidad y una elección particular de la longitud del paso permiten aprovechar situaciones especiales que se presentan en muchos problemas, acelerando la convergencia con mínimos costos de almacenamiento de datos. Entre sus características más atractivas aparece su bajo costo en operaciones: SPG no calcula matrices hessianas ni resuelve sistemas lineales. SPG sólo utiliza productos matriz vector y una estrategia de búsqueda lineal no monótona para garantizar convergencia global. Combinado con un esquema de Lagrangiano Aumentado, el método se muestra como una herramienta muy prometedora para el abordaje de problemas muy exigentes en cuanto a esfuerzo computacional y eficiencia. Sus puntos débiles se encuentran en el requerimiento de muchas búsquedas lineales para obtener un nuevo iterado, y en la necesidad de una buena aproximación del gradiente cuando éste no está disponible en forma analítica. En problemas de aplicaciones industriales estos dos aspectos pueden devenir en verdaderos cuellos de botella del algoritmo. En consecuencia, el bajo costo aritmético por iteración no se ve reflejado en el tiempo total de resolución. El auge del desarrollo en la programación en paralelo hace que este paradigma se presente como un recurso que ofrece una gran oportunidad para superar estos inconvenientes. El objetivo de esta tesis fue el desarrollo y análisis del desempeño de una versión eficiente del algoritmo SPG programado en paralelo, asumiendo desconocimiento de expresiones analíticas de la función objetivo o de los gradientes. Este escenario a menudo se presenta en los problemas de optimización en ingeniería de procesos con gran cantidad de variables y restricciones no lineales. La nueva versión del algoritmo SPG genera una sucesión de iterados que es alternativa a la que genera la versión secuencial lo que lo hace más competitivo, pero manteniendo la robustez de convergencia que posee el método SPG original. Se desarrollaron e implementaron dos versiones del algoritmo paralelo: una fue concebida para ejecutarse eficientemente sobre una arquitectura distribuida mediante pasaje de mensajes sobre una red de área local estándar, y la otra fue diseñada para ejecutarse sobre una arquitectura de memoria local compartida. La experimentación numérica se realizó sobre un cluster de 8 procesadores y en una computadora multicore de 12 núcleos. Se demostró en forma teórica la eficiencia esperada. Además, hemos contrastado estos desarrollos teóricos con resultados empíricos obtenidos en algunos problemas de diseño relacionados a plantas de procesos industriales, ubicando así a este resolvedor paralelo como una herramienta competitiva frente a los resolvedores clásicos de paquetes comerciales. / There are many nonlinear optimization problems in the area of Process Engineering. In the search of more realistic formulations the need of more rigorous modeling has grown. The presence of binary variables, the increasing amount of continuous variables and nonlinear constraints count among the incorporated complexities. In many cases the problems are solved by relaxing variables and conditions, thus generating nonlinear subproblems whose resolution is carried out through linear and quadratic approximations. The question posed in this thesis is the following: Can we achieve efficiency without having to relax the problem? I mean: Can we get the original model solutions in reasonable time? In this thesis we propose to exploit the Spectral Projected Gradient method (SPG) by its relaunching from the parallel paradigm. SPG is a non-monotone global optimization method for nonlinear programming problems, its features being different from those exhibited by the classical projectedgradient methods. The non-monotonicity and a particular choice of the step length allow to exploit special situations that arise in many problems, accelerating the convergence with minimal data-storage costs. Its low operating cost features among its most attractive attributes SPG neither calculates Hessian matrices nor solves linear systems. SPG just performs matrix vector products and a non-monotone line-search strategy in order to ensure global convergence. When combined with an Augmented Lagrangian scheme, the method looks like a promising tool for addressing demanding problems in terms of computational effort and efficiency. Its weaknesses lie in the requirement of too many line-searches for a new iterate, and in the need for a good approximation of the gradient when it is not available in analytical form. In industrial application these two mentioned aspects may become real bottlenecks in the algorithm. In consequence, the low arithmetic cost per iteration is not reflected in the total elapsed time of resolution. The boom development in parallel programming presents this paradigm as a resource that provides a great opportunity to overcome these drawbacks. The goal of this thesis was the development and analysis of the performance of an efficient version of the SPG algorithm programmed in parallel, assuming lack of knowledge about the analytical expressions of the objective function or gradients. This scenario often appears in process engineering optimization problems with many variables and non-linear constraints. The new version of the SPG algorithm generates a sequence of iterates that is alternative to the one generated by the sequential version. In this way, the proposed version becomes more competitive, while maintaining the robustness of the original method. Two versions of the parallel algorithm were developed and implemented: one of them was conceived to run efficiently on a distributed architecture by using message passing on a standard local area network, and another one was designed to run on a shared local-memory architecture. The numerical experiments were performed on a cluster of 8 processors and a 12-core multicore computer. We have proved the expected efficiency theoretically. Besides, we have contrasted these theoretical developments with empirical results in some design problems related to industrial plants processes. thus placing this parallel solver as a competitive tool against classical commercial packages.

Made available in DSpace on 2014-12-17T15:48:10Z (GMT). No. of bitstreams: 1 AparecidaLM_DISSERT.pdf: 8059053 bytes, checksum: a243ee0772a785a00c8a0670955a7cae (MD5) Previous issue date: 2014-02-21 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Alongside the advances of technologies, embedded systems are increasingly present in our everyday. Due to increasing demand for functionalities, many tasks are split among processors, requiring more efficient communication architectures, such as networks on chip (NoC). The NoCs are structures that have routers with channel point-to-point interconnect the cores of system on chip (SoC), providing communication. There are several networks on chip in the literature, each with its specific characteristics. Among these, for this work was chosen the Integrated Processing System NoC (IPNoSyS) as a network on chip with different characteristics compared to general NoCs, because their routing components also accumulate processing function, ie, units have functional able to execute instructions. With this new model, packets are processed and routed by the router architecture. This work aims at improving the performance of applications that have repetition, since these applications spend more time in their execution, which occurs through repeated execution of his instructions. Thus, this work proposes to optimize the runtime of these structures by employing a technique of instruction-level parallelism, in order to optimize the resources offered by the architecture. The applications are tested on a dedicated simulator and the results compared with the original version of the architecture, which in turn, implements only packet level parallelism / Com os avan?os tecnol?gicos os sistemas embarcados est?o cada vez mais presentes em nosso cotidiano. Devido a crescente demanda por funcionalidades, as fun??es s?o distribu?das entre os processadores, demandando arquiteturas de comunica??o mais eficientes, como as redes em chip (Network-on-Chip - NoC). As NoCs s?o estruturas que possuem roteadores com canais ponto-a-ponto que interconectam os cores do SoC (System-on-Chip), provendo comunica??o. Existem diversas redes em chip na literatura, cada uma com suas caracter?sticas espec?ficas. Dentre essas, para este trabalho foi a escolhida a IPNoSyS (Integrated Processing NoC System) por ser uma rede em chip com caracter?sticas diferenciadas em rela??o ?s NoCs em geral, pois seus componentes de roteamento acumulam tamb?m a fun??o de processamento, ou seja, possuem unidades funcionais capazes de executar instru??es. Com esse novo modelo, pacotes s?o processados e roteados pela arquitetura do roteador. Este trabalho visa melhorar o desempenho das aplica??es que possuem repeti??o, pois essas aplica??es gastam um tempo maior na sua execu??o, o que se d? pela repetida execu??o de suas instru??es. Assim, este trabalho prop?e otimizar o tempo de execu??o dessas estruturas, atrav?s do emprego de uma t?cnica de paralelismo em n?vel de instru??es, visando melhor aproveitar os recursos oferecidos pela arquitetura. As aplica??es s?o testadas em um simulador dedicado, e seus resultados comparados com a vers?o original da arquitetura, a qual prov? paralelismo apenas em n?vel de pacotes

[pt] A popularização dos processadores multinúcleo e de tecnologias como o hyper-threading evidencia uma mudança de foco na evolução dos processadores. Essa mudança fomenta o interesse por programação concorrente e a exploração de paralelismo para obtenção de melhor desempenho. Entretanto, os modelos atuais para programação concorrente são alvo de críticas recorrentes, o que estimula a elaboração de propostas alternativas. Este trabalho apresenta uma análise crítica do multithreading preemptivo com compartilhamento de memória, um modelo amplamente utilizado para programação concorrente, e faz um breve apanhado de trabalhos que abordam alternativas para programação concorrente. Em seguida, propõe um modelo para programação concorrente estruturado com a linguagem de programação Lua e descreve as suas principais características e vantagens. Finalmente, apresenta os resultados da avaliação de diversos aspectos de uma biblioteca desenvolvida para implementar o modelo proposto. / [en] The popularization of multi-core processors and of technologies such as hyper-threading indicates a different approach to the evolution of processors. This new approach brings about an increased interest in concurrent programming and the exploration of parallelism in order to achieve better performance. However, concurrent programming models now in use are subject to recurring criticism, which stimulates the development of alternative proposals. This work presents a critical analysis of preemptive multithreading with shared memory, which is a widely used model for concurrent programming, and brie y summarizes some studies that deal with alternatives for concurrent programming. It then, proposes a model for concurrent programming structured with the Lua programming language and describes its main characteristics and advantages. Finally, it presents the results of an evaluation of several aspects of a library developed to implement the proposed model.

Este trabalho descreve técnicas de análise estática de compilação baseadas na álgebra e programação linear que buscam otimizar a distribuição de loops forall e array em programas escritos na linguagem S/SAL visando à execução em máquinas paralelas de memória distribuídas. Na fase de alinhamento, nós trabalhamos com o alinhamento de hiperplanos onde objetivo é tentar encontrar as porções dos diferentes arrays que necessitam ser distribuídas juntas. Na fase de divisão, que tenta quebrar em partes independente dados e computações, nós usamos duas funções afins, a função de decomposição de dados e a função de decomposição de computação. A última fase, o mapeamento, distribui os elementos de computação nos elementos de processamento usando um conjunto de inequações. As técnicas foram implementadas num compilador SISAL, mas pode ser usada sem mudanças em outras linguagens de associação simples e com a adição de análise de dependências pode ser usada em linguagens imperativas. / This work describes static compiler analysis techniques based on linear algebra and linear programming for optimizing the distribution of forall loops and of array elements in programs written in the SISAL programming language for distributed memory parallel machines. In the alignment phase, attempt is made in the identification of portions of different arrays that need to be distributed jointly by means of alignment of hyperplanes. In the partitioning phase, effort is made in breaking as even possible the computation and pertinent data in independent parts, by means of using related functions: the data decomposition function and the computation decomposition function. The last phase is dedicated to the mapping, which comprises the distribution of the elements of computation into the existing processing elements by means of a set of inequations. These techniques are being implemented in a SISAL compiler, but can be also used without changes by means of other single assignment languages or, with the addition of dependency analysis when using other set of languages, as well.