Tese de mestrado. Redes e Serviços de Comunicação. Faculdade de Engenharia. Universidade do Porto. 2009

À medida que a ciência avança, muitas aplicações em diferentes áreas precisam de grande poder computacional. A computação em grade é uma importante alternativa para a obtenção de alto poder de processamento, no entanto, esse alto poder computacional deve ser bem aproveitado. Mediante o uso de técnicas de escalonamento especializadas, os recursos podem ser utilizados adequadamente. Atualmente existem vários algoritmos propostos para computação em grade, portanto, é necessário seguir uma boa metodologia para escolher o algoritmo que ofereça melhor desempenho, dadas determinadas características. No presente trabalho comparamos os algoritmos de escalonamento: Heterogeneous Earliest Finish Time (HEFT), (b) Critical Path on a Processor (CPOP) e (c) Path Clustering Heuristic (PCH); cada algoritmo é avaliado com diferentes aplicações e sobre diferentes arquiteturas usando técnicas de simulação, seguindo quatro critérios: (i) desempenho, (ii) escalabilidade, (iii) adaptabilidade e (iv) distribuição da carga do trabalho. Diferenciamos as aplicações para grade em dois tipos: (i) aplicações regulares e (ii) aplicações irregulares; dado que em aplicações irregulares não é facil comparar o critério de escalabilidade. Seguindo esse conjunto de critérios o algoritmo HEFT possui o melhor desempenho e escalabilidade; enquanto que os três algoritmos possuem o mesmo nível de adaptabilidade. Na distribuição de carga de trabalho o algoritmo HEFT aproveita melhor os recursos do que os outros. Por outro lado os algoritmos CPOP e PCH usam a técnica de escalonar o caminho crítico no processador que ofereça o melhor tempo de término, mas essa abordagem nem sempre é a mais adequada. / As science advances, many applications in different areas need a big amount of computational power. Grid computing is an important alternative to obtain high processing power, but this high computational power must be well used. By using specialized scheduling techniques, resources can be properly used. Currently there are several algorithms for grid computing, therefore, is necessary to follow a good methodology to choose an algorithm that offers better performance given certain settings. In this work, we compare task dependent scheduling algorithms: (a) Heterogeneous Earliest Finish Time (HEFT), (b) Critical Path on a Processor (CPOP) e Path Clustering Heuristic (PCH); each algorithm is evaluated with different applications and on different architectures using simulation techniques, following four criterias: (i) performance, (ii) scalability, (iii) adaptability and (iv) workload distribution. We distinguish two kinds of grid applications: (i) regular applications and (ii) irregular applications, since in irregular applications is not easy to compare scalability criteria. Following this set of criteria the HEFT algorithm reaches the best performance and scalability, while the three algorithms have the same level of adaptability. In workload distribution HEFT algorithm makes better use of resources than others. On the other hand, CPOP and PCH algorithms use scheduling of tasks which belong to the critical path on the processor which minimizes the earliest finish time, but this approach is not always the most appropriate.

A Computação em Nuvem é um paradigma de computação distribuída que vem sendo utilizado extensivamente em vários campos de interesse nos últimos anos, desde aplicações web comuns até a aplicações de alta-performance computacional. O modelo de pagamento pelo uso e a isonomia dos métodos de acesso transformaram o ambiente de Computação em Nuvem em uma alternativa extremamente popular e atrativa tanto para universidades como para empresas privadas. Entre os modelos de implantação adotados atualmente destaca-se o de nuvem em comunidade, onde várias entidades que possuem interesses em comum constroem, mantém e compartilham a mesma infraestrutura de serviços em nuvem. O modelo computacional em nuvem também pode ser atrativo para aplicações que tenham como requisito o processamento em tempo real, principalmente pela capacidade de manipulação de grandes volumes de dados e pela propriedade de elasticidade, que é a inserção ou remoção de recursos computacionais dinamicamente de acordo com a demanda. Nesta tese, são identificados os requisitos para a construção de um ambiente em nuvem em comunidade para aplicações de tempo real. A partir destes requisitos e de uma revisão bibliográfica baseada em nuvem e sistemas distribuídos de tempo real, é desenvolvida a proposta de uma arquitetura de nuvem em comunidade de tempo real. Um estudo de caso de compra e venda de ações em bolsa de valores é apresentado como uma aplicação viável para este modelo, sendo que um algoritmo de escalonamento de tempo real para este ambiente é proposto. Por fim, é desenvolvido nesta tese um simulador cujo objetivo é demonstrar em termos quantitativos quais as melhorias de desempenho atingidas com esta arquitetura. / Cloud Computing is a distributed computing paradigm which is being extensively applied to many fields of interest in the last few years, ranging from ordinary web applications to highperformance computing. The pay-per-use model and ubiquitous access methods have made Cloud Computing an interesting and popular alternative for both enterprises and universities. Among the deployment models adopted, one of the most prominent is the community cloud, where several entities who share similar interests build, maintain and use the same infrastructure of cloud services. The cloud computing paradigm can be attractive to applications whose requirements are the processing in real-time too, mainly because of its capacity of handling huge amounts of data as for the property of elasticity, which is the dynamic and automatic insertion or removal of computing resources on-demand. In this thesis, the requirements of a community cloud for real-time applications are identified. Based on these requirements and on a bibliographical review of the research fields of real-time distributed systems and real-time clouds, it is developed a proposal for a real-time community cloud architecture. A case study of a trading real-time application at a stock exchange is presented as a feasible application for this model. Also, a real-time scheduling algorithm is proposed for this environment. A simulator is built in order to demonstrate the quantitative improvements this architecture brings.

A Computação em Nuvem é um paradigma de computação distribuída que vem sendo utilizado extensivamente em vários campos de interesse nos últimos anos, desde aplicações web comuns até a aplicações de alta-performance computacional. O modelo de pagamento pelo uso e a isonomia dos métodos de acesso transformaram o ambiente de Computação em Nuvem em uma alternativa extremamente popular e atrativa tanto para universidades como para empresas privadas. Entre os modelos de implantação adotados atualmente destaca-se o de nuvem em comunidade, onde várias entidades que possuem interesses em comum constroem, mantém e compartilham a mesma infraestrutura de serviços em nuvem. O modelo computacional em nuvem também pode ser atrativo para aplicações que tenham como requisito o processamento em tempo real, principalmente pela capacidade de manipulação de grandes volumes de dados e pela propriedade de elasticidade, que é a inserção ou remoção de recursos computacionais dinamicamente de acordo com a demanda. Nesta tese, são identificados os requisitos para a construção de um ambiente em nuvem em comunidade para aplicações de tempo real. A partir destes requisitos e de uma revisão bibliográfica baseada em nuvem e sistemas distribuídos de tempo real, é desenvolvida a proposta de uma arquitetura de nuvem em comunidade de tempo real. Um estudo de caso de compra e venda de ações em bolsa de valores é apresentado como uma aplicação viável para este modelo, sendo que um algoritmo de escalonamento de tempo real para este ambiente é proposto. Por fim, é desenvolvido nesta tese um simulador cujo objetivo é demonstrar em termos quantitativos quais as melhorias de desempenho atingidas com esta arquitetura. / Cloud Computing is a distributed computing paradigm which is being extensively applied to many fields of interest in the last few years, ranging from ordinary web applications to highperformance computing. The pay-per-use model and ubiquitous access methods have made Cloud Computing an interesting and popular alternative for both enterprises and universities. Among the deployment models adopted, one of the most prominent is the community cloud, where several entities who share similar interests build, maintain and use the same infrastructure of cloud services. The cloud computing paradigm can be attractive to applications whose requirements are the processing in real-time too, mainly because of its capacity of handling huge amounts of data as for the property of elasticity, which is the dynamic and automatic insertion or removal of computing resources on-demand. In this thesis, the requirements of a community cloud for real-time applications are identified. Based on these requirements and on a bibliographical review of the research fields of real-time distributed systems and real-time clouds, it is developed a proposal for a real-time community cloud architecture. A case study of a trading real-time application at a stock exchange is presented as a feasible application for this model. Also, a real-time scheduling algorithm is proposed for this environment. A simulator is built in order to demonstrate the quantitative improvements this architecture brings.

À medida que a ciência avança, muitas aplicações em diferentes áreas precisam de grande poder computacional. A computação em grade é uma importante alternativa para a obtenção de alto poder de processamento, no entanto, esse alto poder computacional deve ser bem aproveitado. Mediante o uso de técnicas de escalonamento especializadas, os recursos podem ser utilizados adequadamente. Atualmente existem vários algoritmos propostos para computação em grade, portanto, é necessário seguir uma boa metodologia para escolher o algoritmo que ofereça melhor desempenho, dadas determinadas características. No presente trabalho comparamos os algoritmos de escalonamento: Heterogeneous Earliest Finish Time (HEFT), (b) Critical Path on a Processor (CPOP) e (c) Path Clustering Heuristic (PCH); cada algoritmo é avaliado com diferentes aplicações e sobre diferentes arquiteturas usando técnicas de simulação, seguindo quatro critérios: (i) desempenho, (ii) escalabilidade, (iii) adaptabilidade e (iv) distribuição da carga do trabalho. Diferenciamos as aplicações para grade em dois tipos: (i) aplicações regulares e (ii) aplicações irregulares; dado que em aplicações irregulares não é facil comparar o critério de escalabilidade. Seguindo esse conjunto de critérios o algoritmo HEFT possui o melhor desempenho e escalabilidade; enquanto que os três algoritmos possuem o mesmo nível de adaptabilidade. Na distribuição de carga de trabalho o algoritmo HEFT aproveita melhor os recursos do que os outros. Por outro lado os algoritmos CPOP e PCH usam a técnica de escalonar o caminho crítico no processador que ofereça o melhor tempo de término, mas essa abordagem nem sempre é a mais adequada. / As science advances, many applications in different areas need a big amount of computational power. Grid computing is an important alternative to obtain high processing power, but this high computational power must be well used. By using specialized scheduling techniques, resources can be properly used. Currently there are several algorithms for grid computing, therefore, is necessary to follow a good methodology to choose an algorithm that offers better performance given certain settings. In this work, we compare task dependent scheduling algorithms: (a) Heterogeneous Earliest Finish Time (HEFT), (b) Critical Path on a Processor (CPOP) e Path Clustering Heuristic (PCH); each algorithm is evaluated with different applications and on different architectures using simulation techniques, following four criterias: (i) performance, (ii) scalability, (iii) adaptability and (iv) workload distribution. We distinguish two kinds of grid applications: (i) regular applications and (ii) irregular applications, since in irregular applications is not easy to compare scalability criteria. Following this set of criteria the HEFT algorithm reaches the best performance and scalability, while the three algorithms have the same level of adaptability. In workload distribution HEFT algorithm makes better use of resources than others. On the other hand, CPOP and PCH algorithms use scheduling of tasks which belong to the critical path on the processor which minimizes the earliest finish time, but this approach is not always the most appropriate.