BALTAZAR, H. I. Métricas críticas do funcional volume e não-existência de múltiplos buracos negros em espaço-tempo estático. 2017. 67 f. Tese (Doutorado em Matemática) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Andrea Dantas (pgmat@mat.ufc.br) on 2017-07-12T19:24:59Z No. of bitstreams: 1 2017_tese_hibaltazar.pdf: 449308 bytes, checksum: a4275b6fceeb5cb76fe217e956f933cd (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-07-13T12:17:45Z (GMT) No. of bitstreams: 1 2017_tese_hibaltazar.pdf: 449308 bytes, checksum: a4275b6fceeb5cb76fe217e956f933cd (MD5) / Made available in DSpace on 2017-07-13T12:17:46Z (GMT). No. of bitstreams: 1 2017_tese_hibaltazar.pdf: 449308 bytes, checksum: a4275b6fceeb5cb76fe217e956f933cd (MD5) Previous issue date: 2017-07-05 / This work is divided in two parts. In the first one we prove a Böchner type formula for critical metrics of the volume functional on compact manifolds with fixed metric on boundary (such critical metrics are called Miao-Tam critical metrics). As an application, we derive an integral formula that will be crucial to deduce a generalization of a result obtained by Miao and Tam in 2011 for the Einstein case. More precisely, we prove that a Miao-Tam critical metric with parallel Ricci curvature must be isometric to a geodesic ball in a simply connected space form Rn, Sn or Hn. Furthermore, in dimension 3, we prove that critical metrics with non-negative sectional curvature are precisely geodesic balls of R3 or S3. Moreover, we generalize a result due to Kim and Shin (2016), replacing the harmonic Weyl tensor condition by the second order divergence free Weyl tensor condition (i.e., div2W = 0), which is weaker that the former. To be precise, we shall show that a 4-dimensional Miao-Tam critical metric, with boundary isometric to a standard sphere S3 and satisfying div2W = 0 is isometric to a geodesic ball in a simply connected space form R4, S4 or H4. At the same time, we get some rigidity results for positive static triples. In the second part, we study static vacuum space-times, which can be seen as a special case of the V-static metrics for complete Riemannian manifolds with null scalar curvature. In this case, we focus our attention on four dimensions. We prove that there are no multiple black holes on static vacuum space-times with half harmonic Weyl tensor (i.e., divW+ = 0). / Esse trabalho está dividido em duas partes. A primeira delas está relacionada ao estudo de fórmulas tipo-Böchner para métricas críticas do funcional volume em variedades compactas com métrica fixada no bordo (estas são conhecidas como métricas críticas de Miao-Tam). Como aplicação, estabeleceremos uma fórmula integral que permitirá generalizar o resultado obtido por Miao e Tam em 2011 para o caso Einstein, mais precisamente, provaremos que métricas críticas de Miao-Tam com curvatura de Ricci paralelo são isométricas às bolas geodésicas em um espaço forma simplesmente conexo Rn, Sn ou Hn. Se nos restringirmos às variedades com dimensão 3, veremos que tais estruturas se mostram ainda mais rígidas, a saber, provaremos que métricas críticas com curvatura seccional não-negativa são precisamente as bolas geodésicas de R3 ou S3. Além disso, generalizamos o resultado obtido por Kim e Shin (2016) substituindo condição de harmonicidade do tensor de Weyl pela hipótese que o tensor de Weyl tem divergente de segunda ordem nulo (i.e., div2W = 0). Mais precisamente, mostraremos que métricas críticas de Miao-Tam em dimensão 4, com bordo isométrico a esfera S3 e satisfazendo div2W = 0, são isométricas às bolas geodésicas em um espaço forma simplesmente conexo R4, S4 ou H4. Concomitantemente, obtemos resultados de rigidez para triplas estáticas positivas. Na segunda parte do trabalho, estudaremos o espaço-tempo estático no vácuo, o qual pode ser visto como um caso especial das mátricas V-estáticas para variedades completas com curvatura escalar nula. Neste caso, restringiremos nosso estudo a quarta dimensão e provaremos que não existem múltiplos buracos negros em um espaço-tempo estático no vácuo com a parte autodual do tensor de Weyl harmônico (i.e., divW+ = 0).

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.

Em ambientes de Computação de Alto Desempenho, as aplicações científicas dependem dos Sistemas de Arquivos Paralelos (SAP) para obter desempenho de Entrada/Saída (E/S), especialmente ao lidar com grandes quantidades de dados. No entanto, E/S ainda é um gargalo para um número crescente de aplicações, devido à diferença histórica entre a velocidade de processamento e de acesso aos dados. Para aliviar a concorrência causada por milhares de nós que acessam um número significativamente menor de servidores SAP, normalmente nós intermediários de E/S são adicionados entre os nós de processamento e o sistema de arquivos. Cada nó intermediário encaminha solicitações de vários clientes para o sistema, uma configuração que dá a este componente a oportunidade de executar otimizações como o escalonamento de requisições de E/S. O objetivo desta dissertação é avaliar diferentes algoritmos de escalonamento, na camada de encaminhamento de E/S, cuja finalidade é melhorar o padrão de acesso das aplicações, agregando e reordenando requisições para evitar padrões que são conhecidos por prejudicar o desempenho. Demonstramos que os escalonadores FIFO (First In, First Out), HBRR (Handle-Based Round-Robin), TO (Time Order), SJF (Shortest Job First) e MLF (Multilevel Feedback) são apenas parcialmente eficazes porque o padrão de acesso não é o principal fator que afeta o desempenho na camada de encaminhamento de E/S, especialmente para requisições de leitura Um novo algoritmo de escalonamento chamado TWINS é proposto para coordenar o acesso de nós intermediários de E/S aos servidores de dados do sistema de arquivos paralelo. Nossa abordagem reduz a concorrência nos servidores de dados, um fator previamente demonstrado como reponsável por afetar negativamente o desempenho. O algoritmo proposto é capaz de melhorar o tempo de leitura de arquivos compartilhados em até 28% se comparado a outros algoritmos de escalonamento e em até 50% se comparado a não fazer o encaminhamento de requisições de E/S. / In High Performance Computing (HPC) environments, scientific applications rely on Parallel File Systems (PFS) to obtain Input/Output (I/O) performance especially when handling large amounts of data. However, I/O is still a bottleneck for an increasing number of applications, due to the historical gap between processing and data access speed. To alleviate the concurrency caused by thousands of nodes accessing a significantly smaller number of PFS servers, intermediate I/O nodes are typically employed between processing nodes and the file system. Each intermediate node forwards requests from multiple clients to the parallel file system, a setup which gives this component the opportunity to perform optimizations like I/O scheduling. The objective of this dissertation is to evaluate different scheduling algorithms, at the I/O forwarding layer, that work to improve concurrent access patterns by aggregating and reordering requests to avoid patterns known to harm performance. We demonstrate that the FIFO (First In, First Out), HBRR (Handle- Based Round-Robin), TO (Time Order), SJF (Shortest Job First) and MLF (Multilevel Feedback) schedulers are only partially effective because the access pattern is not the main factor that affects performance in the I/O forwarding layer, especially for read requests. A new scheduling algorithm, TWINS, is proposed to coordinate the access of intermediate I/O nodes to the parallel file system data servers. Our approach decreases concurrency at the data servers, a factor previously proven to negatively affect performance. The proposed algorithm is able to improve read performance from shared files by up to 28% over other scheduling algorithms and by up to 50% over not forwarding I/O requests.

Essa dissertação propõe um conjunto de experimentos de simulação em sistemas sujeitos a dois modos de falha com vistas à otimização de confiabilidade. Para tanto, propõe a modelagem analítica e otimização via Algoritmo Genético em sistemas série-paralelo com múltipla escolha de componentes. A ocorrência de falhas em produtos e serviços pode gerar descontentamento aos clientes e até riscos à sua segurança. Em muitos casos práticos, sistemas constituídos por componentes que apresentam dois modos de falha (ou seja, que podem falhar no modo aberto ou curto) são caracterizados por elevada complexidade matemática e analítica para mensuração de sua confiabilidade e estabelecimento de arranjos ótimos. O objetivo da modelagem de estruturas com foco na otimização de confiabilidade consiste em determinar o arranjo que proporciona níveis mais elevados de confiabilidade, ao passo que problemas de alocação de redundância visam à seleção de componentes e níveis apropriados de redundância que maximizem a confiabilidade ou minimizem os custos do sistema frente a restrições de projeto. São estudados os sistemas série-paralelo k-out-of-n (em que qualquer combinação de k dentre n componentes devem operar devidamente). Esse trabalho inova ao apresentar sistemas série-paralelo l-out-of-m, onde a falha de até l dentre m subsistemas não ocasiona falha no sistema geral. Os métodos apresentados fornecem uma contribuição ao estudo de confiabilidade em sistemas com dois modos de falha. / This dissertation proposes a set of simulation experiments in series-parallel systems subject to two failure modes with a view to reliability optimization. Therefore, proposes analytical modeling and optimization by the genetic algorithms in k-out-of-n series-parallel systems and l-out-of-m series-parallel systems, with multiple choice of components. When it comes to products and services, functional errors can lead disgruntlement by customers and even security risks. In many practical cases, systems consisting of two failure modes components (ie, they can fail in open or short mode) rely on highly mathematical and analytical complexity for reliability estimation and establishment of optimal arrangements. The goal of structural modeling focused on reliability optimization is to determine the design that provides the highest reliability levels, while the redundancy allocation problem involves selecting components and appropriate levels of redundancy that either maximize reliability or minimize system costs against design constraints. The k-out-of-n series-parallel structure (any combination of k among n components must operate properly) are studied and this work innovates by presenting l-out-of-m series-parallel systems, where failure of up to l within m subsystems does not cause a overall system failure. The methods presented contribute to the study of reliability in systems with two modes of failure.

Esta tese de doutorado apresenta o projeto de uma arquitetura de memória híbrida energeticamente eficiente baseada em memórias do tipo scratchpad (Hy-SVM) para a codificação paralela de vídeos segundo o padrão HEVC. A codificação de vídeo se destaca como uma parte extremamente complexa nas aplicações de processamento de vídeo. O padrão HEVC traz inovações que complicam fortemente os requerimentos de memória de tais aplicações, principalmente devido a: (a) novas estruturas de codificação, as quais agravam a complexidade computacional por proporcionarem muitas modos possíveis de codificação que devem ser analisados; além do (b) suporte de alto nível à paralelização da codificação por meio do particionamento das unidades de codificação em múltiplos Tiles, o qual provê a aceleração da performance dos codificadores, porém, ao mesmo tempo, adiciona grandes desafios à infraestrutura de memória. O principal gargalo em termos de comunicação com a memória externa e de armazenamento interno (dentro do chip do codificador) é dados pelas informações dos quadros de referência: que consiste em uma série de quadros completos já codificados (e reconstruídos) que devem ser mantidos em memória e acessados de forma intensa durante o processamento dos quadros futuros. Devido ao grande volume de dados que são necessários para representar os quadros de referência, estes são tipicamente armazenados na memória externa dos codificadores (principalmente quando vídeos de alta e ultra alta resolução são processados) A arquitetura proposta Hy-SVM está inserida em um sistema de codificação baseado no particionamento dos quadros do vídeo de entrada em múltiplos Tiles, de forma a habilitar a codificação paralela das informações segundo o padrão HEVC: neste cenário, cada Tile é assinalado para uma específica unidade de processamento do codificador HEVC, o qual executa o processamento dos diferentes Tiles em paralelo. A ideias chave da arquitetura Hy- SVM incluem: projeto e gerenciamento de memórias para a aplicação específica de codificação de vídeo; uso de múltiplos níveis de memórias privadas e compartilhadas, com o objetivo de explorar o reuso de dados intra-Tile e inter-Tiles de forma combinada; uso de memórias do tipo scratchpad (SPMs) para o armazenamento interno da informações de forma eficiente em termos de consumo de energia; projeto de memórias híbridas utilizando as tecnologias SRAM e STTRAM como base. Uma metodologia de projeto é proposta para a arquitetura Hy-SVM, a qual aproveita propriedades específicas da aplicação para, de forma adequada, definir os parâmetros de projeto das memórias híbridas. De forma a prover adaptação em tempo de execução (para ambas as memórias on-chip e off-chip), a arquitetura Hy-SVM integra uma camada de gerenciamento composta pelas seguintes estratégias (1) predição do overlap (sobreposição de acessos), o qual busca identificar o comportamento dos acessos redundantes entre diferentes unidades de processamento do codificador HEVC a partir da análise dos acessos à memória das codificações dos quadros passados do vídeo, com o objetivo de aumentar o potencial de exploração do reuso de dados inter-Tiles; (2) gerenciamento dos acessos à memória externa, responsável por balancear a vazão de dados com a memória acumulada entre as múltiplas unidades de processamento do codificador HEVC paralelo, com o objetivo de melhorar o uso do barramento de comunicação com a memória externa; e (3) gerenciamento de dados das SPMs implementadas a partir de células de memória STT-RAM, o qual alivia estas células de acessos de escrita com alta atividade de chaveamento dos bits armazenados, com o objetivo de aumentar o tempo de vide destas células, bem como reduzir as penalidades relativas à ineficiência dos acessos de escrita nas memórias STT-RAM. O conhecimento específico da aplicação foi utilizado nas estratégias de gerenciamento em tempo de execução das seguintes formas: explorando parâmetros da codificação HEVC e realizando monitorando em tempo real dos acessos à memória realizados pelo codificador Estas informações são utilizadas tanto pelas técnicas de gerenciamento, quanto pelas metodologias de projeto das memórias. Baseadas nas decisões tomadas pela camada de gerenciamento, a arquitetura Hy-SVM integra unidades de gerenciamento de acessos à memória (memory access management units – MAMUs) para controlar as dinâmicas de acesso das memórias SPM privadas e compartilhadas. Além disso, unidades adaptativas de gerenciamento de potência (adaptive power management units – APMUs) são capazes de reduzir o consumo de energia interno do chip do codificador a partir das estimativas precisas de formação dos overlaps. Os resultados obtidos por meio dos experimentos realizados demonstram economias de consumo energético da arquitetura Hy-SVM, quando comparada a trabalhos relacionados, sob diversos cenários de teste. Quando comparada a estratégias de reuso de dados tradicionais para codificadores de vídeo, como o esquema Level-C, a exploração do reuso de dados combinado nos níveis intra-Tile e inter-Tiles provê 69%-79% de redução de energia. Considerando as arquiteturas de memória de vídeo com foco no padrão HEVC, os ganhos variaram desde 2,8% (pior caso) até 67% (melhor caso) Da perspectiva do consumo de energia relacionado à comunicação com a memória externa, a arquitetura Hy-SVM é capaz de melhorar o reuso de dados (por explorar também o reuso de dados inter-Tiles), resultando em um consumo de energia on-chip 11%-17% menor. Além disso, as APMUs contribuem para reduzir o consumo de energia on-chip da arquitetura Hy-SVM em 56%-95%, para os cenários de teste analisados. Desta forma, comparada aos trabalhos relacionados, a arquitetura Hy-SVM apresenta o menor consumo energético on-chip. O gerenciamento da vazão da comunicação com a memória externa é capaz de reduzir as variações de largura de banda em 37%-83%, quando comparado à ordem tradicional de processamento, para cenários de teste com 4 e 16 Tiles sendo processados em paralelo pelo codificador HEVC. O gerenciamento de dados pôde, de forma significativa, estender o tempo de vida das células de memória STT-RAM, alcançando 0,83 de tempo de vida normalizado (métrica adotada para comparação, ficando muito próximo do caso ideal). Além disso, as sobrecargas causadas pela implementação das unidades de gerenciamento não afetam de foram significativa a performance e a eficiência energética da arquitetura Hy- SVM propostas por este trabalho. / This Thesis presents the design of an energy-efficient hybrid scratchpad video memory architecture (called Hy-SVM) for parallel High-Efficiency Video Coding. Video coding stands out as a high complex part in the video processing applications. HEVC standard brought innovations that increase the memory requirements, mainly due to: (a) the novel coding structures, which aggravates the computational complexity by providing a wider range of possibilities to be analyzed; and (b) the high-level parallelism features provided by the Tiles partitioning, which provides performance acceleration, but, at the same time, strongly adds hard challenges to the memory infrastructure. The main bottleneck in terms of external memory transmission and on-chip storage is the reference frames data: which consists of already coded (and reconstructed) entire frames that must be stored and intensively accessed during the encoding process of future frames. Due to the large volume of data required to represent the reference frames, they are typically stored in the external memory (especially when highdefinition videos are targeted). The proposed Hy-SVM architecture is inserted in a video coding system, which is based on multiple Tiles partitioning to enable parallel HEVC encoding: each Tile is assigned to a specific processing unit. The key ideas of Hy-SVM include: applicationspecific design and management; combined multiple levels of private and shared memories that jointly exploit intra-Tile and inter-Tiles data reuse; scratchpad memories (SPMs) as energyefficient on-chip data storage; combined SRAM and STT-RAM hybrid memory (HyM) design We propose a design methodology for Hy-SVM that leverages application-specific properties to properly define the HyMs parameters. In order to provide run-time adaptation (for both offand on-chip parts), Hy-SVM integrates a memory management layer composed of: (1) overlap prediction, which has the goal of identifying the redundant memory access behavior by analyzing monitored past frames encoding to increase inter-Tiles data reuse exploitation; (2) memory pressure management, which aims on balancing the Tiles-accumulated memory pressure targeting on improving external memory communication channel usage; and (3) lifetime-aware data management scheme that alleviates STT-RAM SPMs of high bit-toggling write accesses to increase the their cells lifetime, as well as to reduce overhead issues related to poor write characteristics of STT-RAM. Application-specific knowledge was exploited by inheriting HEVC properties and performing run-time monitoring of memory accesses. Such information is used to properly design the on-chip video memories, as well as being utilized as input parameters of the run-time memory management layer. Based on the run-time decisions from the proposed Hy-SVM management strategies, Hy-SVM integrates distributed memory access management units (MAMUs) to control the access dynamics of private and shared SPMs. Additionally, adaptive power management units (APMUs) are able to strongly reduce on-chip energy consumption due to an accurate overlap prediction The experimental results demonstrate Hy-SVM overall energy savings over related works under various HEVC encoding scenarios. Compared to traditional data reuse schemes, like Level-C, the combined intra-Tile and inter-Tiles data reuse provides 69%-79% of energy reduction. Regarding related HEVC video memory architectures, the savings varied from 2.8% (worst case) to 67% (best case). From the external memory perspective, Hy-SVM can improve data reuse (by also exploiting inter-Tiles data redundancy), resulting on 11%-71%% of reduced off-chip energy consumption. Additionally, our APMUs contribute by reducing on-chip energy consumption of Hy-SVM by 56%-95%, for the evaluated HEVC scenarios. Thus, compared to related works, Hy-SVM presents the lowest on-chip energy consumption. The memory pressure management scheme can reduce the variations in the memory bandwidth by 37%-83% when compared to the traditional raster scan processing for 4- and 16-core parallelized HEVC encoder. The lifetime-aware data management significantly extends the STT-RAM lifetime, achieving 0.83 of normalized lifetime (near to the optimal case). Moreover, the overhead of implementing our management units insignificantly affects the performance and energyefficiency of Hy-SVM.

Nesta tese é apresentado um novo workflow de simulação para avaliar o desempenho do balanceamento de carga dinâmico baseado em sobre-decomposição aplicado a aplicações paralelas iterativas. Seus objetivos são realizar essa avaliação com modificações mínimas da aplicação e a baixo custo em termos de tempo e de sua necessidade de recursos computacionais. Muitas aplicações paralelas sofrem com desbalanceamento de carga dinâmico (temporal) que não pode ser tratado a nível de aplicação. Este pode ser causado por características intrínsecas da aplicação ou por fatores externos de hardware ou software. Como demonstrado nesta tese, tal desbalanceamento é encontrado mesmo em aplicações cujo código não aparenta qualquer dinamismo. Portanto, faz-se necessário utilizar mecanismo de balanceamento de carga dinâmico a nível de runtime. Este trabalho foca no balanceamento de carga dinâmico baseado em sobre-decomposição. No entanto, avaliar e ajustar o desempenho de tal técnica pode ser custoso. Isso geralmente requer modificações na aplicação e uma grande quantidade de execuções para obter resultados estatisticamente significativos com diferentes combinações de parâmetros de balanceamento de carga Além disso, para que essas medidas sejam úteis, são usualmente necessárias grandes alocações de recursos em um sistema de produção. Simulated Adaptive MPI (SAMPI), nosso workflow de simulação, emprega uma combinação de emulação sequencial e replay de rastros para reduzir os custos dessa avaliação. Tanto emulação sequencial como replay de rastros requerem um único nó computacional. Além disso, o replay demora apenas uma pequena fração do tempo de uma execução paralela real da aplicação. Adicionalmente à simulação de balanceamento de carga, foram desenvolvidas técnicas de agregação espacial e rescaling a nível de aplicação, as quais aceleram o processo de emulação. Para demonstrar os potenciais benefícios do balanceamento de carga dinâmico com sobre-decomposição, foram avaliados os ganhos de desempenho empregando essa técnica a uma aplicação iterativa paralela da área de geofísica (Ondes3D). Adaptive MPI (AMPI) foi utilizado para prover o suporte a balanceamento de carga dinâmico, resultando em ganhos de desempenho de até 36.58% em 288 cores de um cluster Essa avaliação também é usada pra ilustrar as dificuldades encontradas nesse processo, assim justificando o uso de simulação para facilitá-la. Para implementar o workflow SAMPI, foi utilizada a interface SMPI do simulador SimGrid, tanto no modo de emulação, como no de replay de rastros. Para validar esse simulador, foram comparadas execuções simuladas (SAMPI) e reais (AMPI) da aplicação Ondes3D. As simulações apresentaram uma evolução do balanceamento de carga bastante similar às execuções reais. Adicionalmente, SAMPI estimou com sucesso a melhor heurística de balanceamento de carga para os cenários testados. Além dessa validação, nesta tese é demonstrado o uso de SAMPI para exploração de parâmetros de balanceamento de carga e para planejamento de capacidade computacional. Quanto ao desempenho da simulação, estimamos que o workflow completo é capaz de simular a execução do Ondes3D com 24 combinações de parâmetros de balanceamento de carga em 5 horas para o nosso cenário de terremoto mais pesado e 3 horas para o mais leve. / In this thesis we present a novel simulation workflow to evaluate the performance of dynamic load balancing with over-decomposition applied to iterative parallel applications at low-cost. Its goals are to perform such evaluation with minimal application modification and at a low cost in terms of time and of resource requirements. Many parallel applications suffer from dynamic (temporal) load imbalance that can not be treated at the application level. It may be caused by intrinsic characteristics of the application or by external software and hardware factors. As demonstrated in this thesis, such dynamic imbalance can be found even in applications whose codes do not hint at any dynamism. Therefore, we need to rely on runtime dynamic load balancing mechanisms, such as dynamic load balancing based on over-decomposition. The problem is that evaluating and tuning the performance of such technique can be costly. This usually entails modifications to the application and a large number of executions to get statistically sound performance measurements with different load balancing parameter combinations. Moreover, useful and accurate measurements often require big resource allocations on a production cluster. Our simulation workflow, dubbed Simulated Adaptive MPI (SAMPI), employs a combined sequential emulation and trace-replay simulation approach to reduce the cost of such an evaluation Both sequential emulation and trace-replay require a single computer node. Additionally, the trace-replay simulation lasts a small fraction of the real-life parallel execution time of the application. Besides the basic SAMPI simulation, we developed spatial aggregation and applicationlevel rescaling techniques to speed-up the emulation process. To demonstrate the real-life performance benefits of dynamic load balance with over-decomposition, we evaluated the performance gains obtained by employing this technique on a iterative parallel geophysics application, called Ondes3D. Dynamic load balancing support was provided by Adaptive MPI (AMPI). This resulted in up to 36.58% performance improvement, on 288 cores of a cluster. This real-life evaluation also illustrates the difficulties found in this process, thus justifying the use of simulation. To implement the SAMPI workflow, we relied on SimGrid’s Simulated MPI (SMPI) interface in both emulation and trace-replay modes.To validate our simulator, we compared simulated (SAMPI) and real-life (AMPI) executions of Ondes3D. The simulations presented a load balance evolution very similar to real-life and were also successful in choosing the best load balancing heuristic for each scenario. Besides the validation, we demonstrate the use of SAMPI for load balancing parameter exploration and for computational capacity planning. As for the performance of the simulation itself, we roughly estimate that our full workflow can simulate the execution of Ondes3D with 24 different load balancing parameter combinations in 5 hours for our heavier earthquake scenario and in 3 hours for the lighter one.

A presente tese trata o problema do reescalonamento de processos durante a execução da aplicação, oferecendo rebalanceamento dinâmico de carga entre os recursos disponíveis. Uma vez que os cenários da computação distribuída envolvem cada vez mais recursos e aplicações dinâmicas, a carga é uma medida variável e um mapeamento inicial processos-recursos pode não permanecer eficiente no decorrer do tempo. O estado dos recursos e da rede podem variar no decorrer da aplicação, bem como a quantidade de processamento e a interação entre os processos. Consequentemente, o remapeamento de processos para novos recursos é pertinente para aumentar o uso dos recursos e minimizar o tempo de execução da aplicação. Nesse contexto, essa tese de doutorado apresenta um modelo de reescalonamento chamado MigBSP, o qual controla a migração de processos de aplicações BSP (Bulk Synchronous Parallel). O modelo de aplicação BSP foi adotado visto que torna a programação paralela mais fácil e é muito comum nos cenários de desenvolvimento de aplicações científicas. Considerando o escopo de aplicações BSP, as novas idéias de MigBSP são em número de três: (i) combinação de três métricas - Memória, Computação e Comunicação - em uma outra escala com o intuito de medir o Potencial de Migração de cada processo BSP; (ii) emprego de um Padrão de Computação e outro Padrão de Comunicação para controlar a regularidade dos processos e; (iii) adatação eficiente na freqüência do lançamento do reescalonamento de processos. A infra-estrutura de máquina paralela considera sistemas distribuídos heterogêneos (diferentes velocidades de processador e de rede). Os processos podem passar mensagens entre si e a máquina paralela pode agregar redes locais e clusters. O modelo de reescalonamento provê um formalismo matemático para decidir as seguintes questões: (i) Quando lançar o reescalonamento dos processos; (ii) Quais processos são candidatos a migração e; (iii) Para onde os processos selecionados serão migrados. A técnica de simulação foi usada para validar MigBSP. Além do próprio MigBSP, três aplicações científicas foram foram desenvolvidas e executadas usando o simulador Simgrid. Os resultados mostraram que MigBSP oferece oportunidade de ganhar desempenho sem alterações no código fonte da aplicação. MigBSP torna possível ganhos de desempenho na casa de 20%, bem como produz uma baixa sobrecarga quando migrações são inviáveis. Sua sobrecarga média ficou abaixo de 8% do tempo de execução normal da aplicação. Essa taxa foi obtida desabilitando quaisquer migrações indicadas por MigBSP. Os resultados mostraram que a união das métricas consideradas é uma boa solução para o controle de migração de processos. Além disso, eles revelaram que as adaptações desenvolvidas na freqüência do reescalonamento são cruciais para tornar a execução de MigBSP viável, principalmente em ambientes desbalanceados. / This thesis treats the processes rescheduling problem during application runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios. Considering the scope of BSP applications, the novel ideas of MigBSP are threefold: (i) combination of three metrics - Memory, Computation and Communication - in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed) distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually. We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code. MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead is lower than 8% of the normal application execution time. This rate was obtained disabling any processes migration indicated by MigBSP. The results show that the union of considered metrics is a good solution to control processes migration. Moreover, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.

O aumento crescente no número de processadores das arquiteturas paralelas que estão no topo dos rankings de desempenho, apesar de permitir uma maior capacidade de processamento, também traz consigo um aumento na taxa de falhas diretamente proporcional ao número de processadores. Atualmente, as técnicas de tolerância a falhas com recuperação retroativa são as mais empregadas em aplicações MPI, principalmente a técnica de checkpoint coordenado. No entanto, previsões afirmam que essa última técnica será inadequada para as arquiteturas emergentes. Em contrapartida, as técnicas de log de mensagens possuem características que as tornam mais apropriadas no novo cenário que se estabelece. O presente trabalho consiste em uma proposta de log de mensagens pessimista remoto com checkpoint não-coordenado e a avaliação de desempenho da comunicação MPI sobre Publish/Subscriber no qual se baseia o log de mensagens. O trabalho compreende: um estudo das técnicas de tolerância a falhas mais empregadas em ambientes de alto desempenho e a motivação para a escolha dessa variante de log de mensagens; a proposta de log de mensagens; uma implementação de comunicação Open MPI sobre OpenAMQ e sua respectiva avaliação de desempenho com comunicação tradicional TCP/IP e com o log de mensagens pessimista local da distribuição do Open MPI. Os benchmarks utilizados foram o NetPIPE, o NAS Parallel Benchmarks e a aplicação Virginia Hydrodynamics (VH-1). / The growing number of processors in parallel architectures at the top of performance rankings allows a higher processing capacity. However, it also brings an increase in the fault rate which is directly proportional to the number of processors. Nowadays, coordinated checkpoint is the most widely used rollback technique for system recovery in the occurrence of faults in MPI applications. Nevertheless, projections point that this technique will be inappropriate for the emerging architectures. On the other hand, message logging seems to be more appropriate to this new scenario. This work consists in a proposal of pessimistic message logging (remote based) with non-coordinated checkpoint and the performance evaluation of an MPI communication mechanism that works over Publish/Subscriber channels in which the proposed message logging is based. The work is organized as following: an study of fault tolerant techniques used in HPC and the motivation for choosing this variant of message logging; a message logging proposal; an implementation of Open MPI communication over OpenAMQ; performance evaluation and comparision with the tradicional TCP/IP communication and a pessimistic message logging (sender based) from Open MPI distribution. The benchmark set is composed of NetPIPE, NAS Parallel Benchmarks and Virginia Hydrodynamics (VH-1).

Made available in DSpace on 2014-06-11T19:24:00Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-10-17Bitstream added on 2014-06-13T20:30:51Z : No. of bitstreams: 1 gulo_casj_me_sjrp.pdf: 1004896 bytes, checksum: d189543ceda76e9ee5b4a62ae7aaaffa (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / A evolução constante na velocidade de cálculos dos processadores tem sido uma grande aliada no desenvolvimento de áreas da Ciência que exigem processamento de alto desempenho. Associados aos recursos computacionais faz-se necessário o emprego de técnicas de computação paralela no intuito de explorar ao máximo a capacidade de processamento da arquitetura escolhida, bem como, reduzir o tempo de espera no processamento. No entanto, o custo financeiro para aquisição deste tipo dehardwarenão é muito baixo, implicando na busca de alternativas para sua utilização. As arquiteturas de processadores multicoree General Purpose Computing on Graphics Processing Unit(GPGPU), tornam-se opções de baixo custo, pois são projeta-das para oferecer infraestrutura para o processamento de alto desempenho e atender aplicações de tempo real. Com o aperfeiçoamento das tecnologias multicomputador, multiprocessador e GPGPU, a paralelização de técnicas de processamento de imagem tem obtido destaque por vi-abilizar a redução do tempo de processamento de métodos complexos aplicados em imagem de alta resolução. Neste trabalho, é apresentado o estudo e uma abordagem de paralelização em GPGPU, utilizando a arquitetura CUDA, do método de suavização de imagem baseado num modelo variacional, proposto por Jin e Yang (2011), e sua aplicação em imagens com al-tas resoluções. Os resultados obtidos nos experimentos, permitiram obter um speedupde até quinze vezes no tempo de processamento de imagens, comparando o algoritmo sequencial e o algoritmo otimizado paralelizado em CUDA, o que pode viabilizar sua utilização em diversas aplicações de tempo real / Supported by processors evolution, high performance computing have contributed to develop-ment in several scientific research areas which require advanced computations, such as image processing, augmented reality, and others. To fully exploit high performance computing availa-ble in these resources and to decrease processing time, is necessary apply parallel computing. However, those resources are expensive, which implies the search for alternatives ways to use it. The multicore processors architecture andGeneral Purpose Computing on Graphics Proces-sing Unit(GPGPU) become a low cost options, as they were designed to provide infrastructure for high performance computing and attend real-time applications.With the improvements gai-ned in technologies related to multicomputer, multiprocessor and, more recently, to GPGPUs, the parallelization of computational image processing techniques has gained extraordinary pro-minence. This parallelization is crucial for the use of such techniques in applications that have strong demands in terms of processing time, so that even more complex computational algo-rithms can be used, as well as their use on images of higher resolution. In this research, the parallelization in GPGPU of a recent image smoothing method based on a variation model is described and discussed. This method was proposed by Jin and Yang (2011) and is in-demand due to its computation time, and its use with high resolution images. The results obtained are very promising, revealing a speedup about fifteen times in terms of computational speed

Made available in DSpace on 2016-06-02T19:52:03Z (GMT). No. of bitstreams: 1 DissFSS.pdf: 471874 bytes, checksum: 52bc0458fea36b975556da8d0d9d80ca (MD5) Previous issue date: 2003-08-14 / This work consists in the development of genetic algorithms for the Task-to-Processo Assignment Problem in multiprocessor applications. Specifically, the objective is to find the task-to-processor assignment that minimizes the total delay in a particular multiprocessor digital signal processing architecture. We present a description of our algorithm implementations and the results found with a set of 117 randomly generated and real-life instances. The algorithms performance is compared with the results provided by a competitive dynamic list heuristic and a multiple start search algorithm. The results indicate lower delays in more than 68% of the instances, at a higher computational cost. / O objetivo deste projeto consiste no desenvolvimento de algoritmos genéticos para resolução do problema de designação de tarefas em multiprocessadores de processamento digital de sinal (PDS). Especificamente, busca-se minimizar o atraso total em uma arquitetura de multiprocessadores particular, bastante utilizada em sistemas reais. Neste trabalho são apresentadas implementações de algoritmos genéticos, e os resultados computacionais decorrentes de sua aplicação a um conjunto de 117 exemplos gerados aleatoriamente e extraídos de contextos reais. O desempenho dos algoritmos é analisado, comparando-se a qualidade das soluções e os tempos computacionais requeridos com os obtidos por uma heurística competitiva da literatura e por um algoritmo de busca multiple starts. Os algoritmos genéticos obtiveram menores valores de atraso em mais de 68% dos exemplos, a um tempo computacional maior.