[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.

We study techniques to enforce and provision differentiated service levels in Computational Grid 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 Grid Market 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. / QC 20101116

OGrid Anywhere é um middleware de grade computacional ponto-aponto (P2P), capaz de agrupar em uma organização virtual ou federação qualquer equipamento dotado de recursos computacionais, inclusive receptores digitais. O objetivo deste projeto de mestrado apresentado nesta monografia é desenvolver e avaliar algoritmos de escalonamento que possibilitem uma distribuição adequada de processos nos elementos da grade computacional proposta pelo Grid Anywhere. Foram realizados experimentos utilizando o simulador GridSim, simulando um ambiente definido por esse middleware. Por meio dessa junção entre Grades Computacionais e TV Digital, pretende-se promover a inclusão digital permitindo que recursos computacionais sejam compartilhados de maneira a possibilitar que usuários com receptores limitados executem aplicações que demandem mais recursos que aqueles ofertados pelo hardware / GRid Anywhere is a middleware for grid computing peer-to-peer (P2P), capable of bringing together into a virtual organization or federation any equipment having computing resources, including digital receivers. The objective of this masters project presented in this monograph is to develop and evaluate scheduling algorithms that allow an adequate distribution of applications in computational grid elements proposed by the Grid Anywhere. Experiments were carried out using the GridSim simulator, simulating an environment defined by the middleware. Through this joint between Grid Computing and Digital TV, it is possible to promote digital inclusion by allowing computing resources to be shared, so as to enable users with limited receivers to run applications that require more resources than those offered by the hardware

OGrid Anywhere é um middleware de grade computacional ponto-aponto (P2P), capaz de agrupar em uma organização virtual ou federação qualquer equipamento dotado de recursos computacionais, inclusive receptores digitais. O objetivo deste projeto de mestrado apresentado nesta monografia é desenvolver e avaliar algoritmos de escalonamento que possibilitem uma distribuição adequada de processos nos elementos da grade computacional proposta pelo Grid Anywhere. Foram realizados experimentos utilizando o simulador GridSim, simulando um ambiente definido por esse middleware. Por meio dessa junção entre Grades Computacionais e TV Digital, pretende-se promover a inclusão digital permitindo que recursos computacionais sejam compartilhados de maneira a possibilitar que usuários com receptores limitados executem aplicações que demandem mais recursos que aqueles ofertados pelo hardware / GRid Anywhere is a middleware for grid computing peer-to-peer (P2P), capable of bringing together into a virtual organization or federation any equipment having computing resources, including digital receivers. The objective of this masters project presented in this monograph is to develop and evaluate scheduling algorithms that allow an adequate distribution of applications in computational grid elements proposed by the Grid Anywhere. Experiments were carried out using the GridSim simulator, simulating an environment defined by the middleware. Through this joint between Grid Computing and Digital TV, it is possible to promote digital inclusion by allowing computing resources to be shared, so as to enable users with limited receivers to run applications that require more resources than those offered by the hardware

Existem atualmente diversas propostas para integração de dispositivos móveis em uma grade computacional, porém vários problemas são observados em tais ambientes. Esta dissertação mantém o foco em um problema, a restrição sobre a quantidade de energia despendida na execução das aplicações, ao utilizar esses dispositivos móveis como provedores de recursos em uma grade computacional que fornece processamento para aplicações paralelas. Para tanto, este trabalho propõe um método para estimar o consumo de energia das aplicações considerando que elas utilizam um determinado conjunto de operações as quais estão presentes na grande maioria das aplicações paralelas (operações matemáticas e alocação de memória). Com base no método proposto, dois dispositivos móveis foram estudados e foi criada uma representação do consumo de energia utilizando-se de métodos de regressão. Para validar os modelos, duas aplicações foram analisadas e o consumo de energia real foi comparado ao consumo estimado. O modelo criado apresentou resultados próximos ao medido, mostrando um aumento entre 6% e 14,24% em relação ao resultado medido. / Nowadays, there are different proposals to integrate mobile devices in a computational grid, although several problems are introduces. This dissertation focus on the energy limitation problem when using mobile devices to provide resources, such as processing power to run parallel applications. It also proposes a method to estimate energy consumption for a task that needs to be executed in this environment. To achieve this goal two mobile devices were used as a test case and a representation of its energy consumption was created running benchmarks and using regression techniques. To validate the model created, two applications were executed and had the measured values compared to the estimated ones. The estimation showed a raise between 6 and 14.24 percent.

Philosophiae Doctor - PhD / The high rate of grid computing adoption, both in academe and industry, has posed challenges regarding efficient access control, interoperability and scalability. Although several methods have been proposed to address these grid computing challenges, none has proven to be completely efficient and dependable. To tackle these challenges, a novel access control architecture framework, a triple-domain grid-based environment, modelled on role based access control, was developed. The architecture’s framework assumes three domains, each domain with an independent Local Security Monitoring Unit and a Central Security Monitoring Unit that monitors security for the entire grid.The architecture was evaluated and implemented using the G3S, grid security services simulator, meta-query language as “cross-domain” queries and Java Runtime Environment 1.7.0.5 for implementing the workflows that define the model’s task. The simulation results show that the developed architecture is reliable and efficient if measured against the observed parameters and entities. This proposed framework for access control also proved to be interoperable and scalable within the parameters tested.

Existem atualmente diversas propostas para integração de dispositivos móveis em uma grade computacional, porém vários problemas são observados em tais ambientes. Esta dissertação mantém o foco em um problema, a restrição sobre a quantidade de energia despendida na execução das aplicações, ao utilizar esses dispositivos móveis como provedores de recursos em uma grade computacional que fornece processamento para aplicações paralelas. Para tanto, este trabalho propõe um método para estimar o consumo de energia das aplicações considerando que elas utilizam um determinado conjunto de operações as quais estão presentes na grande maioria das aplicações paralelas (operações matemáticas e alocação de memória). Com base no método proposto, dois dispositivos móveis foram estudados e foi criada uma representação do consumo de energia utilizando-se de métodos de regressão. Para validar os modelos, duas aplicações foram analisadas e o consumo de energia real foi comparado ao consumo estimado. O modelo criado apresentou resultados próximos ao medido, mostrando um aumento entre 6% e 14,24% em relação ao resultado medido. / Nowadays, there are different proposals to integrate mobile devices in a computational grid, although several problems are introduces. This dissertation focus on the energy limitation problem when using mobile devices to provide resources, such as processing power to run parallel applications. It also proposes a method to estimate energy consumption for a task that needs to be executed in this environment. To achieve this goal two mobile devices were used as a test case and a representation of its energy consumption was created running benchmarks and using regression techniques. To validate the model created, two applications were executed and had the measured values compared to the estimated ones. The estimation showed a raise between 6 and 14.24 percent.

Climate science or climatology is the scientific study of the earth’s climate, where climate is the term representing weather conditions averaged over a period of time. Climate models are mathematical models used to quantitatively describe, simulate and study the interactions among the components of the climate system -atmosphere, ocean, land and sea-ice. CCSM (Community Climate System Model) is a state-of-the-art climate model, and a long-running coupled multicomponent parallel application involving component models for simulating the components of the climate system. Each of the component models is a large-scale parallel application, and the parallel components exchange climate data through a specialized component called coupler. Typical multi-century climate simulations using CCSM take several weeks or months to execute on most parallel systems. In this thesis, we study the applicability of a computational grid for effective execution of long-running coupled multi-component climate applications like CCSM. Initial studies of the application characteristics led us to develop a dynamic component extension strategy for temporal inter-component load-balancing. By means of experiments on different parallel platforms with different number of processors, we showed that using our strategy can lead to about 15% reduction and savings of several days in execution times of CCSM for 1000-year simulation runs. Our initial studies also indicated that unlike typical grid applications, CCSM has limits on scalability to very large number of processors and hence cannot directly benefit from the large number of processors on a computational grid. However, its long-running nature and the limits of execution imposed on jobs on most multi-user batch queueing systems, led us to investigate the benefits of its execution on a grid of batch systems. The idea is that multiple batch queues can improve the processor availability rate with respect to the application thereby possibly improving its effective throughput. We explored this idea in detail with simulation studies involving various system and application characteristics, and execution models. By conducting large number of simulations with different workload characteristics and queuing policies of the systems, processor allocations to components of the application, distributions of the components to the batch systems and inter-cluster bandwidths, we showed that multiple batch executions lead to upto 55% average increase in throughput over single batch executions for long-running CCSM. Having convinced ourselves of possible advantages in performance, we then ventured to construct an application-level middleware framework. Our framework supports long duration execution of multi-component applications spanning multiple submissions to queues on multiple batch systems. It coordinates the distribution, execution, rescheduling, migration and restart of the application components across resources on different sites. It also addresses challenges including execution time limits for jobs, and differences in job-startup times corresponding to different components. Further, within the framework, we developed robust rescheduling policies that decide when and where to reschedule the components to the available resources based on the application execution characteristics and queue dynamics. Our grid middleware framework resulted in multi-site executions that provided larger application throughput than single-site executions, typically performed by climate scientists, and also removed the bottlenecks associated with a single system execution. We used this framework for long-running executions of CCSM to study the effect of increased black carbon aerosols and dust aerosols on the Indian monsoons. Black Carbon aerosols are essentially of anthropogenic origin and occur due to improper burning of fossil fuels, and dust is a naturally occurring aerosol. The concentrations of both these aerosols is high over the Indian region. We study the impact of these aerosols on precipitation and sea surface temperature (SST) through multi-decadal simulations conducted with our grid-enabled climate system model. Our observations indicated that increasing the concentrations of aerosols leads to an increase in precipitation in the central and eastern parts of India, and a decrease in SST over most of Indian ocean.

Les structures planaires de tailles finies sont de plus en plus utilisées dans les applications des satellites et des radars. Deux grands types de ces structures sont les plus utilisés dans le domaine de la conception RF à savoir Les Surfaces Sélectives en Fréquence (FSS) et les Reflectarrays. Les FSSs sont un élément clé dans la conception de systèmes multifréquences. Elles sont utilisées comme filtre en fréquence, et trouvent des applications telles que les radômes, les réflecteurs pour antenne Cassegrain, etc. Les performances des FSSs sont généralement évaluées en faisant l'hypothèse d'une FSS de dimension infinie et périodique en utilisant les modes de Floquet, le temps de calcul étant alors réduit quasiment à celui de la cellule élémentaire. Plusieurs méthodes permettant la prise en compte de la taille finie des FSSs ont été développées. La méthode de Galerkin basée sur l'approche rigoureuse permet la prise en compte des interactions entre les différents éléments du réseau, mais cette technique ne fonctionne que pour les FSSs de petite taille, typiquement 3x3 éléments. Pour les grands réseaux, cette méthode n'est plus adaptée, car le temps de calcul et l'exigence en mémoire deviennent trop grands. Donc, une autre approche est utilisée, celle basée sur la décomposition spectrale en onde plane. Elle permet de considérer un réseau fini comme un réseau périodique infini, illuminé partiellement par une onde plane. Avec cette approche, des FSSs de grande taille sont simulées, mais elle ne permet pas dans la plupart des cas, de prendre en compte les couplages qui existent entre les différentes cellules du réseau, les effets de bord non plus. La simulation des FSSs par les méthodes numériques classiques basées sur une discrétisation spatiale (méthode des éléments finis, méthode des différences finies, méthode des moments) ou spectrale (méthodes modales) aboutit souvent à des matrices mal conditionnées, des problèmes de convergence numérique et/ou des temps de calcul excessifs. Pour éviter tous ces problèmes, une technique appelée technique par changements d'échelle tente de résoudre ces problèmes. Elle est basée sur le partitionnement de la géométrie du réseau en plusieurs sous-domaines imbriqués, définis à différents niveaux d'échelle du réseau. Le multi-pôle de changement d'échelle, appelé Scale-Changing Networks (SCN), modélise le couplage électromagnétique entre deux échelles successives. La cascade de ces multi-pôles de changement d'échelle, permet le calcul de la matrice d'impédance de surface de la structure complète et donc la modélisation globale du réseau. Ceci conduit à une réduction significative en termes de temps de calcul et d'espace mémoire par rapport aux méthodes numériques classiques. Comme le calcul des multi-pôles de changement d'échelle est mutuellement indépendant, les temps d'exécution peuvent encore être réduits de manière significative en parallélisant le calcul. La SCT permet donc de modéliser des FSSs Finies tout en prenant en compte le couplage entre les éléments adjacents du réseau. / The finite size planar structures are increasingly used in applications of satellite and radar. Two major types of these structures are the most used in the field of RF design ie Frequency Selective Surfaces (FSS) and the Reflectarrays. The FSSs are a key element in the design of multifrequency systems. They are used as frequency filter, and find applications such as radomes, reflector Cassegrain antenna, etc.. The performances of FSSs are generally evaluated by assuming an infinite dimensional FSS using periodic Floquet modes, the computation time is then reduced almost to that of the elementary cell. Several methods have been developed for taking into account the finite dimensions of arrays. For example the Galerkin method uses a rigorous element by element approach. With this method, the exact interactions between the elements are taken into account but this technique works only for small FSS, typically 3x3 elements. For larger surfaces, this method is no more adapted. The computation time and the memory requirement become too large. So another approach is used based on plane wave spectral decomposition. It allows considering the finite problem as a periodic infinite one locally illuminated. With this approach, large FSS are indeed simulated, but the exact interactions between the elements are not taken into account, the edge effects either. The simulation of FSS by conventional numerical methods based on spatial meshing (finite element method, finite difference, method of moments) or spectral (modal methods) often leads in the practice to poorly conditioned matrices, numerical convergence problems or/and excessive computation time. To avoid these problems, a new technique called Scale Changing Technique attempts to solve these problems. The SCT is based on the partition of discontinuity planes in multiple planar sub-domains of various scale levels. In each sub- omain the higher-order modes are used for the accurate representation of the electromagnetic field local variations while low-order modes are used for coupling the various scale levels. The electromagnetic coupling between scales is modelled by a Scale Changing Network (SCN). As the calculation of SCN is mutually independent, the execution time can still be significantly reduced by parallelizing the computation. With the SCT, we can simulate large finite FSS, taking into account the exact interactions between elements, while addressing the problem of excessive computation time and memory