Escalonamento em Grid tem sido vastamente estudado devido à sua grande importância para o desempenho da Grid. Dada a sua complexidade, este é subdividido em escalonamento de recursos e de aplicações. A qualidade do escalonamento está relacionada ao algoritmo de escalonamento de tarefas. O presente trabalho tem como objetivo apresentar a metodologia AGSA (Analysis of Grid Scheduling Algorithms) para a comparação de algoritmos de escalonamento de tarefas em Grid. O intuito desta metodologia é analisar o comportamento e desempenho dos algoritmos em diversos cenários. O ambiente de simulação CEGSE (Characterization oriEnted Grid Scheduling Environment) foi desenvolvido para a criação e simulação destes cenários. Os estudos de caso comprovam a eficácia da metodologia. / Grid Scheduling has been studied because it is very important for Grid performance. Due Grid Scheduling\'s complexity, it is subdivided in resource and application scheduling. The quality of scheduling is related a tasks scheduling algorithm. The dissertation presents the AGSA (Analysis of Grid Scheduling Algorithms) methodology for comparison of Grid Scheduling Algorithms in Grid Computing. The methodology purpose is the behavior and performance analysis of algorithms in various scenarios. The CEGSE (Characterization oriEnted Grid Scheduling Environment) simulation environment is developed for this scenarios create and simulate. The case studies ratify the methodology efficiency.

O termo grade computacional faz referência a uma classe de sistemas distribuídos que permitem a associação e a integração de múltiplos domínios em organizações virtuais. Um serviço de controle de acesso coerente a sistemas com estas características deve ser flexível para integrar múltiplas políticas, permitindo que administradores, sítios e usuários determinem as regras e os mecanismos para proteger seus recursos. Esta tese apresenta o GridMultiPolicy, um sistema flexível para o gerenciamento e a integração de múltiplas políticas e mecanismos para a efetivação de controle de acesso em ambientes de grade computacional. Adicionalmente, foram desenvolvidas políticas para demonstrar a capacidade do sistema proposto em oferecer respostas às necessidades presentes em cenários de uso de uma grade computacional. O impacto da utilização do GridMultiPolicy e das políticas desenvolvidas foi avaliado por meio de testes de desempenho. Palavras-chave: Grade computacional. Grades. Sistemas distribuídos. Políticas de segurança em organizações virtuais. GridMultiPolicy. / The term computational grid refers to a class of distributed systems that allows for the association and integration of multiple independent domains in virtual organizations. A coherent access control services in such a system should be flexible to integrate multiple polices so as to permit administrators, sites, and users to determine roles and mechanisms to protect their resources. This thesis introduces the GridMultiPolicy, a flexible system that manages and integrates multiple policies and mechanisms to enforce access control in grid environments. Additionally, policies have been developed to show how the proposed system is able to offer answers to security needs present in grid use scenarios. The impact of the GridMultiPolicy and the developed policies was evaluated by performance tests. Key-words: Computational grid. Grid. Distribuited system. Virtual organization. Policy and security for virtual organization. GridMultiPolicy.

No Brasil as informações sobre o câncer estão distribuídas entre diferentes instituições que realizam o seu tratamento, nesse contexto são necessárias ferramentas para o levantamento do cenário nacional que possa auxiliar na atenção a doença. Este contexto motivou a criação do Oncogrid, que é uma grade computacional para integração e compartilhamento de dados médicos em oncologia e permitirá à comunidade médica a análise dos tratamentos aplicados com reflexos na gestão do câncer. Foi realizada uma pesquisa analizando as diferentes arquiteturas e componentes utilizados em projetos de grade voltados à saúde, a fim de propor uma arquitetura flexível, modular e escalável para o Oncogrid, em conformidade com as necessidades brasileiras. Realizou-se um projeto piloto entre o LSI/EPUSP e o NUTES/UFPE o qual implementou uma aplicação para geração de curvas de sobrevida utilizando o método Kaplan-Meier e serviu para avaliar a arquitetura do Oncogrid. Os resultados obtidos comprovaram a viabilidade da arquitetura utilizada e o potencial da proposta de uma grade computacional como um novo paradigma para a integração e compartilhamento de informações. O Oncogrid mostrou-se uma arquitetura computacional interessante para a realidade brasileira, especialmente no acesso as informações distribuídas, o que pode fornecer maiores subsídios para a evolução dos tratamentos e desenvolvimento de novas frentes de pesquisas. / In Brazil the cancer information is distributed among several institutions that accomplish your treatment, in this context we are need tools to build a national scenery that can be aid the cancer care. This context motivated the Oncogrid creation that is a grid computing for integration and sharing medical data in oncology and will allow the medical community to analise the applied treatments with reflection in cancer management.A study was done to analise the several architectures and components used in grid projects to health care, making possible to propose a flexible, modular and scalable architecture to the Oncogrid accordingly with the brazilian reality. An initial project between LSI/EPUSP and NUTES/UFPE that was developed an application to plot the survival curve using the Kaplan-Meier method and allow the evaluation of the Oncogrid architecture. The results achieved confirm the architecture viability used and the proposal potentiality of a grid computing with a new paradigm to the integration and sharing informations. The Oncogrid shows a viable computing architecture to Brazil, especially to access distributed information that can be prove great contributions to treatment evolution and to develop new research areas.

A grande demanda por computação de alto desempenho culminou na construção de ambientes de execução de larga escala como as Grades Computacionais. Não diferente de outras plataformas de execução, seus usuários precisam obter os dados de entrada para suas aplicações e muitas vezes precisam armazenar os resultados por elas gerados. Apesar de o termo Grade ter surgido de uma metáfora onde os recursos computacionais estão tão facilmente acessíveis como os da rede elétrica, as ferramentas para gerenciamento de dados e de recursos de armazenamento disponíveis estão muito aquém do necessário para concretizar essa idéia. A imaturidade desses serviços se torna crítica para aplicações científicas que necessitam processar grandes volumes de dados. Nesses casos, utiliza-se apenas os recursos de alto desempenho e assegura-se confiabilidade, disponibilidade e segurança para os dados através de presença humana. Este trabalho apresenta o JavaRMS, um sistema de gerência de dados para Grades. Ao empregar um modelo par-a-par, consegue-se agregar os recursos menos capacitados disponíveis no ambiente de Grade, diminuindo-se assim o custo da solução. O sistema utiliza a técnica de nodos virtuais para lidar com a grande heterogeneidade de recursos, distribuindo os dados de acordo com o espaço de armazenamento fornecido. Empregase fragmentação para viabilizar o uso dos recursos menos capacitados e para melhorar o desempenho das operações que envolvem a transferência de arquivos. Utiliza-se replicação para prover persistência aos dados e para melhorar sua disponibilidade. JavaRMS lida ainda com a dinamicidade e a instabilidade dos recursos através de um modelo de estados, de forma a diminuir o impacto das operações de manutenção. A arquitetura contempla também serviços para gerenciamento de usuários e protege os recursos contra fraudes através de um sistema de cotas. Todas as operações foram projetadas para serem seguras. Por fim, disponibiliza-se toda a infra-estrutura necessária para que serviços de busca e ferramentas de interação com o usuário sejam futuramente fornecidos. Os experimentos realizados com o protótipo do JavaRMS comprovam que usar um modelo par-a-par para organizar os recursos e localizar os dados resulta em boa escalabilidade. Já a técnica de nodos virtuais se mostrou eficiente para distribuir de forma balanceada os dados entre as máquinas, de acordo com a capacidade de armazenamento oferecida. Através de testes com a principal operação que envolve a transferência de arquivos, comprovou-se que o modelo é capaz de melhorar significativamente o desempenho de aplicações que necessitam processar grandes volumes de dados. / Large scale execution environments such as Grids emerged to meet high-performance computing demands. Like in other execution platforms, its users need to get input data to their applications and to store their results. Although the Grid term is a metaphor where computing resources are so easily accessible as those from the eletric grid, its data and resource management tools are not sufficiently mature to make this idea a reality. They usually target high-performance resources, where data reliability, availability and security is assured through human presence. It turns to be critical when scientific applications need to process huge amounts of data. This work presents JavaRMS, a Grid data management system. By using a peer-topeer model, it aggregates low capacity resources to reduce storage costs. Resource heterogeneity is dealt with the virtual node technique, where peers receive data proportionally to their provided storage space. It applies fragmentation to make feasible the usage of low capacity resources and to improve file transfer operations performance. Also, the system achieves data persistence and availability through replication. In order to decrease the impact of maintenance operations, JavaRMS deals with resource dinamicity and instability with a state model. The architecture also contains user management services and protects resources through a quota system. All operations are designed to be secure. Finally, it provides the necessary infrastructure for further deployment of search services and user interactive tools. Experiments with the JavaRMS prototype showed that using a peer-to-peer model for resource organization and data location results in good scalability. Also, the virtual node technique showed to be efficient to provide heterogeneity-aware data distribution. Tests with the main file transfer operation proved the model can significantly improve data-intensive applications performance.

As grades computacionais e as redes peer-to-peer (P2P) surgiram como áreas distintas, com diferentes propósitos, modelos e ferramentas. No decorrer dos últimos anos, estas áreas foram convergindo, uma vez que a infraestrutura e o modelo de execução descentralizada das redes P2P provaram ser uma alternativa adequada para o tratamento de questões relacionadas à manutenção de grades de larga escala, tais como escalabilidade, descoberta, alocação e monitoramento de recursos. O modelo MultiCluster trata a convergência entre grades computacionais e redes peer-to-peer de uma forma mais restrita: os problemas de escalabilidade, de descoberta e alocação de recursos são minimizados considerando-se apenas recursos localmente disponíveis para a construção de uma grade, a qual pode ser usada para a execução de aplicações com diferentes características de acoplamento e comunicação. Esse trabalho apresenta a arquitetura do modelo e seus aspectos funcionais, bem como um primeira implementação do modelo, realizada através da adaptação da biblioteca de programação DECK sobre os protocolos do projeto JXTA. A avaliação do funcionamento dessa implementação é apresentada e discutida, com base em algumas aplicações com diferentes características. / Grid computing and peer-to-peer computing emerged as distinct areas with different purposes, models and tools. Over the last years, these areas has been converging since the infrastructure and the execution model used in peer-to-peer networks have proven to be a suitable way to treat some problems related to the maintenance of large scale grids, such as scalability, monitoring, and resource discovery and allocation. The MultiCluster model addresses the convergence of grids and peer-to-peer networks in a more restricted way: the problems related to scalability, resource allocation and discovery are minimized by considering only local resources for the conception of a small scale grid, which can be used to run applications with different characteristics of granularity and communication. This work presents the MultiCluster architecture and its functional aspects, as well as a first implementation carried out by adapting the DECK programming library to use JXTA protocols and its consequent evaluation, based on applications with different characteristics.

No Brasil as informações sobre o câncer estão distribuídas entre diferentes instituições que realizam o seu tratamento, nesse contexto são necessárias ferramentas para o levantamento do cenário nacional que possa auxiliar na atenção a doença. Este contexto motivou a criação do Oncogrid, que é uma grade computacional para integração e compartilhamento de dados médicos em oncologia e permitirá à comunidade médica a análise dos tratamentos aplicados com reflexos na gestão do câncer. Foi realizada uma pesquisa analizando as diferentes arquiteturas e componentes utilizados em projetos de grade voltados à saúde, a fim de propor uma arquitetura flexível, modular e escalável para o Oncogrid, em conformidade com as necessidades brasileiras. Realizou-se um projeto piloto entre o LSI/EPUSP e o NUTES/UFPE o qual implementou uma aplicação para geração de curvas de sobrevida utilizando o método Kaplan-Meier e serviu para avaliar a arquitetura do Oncogrid. Os resultados obtidos comprovaram a viabilidade da arquitetura utilizada e o potencial da proposta de uma grade computacional como um novo paradigma para a integração e compartilhamento de informações. O Oncogrid mostrou-se uma arquitetura computacional interessante para a realidade brasileira, especialmente no acesso as informações distribuídas, o que pode fornecer maiores subsídios para a evolução dos tratamentos e desenvolvimento de novas frentes de pesquisas. / In Brazil the cancer information is distributed among several institutions that accomplish your treatment, in this context we are need tools to build a national scenery that can be aid the cancer care. This context motivated the Oncogrid creation that is a grid computing for integration and sharing medical data in oncology and will allow the medical community to analise the applied treatments with reflection in cancer management.A study was done to analise the several architectures and components used in grid projects to health care, making possible to propose a flexible, modular and scalable architecture to the Oncogrid accordingly with the brazilian reality. An initial project between LSI/EPUSP and NUTES/UFPE that was developed an application to plot the survival curve using the Kaplan-Meier method and allow the evaluation of the Oncogrid architecture. The results achieved confirm the architecture viability used and the proposal potentiality of a grid computing with a new paradigm to the integration and sharing informations. The Oncogrid shows a viable computing architecture to Brazil, especially to access distributed information that can be prove great contributions to treatment evolution and to develop new research areas.

The advance in technologies such as massive storage devices and high speed internet has led to an enormous increase in the volume of available documents in electronic form. These documents represent information in a complex and rich manner that cannot be analysed using conventional statistical data mining methods. Consequently, text mining is developed as a growing new technology for discovering knowledge from textual data and managing textual information. Processing and analysing textual information can potentially obtain valuable and important information, yet these tasks also requires enormous amount of computational resources due to the sheer size of the data available. Therefore, it is important to enhance the existing methodologies to achieve better scalability, efficiency and accuracy. / The emerging Grid technology shows promising results in solving the problem of scalability by splitting the works from text clustering algorithms into a number of jobs, each to be executed separately and simultaneously on different computing resources. That allows for a substantial decrease in the processing time and maintaining the similar level of quality at the same time. / To improve the quality of the text clustering results, a new document encoding method is introduced that takes into consideration of the semantic similarities of the words. In this way, documents that are similar in content will be more likely to be group together. / One of the ultimate goals of text mining is to help us to gain insights to the problem and to assist in the decision making process together with other source of information. Hence we tested the effectiveness of incorporating text mining method in the context of stock market prediction. This is achieved by integrating the outcomes obtained from text mining with the ones from data mining, which results in a more accurate forecast than using any single method.

<p>Scientific Computing is the collection of tools, techniques, and theories required to solve on a computer, mathematical models of problems from science and engineering, and its main goal is to gain insight in such problems. Generally, it is difficult to understand or communicate information from complex or large datasets generated by Scientific Computing methods and techniques (computational simulations, complex experiments, observational instruments etc.). Therefore, support of Scientific Visualization is needed, to provide the techniques, algorithms, and software tools needed to extract and display appropriately important information from numerical data.</p><p>Usually, complex computational and visualization algorithms require large amounts of computational power. The computing power of a single desktop computer is insufficient for running such complex algorithms, and, traditionally, large parallel supercomputers or dedicated clusters were used for this job. However, very high initial investments and maintenance costs limit the availability of such systems. A more convenient solution, which is becoming more and more popular, is based on the use of nondedicated desktop PCs in a Desktop Grid Computing environment. Harnessing idle CPU cycles, storage space and other resources of networked computers to work together on a particularly computational intensive application does this. Increasing power and communication bandwidth of desktop computers provides for this solution.</p><p>In a desktop grid system, the execution of an application is orchestrated by a central scheduler node, which distributes the tasks amongst the worker nodes and awaits workers’ results. An application only finishes when all tasks have been completed. The attractiveness of exploiting desktop grids is further reinforced by the fact that costs are highly distributed: every volunteer supports her resources (hardware, power costs and internet connections) while the benefited entity provides management infrastructures, namely network bandwidth, servers and management services, receiving in exchange a massive and otherwise unaffordable computing power. The usefulness of desktop grid computing is not limited to major high throughput public computing projects. Many institutions, ranging from academics to enterprises, hold vast number of desktop machines and could benefit from exploiting the idle cycles of their local machines.</p><p>In the work presented in this thesis, the central idea has been to provide a desktop grid computing framework and to prove its viability by testing it in some Scientific Computing and Visualization experiments. We present here QADPZ, an open source system for desktop grid computing that have been developed to meet the above presented needs. QADPZ enables users from a local network or Internet to share their resources. It is a multi-platform, heterogeneous system, where different computing resources from inside an organization can be used. It can be used also for volunteer computing, where the communication infrastructure is the Internet. QADPZ supports the following native operating systems: Linux, Windows, MacOS and Unix variants. The reason behind natively supporting multiple operating systems, and not only one (Unix or Windows, as other systems do), is that often, in real life, this kind of limitation restricts very much the usability of desktop grid computing.</p><p>QADPZ provides a flexible object-oriented software framework that makes it easy for programmers to write various applications, and for researchers to address issues such as adaptive parallelism, fault-tolerance, and scalability. The framework supports also the execution of legacy applications, which for different reasons could not be rewritten, and that makes it suitable for other domains as business. It also supports low-level programming languages as C/C++ or high-level language applications, (e.g. Lisp, Python, and Java), and provides the necessary mechanisms to use such applications in a computation. Consequently, users with various backgrounds can benefit from using QADPZ. The flexible object-oriented structure and the modularity allow facile improvements and further extensions to other programming languages.</p><p>We have developed a general-purpose runtime and an API to support new kinds of high performance computing applications, and therefore to benefit from the advantages offered by desktop grid computing. This API directly supports the C/C++ programming language. We have shown how distributed computing extends beyond the master-worker paradigm (typical for such systems) and provided QADPZ with an extended API that supports in addition lightweight tasks and parallel computing (using the message passing paradigm - MPI). This extends the range of applications that can be used to already existing MPI based applications - e.g. parallel numerical solvers used in computational science, or parallel visualization algorithms.</p><p>Another restriction of existing systems, especially middleware based, is that each resource provider needs to install a runtime module with administrator privileges. This poses some issues regarding data integrity and accessibility on providers computers. The QADPZ system tries to overcome this by allowing the middleware module to run as a non-privileged user, even with restricted access, to the local system.</p><p>QADPZ provides also low-level optimizations, such as on-the-fly compression and encryption for communication. The user can choose from different algorithms, depending on the application, improving both the communication overhead imposed by large data transfers and keeping privacy of the data. The system goes further, by providing an experimental, adaptive compression algorithm, which can transparently choose different algorithms to improve the application. QADPZ support two different protocols (UDP and TCP/IP) in order to improve the efficiency of communication.</p><p>Free source code allows its flexible installations and modifications based on the particular needs of research projects and institutions. In addition to being a very powerful tool for computationally intensive research, the open sourceness makes QADPZ a flexible educational platform for numerous smallsize student projects in the areas of operating systems, distributed systems, mobile agents, parallel algorithms, etc. Open source software is a natural choice for modern research as well, because it encourages effectively integration, cooperation and boosting of new ideas.</p><p>This thesis proposes also an improved conceptual model (based on the master-worker paradigm), which makes contributions in several directions: pull vs. push work-units, pipelining of work-units, more work-units sent at a time, adaptive number of workers, adaptive time-out interval for work-units, and multithreading. We have also demonstrated that the use of desktop grids should not be limited to only master-worker applications, but it can be used for more fine-grained parallel Scientific Computing and Visualization applications, by performing some specific experiments. This thesis makes supplementary contributions: a hierarchical taxonomy of the main existing desktop grids, and an adaptive compression algorithm for remote visualization. QADPZ has also pioneered autonomic computing approach for desktop grids and presents specific self-management features: self-knowledge, self-configuration, selfoptimization and self-healing. It is worth to mention that to the present the QADPZ has over a thousand users who have download it (since July, 2001 when it has been uploaded to sourceforge.net), and many of them use it for their daily tasks (see the appendix). Many of the results have been published or are in course of publishing as it can be seen from the references.</p>

<p>During the past decade, Grid computing has gained popularity as a means to build powerful computing infrastructures by aggregating distributed computing capacity. Grid technology allows computing resources that belong to different organizations to be integrated into a single unified system image – a Grid. As such, Grid technology constitutes a key enabler of large-scale, crossorganizational sharing of computing resources. An important objective for the Virtual Organizations (VOs) that result from such sharing is to tame the distributed capacity of the Grid in order to manage it and make fair and efficient use of the pooled computing resources.</p><p>Most Grids to date have, however, been completely unregulated, essentially serving as a “source of free CPU cycles” for authorized Grid users. Whenever unrestricted access is admitted to a shared resource there is a risk of overexploitation and degradation of the common resource, a phenomenon often referred to as “the tragedy of the commons”. This thesis addresses this problem by presenting two complementary Grid capacity allocation systems that allow the aggregate computing capacity of a Grid to be divided between users in order to protect the Grid from overuse while delivering fair service that satisfies the individual computational needs of different user groups.</p><p>These two Grid capacity allocation mechanisms constitute the core contribution of this thesis. The first mechanism, the SweGrid Accounting System (SGAS), addresses the need for coordinated soft, real-time quota enforcement across Grid sites. The SGAS project was an early adopter of the serviceoriented principles that are now common practice in the Grid community, and the system has been tested in the Swegrid production environment. Furthermore, SGAS has been included in the Globus Toolkit, the de-facto standard Grid middleware toolkit. SGAS employs a credit-based allocation model where research projects are granted quota allowances that can be spent across the Grid resources, which charge users for their resource consumption. This enforcement of usage limits thus produces real-time overuse protection.</p><p>The second approach, employed by the Fair Share Grid (FSGrid) system, uses a share-based allocation model where project entitlements are expressed in terms of hierarchical share policies that logically divide the Grid capacity between user groups. By coordinating local job scheduling to maintain these global capacity shares, the Grid resources collectively strive to schedule users for a “share of the Grid”. We refer to this cooperative scheduling model as decentralized Grid-wide fairshare scheduling.</p>

<p>The emergence of Grid computing infrastructures enables researchers to share resources and collaborate in more efficient ways than before, despite belonging to different organizations and being distanced geographically. While the Grid computing paradigm offers new opportunities, it also gives rise to new difficulties. One such problem is the selection of resources for user applications. Given the large and disparate set of Grid resources, manual resource selection becomes impractical, even for experienced users. This thesis investigates methods, algorithms and software for a Grid resource broker, i.e., a scheduling agent that automates the resource selection process for the user. The development of such a component is a non-trivial task as Grid resources are heterogeneous in hardware, software, availability, ownership and usage policies. A wide range of algorithmically difficult issues must also be solved, including characterization of jobs, prediction of resource performance, data placement considerations, and, how to provide Quality of Service guarantees. One contribution of this thesis is the development of resource brokering algorithms that enable resource selection based on Grid job performance predictions and use advance reservations to provide Quality of Service guarantees. The thesis also includes an algorithm for coallocation of sets of jobs. This algorithm guarantees a simultaneous start of each subjob, as required e.g., when running larger-than-supercomputer simulations that involve multiple resources.</p><p>We today have the somewhat paradoxal situation where Grids, originally aimed to overcome interoperability problems between different computing platforms, themselves struggle with interoperability problems caused by the wide range of interfaces, protocols and data formats that are used in different environments. The reasons for this situation are obvious, expected and almost impossible to avoid, as the task of defining appropriate standards, models and best-practices must be preceded by basic research, proof-of-concept implementations and real-world testing. We address the interoperability problem with a generic Grid resource brokering architecture and job submission service.</p><p>By using (proposed) standard formats and protocols, the service acts as an interoperability-bridge that translates job requests between clients and resources running different Grid middlewares. This concept is demonstrated by the integration of the service with three different Grid middlewares. The service also enables users to both fine-tune the existing resource selection algorithms and plug in custom brokering algorithms tailored to their requirements.</p>