Grid computing is a field of research that combines many computers from distant locations to form one large computing resource. In order to be able to make use of the full potential of such a system there is a need to effectively manage resources on the Grid. There are numerous scheduling systems to perform this management for clusters of computers and a few scheduling systems for the Grid. These systems try for optimality (or close to optimality) with the goals of obtaining good throughput and minimizing job completion time. In this research, we examine issues that we believe have not been tackled in schedulers for the Grid. These issues revolve around the problem of coordinating resources belonging to separate administrative domains and scheduling in this context. In order for grid computing's vision of virtual organizations to be realized to its fullest extent, there is a need to implement and test schedulers that find resources and schedule tasks on them in a manner that is transparent to the user. These resources might be on a different administrative domain altogether and obtaining either resource or user account information on those resources might be difficult. Also, each organization might require their own policies and mechanisms to be enforced. Hence having a centralized scheduler is not feasible due to the pragmatics of the Grid. There are two basic aims to this thesis. The first aim is to design and implement a framework that takes administrative concerns into consideration during scheduling. The aim of the framework is to provide a lightweight, extensible, secure and scalable architecture under which multiple scheduling algorithms can be implemented. Second, we evaluate two prototypical of scheduling algorithms in the context of this framework. Scheduling algorithms are diverse and the applications are varied. Thus no single algorithm can obtain a good mapping for every application. We believe that different scheduling algorithms will be necessary to schedule different types of applications. In order to facilitate development of such algorithms, a framework in which it is easy to integrate other scheduling algorithms is necessary. The framework developed in this project is designed for such extensibility. / Master of Science

Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-08-18T14:43:06Z No. of bitstreams: 1 Gilberto.pdf: 2769310 bytes, checksum: 210d2e0115f0c134b325cbf3a2354263 (MD5) / Made available in DSpace on 2017-08-18T14:43:06Z (GMT). No. of bitstreams: 1 Gilberto.pdf: 2769310 bytes, checksum: 210d2e0115f0c134b325cbf3a2354263 (MD5) Previous issue date: 2009-02-13 / CAPES / During the development of Grid middleware systems, researchers often employ simulation tools and techniques for validating new concepts and implementations. Simulation tools play a fundamental role on the development of Grid middleware systems since: (a) researchers often do not have access to huge Grid testbed environments, limiting the capacity for evaluating situations that demand high amount of resources; (b) it is difficult to explore in large scale application and resources scenarios involving several users in a repetitive and controlled way, due to the dynamic nature of Grid environments; (c) real Grid applications usually consume great amount of time, ranging from a few hours to even weeks. This work describes OGST, an object-oriented discrete event simulator whose main objective is to assist developers of opportunistic Grid middleware on validating new concepts and implementations. The preliminary motivation for OGST development was to provide a way for evaluating the behavior of scheduling algorithms commonly used on Grid environments under different execution environment conditions and the investigation of adaptive scheduling approaches. It was carefully designed to take into consideration the dynamics of opportunistic Grids, providing a set of features that hasten the development of simulations that takes into consideration the dynamism of the execution environment. The simulator was developed in the context of the InteGrade project, but was designed to allow the simulation of generic opportunistic Grids in order to be applied by other Grid middleware research projects. / Durante o desenvolvimento de sistemas de middleware de grade, pesquisadores freqüentemente empregam técnicas e ferramentas de simulação para valida- ção de novos conceitos e implementações. Ferramentas de simulação têm um papel fundamental no desenvolvimento de sistemas de middleware de grade uma vez que: (a) pesquisadores freqüentemente não têm acesso a grandes ambientes de grade para testes, limitando a capacidade para avaliar situações que demandam por uma grande quantidade de recursos; (b) é difícil explorar cenários com recursos e aplicações em larga escala envolvendo diversos usuários de forma repetitiva e controlada, devido à natureza dinâmica de ambientes de grade; (c) aplicações reais da grade geralmente consomem muito tempo, de poucas horas até mesmo a semanas. Este trabalho descreve o OGST, um simulador de eventos discretos orientado a objetos cujo principal objetivo é auxiliar desenvolvedores de sistemas de middleware de grade oportunista na validação de novos conceitos e implementações. A motivação preliminar para o desenvolvimento do OGST foi prover um caminho para avaliar o comportamento de algoritmos de escalonamento comumente usados em ambientes de grade sob diferentes condições do ambiente de execução e a investigação de abordagens de escalonamento adaptativo. Ele foi cuidadosamente projetado para levar em consideração a dinâmica de grades oportunistas, provendo um conjunto de funcionalidades que agilizam o desenvolvimento de simulações que consideram o dinamismo do ambiente de execução. O simulador foi desenvolvido no contexto do projeto InteGrade, mas foi projetado para permitir a simulação de grades oportunistas de uma maneira em geral com o propósito de ser aplicado a outros projetos de pesquisa envolvendo middleware de grades.

Today many computing resources distributed geographically are idle much of time. The aim of the grid computing is collecting these resources into a single system. It helps to solve problems that are too complex for a single PC. Scheduling plays a critical role in the efficient and effective management of resources to achieve high performance on grid computing environment. Due to the heterogeneity and highly dynamic nature of grid, developing scheduling algorithms for grid computing involves some challenges. In this work, we concentrate on efficient scheduling of distributed tasks on grid. We propose a novel scheduling heuristic for bag-of-tasks applications. The proposed algorithm primarily makes use of history based runtime estimation. The history stores information about the applications whose runtimes and other specific properties are recorded during the previous executions. Scheduling decisions are made according to similarity between the applications. Definition of similarity is an important aspect of this approach, apart from the best resource allocation. The aim of this scheduling algorithm (HISA-History Injected Scheduling Algorithm) is to define and find the similarity, and assign the job to the most suitable resource, making use of the similarity. In our evaluation, we use Grid simulation tool called GridSim. A number of intensive experiments with various simulation settings have been conducted. Based on the experimental results, the effectiveness of HISA scheduling heuristic is studied and compared to the other scheduling algorithms embedded in GridSim. The results show that history injection improves the performance of future job submissions on a grid.

As computational grids have become popular and ubiquitous, users have access to large number and different types of geographically distributed grid resources. Many computational grid frameworks are composed of multiple distributed sites with each site consisting of one or more dedicated or non-dedicated clusters. Jobs submitted to a grid are handled by a matascheduler which interacts with the local schedulers of the clusters for scheduling jobs to the individual clusters. Computational grids have been found to be powerful research-beds for execution of various kinds of parallel applications. When a parallel application is submitted to a grid, the metascheduler has to choose a set of resources from a cluster for application execution. To select the best set of resources for application execution, it is important to determine the performance of the application. Accurate performance estimates of an application is essential in assisting a grid meta scheduler to efficiently schedule user jobs. Thus models that predict execution times of parallel applications on a set of resources and a search procedure (scheduling strategy) which selects the best set of machines within a cluster for application execution are of importance for enabling the parallel applications on grids. For efficient execution of large scientific parallel applications consisting of multiple phases, performance models of the individual phases should be obtained. Efficient rescheduling strategies that can use the per-phase models to adapt the parallel applications to application and resource dynamics are necessary for maintaining high performance of the applications on grids. A practical and robust grid computing infrastructure that integrates components related to application and resource monitoring, performance modeling, scheduling and rescheduling techniques, is highly essential for large-scale deployment and high performance of scientific applications on grid systems and hence for fostering high performance computing. This thesis focuses on developing performance models for predicting execution times of parallel problems/subproblems on dedicated and non-dedicated grid resources. The thesis also constructs robust scheduling and rescheduling strategies in a grid metascheduler that can use the performance models for efficient execution of large scientific parallel applications on dynamic grids. Finally, the thesis builds a practical and robust grid middleware infrastructure which integrates components related to performance modeling, scheduling and rescheduling, monitoring and migration frameworks for large-scale deployment and use of high performance applications on grids. The thesis consists of four main components. In the first part of the thesis, we have developed a comprehensive set of performance modeling strategies to predict the execution times of tightly-coupled parallel applications on a set of resources in a dedicated or non-dedicated cluster. The main purpose of our prediction strategies is to aid grid metaschedulers in making scheduling decisions. Our performance modeling strategies, based on linear regression, can deal with non-dedicated systems where the loads can change during application executions. Our models do not require detailed knowledge and instrumentation of the applications and can be constructed without the involvement of application developers. The strategies are intended for rapid and large scale deployment of parallel applications on non-dedicated grid systems. We have evaluated our strategies on 8, 16, 24 and 32-node clusters with random loads and load traces from a grid system. Our performance modeling strategies gave less than 30% average percentage prediction errors in all cases, which is reasonable for non-dedicated systems. We also found that scheduling based on the predictions by our strategies will result in perfect scheduling in many cases. For modeling large-scale scientific applications, we use execution profiles and automatic program analysis, and manual analysis of significant portions of the application’s code to identify the different phases of applications. We then adopt our performance modeling strategies to predict execution times for the different phases of the tightly-coupled parallel applications on a set of resources in a dedicated or non-dedicated cluster. Our experiments show that using combinations of performance models of the phases give 18% – 70% more accurate predictions than using single performance models for the applications. In the second part of the thesis, we have devised, evaluated and compared algorithms for scheduling tightly-coupled parallel applications on multi-cluster grids. Our algorithms use performance models that predict the execution times of parallel applications, for evaluations of candidate schedules. In this work, we propose a novel algorithm called Box Elimination (BE) that searches a space of performance model parameters to determine efficient schedules. By eliminating large search space regions containing poorer solutions at each step and searching high quality solutions, our algorithm is able to generate efficient schedules within few seconds for even clusters of 512 processors. By means of large number of real and simulation experiment, we compared our algorithm with popular optimization techniques. We show that our algorithm generates up to 80% more efficient schedules than other algorithms and the resulting execution times are more robust against performance modeling errors. The third part of the thesis deals with policies for rescheduling long-running multi-phase parallel applications in response to application and resource dynamics. In this work, we use our performance modeling and scheduling strategies to derive rescheduling plans for executing multi-phase parallel applications on grids. A rescheduling plan consists of potential points in application execution for rescheduling and schedules of resources for application execution between two consecutive rescheduling points. We have developed three algorithms, namely an incremental algorithm, a divide-and-conquer algorithm and a genetic algorithm, for deriving a rescheduling plan for a parallel application execution. We have also developed an algorithm that uses rescheduling plans derived on different clusters to form a single coherent rescheduling plan for application execution on a grid consisting of multiple clusters. The rescheduling plans generated by our algorithms are highly efficient leading to application execution times that are higher than the execution times corresponding to brute force method by less than 10%. We also find that rescheduling in response to changing application and resource dynamics, using the rescheduling plans for multi-cluster grids generated by our algorithms, give much lesser execution times when compared to executions of the applications on a single schedule throughout application execution. In the final part of the thesis, we have developed a practical grid middleware framework called MerITA (Middleware for Performance Improvement of Tightly Coupled Parallel Applications on Grids), a system for effective execution of tightly-coupled parallel applications on multi-cluster grids consisting of dedicated or non-dedicated, interactive or batch systems. The framework brings together performance modeling for automatically determining the characteristics of parallel applications, scheduling strategies that use the performance models for efficient mapping of applications to resources, rescheduling policies for determining the points in application execution when executing applications can be rescheduled to different sets of resources to obtain performance improvement and a check-pointing library for enabling rescheduling.

A scheduler, as a central components of a computing site, aggregates computing resources and is responsible to distribute the incoming load (jobs) between the resources. Under such an environment, the optimum performance of the system against the service level agreement (SLA) based workloads, can be achieved by calculating the priority of SLA bound jobs using integrated heuristic. The SLA defines the service obligations and expectations to use the computational resources. The integrated heuristic is the combination of different SLA terms. It combines the SLA terms with a specific weight for each term. Theweights are computed by applying parameter sweep technique in order to obtain the best schedule for the optimum performance of the system under the workload. The sweepingof parameters on the integrated heuristic observed to be computationally expensive. The integrated heuristic becomes more expensive if no value of the computed weights result in improvement in performance with the resulting schedule. Hence, instead of obtaining optimum performance it incurs computation cost in such situations. Therefore, there is a need of detection of situations where the integrated heuristic can be exploited beneficially. For that reason, in this thesis we propose a metric based on the concept of utilization, to evaluate the SLA based parallel workloads of independent jobs to detect any impact of integrated heuristic on the workload.

<p>Advances in network technologies and computing resources have led to the deployment of large scale computational systems, such as those following Grid or Cloud architectures. The scheduling problem is a significant issue in these distributed computing environments, where a scheduling algorithm should consider multiple objectives and performance metrics. Moreover, heterogeneity is increasing at both the application and resource levels. The heterogeneity in these systems can have a huge impact on performance in terms of metrics such as average completion time. However, traditional Grid and Cloud scheduling algorithms neglect heterogeneity in their scheduling decisions. This PhD dissertation studies the scheduling challenges in Computational Grid, Data Grid, and Cloud computing systems, and introduces new scheduling algorithms for each of these systems.</p> <p>The main issue in Grid scheduling is the wide distribution of resources. As a result, gathering full state information can add huge overhead to the scheduler. This thesis introduces a Computational Grid scheduling algorithm which simultaneously addresses minimizing completion times (by considering system heterogeneity), while requiring zero dynamic state information. Simulation results show the promising performance of this algorithm, and its robustness with respect to errors in parameter estimates.</p> <p>In the case of Data Grid schedulers, an efficient scheduling decision should select a combination of resources for a task that simultaneously mitigates the computation and the communication costs. Therefore, these schedulers need to consider a large search space to find an appropriate combination. This thesis introduces a new Data Grid scheduling algorithm, which dynamically makes replication and scheduling decisions. The proposed algorithm reduces the search space, decreases the required state information, and improves the performance by considering the system heterogeneity. Simulation results illustrate the promising performance of the introduced algorithm.</p> <p>Cloud computing can be considered as a next generation of Grid computing. One of the main challenges in Cloud systems is the enormous expansion of data in different applications. The MapReduce programming model and Hadoop framework were designed as a solution for executing large scale data-intensive applications. A large number of (heterogeneous) users, using the same Hadoop cluster, can result in tensions between the various performance metrics by which such systems are measured. This research introduces and implements a Hadoop scheduling system, which uses system information such as estimated job arrival rates and mean job execution times to make scheduling decisions. The proposed scheduling system, named COSHH (Classification and Optimization based Scheduler for Heterogeneous Hadoop systems), considers heterogeneity at both the application and cluster levels. The main objective of COSHH is to improve the average completion time of jobs. However, as it is concerned with other key Hadoop performance metrics, it also achieves competitive performance under minimum share satisfaction, fairness and locality metrics, with respect to other well-known Hadoop schedulers. The proposed scheduler can be efficiently applied in heterogeneous clusters, in contrast to most Hadoop schedulers, which assume homogeneous clusters.</p> <p>A Hadoop system can be described based on three factors: cluster, workload, and user. Each factor is either heterogeneous or homogeneous, which reflects the heterogeneity level of the Hadoop system. This PhD research studies the effect of heterogeneity in each of these factors on the performance of Hadoop schedulers. Three schedulers which consider different levels of Hadoop heterogeneity are used for the analysis: FIFO, Fair sharing, and COSHH. Performance issues are introduced for Hadoop schedulers, and experiments are provided to evaluate these issues. The reported results suggest guidelines for selecting an appropriate scheduler for different Hadoop systems. The focus of these guidelines is on systems which do not have significant fluctuations in the number of resources or jobs.</p> <p>There is a considerable challenge in Hadoop to schedule tasks and resources in a scalable manner. Moreover, the potential heterogeneous nature of deployed Hadoop systems tends to increase this challenge. This thesis analyzes the performance of widely used Hadoop schedulers including FIFO and Fair sharing and compares them with the COSHH scheduler. Based on the discussed insights, a hybrid solution is introduced, which selects appropriate scheduling algorithms for scalable and heterogeneous Hadoop systems with respect to the number of incoming jobs and available resources. The proposed hybrid scheduler considers the guidelines provided for heterogeneous Hadoop systems in the case that the number of jobs and resources change considerably.</p> <p>To improve the performance of high priority users, Hadoop guarantees minimum numbers of resource shares for these users at each point in time. This research compares different scheduling algorithms based on minimum share consideration and under different heterogeneous and homogeneous environments. For this evaluation, a real Hadoop system is developed and evaluated using Facebook workloads. Based on the experiments performed, a reliable scheduling algorithm is suggested which can work efficiently in different environments.</p> / Doctor of Philosophy (PhD)