Orientador: Edmundo Roberto Mauro Madeira / Dissertação (mestrado) ¿ Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T01:33:20Z (GMT). No. of bitstreams: 1 Silva_GeraldoMagela_M.pdf: 6211710 bytes, checksum: 5a88c999846d2e6c89c5a5487e7cbed2 (MD5) Previous issue date: 2013 / Resumo: Agências governamentais ao redor do mundo estão realizando grandes investimentos na utilização de Tecnologia da Informação e Comunicação em suas atividades. Essa tendência, conhecida como Governo eletrônico, impulsiona grande demanda por pesquisas cujo foco principal é o desenvolvimento de aplicações destinadas a um governo mais transparente e colaborativo. Aplicações para esse tipo de cenário introduzem uma série de desafios que precisam ser enfrentados, incluindo maior interoperabilidade entre sistemas, escalabilidade, questões de segurança, entre outros. Nesse sentido, o paradigma de Arquitetura Orientada a Serviços (SOA) apresenta-se como uma interessante proposta para mitigar a heterogeneidade dos serviços prestados pelas diversas entidades envolvidas. Além disso, computação em grade pode ser considerada uma solução promissora para aplicações de middleware em Governo eletrônico, graças à sua alta capacidade de armazenamento e processamento, além de sua recente orientação a serviços, tornando-a uma poderosa ferramenta para aplicações intra-domínio. Considerando esses desafios, este trabalho propõe uma plataforma para aplicações de Governo eletrônico em sistemas em grades utilizando serviços de suporte fornecidos pelo Globus Toolkit 4 (GT4) no contexto da Web Semântica. O trabalho inclui a implementação de um protótipo do middleware e sua validação através de um cenário de aplicação / Abstract: Government agencies around the world are making large investments in the use of Information and Communication Technology in their activities. This trend, known as electronic government, drives a demand for research focused on development of applications aimed at a more transparent and collaborative government. Applications for this type of scenario pose a series of challenges to be faced, including greater interoperability between systems, scalability, and security issues, among others. In this sense, the paradigm of Service-Oriented Architecture (SOA) presents itself as an interesting proposal to mitigate the heterogeneity of services provided by various involved entities. Furthermore, grid computing can be considered a promising solution for middleware applications in e-Government due to its high storage and processing capacity, and also its recent service orientation, making it a powerful tool for intra-domain applications. Considering these challenges, this dissertation proposes a platform for e-Government applications on grid computing, using the support services provided by the Globus Toolkit 4 (GT4) in the context of the Semantic Web. The work includes the implementation of a middleware prototype and its validation through an application scenario / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Grades computacionais oportunistas utilizam recursos ociosos de máquinas compartilhadas para executar aplicações que necessitam de um alto poder computacional e/ou trabalham com grandes quantidades de dados. Mas a execução de aplicações paralelas computacionalmente intensivas em ambientes dinâmicos e heterogêneos, como grades computacionais oportunistas, é uma tarefa difícil. Máquinas podem falhar, ficar inacessíveis ou passar de ociosas para ocupadas inesperadamente, comprometendo a execução de aplicações. Um mecanismo de tolerância a falhas que dê suporte a arquiteturas heterogêneas é um importante requisito para estes sistemas. Neste trabalho, analisamos, implementamos e avaliamos um mecanismo de tolerância a falhas baseado em checkpointing para aplicações paralelas em grades computacionais oportunistas. Este mecanismo permite o monitoramento de execuções e a migração de aplicações entre nós heterogêneos da grade. Mas além da execução, é preciso gerenciar e armazenar os dados gerados e utilizados por estas aplicações. Desejamos uma infra-estrutura de armazenamento de dados de baixo custo e que utilize o espaço livre em disco de máquinas compartilhadas da grade. Devemos utilizar somente os ciclos ociosos destas máquinas para armazenar e recuperar dados, de modo que um sistema de armazenamento distribuído que as utilize deve ser redundante e tolerante a falhas. Para resolver o problema do armazenamento de dados em grades oportunistas, projetamos, implementamos e avaliamos o middleware OppStore. Este middleware provê armazenamento distribuído e confiável de dados, que podem ser acessados de qualquer máquina da grade. As máquinas são organizadas em aglomerados, que são conectados por uma rede peer-to-peer auto-organizável e tolerante a falhas. Dados são codificados em fragmentos redundantes antes de serem armazenados, de modo que arquivos podem ser reconstruídos utilizando apenas um subconjunto destes fragmentos. Finalmente, para lidar com a heterogeneidade dos recursos, desenvolvemos uma extensão ao protocolo de roteamento em redes peer-to-peer Pastry. Esta extensão adiciona balanceamento de carga e suporte à heterogeneidade de máquinas ao protocolo Pastry. / Opportunistic computational grids use idle resources from shared machines to execute applications that need large amounts of computational power and/or deal with large amounts of data. But executing computationally intensive parallel applications in dynamic and heterogeneous environments, such as opportunistic grids, is a daunting task. Machines may fail, become inaccessible, or change from idle to occupied unexpectedly, compromising the application execution. A fault tolerance mechanism that supports heterogeneous architectures is an important requisite for such systems. In this work, we analyze, implement and evaluate a checkpointing-based fault tolerance mechanism for parallel applications running on opportunistic grids. The mechanism monitors application execution and allows the migration of applications between heterogeneous nodes of the grid. But besides application execution, it is necessary to manage data generated and used by those applications. We want a low cost data storage infrastructure that utilizes the unused disk space of grid shared machines. The system should use the machines to store and recover data only during their idle periods, requiring the system to be redundant and fault-tolerant. To solve the data storage problem in opportunistic grids, we designed, implemented and evaluated the OppStore middleware. This middleware provides reliable distributed storage for application data, which can be accessed from any machine in the grid. The machines are organized in clusters, connected by a self-organizing and fault-tolerant peer-to-peer network. During storage, data is codified into redundant fragments, allowing the reconstruction of the original file using only a subset of those fragments. Finally, to deal with resource heterogeneity, we developed an extension to the Pastry peer-to-peer routing substrate, enabling heterogeneity-aware load-balancing message routing.

Um dos maiores desafios envolvidos no projeto de grades computacionais é o escalonamento de processos, o qual consiste no mapeamento de processos sobre os computadores disponíveis, a fim de reduzir o tempo de execução de aplicações ou maximizar a utilização de recursos. A literatura na área de Sistemas Distribuídos trata, geralmente, esses dois objetivos separadamente, dando origem às abordagens de escalonamento orientado a aplicações e orientado a recursos, respectivamente. Mais recentemente, uma nova abordagem, denominada escalonamento orientado a sistemas, tem recebido destaque, buscando otimizar ambos objetivos simultaneamente. Seguindo essas abordagens, algoritmos heurísticos e de aproximação têm sido propostos. Os heurísticos buscam por soluções de maneira eficiente sem, contudo, apresentar garantias quanto à qualidade das soluções obtidas. Em contrapartida, os algoritmos de aproximação provêm tais garantias, contudo são mais difíceis de serem projetados, o que justifica o fato de haver apenas versões simplificadas desses algoritmos para cenários de escalonamento de processos. A falta de algoritmos de aproximação adequados para abordar o problema de escalonamento de processos e a necessidade de soluções que atendam o escalonamento orientado a sistemas motivaram esta tese de doutorado que apresenta a proposta do Min Heap-based Scheduling Algorithm (MHSA), um algoritmo de aproximação para o problema de escalonamento de processos orientado a sistemas. Esse algoritmo foi baseado em um modelo de otimização matemática proposto no contexto desta tese. Esse modelo considera os comportamentos de processos e recursos a fim de quantificar a qualidade de soluções de escalonamento. O funcionamento do MHSA envolve a construção de uma árvore min-heap, em que os nós representam computadores e as chaves de ordenação correspondem aos tempos de fila, i.e., ocupação dos computadores. Apesar de esse algoritmo primordialmente reduzir o tempo de execução (ou makespan) de aplicações, essa estrutura em árvore permite que qualquer computador que ocupe o nó raiz receba cargas, o que favorece a ocupação de recursos e, portanto, sua orientação a sistemas. Esse algoritmo tem complexidade assintótica de pior caso igual a O(\'log IND. 2 m\'), em que m corresponde ao número de computadores do sistema. Sua razão de aproximação foi estudada para ambientes distribuídos heterogêneos com e sem a presença de comunicação entre processos, o que permite conhecer, a priori, o nível mínimo de qualidade alcançado por suas soluções. Experimentos foram conduzidos para avaliar o algoritmo proposto e compará-lo a outras propostas. Os resultados confirmam que o MHSA reduz o tempo dispendido na obtenção de boas soluções de escalonamento / One of the most important challenges involved in the design of grid computing systems is process scheduling, which maps applications into the available computers in attempt to reduce the application execution time, or maximize resource utilization. The literature of Distributed Systems usually deals with these two objectives separately, supporting the application-centric and the resourcecentric scheduling, respectively. More recently, a third approach referred to as system-centric scheduling has emerged which attempts to optimize both objectives in conjunction. Heuristic-based and approximation-based algorithms have been proposed to address this third type of scheduling. Heuristics aim to find good solutions at acceptable time constraints, without guaranteeing solution quality. On the other hand, approximation-based algorithms provide optimal solution bounds, however they are more difficult to design what makes them available only to simple scenarios. The need for approximation-based algorithms to support system-centric scheduling has motivated this thesis which presents Min Heap-based Scheduling Algorithm (MHSA). This approximation algorithm is based on a mathematical optimization model, also proposed in this work, which considers process and resource behaviors to measure the quality of scheduling solutions. MHSA builds a min-heap data structure in which tree nodes represent computers and sorting keys correspond to queuing times, i.e., computer workloads. Besides this algorithm primarily reduces application execution times (also referred to as makespan), its data structure allows any computer assume the root node and, consequently, receive workloads, what favors resource utilization. This algorithm has the worst-case time complexity equals to O(\'log IND. 2 m\'), in which m represents the number of system computers. Its approximation ratio was analyzed to heterogeneous distributed systems considering bag-of-tasks and communication-intensive applications. Having this ratio, we know the minimum quality level provided by every scheduling solution. Experiments were performed to compare MHSA to others. Results confirm MHSA reduces the time spent to obtain good quality scheduling solutions

Submitted by Fabricia Fialho Reginato (fabriciar) on 2015-07-08T01:19:32Z No. of bitstreams: 1 VladimirGuerreiro.pdf: 5547701 bytes, checksum: b807e1f8091b49a5ee1e0b36e2ae4286 (MD5) / Made available in DSpace on 2015-07-08T01:19:32Z (GMT). No. of bitstreams: 1 VladimirGuerreiro.pdf: 5547701 bytes, checksum: b807e1f8091b49a5ee1e0b36e2ae4286 (MD5) Previous issue date: 2014 / Nenhuma / Em ambientes paralelos, uma das alternativas para tratar o dinamismo, tanto em nível de infraestrutura quanto de aplicação é o uso de migração, principalmente em aplicações que executam em fases utilizando BSP (Bulk Synchronous Parallel). Neste contexto, o modelo de reescalonamento MigBSP foi desenvolvido para tratar da realocação de processos em aplica- ções paralelas. Assim como o modelo BSP, ele considera as três fases de execução de uma superetapa: (i) computação local, (ii) comunicação global e (iii) uma barreira de sincroniza- ção; coletando dados localmente durante a computação para efetuar o cálculo do Potencial de Migração (PM) do processo. Com o PM e parâmetros adicionais fornecidos no inicio da execução da aplicação, o MigBSP tem condições de escolher processos candidatos a migração em uma aplicação paralela executando em um ambiente distribuído. Entretanto, as duas heurísticas possíveis de serem utilizadas hoje, dependem de informações fornecidas pelo usuário e/ou podem não selecionar uma quantidade eficiente de processos no momento do reescalonamento, podendo ser necessário várias chamadas para balancear o ambiente. Desta forma, esta disserta- ção apresenta duas novas heurísticas, MigCube e MigHull. Elas utilizam o MigBSP e efetuam a seleção automática de processos candidatos à migração sem a interferência do programador. As informações fornecidas pelo MigBSP são utilizadas nas heurísticas, a combinação das três métricas mensurados, posicionadas em um plano tridimensional, define cada processo como um ponto no espaço que possui as coordenadas x, y e z, onde cada eixo representa uma mé- trica para tomada de decisão. A heurística MigCube monta um cubo a partir das médias das distâncias entre os pontos, utilizando o processo com o maior PM como centro do cubo. A heurística MigHull segue a definição da Envoltória Convexa, tentando envolver todos os pontos, porém utilizando duas adaptações que se fazem necessárias para a aplicação neste trabalho. O MigBSP foi desenvolvido no simulador SimGrid, e este segue sendo utilizado para a criação das duas heurísticas apresentadas nesta dissertação. Nos testes realizados neste simulador, foi possível verificar um ganho de até 45% no tempo de execução da aplicação utilizando a heurística MigHull, e até 42% utilizando a MigCube, quando comparado a aplicação sem o modelo de migração. Porém, em simulações com um maior número de processos, este ganho tende a cair, já que um dos maiores problemas do BSP e aplicações que executam em grades é o tempo de sincronização de tarefas, ou seja, quanto mais processos, maior a necessidade de sincronização, e mesmo o balanceamento dos processos acaba tendo um resultado prejudicado. / In a parallel environment, one of the alternatives to address the dynamism, both at the infrastructure and application levels, is the use of migration, mostly with applications that execute in steps using BSP (Bulk Synchronous Parallel). In this context, the rescheduling model MigBSP was developed to deal with processes reallocation in parallel applications. As BSP model, MigBSP uses the three steps of a superstep: (i) computation, (ii) communication and (iii) a synchronization barrier; collecting local data during the computation step, to compute the processes’ Potential of Migration (PM). With the PM and additional parameters provided in the beginning of the application’s execution, MigBSP have conditions to choose the processes candidate to migrate in a parallel application running in a distributed system. However, the two heuristics possible to be used today depend of information provided by the user and/or may not select the proper quantity of processes in the rescheduling moment, being necessary many executions to balance the environment. This way, this dissertation present two new heuristics, MigCube and MigHull. They make use of MigBSP, and automatically will choose the processes to migrate without user interference. The information provided by MigBSP are used in the heuristics, the combination of the three measured metrics, positioned in a three-dimensional space, defines each process as a point in space and has the coordinates x, y e z, where each axis represents a metric for decision making. The MigCube heuristic build a cube from the average of the distances between points, using the process with the highest PM as the center of the cube. The MigHull follows the definition of a Convex Hull, trying to involve all points, but using two adaptations that are necessary to implement this work. The MigBSP was developed using SimGrid simulator, and it keeps being used to creation of the two heuristics presented in this dissertation. In the conducted tests in this simulator, was possible to achieve a gain of until 45% on application execution time using MigHull, and until 42% using MigCube, when compared with the application without the migration model. However, simulations with a bigger number of processes, this gain tends to fall, since one of the bigger problems of BSP and applications that run in grid is the time of tasks synchronization, that is, as more processes, more need of synchronization, and even the processes balancing ends up having an impaired outcome.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-31T13:58:16Z No. of bitstreams: 1 PAULO DITARSO MACIEL JÚNIOR - TESE PPGCC 2013..pdf: 21161997 bytes, checksum: 33b051924023dbbac092de80229a7705 (MD5) / Made available in DSpace on 2018-07-31T13:58:16Z (GMT). No. of bitstreams: 1 PAULO DITARSO MACIEL JÚNIOR - TESE PPGCC 2013..pdf: 21161997 bytes, checksum: 33b051924023dbbac092de80229a7705 (MD5) Previous issue date: 2013-06-14 / CNPq / Capes / Com o surgimento do paradigma de computação na nuvem e a busca contínua para reduzir o custo de operar infraestruturas de Tecnologia da Informação (TI), estamos vivenciando nos dias de hoje uma importante mudança na forma como estas infraestruturas estão sendo montadas, configuradas e gerenciadas. Nesta pesquisa consideramos o problema de gerenciar uma infraestrutura híbrida, cujo poder computacional é formado por máquinas locais dedicadas, máquinas virtuais obtidas de provedores de computação na nuvem e máquinas virtuais remotas disponíveis a partir de uma grade peer-to-peer (P2P) best-effort. As aplicações executadas nesta infraestrutura são caracterizadas por uma função de utilidade no tempo, ou seja, a utilidade produzida pela execução completa da aplicação depende do tempo total necessário para sua finalização. Tomamos uma abordagem dirigida a negócios para gerenciar esta infraestrutura, buscando maximizar o lucro total obtido. Aplicações são executadas utilizando poder computacional local e da grade best-effort, quando possível. Qualquer capacidade extra requerida no intuito de melhorar a lucratividade da infraestrutura é adquirida no mercado de computação na nuvem. Também assumimos que esta capacidade extra pode ser reservada para uso futuro através de contratos de curta ou longa duração, negociados sem intervenção humana. Para contratos de curto prazo, o custo por unidade de recurso computacional pode variar significativamente entre contratos, com contratos mais urgentes apresentando, geralmente, custos mais caros. Além disso, devido à incerteza inerente à grade best-effort, podemos não saber exatamente quantos recursos serão necessários do mercado de computação na nuvem com certa antecedência. Superestimar a quantidade de recursos necessários leva a uma reserva maior do que necessária; enquanto subestimar leva à necessidade de negociar contratos adicionais posteriormente. Neste contexto, propomos heurísticas que podem ser usadas por agentes planejadores de contratos no intuito de balancear o custo e a utilidade obtida na execução das aplicações, com o objetivo de alcançar um alto lucro global. Demonstramos que a habilidade de estimar o comportamento da grade é uma importante condição para estabelecer contratos que produzem alta eficiência no uso da infraestrutura híbrida de TI. / With the emergence of the cloud computing paradigm and the continuous search to reduce the cost of running Information Technology (IT) infrastructures, we are currently experiencing an importam change in the way these infrastructures are assembled, configured and managed. In this research we consider the problem of managing a hybrid high-performance computing infrastructure whose processing elements are comprised of in-house dedicated machines, virtual machines acquired from cloud computing providers, and remote virtual machines made available by a best-effort peer-to-peer (P2P) grid. The applications that run in this hybrid infrastructure are characterised by a utility function: the utility yielded by the completion of an application depends on the time taken to execute it. We take a business-driven approach to manage this infrastructure, aiming at maximising the total profit achieved. Applications are run using computing power from both in-house resources and the best-effort grid. whenever possible. Any extra capacity required to improve the profitability of the infrastructure is purchased from the cloud computing market. We also assume that this extra capacity is reserved for future use through either short or long term contracts, which are negotiated without human intervention. For short term contracts. the cost per unit of computing resource may vary significantly between contracts, with more urgent contracts normally being more expensive. Furthermore, due to the uncertainty inherent in the besteffort grid, it may not be possible to know in advance exactly how much computing resource will be needed from the cloud computing market. Overestimation of the amount of resources required leads to the reservation of more than is necessary; while underestimation leads to the necessity of negotiating additional contracts later on to acquire the remaining required capacity. In this context, we propose heuristics to be used by a contract planning agent in order to balance the cost of running the applications and the utility that is achieved with their execution. with the aim of producing a high overall profit. We demonstrate that the ability to estimate the grid behaviour is an important condition for making contracts that produce high efficiency in the use of the hybrid IT infrastructure.

Um dos maiores desafios envolvidos no projeto de grades computacionais é o escalonamento de processos, o qual consiste no mapeamento de processos sobre os computadores disponíveis, a fim de reduzir o tempo de execução de aplicações ou maximizar a utilização de recursos. A literatura na área de Sistemas Distribuídos trata, geralmente, esses dois objetivos separadamente, dando origem às abordagens de escalonamento orientado a aplicações e orientado a recursos, respectivamente. Mais recentemente, uma nova abordagem, denominada escalonamento orientado a sistemas, tem recebido destaque, buscando otimizar ambos objetivos simultaneamente. Seguindo essas abordagens, algoritmos heurísticos e de aproximação têm sido propostos. Os heurísticos buscam por soluções de maneira eficiente sem, contudo, apresentar garantias quanto à qualidade das soluções obtidas. Em contrapartida, os algoritmos de aproximação provêm tais garantias, contudo são mais difíceis de serem projetados, o que justifica o fato de haver apenas versões simplificadas desses algoritmos para cenários de escalonamento de processos. A falta de algoritmos de aproximação adequados para abordar o problema de escalonamento de processos e a necessidade de soluções que atendam o escalonamento orientado a sistemas motivaram esta tese de doutorado que apresenta a proposta do Min Heap-based Scheduling Algorithm (MHSA), um algoritmo de aproximação para o problema de escalonamento de processos orientado a sistemas. Esse algoritmo foi baseado em um modelo de otimização matemática proposto no contexto desta tese. Esse modelo considera os comportamentos de processos e recursos a fim de quantificar a qualidade de soluções de escalonamento. O funcionamento do MHSA envolve a construção de uma árvore min-heap, em que os nós representam computadores e as chaves de ordenação correspondem aos tempos de fila, i.e., ocupação dos computadores. Apesar de esse algoritmo primordialmente reduzir o tempo de execução (ou makespan) de aplicações, essa estrutura em árvore permite que qualquer computador que ocupe o nó raiz receba cargas, o que favorece a ocupação de recursos e, portanto, sua orientação a sistemas. Esse algoritmo tem complexidade assintótica de pior caso igual a O(\'log IND. 2 m\'), em que m corresponde ao número de computadores do sistema. Sua razão de aproximação foi estudada para ambientes distribuídos heterogêneos com e sem a presença de comunicação entre processos, o que permite conhecer, a priori, o nível mínimo de qualidade alcançado por suas soluções. Experimentos foram conduzidos para avaliar o algoritmo proposto e compará-lo a outras propostas. Os resultados confirmam que o MHSA reduz o tempo dispendido na obtenção de boas soluções de escalonamento / One of the most important challenges involved in the design of grid computing systems is process scheduling, which maps applications into the available computers in attempt to reduce the application execution time, or maximize resource utilization. The literature of Distributed Systems usually deals with these two objectives separately, supporting the application-centric and the resourcecentric scheduling, respectively. More recently, a third approach referred to as system-centric scheduling has emerged which attempts to optimize both objectives in conjunction. Heuristic-based and approximation-based algorithms have been proposed to address this third type of scheduling. Heuristics aim to find good solutions at acceptable time constraints, without guaranteeing solution quality. On the other hand, approximation-based algorithms provide optimal solution bounds, however they are more difficult to design what makes them available only to simple scenarios. The need for approximation-based algorithms to support system-centric scheduling has motivated this thesis which presents Min Heap-based Scheduling Algorithm (MHSA). This approximation algorithm is based on a mathematical optimization model, also proposed in this work, which considers process and resource behaviors to measure the quality of scheduling solutions. MHSA builds a min-heap data structure in which tree nodes represent computers and sorting keys correspond to queuing times, i.e., computer workloads. Besides this algorithm primarily reduces application execution times (also referred to as makespan), its data structure allows any computer assume the root node and, consequently, receive workloads, what favors resource utilization. This algorithm has the worst-case time complexity equals to O(\'log IND. 2 m\'), in which m represents the number of system computers. Its approximation ratio was analyzed to heterogeneous distributed systems considering bag-of-tasks and communication-intensive applications. Having this ratio, we know the minimum quality level provided by every scheduling solution. Experiments were performed to compare MHSA to others. Results confirm MHSA reduces the time spent to obtain good quality scheduling solutions