Os avanços nas tecnologias de rede e nos componentes computacionais possibilitaram a criação dos sistemas de Computação Voluntária (CV) que permitem que voluntários doem seus ciclos de CPU ociosos da máquina para um determinado projeto. O BOINC é a infra-estrutura mais popular atualmente, composta de mais 5.900.000 máquinas que processam mais de 4.003 TeraFLOP por dia. Os projetos do BOINC normalmente possuem centenas de milhares de tarefas independentes e estão interessados no throughput. Cada projeto tem seu próprio servidor que é responsável por distribuir unidades de trabalho para os clientes, recuperando os resultados e validando-os. Os algoritmos de escalonamento do BOINC são complexos e têm sido usados por muitos anos. Sua eficiência e justiça foram comprovadas no contexto dos projetos orientados ao throughput. Ainda, recentemente, surgiram projetos em rajadas, com menos tarefas e interessados no tempo de resposta. Diversos trabalhos propuseram novos algoritmos de escalonamento para otimizar seu tempo de resposta individual. Entretanto, seu uso pode ser problemático na presença de outros projetos. Neste texto, são estudadas as consequências do comportamento não cooperativo nos ambientes de Computação Voluntária. Para realizar o estudo, foi necessário modificar o simulador SimGrid para melhorar seu desempenho na simulação dos sistemas de CV. A primeira contribuição do trabalho é um conjunto de melhorias no núcleo de simulação do SimGrid para remover os gargalos de desempenho. O resultado é um simulador consideravelmente mais rápido que as versões anteriores e capaz de rodar experimentos nessa área. Ainda, como segunda grande contribuição, apresentou-se como os algoritmos de escalonamento atuais do BOINC são incapazes de garantir a justiça e isolação entre os projetos. Os projetos em rajadas podem impactar drasticamente o desempenho de todos os outros projetos (rajadas ou não). Para estudar tais interações, realizou-se um detalhado, multi jogador e multi objetivo, estudo baseado em teoria dos jogos. Os experimentos e análise realizados proporcionaram um bom entendimento do impacto dos diferentes parâmetros de escalonamento e mostraram que a otimização não cooperativa pode resultar em ineficiências e num compartilhamento injusto dos recursos. / Advances in inter-networking technology and computing components have enabled Volunteer Computing (VC) systems that allows volunteers to donate their computers’ idle CPU cycles to a given project. BOINC is the most popular VC infrastructure today with over 5.900.000 hosts that deliver over 4.003 TeraFLOP per day. BOINC projects usually have hundreds of thousands of independent tasks and are interested in overall throughput. Each project has its own server which is responsible for distributing work units to clients, recovering results and validating them. The BOINC scheduling algorithms are complex and have been used for many years now. Their efficiency and fairness have been assessed in the context of throughput oriented projects. Yet, recently, burst projects, with fewer tasks and interested in response time, have emerged. Many works have proposed new scheduling algorithms to optimize individual response time but their use may be problematic in presence of other projects. In this text, we study the consequences of non-cooperative behavior in volunteer computing environment. In order to perform our study, we needed to modify the SimGrid simulator to improve its performance simulating VC systems. So, the first contribution is a set of improvements in SimGrid’s core simulation to remove its performance bottlenecks. The result is a simulator considerably faster than the previous versions and able to run VC experiments. Also, in the second contribution, we show that the commonly used BOINC scheduling algorithms are unable to enforce fairness and project isolation. Burst projects may dramatically impact the performance of all other projects (burst or non-burst). To study such interactions, we perform a detailed, multi-player and multi-objective game theoretic study. Our analysis and experiments provide a good understanding on the impact of the different scheduling parameters and show that the non-cooperative optimization may result in inefficient and unfair share of the resources.

Facilitar o gerenciamento e o acesso a sistemas de alto desempenho vem sendo uma área de pesquisa explorada nos últimos anos. Isto acontece uma vez que se verifica o aumento do número de usuários, muitos pertencentes a outras áreas, como por exemplo, biologia, geologia, hidrologia, etc e, desta forma, é preciso facilitar os meios de interação destes usuários com tais sistemas, assim como melhorar as técnicas de gerenciamento dos mesmos. Além do aumento do número e da multidisciplinaridade desses usuários, existe também o fato de que grande parte deles tem acesso a diferentes tipos de sistemas de alto desempenho. Em geral, estes sistemas possuem ferramentas não padronizadas, sendo que cada uma apresenta uma interface e um conjunto de ações e comandos a serem realizados para que possam dispor de suas funcionalidades. Este trabalho propõe a definição de uma arquitetura de gerenciamento e acesso a múltiplos clusters, que seja capaz de ser facilmente extensível, transparente, interoperável e de fácil utilização configuração e manutenção. Como resultado da arquitetura proposta, foi desenvolvido um protótipo, denominado ICE - Integrated Cluster Environment. Os principais objetivos da arquitetura e do ambiente ICE são: (i) capacidade de uniformização do modo como as ferramentas de clusters são utilizadas e, também, uniformização na maneira como os clusters são acessados; (ii) transparência na forma de acesso e uso dos clusters; e (iii) capacidade de extensibilidade em dois níveis: o primeiro refere-se á extensibilidade do número de funcionalidades (serviços) providos pelo sistema e o segundo está relacionado á capacidade do sistema lidar com o uso de diferentes ferramentas que possuem a mesma funcionalidade. Além da descrição da arquitetura e do protótipo, neste trabalho, também é realizada uma avaliação do ambiente ICE. Essa avaliação foi dividida em dois momentos. O primeiro traz a comparação das características do ambiente proposto com algumas ferramentas relacionadas. No segundo momento são apresentados alguns experimentos que visam identificar o overhead inserido pelo ambiente ICE na execução das operaçõess do módulo de gerenciamento de aplicações, desenvolvido e descrito neste trabalho. / Some researches have been done over the last years in order to improve the management and access of high performance systems. One of the motivations of these researches is the continuously increase in the number of users who, not rarely, belong to other areas, such as biology, geology, hydrology, etc; so it is necessary to provide some access and also management facilities in these kinds of systems. Furthermore, the users also have access to different kinds of high performance systems, and they have to deal with distinct tools of their underlying, which are not standardize. Therefore, the users need to learn the specificities of each tool in each high performace system that they have permission to access. Aiming to solve this problem, this work proposes an architecture to provide access and management of multiple clusters with extensibility, transparance, interoperability, user-friendly, manageability and maintainability. As a result of the proposed architecture, a prototype called ICE - Integrated Cluster Environment - was developed. The main goals of the architecture and the ICE environment are: (i) the capability of uniforming the manner the cluster tools are used and accessed; (ii) cluster access and transparence use; and (iii) two extensibility levels: the first one refers to capability of extending the number of functionalities/services provided by the environment and the second one concerns to the capability of extending the number of tools, with the same functionality, the system is able to manage. Beyond the architecture and prototype description, this research presents the evaluation of ICE environment, which is divided in two parts. The first one brings the comparison of the features between ICE and some related work. The second part shows some experiments that intend to verify the overhead inserted by ICE environment when performing the tasks of the job management module, also developed and explained in this work.

Ao longo dos anos, a comunidade de gerenciamento de redes têm sido levada a criar alternativas de gerenciamento que sejam capazes de lidar com problemas de heterogeneidade, escalabilidade, confiabilidade, e com a redução da intervenção humana. Atualmente, existem duas principais alternativas empregadas na definição e desenvolvimento de soluções de gerenciamento de redes. A primeira utiliza computação autonômica e propriedades self-*, enquanto a segunda utiliza conceitos e tecnologias peer-to-peer (P2P). Geralmente, as investigações relacionadas com a aplicação de computação autonômica e propriedades self-* no gerenciamento de redes são focadas na definição de modelos de alto nível (ex., ontologias e políticas), os quais são capazes de determinar as ações autônomas do sistema. Em contrapartida, pesquisas relacionadas com P2P no gerenciamento de redes estão mais focadas na definição da infraestrutura de comunicação da solução de gerenciamento. Sendo assim, de um lado existem as pesquisas ligadas à aplicação de computação autonômica e propriedades self-* que sofrem com o problema da falta de aproximação dos modelos de alto nível com a infraestrutura de gerenciamento, e do outro lado existem as que aplicam P2P e que sofrem com o problema oposto. Dado o cenário descrito acima, essa tese tem como objetivo investigar e esclarecer quais são as questões e características envolvidas na integração de propriedades self-* e P2P que contribuem para a definição de novas alternativas de soluções de gerenciamento de redes. A metodologia utilizada nas investigações baseia-se na definição de requisitos de gerenciamento, de questões de integração para o uso conjunto de propriedades self-* e P2P, e na identificação e desenvolvimento de dois estudos de caso. A análise desses estudos de casos mostrou que o primeiro (solução de auto-cura baseada em P2P) é responsável pela quebra do paradigma tradicional do uso de gerenciamento por delegação em cima de infraestruturas P2P. O segundo estudo de caso (auto-organização baseado em P2P) intensifica essa quebra de paradigma ao explorar capacidades de aplicações P2P na definição das propriedades self-* aplicadas ao gerenciamento de redes. As maiores contribuições dessa tese são: (i) a mudança no foco no desenvolvimento das soluções de gerenciamento de redes dos aspectos morfológicos (tais como, APIs, protocolos, arquiteturas, e frameworks) para a definição de algoritmos sofisticados de gerenciamento; (ii) a introdução de técnicas para explorar comportamentos paralelos e cooperativos dos peers de gerenciamento que executam tais algoritmos; (iii) a definição dos design issues que possibilitam o desenvolvimento de ambientes de gerenciamento de redes verdadeiramente distribuídos e cooperativos, onde o papel dos administradores humanos é minimizado e os gerentes estão embutidos dentro dos elementos gerenciados e não na borda dos sistemas. Em resumo, essa tese mostra como repensar a definição e execução de tarefas de gerenciamento de redes. / Over the years, the network management community has been pushed towards the design of alternative management approaches able to support heterogeneity, scalability, reliability, and minor human intervention. Currently, there are two major alternatives that have been employed on the design and development of network management solutions. The first one uses autonomic computing and self-* properties, while the second one employs Peer-To-Peer (P2P) concepts and technologies. In general, the investigations related to self-* properties and autonomic computing applied to network management focus their efforts on defining high level models (e.g., ontologies and policies) that are able to determine and drive the autonomous actions of the system. On the other side, P2P research applied to network management is mainly target to define the communication infrastructure of management solution. Thus, in the case of autonomic and self-* properties, there is a lack of investigations approximating the high level models to the management infrastructure, while the P2P investigations suffer from the opposite problem. Therefore, the investigations carried on this thesis aim at bringing knowledge to issues involving the joint use of self-* properties and P2P to contribute with the development of alternatives for designing network management solutions. The methodology used on the investigations was based on the definition of management requirements, integration issues for the design of the joint use of self-* properties and P2P, and the identification/ development of two case studies. Analyzing these case studies, it is was possible to conclude that the first case study (self-healing P2P solution) had an importance in terms of breaking the traditional paradigms of using Management by Delegation on top of P2P infrastructures for network management. Embracing this break through, the second case study (self-organizing P2P solution) gave a step further on the development of P2P application capabilities for the design of self-* properties applied to network management. The major contributions of this thesis are: (i) the change on the angle of network management solution development from morphological aspects (such as APIs, protocols, architectures, and frameworks) to the design of sophisticated management algorithms; (ii) the introduction of techniques to explore parallel and cooperative behavior of management peers running the management algorithms; (iii) the establishment of design issues that enable the development of truly distributed and cooperative network management environment, where the presence of the human administrator role is minimized and the managers are embedded inside the managed elements and not in the borders of the system. In summary, this thesis shows how to rethink and improve the design and execution of network management tasks.

Message Passing Interface (MPI) é o padrão de facto para o desenvolvimento de aplicações paralelas e de alto desempenho que executem em clusters. O padrão define APIs para as linguagens de programação Fortran, C e C++. Por outro lado a programação orientada a objetos é o paradigma de programação dominante atualmente, onde linguagens de programação como Java e C# têm se tornado muito populares. Isso se deve às abstrações voltadas para facilitar a programação oriundas dessas linguagens de programação, permitindo um ciclo de programação/manutenção mais eficiente. Devido a isso, diversas bibliotecas MPI para essas linguagens emergiram. Dentre elas, pode-se destacar a biblioteca MPI.NET, para a linguagem de programação C#, que possui a melhor relação entre abstração e desempenho. Na computação paralela, o modelo utilizado para o desenvolvimento das aplicações é muito importante, sendo que o modelo Divisão & Conquista é escalável, aplicável a diversos problemas e permite a execução eficiente de aplicações cuja carga de trabalho é desconhecida ou irregular. Para programar utilizando esse modelo é necessário que o ambiente de execução suporte dinamismo, o que não é suportado pela biblioteca MPI.NET. Desse cenário emerge a principal motivação desse trabalho, cujo objetivo é explorar a criação dinâmica de tarefas na biblioteca MPI.NET. Ao final, foi possível obter uma biblioteca com desempenho competitivo em relação ao desempenho das bibliotecas MPI para C++. / Message Passing Interface (MPI) is the de facto standard for the development of high performance applications executing on clusters. The standard defines APIs for the programming languages Fortran C and C++. On the other hand, object oriented programming has become the dominant programming paradigm, where programming languages as Java and C# are becoming very popular. This can be justified by the abstractions contained in these programming languages, allowing a more efficient programming/maintenance cycle. Because of this, several MPI libraries emerged for these programming languages. Among them, we can highlight the MPI.NET library for the C# programming language, which has the best relation between abstraction and performance. In parallel computing, the model used for the development of applications is very important, and the Divide and Conquer model is efficiently scalable, applicable to several problems and allows efficient execution of applications whose workload is unknown or irregular. To program using this model, the execution environment must provide dynamism, which is not provided by the MPI.NET library. From this scenario emerges the main goal of this work, which is to explore dynamic tasks creation on the MPI.NET library. In the end we where able to obtain a library with competitive performance against MPI C++ libraries.

Diversas aplicações executadas em ambientes de cluster necessitam de uma área de armazenamento permanente com alta capacidade e que forneça uma visão homogênea dos dados entre todos os nós. Esta área compartilhada é comumente implementada através de um sistema de arquivos distribuído, permitindo o acesso através da abstração mais comum para gerenciamento de dados. A disparidade entre poder de processamento e desempenho de dispositivos de armazenamento atuais, no entanto, torna tais sistemas um ponto crítico ao desempenho de aplicações paralelas que lidam com grandes volumes de dados. Ambientes de cluster podem apresentar execução concorrente de aplicações em conjuntos independentes de máquinas. Desta forma, uma grande quantidade de clientes com características distintas farão acessos ao sistema de arquivos compartilhado. Em tais casos, o dimensionamento do sistema de armazenamento distribuído nem sempre poderá prover o desempenho necessário à execução das aplicações com os recursos inicialmente a ele destinados. O presente trabalho propõe uma estratégia de reconfiguração dinâmica para o sistema de arquivos dNFSp. Esta estratégia leva em consideração o comportamento temporal presente em aplicações paralelas para inserir servidores de dados exclusivos a aplicações com alta demanda de I/O. Com a utilização de servidores exclusivos, torna-se possível isolar aplicações com comportamentos que causam grande perda de desempenho no sistema como um todo. Foi desenvolvida uma ferramenta de monitoramento do desempenho junto aos servidores do dNFSp, de forma a solicitar novos servidores apenas quando a interação das fases de I/O das aplicações em execução interferirem no desempenho do sistema. Esses novos servidores são solicitados para um sistema escalonador de recursos para cluster, de forma a utilizar nós livres para o armazenamento de dados. Os resultados mostram que a estratégia proposta é capaz de detectar a saturação do sistema de armazenamento e iniciar os servidores exclusivos, levando a um ganho de desempenho para as aplicações em execução. A reconfiguração dinâmica também mostrou-se capaz de evitar baixos desempenhos causados pela interação dos períodos de inatividade de aplicações temporais e pela utilização de diversos processos de I/O em um único nó. / Several applications executed in cluster environments need a shared storage area with high capacity and a homogeneous view of the stored data to all processing nodes. This area is commonly implemented as a distributed file system, allowing the access to data through the well-known file abstraction. The great gap in performance of processors and storage devices, on the other hand, makes such system a critical point to the performance of parallel applications. A common trait of large cluster environments is the concurrent execution of applications. In this scenario, many clients with distinct behaviors will compete to access the shared storage system. The number of I/O resources originally dedicated to this shared storage may provide unsatisfactory performance to the applications in this case. This work proposes a dynamic reconfiguration strategy for the dNFSp file system. This strategy takes into consideration the temporal behavior of distributed applications to launch dedicated I/O resources to the more I/O-demanding applications. The exclusiveness of data servers allows for the isolation of access patterns that cause contention on the system, resulting in improved performance for all executing applications. We developed a tool to monitor the performance of the storage servers in order to launch new servers only when the interaction of I/O phases from running applications cause each other’s performance to drop. These resources are required to a batch scheduler system present on the cluster, allowing the use of computing nodes for temporary data storage. The results show that the proposed metrics lead to the detection of performance saturation on the file system and the start of the dedicated resources, resulting in increased I/O performance. The reconfiguration has also been able to avoid some low performance situations caused by interactions of inactivity periods from temporal applications and by utilization of several I/O processes on the same cluster node.

Os avanços nas tecnologias de rede e nos componentes computacionais possibilitaram a criação dos sistemas de Computação Voluntária (CV) que permitem que voluntários doem seus ciclos de CPU ociosos da máquina para um determinado projeto. O BOINC é a infra-estrutura mais popular atualmente, composta de mais 5.900.000 máquinas que processam mais de 4.003 TeraFLOP por dia. Os projetos do BOINC normalmente possuem centenas de milhares de tarefas independentes e estão interessados no throughput. Cada projeto tem seu próprio servidor que é responsável por distribuir unidades de trabalho para os clientes, recuperando os resultados e validando-os. Os algoritmos de escalonamento do BOINC são complexos e têm sido usados por muitos anos. Sua eficiência e justiça foram comprovadas no contexto dos projetos orientados ao throughput. Ainda, recentemente, surgiram projetos em rajadas, com menos tarefas e interessados no tempo de resposta. Diversos trabalhos propuseram novos algoritmos de escalonamento para otimizar seu tempo de resposta individual. Entretanto, seu uso pode ser problemático na presença de outros projetos. Neste texto, são estudadas as consequências do comportamento não cooperativo nos ambientes de Computação Voluntária. Para realizar o estudo, foi necessário modificar o simulador SimGrid para melhorar seu desempenho na simulação dos sistemas de CV. A primeira contribuição do trabalho é um conjunto de melhorias no núcleo de simulação do SimGrid para remover os gargalos de desempenho. O resultado é um simulador consideravelmente mais rápido que as versões anteriores e capaz de rodar experimentos nessa área. Ainda, como segunda grande contribuição, apresentou-se como os algoritmos de escalonamento atuais do BOINC são incapazes de garantir a justiça e isolação entre os projetos. Os projetos em rajadas podem impactar drasticamente o desempenho de todos os outros projetos (rajadas ou não). Para estudar tais interações, realizou-se um detalhado, multi jogador e multi objetivo, estudo baseado em teoria dos jogos. Os experimentos e análise realizados proporcionaram um bom entendimento do impacto dos diferentes parâmetros de escalonamento e mostraram que a otimização não cooperativa pode resultar em ineficiências e num compartilhamento injusto dos recursos. / Advances in inter-networking technology and computing components have enabled Volunteer Computing (VC) systems that allows volunteers to donate their computers’ idle CPU cycles to a given project. BOINC is the most popular VC infrastructure today with over 5.900.000 hosts that deliver over 4.003 TeraFLOP per day. BOINC projects usually have hundreds of thousands of independent tasks and are interested in overall throughput. Each project has its own server which is responsible for distributing work units to clients, recovering results and validating them. The BOINC scheduling algorithms are complex and have been used for many years now. Their efficiency and fairness have been assessed in the context of throughput oriented projects. Yet, recently, burst projects, with fewer tasks and interested in response time, have emerged. Many works have proposed new scheduling algorithms to optimize individual response time but their use may be problematic in presence of other projects. In this text, we study the consequences of non-cooperative behavior in volunteer computing environment. In order to perform our study, we needed to modify the SimGrid simulator to improve its performance simulating VC systems. So, the first contribution is a set of improvements in SimGrid’s core simulation to remove its performance bottlenecks. The result is a simulator considerably faster than the previous versions and able to run VC experiments. Also, in the second contribution, we show that the commonly used BOINC scheduling algorithms are unable to enforce fairness and project isolation. Burst projects may dramatically impact the performance of all other projects (burst or non-burst). To study such interactions, we perform a detailed, multi-player and multi-objective game theoretic study. Our analysis and experiments provide a good understanding on the impact of the different scheduling parameters and show that the non-cooperative optimization may result in inefficient and unfair share of the resources.

Atualmente, adaptabilidade é uma característica desejada em aplicações paralelas. Por exemplo, o crescente número de usuários competindo por recursos em arquiteturas paralelas gera mudanças constantes no conjunto de processadores disponíveis. Aplicações adaptativas são capazes de executar usando um conjunto volátil de processadores, oferecendo urna melhor utilização dos recursos. Este comportamento adaptativo é conhecido corno maleabilidade. Outro exemplo vem da constante evolução das arquiteturas multi-core, as quais aumentam o número de cores em seus chips a cada nova geração. Adaptabilidade é a chave para permitir que os programas paralelos sejam portáveis de uma máquina a outra. Assim. os programas paralelos são capazes de adaptar a extração do paralelismo de acordo com o grau de paralelismo específico da arquitetura alvo. Este comportamento pode ser visto como um caso particular de evolutividade. Nesse sentido, esta tese está focada em: (i) maleabilidade para adaptar a execução das aplicações paralelas às mudanças na disponibilidade dos processadores; e (ii) evolutividade para adaptar a extração do paralelismo de acordo com propriedades da arquitetura e dos dados de entrada. Portanto, a questão remanescente é "Como prover e suportar aplicações adaptativas?". Esta tese visa responder tal questão com base no MPI (Message-Passing Interface), o qual é a API paralela padrão para HPC em ambientes distribuídos. Nosso trabalho baseia-se nas características do MPI-2 que permitem criar processos em tempo de execução, dando alguma flexibilidade às aplicações MPI. Aplicações MPI maleáveis usam a criação dinâmica de processos para expandir-se nas ações de crescimento (para usar processadores extras). As ações de diminuição (para liberar processadores) finalizam os processos MPI que executam nos processadores requeridos, preservando os dados da aplicação. Note que as aplicações maleáveis requerem suporte do ambiente de execução, uma vez que precisam ser notificadas sobre a disponibilidade dos processadores. Aplicações MPI evolutivas seguem o paradigma do paralelismo de tarefas explícitas para permitir adaptação em tempo de execução. Assim, a criação dinâmica de processos é usada para extrair o paralelismo, ou seja, para criar novas tarefas MPI sob demanda. Para prover tais aplicações nós definimos tarefas MPI abstratas, implementamos a sincronização entre elas através da troca de mensagens, e propusemos uma abordagem para ajustar a granularidade das tarefas MPI, visando eficiência em ambientes distribuídos. Os resultados experimentais validaram nossa hipótese de que aplicações adaptativas podem ser providas usando características do MPI-2. Adicionalmente, esta tese identificou os requisitos rio nível do ambiente de execução para suportá-las em clusters. Portanto, as aplicações MPI maleáveis melhoraram a utilização de recursos de clusters; e as aplicações de tarefas explícitas adaptaram a extração do paralelismo de acordo com a arquitetura alvo. mostrando que este paradigma também é eficiente em ambientes distribuídos. / Currently, adaptability is a desired feature in parallel applications. For instante, the increasingly number of user competing for resources of the parallel architectures causes dynamic changes in the set of available processors. Adaptive applications are able to execute using a set of volatile processors, providing better resource utilization. This adaptive behavior is known as malleability. Another example comes from the constant evolution of the multi-core architectures, which increases the number of cores to each new generation of chips. Adaptability is the key to allow parallel programs portability from one multi-core machine to another. Thus, parallel programs can adapt the unfolding of the parallelism to the specific degree of parallelism of the target architecture. This adaptive behavior can be seen as a particular case of evolutivity. In this sense, this thesis is focused on: (i) malleability to adapt the execution of parallel applications as changes in processors availability; and (ii) evolutivity to adapt the unfolding of the parallelism at runtime as the architecture and input data properties. Thus, the open issue is "How to provide and support adaptive applications?". This thesis aims to answer this question taking into account the MPI (Message-Passing Interface), which is the standard parallel API for HPC in distributed-memory environments. Our work is based on MPI-2 features that allow spawning processes at runtime. adding some fiexibility to the MPI applications. Malleable MPI applications use dynamic process creation to expand themselves in growth action (to use further processors). The shrinkage actions (to release processors) end the execution of the MPI processes on the required processors in such a way that the application's data are preserved. Notice that malleable applications require a runtime environment support to execute, once they must be notified about the processors availability. Evolving MPI applications follow the explicit task parallelism paradigm to allow their runtime adaptation. Thus, dynamic process creation is used to unfold the parallelism, i.e., to create new MPI tasks on demand. To provide these applications we defined the abstract MPI tasks, implemented the synchronization among these tasks through message exchanges, and proposed an approach to adjust MPI tasks granularity aiming at efficiency in distributed-memory environments. Experimental results validated our hypothesis that adaptive applications can be provided using the MPI-2 features. Additionally, this thesis identifies the requirements to support these applications in cluster environments. Thus, malleable MPI applications were able to improve the cluster utilization; and the explicit task ones were able to adapt the unfolding of the parallelism to the target architecture, showing that this programming paradigm can be efficient also in distributed-memory contexts.

Pesquisas sobre a propagação de epidemias são uma constante devido a sua relevância para a contenção de doenças. Porém, devido aos diversos tipos de doenças existentes, a observação de um comportamento genérico e aproximado torna-se impraticável. Neste âmbito, a elaboração de modelos matemáticos epidêmicos auxiliam no fornecimento de informações que podem ser usadas por orgãos públicos para o combate de surtos epidêmicos reais. Em paralelo, por causa do grande volume de dados que são processados na execução da simulação desses modelos, o constante aumento dos recursos computacionais desenvolvidos vem em auxílio desta tarefa. O objetivo desta dissertação é estudar o comportamento da disseminação de uma epidemia simulada computacionalmente através do modelo epidêmico SIR em reticulados quadrados considerando duas propriedades: a existência de vértices vazios e a movimentação aleatória dos agentes. Essas propriedades são conhecidas por taxas de diluição e mobilidade, respectivamente. Para alcançar esse objetivo, algumas técnicas físico-estatística, tais como a análise das transições de fase e fenômenos críticos, foram aplicadas. Através destas técnicas, é possível observar a passagem do sistema da fase em que ocorre um surto epidêmico para a fase em que a epidemia é contida, bem como estudar a dinâmica do modelo quando ele está na criticidade, ou seja, no ponto de mudança de fase, conhecido por ponto crítico. Foi constatado que a taxa de diluição influencia a disseminação das epidemias porque desloca a transição de fase negativamente, reduzindo o valor crítico da imunização. Por sua vez, a taxa da movimentação dos agentes favorece o espalhamento da doença, pois a transição de fase é positivamente deslocada e seu ponto crítico, aumentado. Além disso foi observado que, apesar desse incremento, ele não é completamente restaurado devido às restrições de mobilidade dos agentes e ao alto grau de desconectividade da rede causado pelas altas taxas de diluição. Neste trabalho nós mostramos as razões deste comportamento. / Research on the spreading of epidemics are frequent because of their relevance for the containment of diseases. However, due to the variety of existing illnesses, the observation of an approximated generic behavior becomes impractical. In this context, the development of mathematical models of epidemics assists in providing information that can be used to make strategic decisions for the combat of real epidemic outbreaks. In parallel, because of the large volume of data which has to be processed in the simulation of these models, the increase of computational performance helps with this task. The objective of this thesis is to study the behavior of the spreading of an epidemic, by computationally simulating an SIR epidemic model on square lattices, considering two properties: the existence of empty vertices and random movement of agents. These properties are known as dilution rate and mobility rate, respectively. To achieve this goal, techniques of statistical physics, such as the analysis of phase transition and power laws, were applied. With these techniques, it is possible to observe the transition of the system from the phase in which an outbreak occurs to the phase where the epidemic is contained. Additionally, we studied the dynamics of the model when it is in criticality, that is, at the point of phase transition, known as the critical point. It was found that a higher dilution rate reduces the spreading of epidemics because it shifts the phase transition negatively, reducing the value of its critical point. On the other hand, increasing the rate of movement of the agents favors the spreading of the disease, because the phase transition is shifted positively and its critical point is increased. It was noticed that, despite of this increasing, this point is not completely restored due to restricted mobility of agents and the high degree of the network disconectivity caused by the high dilution rates. In this work we show the reasons for this behavior.

Esta Dissertação de Mestrado propõe dois novos algoritmos para tornar mais eficiente o escalonamento on-line de tarefas com dependências estritas em agregados de computadores que usam como middleware para troca de mensagens alguma implementação da MPI (até a versão 2.1). Esses algoritmos foram projetados tendo-se em vista programas construídos no modelo de programação fork/join, onde a operação de fork é usada sobre uma chamada recursiva da função. São eles: 1. O algoritmo RatMD, implementado através de uma biblioteca de primitivas do tipo map-reduce, que funciona para qualquer implementação MPI, com qualquer versão da norma. Utilizado para minimizar o tempo de execução de uma computação paralela; e 2. O algoritmo RtMPD, implementado através de um sistema distribuído sobre daemons gerenciadores de processos criados dinamicamente com a implementação MPICH2 (que implementa a MPI-2). Utilizado para permitir execuções de instâncias maiores de programas paralelos dinâmicos. Ambos se baseiam em roubo de tarefas, que é a estratégia de balanceamento de carga mais difundida na literatura. Para ambos os algoritmos apresenta-se modelagem téorica de custos. Resultados experimentais obtidos ficam dentro dos limites teóricos calculados. RatMD provê uma redução no tempo de execução de até 80% em relação ao algoritmo usual (baseado em round-robin), com manutenção do speedup próximo ao linear e complexidade espacial idêntica à popular implementação com round-robin. RtMPD mantém, no mínimo, o mesmo desempenho que a implementação canônica do escalonamento em MPICH2, dobrando-se o limite físico de processos executados simultaneamente por cada nó. / This Master’s Dissertation proposes two new algorithms for improvement on on-line scheduling of dynamic-created tasks with strict dependencies on clusters of computers using MPI (up to version 2.1) as its middleware for message-passing communication. These algorithms were built targeting programs written on the fork-join model, where the fork operation is always called over an recursive function call. They are: 1. RatMD, implemented as a map-reduce library working for any MPI implementation, on whatever norm’s version. Used for performance gain; and 2. RtMPD, implemented as a distributed system over dynamic-generated processes manager daemons with MPICH2 implentation of MPI. Used for executing larger instances of dynamic parallel programs. Both algorithms are based on the (literature consolidated) work stealing technique and have formal guarantees on its execution time and load balancing. Experimental results are within theoretical bounds. RatMD shows an improvement on the performance up to 80% when paired with more usual algorithms (based on round-robin strategy). It also provides near-linear speedup and just about the same space-complexity on similar implementations. RtMPD keeps, at minimum, the very same performance of the canonical MPICH2 implementation, near doubling the physical limit of simultaneous program execution per cluster node.

Sistemas modernos de alto desempenho compreendem milhares a milhões de unidades de processamento. O desenvolvimento de uma aplicação paralela escalável para tais sistemas depende de um mapeamento preciso da utilização recursos disponíveis. A identificação de recursos não utilizados e os gargalos de processamento requere uma boa análise desempenho. A observação de rastros de execução é uma das técnicas mais úteis para esse fim. Infelizmente, o rastreamento muitas vezes produz grandes arquivos de rastro, atingindo facilmente gigabytes de dados brutos. Portanto ferramentas para análise de desempenho baseadas em rastros precisam processar esses dados para uma forma legível e serem eficientes a fim de permitirem uma análise rápida e útil. A maioria das ferramentas existentes, tais como Vampir, Scalasca e TAU, focam no processamento de formatos de rastro com semântica associada, geralmente definidos para lidar com programas desenvolvidos com bibliotecas populares como OpenMP, MPI e CUDA. No entanto, nem todas aplicações paralelas utilizam essas bibliotecas e assim, algumas vezes, essas ferramentas podem não ser úteis. Felizmente existem outras ferramentas que apresentam uma abordagem mais dinâmica, utilizando um formato de arquivo de rastro aberto e sem semântica específica. Algumas dessas ferramentas são Paraver, Pajé e PajeNG. Por outro lado, ser genérico tem custo e assim tais ferramentas frequentemente apresentam baixo desempenho para o processamento de grandes rastros. O objetivo deste trabalho é apresentar otimizações feitas para o conjunto de ferramentas PajeNG. São apresentados o desenvolvimento de um estratégia de paralelização para o PajeNG e uma análise de desempenho para demonstrar nossos ganhos. O PajeNG original funciona sequencialmente, processando um único arquivo de rastro que contém todos os dados do programa rastreado. Desta forma, a escalabilidade da ferramenta fica muito limitada pela leitura dos dados. Nossa estratégia divide o arquivo em pedaços permitindo seu processamento em paralelo. O método desenvolvido para separar os rastros permite que cada pedaço execute em um fluxo de execução separado. Nossos experimentos foram executados em máquinas com acesso não uniforme à memória (NUMA).Aanálise de desempenho desenvolvida considera vários aspectos como localidade das threads, o número de fluxos, tipo de disco e também comparações entre os nós NUMA. Os resultados obtidos são muito promissores, escalando o PajeNG cerca de oito a onze vezes, dependendo da máquina. / Modern high performance systems comprise thousands to millions of processing units. The development of a scalable parallel application for such systems depends on an accurate mapping of application processes on top of available resources. The identification of unused resources and potential processing bottlenecks requires good performance analysis. The trace-based observation of a parallel program execution is one of the most helpful techniques for such purpose. Unfortunately, tracing often produces large trace files, easily reaching the order of gigabytes of raw data. Therefore tracebased performance analysis tools have to process such data to a human readable way and also should be efficient to allow an useful analysis. Most of the existing tools such as Vampir, Scalasca, TAU have focus on the processing of trace formats with a fixed and well-defined semantic. The corresponding file format are usually proposed to handle applications developed using popular libraries like OpenMP, MPI, and CUDA. However, not all parallel applications use such libraries and so, sometimes, these tools cannot be useful. Fortunately, there are other tools that present a more dynamic approach by using an open trace file format without specific semantic. Some of these tools are the Paraver, Pajé and PajeNG. However the fact of being generic comes with a cost. These tools very frequently present low performance for the processing of large traces. The objective of this work is to present performance optimizations made in the PajeNG tool-set. This comprises the development of a parallelization strategy and a performance analysis to set our gains. The original PajeNG works sequentially by processing a single trace file with all data from the observed application. This way, the scalability of the tool is very limited by the reading of the trace file. Our strategy splits such file to process several pieces in parallel. The created method to split the traces allows the processing of each piece in each thread. The experiments were executed in non-uniform memory access (NUMA) machines. The performance analysis considers several aspects like threads locality, number of flows, disk type and also comparisons between the NUMA nodes. The obtained results are very promising, scaling up the PajeNG about eight to eleven times depending on the machine.