Submitted by Kleber Silva (kleberbs@ufba.br) on 2017-02-06T17:24:05Z No. of bitstreams: 1 dissertação-Jose Augusto.pdf: 918097 bytes, checksum: d6d73ea4db6be8c29efc7d4d621ec204 (MD5) / Approved for entry into archive by Vanessa Reis (vanessa.jamile@ufba.br) on 2017-02-07T12:20:16Z (GMT) No. of bitstreams: 1 dissertação-Jose Augusto.pdf: 918097 bytes, checksum: d6d73ea4db6be8c29efc7d4d621ec204 (MD5) / Made available in DSpace on 2017-02-07T12:20:16Z (GMT). No. of bitstreams: 1 dissertação-Jose Augusto.pdf: 918097 bytes, checksum: d6d73ea4db6be8c29efc7d4d621ec204 (MD5) / Atualmente, muitos sistemas mecatrônicos apresentam comportamentos definidos segundo restrições temporais e são comumente identificados como Sistemas de Tempo Real (STR). Estes sistemas são encontrados em diversas áreas que envolvem tecnologia, como automação industrial, telecomunicações e sistemas espaciais. Em todas essas áreas, há um rápido progresso tecnológico, que contribuí com o aumento na complexidade do software e na demanda de processamento. Uma tendênca crescente de utilização de plataformas com múltiplas unidades de processamentovem ocorrendo nos últimos anos. Chips contendo 100 núcleos de processamento são agora uma realidade. Neste contexto, o problema de escalonamento de tarefas deve ser avaliado levando em consideração esta tendência de paralelismo, pois a garantia das restrições temporais dos STR depende de como suas tarefas são escalonadas. O problema de escalonar n tarefas esporádicas num sistema de tempo real executando numa plataforma composta de m processadores idênticos é abordado nesta dissertação. A solução proposta é nomeada Hime (Higest-priority migration managed by EDF), a qual possui várias características interessantes: a maioria das tarefas executadas num único processador; existem no máximo [0,5m] tarefas migratórias; tanto os custos de utilização e a complexidade de sua implementação são baixos. O desempenho de Hime foi avaliado analiticamente e por simulação, os quais constataram que qualquer conjunto de tarefas com utilização não superior a 72,2% do sistema cumpre seus requisitos temporais que Hime pode lidar com sistemas que possuem utilização maior que 95% da capatidade de processamento do sistema. Tais resultados vêm contribuir com a área de STR multiprocessados ao mesmo tempo em que indicam possíveis ramos de investigação.

[pt] A proliferação de arquiteturas paralelas torna cada vez mais necessário o desenvolvimento de métodos e a construção de ferramentas que utilizem estes métodos na análise / predição do desempenho de aplicações (programas) executadas em arquiteturas existentes ou em fase de projeto. Uma classe muito importante de arquiteturas paralelas é a das arquiteturas multiprocessadas. Essa classe permite explorar o paralelismo existente dentro do código dos programas: os programas são divididos em unidades menores (tarefas) que são executadas concorrentemente nos diversos processadores da arquitetura. Esta dissertação apresenta uma ferramenta - Tootisys - para modelagem de arquiteturas multiprocessadas onde os processadores compartilham uma memória global e onde diversos programas são executados ao mesmo tempo. Os programas são restritos ao tipo CPU-bound e são representados através de grafos de tarefas acíclicos e dirigidos. A arquitetura é descrita através dos tempos característicos dos seus processadores e através de uma função que fornece retardo no acesso à memória global. Tootisys permite modelar sistemas que apresentam disputa por processador tanto a nível de tarefas quanto a nível de programas e sistemas onde tarefas múltiplas podem ser executadas simultaneamente em cada processador. O algoritmo utilizado por Tootistys na análise de desempenho de um sistema concorrente é iterativo. Este algoritmo monstrou-se bastante eficiente em termos computacionais tendo apresentado rápida convergência para valores finais em todos os casos analisados. Esta dissertação também apresenta o projeto e a implementação da interface gráfica do Tootisys. A interface construída é uma variação do tipo manipulação direta, possuindo ainda características de interfaces tipo seleção por menu. A interface obtida é eficiente, pouco sujeita a erros cometidos por usuários e fácil de usar, aprender e memorizar. Como esta interface foi implementada em C e segue o padrão X11, espera-se que Tootisys possa ser facilmente adaptado para executar em diversas máquinas. / [en] The proliferation of parallel architectures demands the development of methods and the construction of tools that use these methods in the performance analysis prediction of applications (programs) running in architectures which are already in use or still being designed. A very important class of parallel architecture is called multiprocessors. This class allows the exploration of the parallelism that exist within the program`s code: programs are partitioned into smaller units (tasks) that execute concurrently in the processors of the architecture. This dissertation presents a tool - Tootisys - for modeling multiprocessors where processors share a global memory and where several programs execute at the same time. Programs are restricted to be CPU-bound and are represented by direct acyclic task graphs. The architecture is described by the time parameters of its processors and by a function that gives the delay in the access to the global memory. Tootisys allows the modeling of system where processors are disputed by tasks or programs and where multiple tasks can execute at the same time in each professor. The algorithm used by tootisys in the analysis of a concurrent system is iterative. This algorithm has pointed out to very computationally efficient: it has rapidly converged to final values in all cases studied. This dissertation also presents the graphic interface project of Tootisys and its implementation. Tootisys’s interface is a king of direct manipulation. However, some characteristcs of menu selection interfaces can also be found in it. The designed interface is efficient and minimizes error possibilities. Furthermore, it is easy to use, to learn and to remember. Since this interface was implemented in C and follows the X11 satandard, it is expected that Tootisys can be easily modifield to run in several machines.

Made available in DSpace on 2016-06-02T19:06:06Z (GMT). No. of bitstreams: 1 5351.pdf: 2740873 bytes, checksum: e4ce3a33279ffb7afccf2fc418af0f79 (MD5) Previous issue date: 2013-02-04 / During the last years we have witnessed a significant growing in the amount of data processed in a daily basis by companies, universities, and other institutions. Many use cases report processing of data volumes of petabytes in thousands of cores by a single application. MapReduce is a programming model, and a framework for the execution of applications which manipulate large data volumes in machines composed of thousands of processors/cores. Currently, Hadoop is the most widely adopted free implementation of MapReduce. Although there are reports in the literature about the use of MapReduce applications on platforms with more than one hundred cores, the scalability is not stressed and much remain to be studied in this field. One of the main challenges in the scalability study of MapReduce applications is the large number of configuration parameters of Hadoop. There are reports in the literature that mention more than 190 configuration parameters, 25 of which are known to impact the application performance in a significant way. In this work we study the scalability of MapReduce applications running on Hadoop. Due to the limited number of processors/cores available, we adopted a combined approach involving both experimentation and simulation. The experimentation has been carried out in a local cluster of 32 nodes, and for the simulation we have used MRSG (MapReduce Over SimGrid). In a first set of experiments, we identify the most impacting parameters in the performance and scalability of the applications. Then, we present a method for calibrating the simulator. With the calibrated simulator, we evaluated the scalability of one well-optimized application on larger clusters, with up to 10 thousands of nodes. / Durante os últimos anos, houve um significativo crescimento na quantidade de dados processados diariamente por companhias, universidades e outras instituições. Mapreduce é um modelo de programação e um framework para a execução de aplicações que manipulam grandes volumes de dados em máquinas compostas por milhares de processadores ou núcleos. Atualmente, o Hadoop é a implementação como software livre de Mapreduce mais largamente adotada. Embora existam relatos na literatura sobre o uso de aplicações Mapreduce em plataformas com cerca de quatro mil núcleos processando dados da ordem de dezenas de petabytes, o estudo dos limites de escalabilidade não foi esgotado e muito ainda resta a ser estudado. Um dos principais desafios no estudo de escalabilidade de aplicações Mapreduce é o grande número de parâmetros de configuração da aplicação e do ambiente Hadoop. Na literatura há relatos que mencionam mais de 190 parâmetros de configuração, sendo que 25 podem afetar de maneira significativa o desempenho da aplicação. Este trabalho contém um estudo sobre a escalabilidade de aplicações Mapreduce executadas na plataforma Hadoop. Devido ao número limitado de processadores disponíveis, adotou-se uma abordagem que combina experimentação e simulação. A experimentação foi realizada em um cluster local de 32 nós (com 64 processadores), e para a simulação empregou-se o simulador MRSG (MapReduce Over SimGrid). Como principais resultados, foram identificados os parâmetros de maior impacto no desempenho e na escalabilidade das aplicações. Esse resultado foi obtido por meio de simulação. Além disso, apresentou-se um método para a calibração do simulador MRSG, em função de uma aplicação representativa escolhida como benchmark. Com o simulador calibrado, avaliou-se a escalabilidade de uma aplicação bem otimizada. O simulador calibrado permitiu obter uma predição sobre a escalabilidade da aplicação para uma plataforma com até 10 mil nós.

Despiste the fact that many scheduling models teoretically capable of high system resource utilization were proposed with the development of the real-time system, the industry still uses the first scheduling model proposed for multi-processor real-time systems, the partitioned scheduling model. This scheduling model can guarantee scheduling of task sets up to around 69% processor utilization, which falls pale in comparison to recent scheduling models that can guarantee scheduling up to 97% processor utilization. The motive behind the utilization of the partitioned scheduling as industrial model is the amount of studies made on this model and the development of scheduling analysis capable of providing temporal guarantees for this model on a real system environment. Recent scheduling models, like semi-partitioned scheduling, offer the possibility of a higher system resource utilization, it still lack studies and scheduling analysis capable of provide temporal guarantees under a real environment. The current scheduling analysis for most of the more recent models take advantage of a series of abstractions, failing to provide guarantees under real circumstances. This papers primary objective is to produce a new scheduling analysis for semi-partitioned scheduling, capable of achieving temporal guarantees taking some of the previously abstracted factors, like task communication and the impact f task migration on its communications flows, approximating the scheduling model to real environmental conditions. With the development of such analysis preliminary studies were made on heuristic task mapping algorithms for semipartitioned systems. / Com a popularização de sistemas multi-processador, surgiu uma série de propostas de modelos de escalonamento, na área de sistemas de tempo real que, teoricamente, são capazes de obter um alto aproveitamento dos recursos do sistema. Entretanto, o modelo de escalonamento mais adotado continua sendo um dos primeiros modelos de escalonamento propostos na área, o modelo de escalonamento particionado. O modelo de escalonamento particionado só pode garantir o escalonamento de conjuntos com até cerca de 69% de utilização de processador, sendo limitado se comparado com garantias de escalonamento de até 97% de utilização de modelos mais recentes. O motivo pelo qual o escalonamento particionado continua sendo utilizado é a grande concentração de estudos a respeito do modelo e o desenvolvimento de análises de escalonamento capazes de garantir o escalonamento do modelo em condições reais do sistema. Modelos mais recentes, como o escalonamento semi-particionado, apresentam uma possibilidade de um maior aproveitamento do sistema, porém, ainda possuem estudos limitados e não dispõe de análises de escalonamento capazes de prover garantias temporais para o sistema em condições reais, devido à presença de diversas abstrações no modelo. Neste sentido, este trabalho foca em arquiteturas Network-on-Chip que apresentam comunicação explícita, abstraída nos trabalhos encontrados na literatura. Este trabalho tem como objetivo primário o desenvolvimento de uma análise de escalonamento capaz de prover garantias temporais para o modelo de escalonamento semi-particionado levando em consideração fatores previamente abstraídos, como a necessidade de comunicação entre tarefas e o impacto da migração das tarefas nos seus fluxos de comunicação, aproximando o modelo da realidade. O desenvolvimento de tal análise possibilita o estudo preliminar de algoritmos heurísticos de mapeamento de tarefas, capazes de mapear conjuntos de tarefas levando em consideração migrações de tarefas e comunicação entre tarefas em um modelo de escalonamento semi-particionado.