Este trabalho propõe e descreve em detalhes o projeto do AMIGO (DynAMical FlexIble SchedulinG EnvirOnment), uma nova ferramenta de software capaz de viabilizar a união de diferentes algoritmos de escalonamento, de uma maneira completamente transparente ao usuário. O AMIGO é capaz de flexibilizar o escalonamento (em tempo de execução da aplicação) desde a sua configuração até a sua efetiva aplicação. Além da flexibilidade dinâmica e da transparência, o AMIGO também é modular: o seu projeto está dividido em módulos que, entre outras vantagens, facilitam sua execução em diferentes plataformas. Este trabalho também contribui apresentando uma análise crítica da literatura da área, apontando divergências e propondo pontos de convergência importantes. Assim, o levantamento bibliográfico apresentado atua como um material introdutório precioso para que os pesquisadores iniciantes formem um contexto geral sobre a área e, desse modo, aprofundem mais rapidamente seus estudos em outros trabalhos mais específicos. A avaliação de desempenho feita com o AMIGO demonstra que é possível a obtenção de ganhos de desempenho expressivos, com total transparência para o usuário final. Unindo-se desempenho, flexibilidade e transparência, espera-se contribuir para a redução da lacuna existente entre teoria e prática na área de escalonamento de processos / This thesis proposes and describes in details the design of the AMIGO (DynAMical FlexIble SchedulinG EnvirOnment), a novel software tool that makes possible the union of different scheduling algorithms, in a way completely transparent to the user. The AMIGO is able to make flexible the scheduling activity (at run-time), covering all the steps from its configuration up to its effective application. Besides the dynamic flexibility and transparency, AMIGO is also modular: it is split into modules that, among other advantages, facilitate its execution on different platforms. This work also contributes by presenting a critical analysis of the process-scheduling literature, pointing out the existing divergences and proposing important convergence points. Thus, the literature survey presented acts as a precious introductory material, which is able, on one hand, to give to the beginners a broad view of the process-scheduling area and, on the other hand, to facilitate the development of deeper studies in a quicker fashion when more specific works are needed. The performance evaluation of the AMIGO shows that is possible to have expressive performance gains, while having total user transparency. Joining flexibility and transparency it is hoped to contribute for the reduction of the existing gap between theory and practice in the scheduling process area

Esta dissertação aborda o escalonamento de processos em sistemas de clusters de computadores, tanto em plataformas homogêneas quanto heterogêneas. As heterogeneidades abordadas incluem a potência computacional dos processadores, quantidade de memória principal do sistema e o tempo médio de acesso ao disco. Neste trabalho são propostas quatro novas políticas destinadas a realizar o compartilhamento de carga nesses ambientes, considerando cargas de trabalho com aplicações variando entre CPU-bound e memoryintensive. Dentre as quatro políticas, uma utiliza apenas índices de CPU, enquanto as demais utilizam também índices de memória. Os resultados foram obtidos através de simulações baseadas em trace e mostram reduções significativas das perdas de desempenho observadas nos resultados obtidos com as políticas de escalonamento propostas. Como referências foram utilizadas políticas de escalonamento tradicionais encontradas na literatura / This dissertation approaches the process scheduling on clusters of computers, on both homogeneous and heterogeneous platforms. The heterogeneities considered include processor computational power, system main memory quantity and the average disk access time. In this work are proposed four novel policies aimed at realizing the work load sharing on these environments, considering workloads with applications varying between CPU-bound and memory-intensive. Among the four policies, one of them uses only CPU indices, while the others also use memory indices. The results were obtained by means of trace-based simulations and show a significant reduction on the performance losses observed on the results obtained with the proposed scheduling policies. As references were used traditional scheduling policies found in the literature

Esta tese aborda o problema de obtenção de um índice de carga ou de desempenho adequado para utilização no escalonamento de processos em sistemas computacionais heterogêneos paralelos/distribuídos. Uma ampla revisão bibliográfica com a correspondente análise crítica é apresentada. Essa revisão é a base para a comparação das métricas existentes para a avaliação do grau de heterogeneidade/homogeneidade dos sistemas computacionais. Uma nova métrica é proposta neste trabalho, removendo as restrições identificadas no estudo comparativo realizado. Resultados de aplicações dessa nova métrica são apresentados e discutidos. Esta tese propõe também o conceito de heterogeneidade/homogeneidade temporal que pode ser utilizado para futuros aprimoramentos de políticas de escalonamento empregadas em plataformas computacionais heterogêneas paralelas/distribuídas. Um novo índice de desempenho (Vector for Index of Performance - VIP), generalizando o conceito de índice de carga, é proposto com base em uma métrica Euclidiana. Esse novo índice é aplicado na implementação de uma política de escalonamento e amplamente testado através de modelagem e simulação. Os resultados obtidos são apresentados e analisados estatisticamente. É demonstrado que o novo índice leva a bons resultados de modo geral e é apresentado um mapeamento mostrando as vantagens e desvantagens de sua adoção quando comparado às métricas tradicionais. / This thesis approaches the problem of evaluating an adequate load index or a performance index, for using in process scheduling in heterogeneous parallel/distributed computing systems. A wide literature review with the corresponding critical analysis is presented. This review is the base for the comparison of the existing metrics for the evaluation of the computing systems homogeneity/heterogeneity degree. A new metric is proposed in this work, removing the restrictions identified during the comparative study realized. Results from the application of the new metric are presented and discussed. This thesis also proposes the concept of temporal heterogeneity/homogeneity that can be used for future improvements in scheduling polices for parallel/distributed heterogeneous computing platforms. A new performance index (Vector for Index of Performance - VIP), generalizing the concept of load index, is proposed based on an Euclidean metric. This new index is applied to the implementation of a scheduling police and widely tested through modeling and simulation. The results obtained are presented and statistically analyzed. It is shown that the new index reaches good results in general and it is also presented a mapping showing the advantages and disadvantages of its adoption when compared with the traditional metrics.

Esta tese aborda o problema de obtenção de um índice de carga ou de desempenho adequado para utilização no escalonamento de processos em sistemas computacionais heterogêneos paralelos/distribuídos. Uma ampla revisão bibliográfica com a correspondente análise crítica é apresentada. Essa revisão é a base para a comparação das métricas existentes para a avaliação do grau de heterogeneidade/homogeneidade dos sistemas computacionais. Uma nova métrica é proposta neste trabalho, removendo as restrições identificadas no estudo comparativo realizado. Resultados de aplicações dessa nova métrica são apresentados e discutidos. Esta tese propõe também o conceito de heterogeneidade/homogeneidade temporal que pode ser utilizado para futuros aprimoramentos de políticas de escalonamento empregadas em plataformas computacionais heterogêneas paralelas/distribuídas. Um novo índice de desempenho (Vector for Index of Performance - VIP), generalizando o conceito de índice de carga, é proposto com base em uma métrica Euclidiana. Esse novo índice é aplicado na implementação de uma política de escalonamento e amplamente testado através de modelagem e simulação. Os resultados obtidos são apresentados e analisados estatisticamente. É demonstrado que o novo índice leva a bons resultados de modo geral e é apresentado um mapeamento mostrando as vantagens e desvantagens de sua adoção quando comparado às métricas tradicionais. / This thesis approaches the problem of evaluating an adequate load index or a performance index, for using in process scheduling in heterogeneous parallel/distributed computing systems. A wide literature review with the corresponding critical analysis is presented. This review is the base for the comparison of the existing metrics for the evaluation of the computing systems homogeneity/heterogeneity degree. A new metric is proposed in this work, removing the restrictions identified during the comparative study realized. Results from the application of the new metric are presented and discussed. This thesis also proposes the concept of temporal heterogeneity/homogeneity that can be used for future improvements in scheduling polices for parallel/distributed heterogeneous computing platforms. A new performance index (Vector for Index of Performance - VIP), generalizing the concept of load index, is proposed based on an Euclidean metric. This new index is applied to the implementation of a scheduling police and widely tested through modeling and simulation. The results obtained are presented and statistically analyzed. It is shown that the new index reaches good results in general and it is also presented a mapping showing the advantages and disadvantages of its adoption when compared with the traditional metrics.

Esta dissertação aborda o escalonamento de processos em sistemas de clusters de computadores, tanto em plataformas homogêneas quanto heterogêneas. As heterogeneidades abordadas incluem a potência computacional dos processadores, quantidade de memória principal do sistema e o tempo médio de acesso ao disco. Neste trabalho são propostas quatro novas políticas destinadas a realizar o compartilhamento de carga nesses ambientes, considerando cargas de trabalho com aplicações variando entre CPU-bound e memoryintensive. Dentre as quatro políticas, uma utiliza apenas índices de CPU, enquanto as demais utilizam também índices de memória. Os resultados foram obtidos através de simulações baseadas em trace e mostram reduções significativas das perdas de desempenho observadas nos resultados obtidos com as políticas de escalonamento propostas. Como referências foram utilizadas políticas de escalonamento tradicionais encontradas na literatura / This dissertation approaches the process scheduling on clusters of computers, on both homogeneous and heterogeneous platforms. The heterogeneities considered include processor computational power, system main memory quantity and the average disk access time. In this work are proposed four novel policies aimed at realizing the work load sharing on these environments, considering workloads with applications varying between CPU-bound and memory-intensive. Among the four policies, one of them uses only CPU indices, while the others also use memory indices. The results were obtained by means of trace-based simulations and show a significant reduction on the performance losses observed on the results obtained with the proposed scheduling policies. As references were used traditional scheduling policies found in the literature

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

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