Grid computing provides a powerful, virtual parallel system known as a computational Grid on which users can run parallel applications to solve problems quickly. However, users must be careful to allocate tasks to nodes properly because improper allocation of only one task could result in lengthy executions of applications, or even worse, applications could crash. This allocation problem is called the mapping problem, and an entity that tackles this problem is called a mapper. In this thesis, we aim to develop an efficient, practical, portable mapper. To study the mapping problem, researchers often make unrealistic assumptions such as that nodes of Grids are always reliable, that execution times of tasks assigned to nodes are known a priori, or that detailed information of parallel applications is always known. As a result, the practicality and portability of mappers developed in such conditions are uncertain. Our review of related work suggested that a more efficient tool is required to study this problem; therefore, we developed GMap, a simulator researchers/developers can use to develop practical, portable mappers. The fact that nodes are not always reliable leads to the development of an algorithm for predicting the reliability of nodes and a predictor for identifying reliable nodes of Grids. Experimental results showed that the predictor reduced the chance of failures in executions of applications by half. The facts that execution times of tasks assigned to nodes are not known a priori and that detailed information of parallel applications is not alw ays known, lead to the evaluation of five nearest-neighbour (nn) execution time estimators: k-nn smoothing, k-nn, adaptive k-nn, one-nn, and adaptive one-nn. Experimental results showed that adaptive k-nn was the most efficient one. We also implemented the predictor and the estimator in GMap. Using GMap, we could reliably compare the efficiency of six mapping algorithms: Min-min, Max-min, Genetic Algorithms, Simulated Annealing, Tabu Search, and Quick-quality Map, with none of the preceding unrealistic assumptions. Experimental results showed that Quick-quality Map was the most efficient one. As a result of these findings, we achieved our goal in developing an efficient, practical, portable mapper.

Made available in DSpace on 2014-06-11T19:29:40Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-07-01Bitstream added on 2014-06-13T18:39:29Z : No. of bitstreams: 1 franco_pb_me_sjrp.pdf: 2600940 bytes, checksum: c5d3454406b1b9e853e5a555f0a171cb (MD5) / Diversos são os esforços para o desenvolvimento de políticas de escalonamento em grid computacional. O uso de simuladores de grid computacional é de especial importância para o estudo de algoritmos de escalonamento de tarefas. Através dos simuladores, é possível avaliar e comparar o desempenho de diferentes algoritmos em diferentes cenários. Apesar das ferramentas de simulação fornecerem funcionalidades básicas para simulação de ambientes distribuídos, elas não disponibilizam políticas internas de escalonamento de tarefas; além disso, a implementação dos algoritmos deve ser feita pelo próprio usuário. Portanto, o objetivo deste trabalho é desenvolver a biblioteca de escalonamento de tarefas LIBTS (Library Tasks Scheduling) e adaptá-la ao simulador SimGrid para oferecer aos usuários uma ferramenta que possibilite o estudo de algoritmos de escalonamento de tarefas em grid computacional. Através da LIBTS os usuários podem comparar os algoritmos implementados (Workqueue (WQ), Workqueue with Replication (WQR), Sufferage, XSufferage, Dynamic FPLTF) em diversos cenários, como também desenvolver e implementar novos algoritmos de escalonamento de tarefas. Este trabalho também proporciona uma revisão de literatura sobre grid computacional, apresentando as características e metodologias dos algoritmos implementados na LIBTS e as principais características das ferramentas de simulação. Além disso, os cenários de testes criados para comparar os algoritmos validaram o funcionamento da biblioteca e o funcionamento correto dos algoritmos na LIBTS / Too much has been done to develop scheduling policies in computational grid. The use of computational grid simulators is particularly important for studying the algorithms of task scheduling. Through the simulators it’s possible to assess and compare the performance of different algorithms in various scenarios. Despite the simulation tools provide basic features for simulation in distributed environments, they don’t offer internal policies of task scheduling, so that the implementation of the algorithms must be realized by the user himself. Therefore, this study aims to develop the library of task scheduling LIBTS (Library Tasks Scheduling) and adapt it to the SimGrid simulator to provide the users with a tool to analyze the algorithms of task scheduling in the computational grid. Through the LIBTS, the users can compare the implemented algorithms (Workqueue (WQ), Workqueue with Replication (WQR), Sufferage, XSufferage, Dynamic FPLTF) in several scenarios, as well as to develop and implement new algorithms of task scheduling. This work also provides a literature review about the computational grid, presenting the characteristics and methodologies of the implemented algorithms in the LIBTS and the most important features of the simulation tools. Furthermore, the test scenarios created to compare the algorithms validate the library operation and the correct operation of the algorithms in LIBTS

Este texto apresenta nosso projeto de implementação de um arcabouço de suporte a agentes móveis dentro de um ambiente de grade denominado InteGrade. Nosso arcabouço - MobiGrid - foi criado de forma a permitir que aplicações seqüenciais longas possam ser executadas em uma rede de estações de trabalho pessoais. Os agentes móveis são utilizados para encapsular essas aplicações com longo tempo de processamento. O encapsulamento de uma aplicação com longo tempo de processamento dentro de um agente móvel é o que denominamos como tarefa. Sendo assim, as tarefas podem migrar sempre que a máquina é requisitada por seu usuário local, já que são providas com capacidade de migração automática. Nosso arcabouço também fornece ao usuário um gerente que rastreia as tarefas por ele submetidas. Baseados no ambiente de execução de tarefas descrito, criamos um modelo matemático para efetuarmos simulações de como se comportariam muitas tarefas submetidas a uma grade com grande quantidade de estações de trabalho. Neste trabalho apresentamos também esse modelo, bem como os resultados das simulações nele baseadas. / This text presents a project which focuses on the implementation of a framework for mobile agents support within a grid environment project, namely InteGrade. Our framework - MobiGrid - was created in such a way that time consuming sequential applications can be executed on a network of personal workstations. The encapsulation of a long processing application by a mobile agent is what we call task. Hence, the tasks can migrate whenever the local machine is requested by its local user, since they are provided with automatic migration capabilities. Our framework also provides the user with a manager that keeps track of the submitted agents. Based on the execution environment described above, we have created a mathematical model which allows us to simulate how a great quantity of tasks submitted to a grid with many workstations would behave. In this text, we also present our model, as well as the results of our simulations.

A crescente disponibilizaÃÃo de serviÃos atravÃs da Internet vem impondo uma demanda cada vez maior por recursos de processamento no lado servidor favorecendo a utilizaÃÃo dos Clusters de Computadores e das Grades Computacionais. Em paralelo, a engenharia de software traz novos paradigmas, como a OrientaÃÃo a ServiÃos, que impÃem novos desafios a serem tratados pelos fornecedores de serviÃos. A convergÃncia destes fatores deu origem as Arquiteturas de Grades Computacionais Orientadas a ServiÃos. Neste trabalho à apresentada uma proposta de arquitetura em grades computacionais orientada a serviÃos, denominada GDSAC (Grid â DiffServ Admission Control), que trata de aspectos ligados à QoS (Quality of Service) e a diferenciaÃÃo de serviÃos. A arquitetura G-DSAC à uma extensÃo da arquitetura WS-DSAC (Web Servers â DiffServ AdmissionControl). Està extensÃo compreende a concepÃÃo de uma soluÃÃo voltada para grades computacionais que à capaz de garantir os SLAs (Service Level Agreements) estabelecidos com os consumidores de serviÃos utilizando de forma otimizada os recursos de processamento disponibilizados na grade. A soluÃÃo permite ainda a diferenciaÃÃo de serviÃos no que diz respeito aos tempos de resposta oferecidos aos clientes, usuÃrios finais e serviÃos consumidores. A nova arquitetura introduz um bloco de funcionalidades em uma plataforma de grade computacional orientada a serviÃos formada por multclusters. Esse bloco permite a publicaÃÃo e localizaÃÃo de serviÃos, autenticaÃÃo e classificaÃÃo de requisiÃÃes e o escalonamento das mesmas dentro da grade de acordo com a classe de serviÃo a qual pertencem. Foi tambÃm implementado um protÃtipo que permitiu a realizaÃÃo de experimentos em uma plataforma real de testes visando avaliar a capacidade da soluÃÃo em atingir os objetivos por ela proposto

In this paper, we discuss a wireless grid in which users are highly mobile, and form ad-hoc and sometimes short-lived connections with other devices. As they roam through networks, the users may choose to employ privacy-enhancing technologies to address their privacy needs and benefit from the computational power of the grid for a variety of tasks, including sharing content. The high rate of mobility of the users on the wireless grid, when combined with privacy enhancing mechanisms and ad-hoc connections, makes it difficult to conclusively link devices and/or individuals with network activities and to hold them liable for particular downloads. Protecting intellectual property in this scenario requires a solution that can work in absence of knowledge about behavior of particular individuals. Building on previous work, we argue for a solution that ensures proper compensation to content owners without inhibiting use and dissemination of works. Our proposal is based on digital tracking for measuring distribution volume of content and compensation of authors based on this accounting information. The emphasis is on obtaining good estimates of rate of popularity of works, without keeping track of activities of individuals or devices. The contribution of this paper is a revenue protection mechanism, Distribution Volume Tracking, that does not invade the privacy of users in the wireless grid and works even in the presence of privacy-enhancing technologies they may employ.

Este texto apresenta nosso projeto de implementação de um arcabouço de suporte a agentes móveis dentro de um ambiente de grade denominado InteGrade. Nosso arcabouço - MobiGrid - foi criado de forma a permitir que aplicações seqüenciais longas possam ser executadas em uma rede de estações de trabalho pessoais. Os agentes móveis são utilizados para encapsular essas aplicações com longo tempo de processamento. O encapsulamento de uma aplicação com longo tempo de processamento dentro de um agente móvel é o que denominamos como tarefa. Sendo assim, as tarefas podem migrar sempre que a máquina é requisitada por seu usuário local, já que são providas com capacidade de migração automática. Nosso arcabouço também fornece ao usuário um gerente que rastreia as tarefas por ele submetidas. Baseados no ambiente de execução de tarefas descrito, criamos um modelo matemático para efetuarmos simulações de como se comportariam muitas tarefas submetidas a uma grade com grande quantidade de estações de trabalho. Neste trabalho apresentamos também esse modelo, bem como os resultados das simulações nele baseadas. / This text presents a project which focuses on the implementation of a framework for mobile agents support within a grid environment project, namely InteGrade. Our framework - MobiGrid - was created in such a way that time consuming sequential applications can be executed on a network of personal workstations. The encapsulation of a long processing application by a mobile agent is what we call task. Hence, the tasks can migrate whenever the local machine is requested by its local user, since they are provided with automatic migration capabilities. Our framework also provides the user with a manager that keeps track of the submitted agents. Based on the execution environment described above, we have created a mathematical model which allows us to simulate how a great quantity of tasks submitted to a grid with many workstations would behave. In this text, we also present our model, as well as the results of our simulations.

Orientador: Roberta Spolon / Banca: Sarita Mazzini Brushi / Banca: Marcos Antônio Cavenaghi / Resumo: Diversos são os esforços para o desenvolvimento de políticas de escalonamento em grid computacional. O uso de simuladores de grid computacional é de especial importância para o estudo de algoritmos de escalonamento de tarefas. Através dos simuladores, é possível avaliar e comparar o desempenho de diferentes algoritmos em diferentes cenários. Apesar das ferramentas de simulação fornecerem funcionalidades básicas para simulação de ambientes distribuídos, elas não disponibilizam políticas internas de escalonamento de tarefas; além disso, a implementação dos algoritmos deve ser feita pelo próprio usuário. Portanto, o objetivo deste trabalho é desenvolver a biblioteca de escalonamento de tarefas LIBTS (Library Tasks Scheduling) e adaptá-la ao simulador SimGrid para oferecer aos usuários uma ferramenta que possibilite o estudo de algoritmos de escalonamento de tarefas em grid computacional. Através da LIBTS os usuários podem comparar os algoritmos implementados (Workqueue (WQ), Workqueue with Replication (WQR), Sufferage, XSufferage, Dynamic FPLTF) em diversos cenários, como também desenvolver e implementar novos algoritmos de escalonamento de tarefas. Este trabalho também proporciona uma revisão de literatura sobre grid computacional, apresentando as características e metodologias dos algoritmos implementados na LIBTS e as principais características das ferramentas de simulação. Além disso, os cenários de testes criados para comparar os algoritmos validaram o funcionamento da biblioteca e o funcionamento correto dos algoritmos na LIBTS / Abstract: Too much has been done to develop scheduling policies in computational grid. The use of computational grid simulators is particularly important for studying the algorithms of task scheduling. Through the simulators it's possible to assess and compare the performance of different algorithms in various scenarios. Despite the simulation tools provide basic features for simulation in distributed environments, they don't offer internal policies of task scheduling, so that the implementation of the algorithms must be realized by the user himself. Therefore, this study aims to develop the library of task scheduling LIBTS (Library Tasks Scheduling) and adapt it to the SimGrid simulator to provide the users with a tool to analyze the algorithms of task scheduling in the computational grid. Through the LIBTS, the users can compare the implemented algorithms (Workqueue (WQ), Workqueue with Replication (WQR), Sufferage, XSufferage, Dynamic FPLTF) in several scenarios, as well as to develop and implement new algorithms of task scheduling. This work also provides a literature review about the computational grid, presenting the characteristics and methodologies of the implemented algorithms in the LIBTS and the most important features of the simulation tools. Furthermore, the test scenarios created to compare the algorithms validate the library operation and the correct operation of the algorithms in LIBTS / Mestre

In the last decade, advances in sensor and computing technology are revolutionary. The latest-generation of hyperspectral and synthetic aperture radar ((SAR) instruments have increased their spectral, spatial, and temporal resolution. Consequently, the data sets collected are increasing rapidly in size and frequency of acquisition. Remote sensing applications are requiring more computing resources for data analysis. High performance computing (HPC) infrastructure such as clusters, distributed networks, grids, clouds and specialized hardware components, have been used to disseminate large volumes of remote sensing data and to accelerate the computational speed in processing raw images and extracting information from remote sensing data. In previous research we have shown that we can improve computational efficiency of a hyperspectral image denoising algorithm by parallelizing the algorithm utilizing a distributed computing grid. In recent years, computational cloud technology is emerging, bringing more flexibility and simplicity for data processing. Hadoop MapReduce is a software framework for distributed commodity computing clusters, allowing parallel processing of massive datasets. In this project, we implement a software application to map forest aboveground biomass (AGB) with normalized difference vegetation indices (NDVI) using Landsat Thematic Mapper’s bands 4 and 5 (ND45). We present observations and experimental results on the performance and the algorithmic complexity of the implementation. There are three research questions answered in this thesis, as follows. 1) How do we implement remote sensing algorithms, such as forest AGB mapping, in a computer cloud environment? 2) What are the requirements to implement distributed processing of remote sensing images using the cloud programming model? 3) What is the performance increase for large area remote sensing image processing in a cloud environment? / Graduate / 0799 / 0984

<p>We study techniques to enforce and provision differentiated service levels in <i>Computational Grid</i> systems. The Grid offers simplified provisioning of peak-capacity for applications with computational requirements beyond local machines and clusters, by sharing resources across organizational boundaries. Current systems have focussed on access control, i.e., managing who is allowed to run applications on remote sites. Very little work has been done on providing differentiated service levels for those applications that are admitted. This leads to a number of problems when scheduling jobs in a fair and efficient way. For example, users with a large number of long-running jobs could starve out others, both intentionally and non-intentionally. We investigate the requirements of High Performance Computing (HPC) applications that run in academic Grid systems, and propose two models of service-level management. Our first model is based on global real-time quota enforcement, where projects are granted resource quota, such as CPU hours, across the Grid by a centralized allocation authority. We implement the SweGrid Accounting System to enforce quota allocated by the Swedish National Allocations Committee in the SweGrid production Grid, which connects six Swedish HPC centers. A flexible authorization policy framework allows provisioning and enforcement of two different service levels across the SweGrid clusters; high-priority and low-priority jobs. As a solution to more fine-grained control over service levels we propose and implement a <i>Grid</i> <i>Market </i>system, using a market-based resource allocator called Tycoon. The conclusion of our research is that although the Grid accounting solution offers better service level enforcement support than state-of-the-art production Grid systems, it turned out to be complex to set the resource price and other policies manually, while ensuring fairness and efficiency of the system. Our Grid Market on the other hand sets the price according to the dynamic demand, and it is further incentive compatible, in that the overall system state remains healthy even in the presence of strategic users.</p>

[pt] O desenvolvimento de metaheurísticas paralelas autonômicas para serem executadas eficientemente em ambientes de grid é o objetivo desta tese. A aplicação paralela deve ser capaz de se auto-adaptar às mudanças que ocorrem dinamicamente no ambiente, sem que o usuário precise interferir diretamente no código da mesma. Para isso, a metaheurística autonômica deve ser vista como uma aplicação com dois níveis independentes: middleware e estratégia. O middleware é responsável por gerenciar todo o ambiente de execução, de acordo com as características da aplicação. A estratégia hierárquica distribuída permite a cooperação entre todos os processos envolvidos, sem degradar o desempenho da aplicação devido ao aumento da comunicação entre processos. Para validar esta proposta foram desenvolvidas duas implementações paralelas de metaheurísticas, uma para o problema do torneio com viagens espelhado e a outra para o problema da árvore geradora de custo mínimo com restrição de diâmetro. Para ambos os problemas, as implementações desenvolvidas foram testadas no ambiente grid Sinergia, formado por máquinas localizadas em três diferentes cidades do Estado do Rio de Janeiro. As parelizações foram capazes de melhorar, para várias instâncias, os melhores resultados conhecidos na literatura. / [en] The development of autonomic parallel metaheuristics to be efficiently executed in computational grid is the challenge of this thesis. The parallel application must be able to self-adjust to the changes that occur dynamically in the environment, without the user needing to interfere directly in the code of the application. For this, the autonomic metaheuristic should be seen as an application on two independent levels: middleware and strategy. The middleware is responsible for managing the entire execution environment, according to the characteristics of the application. The distributed hierarchical strategy enables the cooperation between all processes involved, without degrading the performance of the application due to increased communication between processes. To validate this proposal, two parallel implementations of metaheuristics were developed, one for the mirrored traveling tournament problem and the other for the diameter constrained minimum spanning tree problem. For both problems, the developed implementations were tested in the grid Synergy environment, formed by machines located in three different cities in the state of Rio de Janeiro. The paralelizations improved, for several instances, the best known results in the literature.