Les systèmes distribués, tels que les grilles, sont utilisés aujourd’hui pour l’exécution des grandes applications parallèles. Quelques caractéristiques de ces systèmes sont l’interconnexion complexe de ressources qui pourraient être présent et de la facile passage à l’échelle. La complexité d’interconnexion vient, par exemple, d’un nombre plus grand de directives de routage pour la communication entre les processus et une latence variable dans le temps. La passage à l’échelle signifie que des ressources peuvent être ajoutées indéfiniment simplement en les reliant à l’infrastructure existante. Ces caractéristiques influencent directement la façon dont la performance des applications parallèles doit être analysée. Les techniques de visualisation traditionnelles pour cette analyse sont généralement basées sur des diagrammes de Gantt que disposent la liste des composants de l’application verticalement et metent la ligne du temps sur l’axe horizontal. Ces représentations visuelles ne sont généralement pas adaptés à l’analyse des applications exécutées en parallèle dans les grilles. La première raison est qu’elles n’ont pas été conçues pour offrir aux développeurs une analyse qui montre aussi la topologie du réseau des ressources. La deuxième raison est que les techniques de visualisation traditionnels ne s’adaptent pas bien quand des milliers d’entités doivent être analysés ensemble. Cette thèse tente de résoudre les problèmes des techniques traditionnelles dans la visualisation des applications parallèles. L’idée principale est d’exploiter le domaine de la visualisation de l’information et essayer d’appliquer ses concepts dans le cadre de l’analyse des programmes parallèles. Portant de cette idée, la thèse propose deux modèles de visualisation : les trois dimensions et le modèle d’agrégation visuelle. Le premier peut être utilisé pour analyser les programmes parallèles en tenant compte de la topologie du réseau. L’affichage lui-même se compose de trois dimensions, où deux sont utilisés pour indiquer la topologie et la troisième est utilisée pour représenter le temps. Le second modèle peut être utilisé pour analyser des applications parallèles comportant un très grand nombre de processsus. Ce deuxième modèle exploite une organisation hiérarchique des données utilisée par une technique appelée Treemap pour représenter visuellement la hiérarchie. Les implications de cette thèse sont directement liées à l’analyse et la compréhension des applications parallèles exécutés dans les systèmes distribués. Elle améliore la compréhension des modes de communication entre les processus et améliore la possibilité d’assortir les motifs avec cette topologie de réseau réel sur des grilles. Bien que nous utilisons abondamment l’exemple de la topologie du réseau, l’approche pourrait être adapté, avec presque pas de changements, à l’interconnexion fourni par un middleware d’une interconnexion logique. Avec la technique d’agrégation, les développeurs sont en mesure de rechercher des patterns et d’observer le comportement des applications à grande échelle. / Sistemas distribuídos tais como grids são usados hoje para a execução de aplicações paralelas com um grande número de processos. Algumas características desses sistemas são a presença de uma complexa rede de interconexão e a escalabilidade de recursos. A complexidade de rede vem, por exemplo, de largura de banda e latências variáveis ao longo do tempo. Escalabilidade é a característica pela qual novos recursos podem ser adicionados em um grid apenas através da conexão em uma infraestrutura pré-existente. Estas características influenciam a forma como o desempenho de aplicações paralelas deve ser analisado. Esquemas tradicionais de visualização de desempenho são usualmente baseados em gráficos Gantt com uma dimensão para listar entidades monitoradas e outra para o tempo. Visualizações como essa não são apropriadas para a análise de aplicações paralelas executadas em grid. A primeira razão para tal é que elas não foram concebidas para oferecer ao desenvolvedor uma análise que mostra a topologia dos recursos e a relação disso com a aplicação. A segunda razão é que técnicas tradicionais não são escaláveis quando milhares de entidades monitoradas devem ser analisadas conjuntamente. Esta tese tenta resolver estes problemas encontrados em técnicas de visualização tradicionais para a análise de aplicações paralelas. A idéia principal consiste em explorar técnicas da área de visualização da informação e aplicá-las no contexto de análise de programas paralelos. Levando em conta isto, esta tese propõe dois modelos de visualização: o de três dimensões e o modelo de agregação visual. O primeiro pode ser utilizado para analisar aplicações levando-se em conta a topologia da rede dos recursos. A visualização em si é composta por três dimensões, onde duas são usadas para mostrar a topologia e a terceira é usada para representar o tempo. O segundo modelo pode ser usado para analisar aplicações paralelas com uma grande quantidade de processos. Ela explora uma organização hierárquica dos dados de monitoramento e uma técnica de visualização chamada Treemap para representar visualmente a hierarquia. Os dois modelos representam uma nova forma de analisar aplicação paralelas visualmente, uma vez que eles foram concebidos para larga-escala e sistemas distribuídos complexos, como grids. As implicações desta tese estão diretamente relacionadas à análise e ao entendimento do comportamento de aplicações paralelas executadas em sistemas distribuídos. Um dos modelos de visualização apresentados aumenta a compreensão dos padrões de comunicação entre processos e oferece a possibilidade de observar tal padrão com a topologia de rede. Embora a topologia de rede seja usada, a abordagem pode ser adaptada sem grandes mudanças para levar em conta interconexões lógicas de bibliotecas de comunicação. Com a técnica de agregação apresentada nesta tese, os desenvolvedores são capazes de observar padrões de aplicações paralelas de larga escala. / Highly distributed systems such as grids are used today for the execution of large-scale parallel applications. Some characteristics of these systems are the complex resource interconnection that might be present and the scalability. The interconnection complexity comes from the different number of hops to provide communication among applications processes and differences in network latencies and bandwidth. The scalability means that the resources can be added indefinitely just by connecting them to the existing infrastructure. These characteristics influence directly the way parallel applications performance must be analyzed. Current traditional visualization schemes to this analysis are usually based on Gantt charts with one dimension to list the monitored entities and the other dimension dedicated to time. These visualizations are generally not suited to parallel applications executed in grids. The first reason is that they were not built to offer to the developer an analysis that also shows the network topology of the resources. The second reason is that traditional visualization techniques do not scale well when thousands of monitored entities must be analyzed together. This thesis tries to overcome the issues encountered on traditional visualization techniques for parallel applications. The main idea behind our efforts is to explore techniques from the information visualization research area and to apply them in the context of parallel applications analysis. Based on this main idea, the thesis proposes two visualization models: the three-dimensional and the visual aggregation model. The former might be used to analyze parallel applications taking into account the network topology of the resources. The visualization itself is composed of three dimensions, where two of them are used to render the topology and the third is used to represent time. The later model can be used to analyze parallel applications composed of several thousands of processes. It uses hierarchical organization of monitoring data and an information visualization technique called Treemap to represent that hierarchy. Both models represent a novel way to visualize the behavior of parallel applications, since they are conceived considering large-scale and complex distributed systems, such as grids. The implications of this thesis are directly related to the analysis and understanding of parallel applications executed in distributed systems. It enhances the comprehension of patterns in communication among processes and improves the possibility of matching this patterns with real network topology of grids. Although we extensively use the network topology example, the approach could be adapted with almost no changes to the interconnection provided by a middleware of a logical interconnection. With the scalable visualization technique, developers are able to look for patterns and observe the behavior of large-scale applications.

Orientador: Rodolfo Jardim de Azevedo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T02:02:14Z (GMT). No. of bitstreams: 1 Goldstein_FelipePortavales_M.pdf: 2303926 bytes, checksum: c44512059a990654552904a0f94d74f2 (MD5) Previous issue date: 2010 / Resumo: A adoção de processadores com múltiplos núcleos pela indústria, levou à necessidade de novas técnicas para facilitar a programação de software paralelo. A técnica chamada memórias transacionais é uma das mais promissoras. Esta técnica é capaz de executar tarefas concorrentemente de forma otimista, o que permite um bom desempenho. Outra vantagem é que a sua utilização é muito mais simples comparada com a técnica clássica de exclusão mútua. Neste trabalho é proposto o primeiro modelo de memória transacional para arquiteturas híbridas, neste caso a arquitetura alvo é o processador Cell BE. O processador Cell BE é especialmente complexo por causa das dificuldades que a arquitetura deste processador impõe ao programador quando se necessita acessar a memória global compartilhada. O modelo proposto age como uma camada entre o programa e a memória principal, permitindo um acesso transparente aos dados, garantindo coerência e realizando o controle de concorrência de forma automática. O modelo proposto utiliza Software Cache combinado com a memória transacional para facilitar o acesso à memória externa a partir dos SPEs. Ele foi implementado e testado utilizando 8 aplicativos benchmark diferentes, mostrando sua viabilidade para casos de uso reais. Foi feita uma análise detalhada de cada parte da arquitetura proposta com relação ao impacto no desempenho geral do sistema. Este modelo foi capaz de obter um desempenho até duas vezes superior à implementação utilizando um mutex global. As vantagens da utilização se concentram principalmente na facilidade de uso, garantias de coerência e por evitar alguns tipos de bugs que seriam comuns em uma implementação com mutex, como por exemplo dead-locks. Este trabalho obteve o prêmio de melhor artigo no SBAC-PAD 2008 / Abstract: The adoption of multi-core processors by the industry has pushed towards the development of new techniques to simplify programming parallel software. The technique called transactional memories is one of the most promising. This technique is able to execute multiple tasks concurrently in an optimistic way to achieve a better performance. Another advantage is that the usage of this technique is simpler than the classic mutual exclusion. This work proposes the first transactional memory model for hybrid architectures, in this case the target architecture is the Cell BE processor. The Cell BE is specially complex because of the dificulties when acessing the main shared memory from one of the SPEs. The proposed model acts as a layer between the program running and the main shared memory, allowing transparent access to the data, guaranteeing coherency and automatic concurrency control. The proposed model uses a Software Cache combined with a transactional memory to facilitate the acess to the main memory from the SPEs. This model was implemented and tested using 8 benchmark applications, showing its feasability in real use cases. A detailed analysis of its internal parts has been made to show the impact of each part in the overal system performance. The model was able to achieve a performance up to two times better than a similar implementation using a global mutex. The advantages of this model rely on its usability, coherency guaranty and because it is able to avoid concurrency programming bugs such as dead-lock, which are common in a mutex implementation. This work won the best paper award at SBAC-PAD 2008 / Mestrado / Arquitetura de Computadores / Mestre em Ciência da Computação

Orientador: Rodolfo Jardim de Azevedo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T06:45:02Z (GMT). No. of bitstreams: 1 Hoyos_FranciscoRafaelLorenzo_M.pdf: 663609 bytes, checksum: 9bf12382c86fbf499da0f33713f074a4 (MD5) Previous issue date: 2009 / Resumo: O Cell Broadand Engine (Cell BE) é um processador com arquitetura de múltiplos núcleos heterogêneos, voltado para o uso em aplicações de alto desempenho. Talvez mais conhecido como o processador do Playstation 3 da Sony, ele também está presente aos milhares no supercomputador Roadrunner da IBM. Entretanto, o SDK do Cell BE não suporta o desenvolvimento de aplicações sem Java. Como é sabido, Java é uma das linguagens mais utilizadas hoje em dia, nas mais variadas plataformas de hardware e para quase todos os tipos de aplicações. Este trabalho introduz um novo modelo para a execução de programas Java no Cell BE. Esse modelo permite ao programador Java executar tarefas (partes do código Java do programa principal) nos Synergistic Processing Elements (SPE), que são núcleos especializados do Cell BE, maiores responsáveis pelo grande poder de processamento desse chip. Enquanto outras soluções tentam esconder completamente a arquitetura de múltiplos núcleos heterogêneos do Cell BE, a nova proposta expõe um modelo de memória explicitamente distribuída, habilitando o programador Java a definir exatamente qual código deve executar nos SPEs. A viabilidade do modelo é então demonstrada através da melhoria de desempenho obtida consistentemente com vários programas executados em uma máquina virtual Java modificada para suportar a plataforma Cell BE. Com seis SPEs, esses programas executam, em média, aproximadamente duas vezes mais rápido do que os mesmos programas na máquina virtual Java original / Abstract: The Cell Broadband Engine (Cell BE) is a processor with a heterogeneous multicore architecture, targeted at high performance applications. Perhaps best known as the processor of Sony's PlayStation 3, it is also used (thousands of them) in the IBM Roadrunner supercomputer. However, the Cell BE SDK does not support Java application development. It is well known that Java is currently one of the most widely used languages, being present on many different hardware platforms and in almost all types of applications. This work introduces a new model for the execution of Java programs on the Cell BE. Such model allows the Java programmer to execute tasks (pieces of the main program's Java code) on the Synergistic Processing Elements (SPE), which are highly specialized cores in the Cell BE and are the main source of the chip's huge processing power. While other solutions try to completely hide the Cell BE's heterogeneous multicore architecture, this new proposal exposes an explicit distributed memory model, empowering the Java programmer to define exactly what code runs on the SPEs. The feasibility of the model is demonstrated by means of consistent performance improvements achieved with several programs executed on a Java virtual machine, which has been modified to support the Cell BE platform. With six SPEs those programs run, on average, around twice as fast as the same programs on the original Java virtual machine / Mestrado / Linguagens de Programação / Mestre em Ciência da Computação

[pt] Apresentamos um método computacional na GPU que lida com eventos de fragmentação dinâmica, simulados por meio de elementos de zona coesiva. O trabalho é dividido em duas partes. Na primeira parte, tratamos o pré-processamento de informações e a verificação de corretude e eficácia da inserção dinâmica de elementos coesivos em malhas grandes. Para tal, apresentamos uma simples estrutura de dados topológica composta de triângulos. Na segunda parte, o código explícito de dinâmica é apresentado, que implementa a formulação extrínsica de zona coesiva, onde os elementos são inseridos dinamicamente quando e onde forem necessários. O principal desafio da implementação na GPU, usando a formulação de zona coesiva extrínsica, é ser capaz de adaptar dinamicamente a malha de uma forma consistente, inserindo elementos coesivos nas facetas fraturadas. Para isso, a estrutura de dados convencional usada no código de elementos finitos (baseado na incidência de elementos) é estendida, armazenando, para cada elemento, referências para elementos adjacentes. Para evitar concorrência ao acessar entidades compartilhadas, uma estratégia convencional de coloração de grafos é adotada. Na fase de pré-processamento, cada nó do grafo (elementos na malha) é associado a uma cor diferente das cores de seus nós adjacentes. Desta maneira, elementos da mesma cor podem ser processados em paralelo sem concorrência. Todos os procedimentos necessários para a inserção de elementos coesivos nas facetas fraturadas e para computar propriedades de nós são feitas por threads associados a triângulos, invocando um kernel por cor. Computações em elementos coesivos existentes também são feitas baseadas nos elementos adjacentes. / [en] A GPU-based computational framework is presented to deal with dynamic failure events simulated by means of cohesive zone elements. The work is divided into two parts. In the first part, we deal with pre-processing of the information and verify the effectiveness of dynamic insertion of cohesive elements in large meshes. To this effect, we employ a simplified topological data structured specialized for triangles. In the second part, we present an explicit dynamics code that implements an extrinsic cohesive zone formulation where the elements are inserted on-the-fly, when needed and where needed. The main challenge for implementing a GPU-based computational framework using extrinsic cohesive zone formulation resides on being able to dynamically adapt the mesh in a consistent way, inserting cohesive elements on fractured facets. In order to handle that, we extend the conventional data structure used in finite element code (based on element incidence) and store, for each element, references to the adjacent elements. To avoid concurrency on accessing shared entities, we employ the conventional strategy of graph coloring. In a pre-processing phase, each node of the dual graph (bulk element of the mesh) is assigned a color different to the colors assigned to adjacent nodes. In that way, elements of a same color can be processed in parallel without concurrency. All the procedures needed for the insertion of cohesive elements along fracture facets and for computing node properties are performed by threads assigned to triangles, invoking one kernel per color. Computations on existing cohesive elements are also performed based on adjacent bulk elements.

[pt] O principal objetivo desta dissertação consiste na geração de novas funcionalidades inteligentes em redes ópticas associadas aos protocolos IP e Gigabit Ethernet, através da utilização de circuitos integrados programáveis operando na taxa do Gigabit. A padronização Ethernet é apresentada através das camadas PHY e MAC, destacando suas funções, interfaces e os tipos de chips disponíveis no mercado. A camada PHY do padrão Ethernet para meios ópticos é detalhada. Algumas tecnologias de chips são discutidas, entre elas o crescimento dedicado, os ASICs, as NPUs e as tecnologias programáveis: FPGAs e CPLDs. O conceito de inteligência óptica e o perfil de camadas equivalentes associados a este conceito são introduzidos. Um novo elemento de rede dedicado à inserção de sinalização na camada óptica é apresentado, destacando-se sua estrutura, sua realização, seu detalhamento para utilização em redes. Diversas montagens experimentais com o elemento desenvolvido são utilizadas para demonstrar as características do sistema, entre elas a eficiência da utilização da tecnologia de FPGAs e a transparência da inteligência na camada óptica para o padrão Ethernet. / [en] The main objective of this work is the generation of new functionalities in optical networks, associated to the Ethernet and IP protocols, by the use of programmable integrated circuits operating in Gigabit rates. The Ethernet standard is presented through its PHY and MAC layers, highlighting its functions, interfaces and the types of commercially available ICs. The Ethernet standard PHY layer for optical media is described. Some IC technologies are discussed, such as dedicated growth, ASICs, NPUs and the programmable technologies: FPGAs e CPLDs. The concept of built-in optical intelligence and a new layers model associated to it are presented. A new network element, dedicated to the insertion of signaling in the optical layer is also presented, and special attention is dedicated to its structure, to its implementation and to the aspects of its use in networks. Several experimental setups using the developed element are shown, demonstrating the characteristics of the system, particularly the efficiency obtained by the use of FPGA technology and the transparency of the optical intelligence with respect to the Ethernet standard.

Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) Previous issue date: 2017-06-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation addresses the class of job scheduling problems with precedence constraints and unit execution times, in identical parallel processors. Such a class of problems is of great importance in computational complexity theory, since small varia- tions in the conditions involved in scheduling make an easy problem very difficult. Two major problems involve the condition of the number of processors, where, if the number of processors is variable, given as input, such problem is proved to be NP-complete, but if the number of processors is fixed, the problem is still open. In this context, the focus of the research involves the problem already proven to be NP-complete, where for which we investigated the main approximation algorithms in the literature and their proofs of approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with 2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs of such algorithms were detailed. As the main contribution of this research, were proved the optimality for specific classes of acyclic directed graphs involving trees (prece- dence trees, such as in-tree and out-tree) for the best approximation algorithms literature. / Esta dissertação aborda a classe de problemas de escalonamento de tarefas com restrições de precedências e tempos unitários em processadores paralelos idênticos. Tal classe de problemas tem uma grande importância em teoria da complexidade computacional, uma vez que pequenas variações nas condições envolvidas no esca- lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes problemas envolvem a condição do número de processadores, onde, se o número de processadores for variável, dado como entrada, tal problema é provado ser NP-completo, mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde para qual se investigou os principais algoritmos aproximativos existentes na literatura e suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal & Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura. As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal contribuição da pesquisa, foram determinados casos especiais ótimos, para classes específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura. / Compreender o que querem em alguns momentos.

Fundação de Amparo a Pesquisa do Estado de Minas Gerais / This work investigates the operation of three phase induction motors in field weakening and high speed regions. Maximum torque per ampère is imposed by using an indirect vector control strategy. Mathematical models that accounts for magnetic saturation is used for simulations and adjustment of controllers used in control algorithm. The driving structure is characterized by the use of VSI static converter with sinusoidal PWM switching strategy and a vector control technique based on orthogonal components. Investigations resulted in the development of a digital simulation using discrete models that turned out generic and reliable, and an experimental system using a low cost fixed point DSP platform. Simulated and experimental results are included and shown the robustness and efficiency of the proposed control system under different operating conditions. / O presente trabalho tem como objetivo estudar a operação de motores de indução trifásicos em regime de enfraquecimento de campo e altas velocidades, com maximização do conjugado por ampère, através de um sistema de acionamento vetorial. Para tanto, foi utilizado uma modelagem matemática completa, por fase, que emprega o conceito de função harmônica magnética e considera as componentes, fundamental e de terceiro harmônico do fluxo de entreferro. A estrutura de acionamento caracteriza-se pela utilização de um inversor de tensão PWM senoidal e da técnica de controle vetorial, esta baseada em componentes ortogonais. A evolução do trabalho resultou no desenvolvimento de uma plataforma de simulação computacional baseada em modelos discretos que é bastante genérica e confiável, e um sistema experimental utilizando um processador digital de sinais de baixo custo com aritmética de ponto fixo. Os resultados de simulação e experimentais que avaliam a eficiência do sistema de controle proposto sob diversas condições de operação e efeitos de dessintonia são apresentados e apontam para robustez do método. / Doutor em Ciências