Submitted by Diogo Barreiros (diogo.barreiros@ufba.br) on 2017-02-17T14:47:00Z No. of bitstreams: 1 flavia maristela santos nascimento.pdf: 1166834 bytes, checksum: 576c7c98a85b5cc824a7869fbb31347e (MD5) / Approved for entry into archive by Vanessa Reis (vanessa.jamile@ufba.br) on 2017-02-17T14:58:14Z (GMT) No. of bitstreams: 1 flavia maristela santos nascimento.pdf: 1166834 bytes, checksum: 576c7c98a85b5cc824a7869fbb31347e (MD5) / Made available in DSpace on 2017-02-17T14:58:14Z (GMT). No. of bitstreams: 1 flavia maristela santos nascimento.pdf: 1166834 bytes, checksum: 576c7c98a85b5cc824a7869fbb31347e (MD5) / Sistemas de tempo real tem sido amplamente utilizados no contexto de sistemas mecatrônicos uma vez que, para controlar entidades do mundo real, ´e necessário considerar tanto seus requisitos lógicos quanto os temporais. Em tais sistemas, mecanismos para prover tolerância a falhas devem ser implementados já que falhas podem implicar em perdas consideráveis. Por exemplo, um erro em um sistema de controle de voo pode incorrer em perda de vidas humanas. Várias abordagens de escalonamento com tolerância a falhas para sistemas de tempo real foram derivadas. Entretanto, a maioria delas restringe o modelo de sistema e/ou falhas de modo particular, ou estão fortemente acopladas ao modelo de recuperação do sistema ou a política de escalonamento. Além disso, não existe uma m´métrica formal que permita comparar as abordagens existentes do ponto de vista da resiliência a falhas. O objetivo principal deste trabalho ´e preencher esta lacuna, fornecendo uma m´métrica de resiliência a falhas para sistemas de tempo real, que seja o mais independente possível dos modelos do sistema e/ou de falhas. Para tanto, uma análise baseada em simulação foi desenvolvida para calcular a resiliência de todas as tarefas de um sistema, através da simulação de intervalos de tempo específicos. Em seguida, t´técnicas de inferência estatística são utilizadas para inferir a resiliência do sistema. Os resultados mostraram que a m´métrica desenvolvida pode ser utilizada para comparar, por exemplo, duas políticas de escalonamento para sistemas de tempo real sob a ´ótica de resiliência a falhas, o que demonstra que a abordagem desenvolvida ´e razoavelmente independente do modelo de sistema.

Submitted by Santos Davilene (davilenes@ufba.br) on 2013-01-25T12:25:33Z No. of bitstreams: 1 TESE - Paul Regnier.pdf: 1122807 bytes, checksum: 968bc4ff6e54e1d57a2a511a607af27d (MD5) / Made available in DSpace on 2013-01-25T12:25:33Z (GMT). No. of bitstreams: 1 TESE - Paul Regnier.pdf: 1122807 bytes, checksum: 968bc4ff6e54e1d57a2a511a607af27d (MD5) / Neste trabalho de doutorado, propõe-se RUN (Redução para Uniprocessor), um novo algoritmo de escalonamento para conjunto de tarefas periódicas com deadlines implícitas em sistemas multiprocessador de tempo real, nos quais as tarefas possuem restrições tanto no domínio do tempo quanto no domínio de valores. RUN apresenta as seguintes propriedades relevantes: - RUN é ótimo no sentido que ele produz um escalonamento correto, no qual todas as restrições temporais são atendidas, de qualquer sistemas de tarefas utilizando até 100% dos processadores da plataforma de tempo real; - RUN usa o conceito-chave do escalonamento do tempo ócio, chamado de escalonamento por dualidade, segundo o qual, em algum instante t, o escalonamento de uma tarefa utiliza tanto o conhecimento de seu tempo de execução restante, bem como o seu tempo ócio restante; - RUN baseia-se na diminuição do número de tarefas a ser escalonadas pela suas agregações em supertasks, os quais chamamos de servidores, com taxa acumulada não superior a 1. Cada servidor é responsável por escalonar o seu conjunto de tarefas clientes, de acordo com alguma política de escalonamento; - RUN utiliza o princípio original de justiça global (Gfair), de acordo com o qual cada servidor de um conjunto de tarefas T é garantido de executar por um tempo proporcional à taxa acumulada das tarefas de T entre cada duas deadlines das tarefas de T; - RUN reduz o problema do escalonamento de um conjunto de tarefas em/m/ processadores no problema equivalente do escalonamento de um ou mais conjuntos de tarefas diferentes em sistemas monoprocessador; - RUN supera significativamente os algoritmos ótimos existentes em termos de preempções com um limite superior de O(log m) preempções média por jobs em/m/ processadores. / Salvador

Made available in DSpace on 2016-08-29T15:36:59Z (GMT). No. of bitstreams: 1 tese_5351_.pdf: 1690430 bytes, checksum: fc8ed930b6e3cdee37d30a437bf819b8 (MD5) Previous issue date: 2012-03-01 / COSTA, Marcos Fávero. Aplicação de meta-heurísticas no escalonamento de motoristas para o transporte de madeira. 2012. Dissertação (Mestrado em Ciências Florestais) Universidade Federal do Espírito Santo, Alegre-ES. Orientador: Prof. Dr. Nilton Cesar Fiedler. Coorientador: Prof. Dr. Geraldo Regis Mauri. O transporte de cargas do setor florestal brasileiro é realizado em sua maior parte pelo modal rodoviário. Sua complexidade exibe a importância de diagnosticar o desenvolvimento da atividade para que se possa, por meio da pesquisa operacional, empregar de forma mais eficiente seus recursos disponíveis sem que haja perda de produtividade. Atualmente, o problema de escalonamento de motoristas é considerado um dos principais entraves à otimização em empresas de transporte, pois apresenta uma grande quantidade de restrições físicas e técnicas. Esta pesquisa teve como objetivo solucionar um problema real de escalonamento de motoristas no transporte de madeira de uma empresa florestal por meio de cinco meta-heurísticas (Algoritmo Genético AG, Algoritmo Memético AM, Clustering Search CS, Greedy Randomized Adaptive Search GRASP e Simulated Annealing SA), comparar os métodos entre si e entre a situação corrente na empresa, e propor uma nova escala de serviços. Para validação da abordagem proposta, foi utilizada uma entrada de dados gerada a partir da pesquisa qualitativa e de estudos de tempos e movimentos. Os resultados indicam que todos os métodos foram eficientes para resolver o problema sobressaindo-se o CS como melhor, seguido do SA, GRASP, AM e AG. O CS conseguiu atender aos objetivos com uma redução em 1/3 do quadro de 150 motoristas além de eliminar médias diárias de horas extras e excedentes que eram de 01h03min e 00h51min, respectivamente. Palavras-chave: transporte florestal, meta-heurísticas, escalonamento de motoristas, logística de transporte, produção florestal.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Automação e Sistemas / Made available in DSpace on 2012-10-26T12:25:42Z (GMT). No. of bitstreams: 1 301047.pdf: 1285723 bytes, checksum: fcb30ba5e90539742c71505b32d65921 (MD5) / Sistemas de tempo real são sistemas onde o correto funcionamento não depende somente da resposta lógica correta, mas também do tempo no qual ela foi dada. Igualmente do ponto de vista lógico, a viabilidade temporal da aplicação deve ser determinada através de técnicas, como por exemplo análise do tempo de reposta. Este tipo de aplicação está cada vez mais presente atualmente e a demanda de processamento é tamanha que necessita-se de processadores com múltiplos núcleos complexos. É perceptível que o desenvolvimento dos multiprocessadores está muito mais avançado em relação às técnicas de análise de tais sistemas e, portanto, é evidente a necessidade de pesquisa com objetivo de promover maior confiabilidade e redução de superdimensionamentos. O objetivo deste trabalho é promover uma solução de escalonamento que considere a escalonabilidade em conjunto com a analisabilidade do código da aplicação. Atualmente, a pesquisa de sistemas de tempo real trata o problema do escalonamento isolado do problema de obtenção do parâmetro do tempo de computação da tarefas (WCET --Worst Case Execution Time). Dependendo da arquitetura do processador, as premissas adotadas no cálculo do WCET são incompatíveis com as premissas de escalonamento, o que gera uma contradição fundamental entre o cálculo do WCET e os algoritmos de escalonamento. A incompatibilidade das premissas pode ser ilustrada pela preempção em arquiteturas com memória cache, onde o cálculo de WCET assume execução contínua da tarefa, o que não é verdade em grande parte dos algoritmos de escalonamento. Este trabalho propõe o uso de uma abordagem heterogênea em multiprocessadores onde parte dos núcleos operam em regime preemptivo e parte em regime não preemptivo para tentar lidar com as diferentes considerações sobre preempção. As análises realizadas mostram que existe vantagem em usar a abordagem heterogênea. / Real-time systems are systems where the correct functioning depends not only on the logically correct response, but also the time when it was given. As the the logic functionality, the application response time could be analyzed to determine the viability of a real-time system. This type of application is increasingly present today and the processing demand is such that complex multi-core processors are needed. It is noticeable that the development of multiprocessor is a long way ahead compared with the techniques of analysis of such systems and is therefore necessary researches to promote more reliability and to reduce over-specified systems. The objective of this work is to promote a solution that considers scheduling in conjunction with the analyzability of the application code. Currently, the real-time research considers the scheduling problem isolated from the WCET (Worst Case Execution Time) problem. Depending on the processor architecture, the values obtained by computing WCET are incompatible with the scheduling model which creates a fundamental contradiction between the assumptions of calculation of WCET and scheduling algorithms. This work proposes the use of a heterogeneous approach where part of the multiprocessor cores operate under preemptive and part on a non-preemptive scheduling. The analysis shows that there are advantages using the heterogeneous approach.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Ciência da Computação. / Made available in DSpace on 2012-10-21T08:46:56Z (GMT). No. of bitstreams: 1 202752.pdf: 768214 bytes, checksum: c8a8db65a7bdaaa5e098882707a683d9 (MD5) / Este trabalho apresenta a resolução de um problema clássico da Síntese de Alto Nível: o escalonamento sob restrições de recursos e de tempo. Para tanto utiliza uma abordagem orientada à exploração automática de soluções alternativas. O problema consiste em escalonar as operações de um algoritmo buscando uma melhor utilização dos recursos físicos e satisfazendo uma série de restrições de recursos, de precedência e de tempo. Os resultados experimentais mostram o sucesso das técnicas propostas em eliminar soluções de baixa qualidade do espaço de busca e melhorar a qualidade média do espaço de soluções. Em adição, na maioria dos testes realizados houve uma redução do tempo de busca por soluções de boa qualidade.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Ciência da Computação / Made available in DSpace on 2012-10-21T08:55:26Z (GMT). No. of bitstreams: 1 209154.pdf: 737730 bytes, checksum: b1bd6844c7543dc5d1373cb7673e595b (MD5) / A utilização de agregados de computadores está cada vez mais presente no contexto computacional atual. Um dos grandes problemas de tais ambientes é a má alocação dos recursos computacionais. O módulo de escalonamento de processos é um importante componente para a melhoria de distribuição das cargas do sistema. Enquanto o escalonamento estático é utilizado nos casos em que o comportamento dos programas é previamente conhecido, o escalonamento dinâmico torna-se necessário em casos onde o comportamento dos processos é desconhecido. As soluções de escalonamento adaptativas tomam decisões com base nos parâmetros atuais do sistema. Desta forma, são capazes de adaptarem-se às variações do ambiente. Nesta dissertação, apresentamos uma abordagem de escalonamento dinâmico de processos baseado em sistemas classificadores. Sistemas classificadores são algoritmos de aprendizado de máquina, baseados em algoritmos genéticos altamente adaptáveis. Em adição, apresentamos um modelo de sistema computacional que é testado sob o paradigma de um sistema classificador. Nossos resultados demonstram um diferencial na capacidade de adaptação do sistema classificador mediante o ambiente sob o qual está inserido.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-21T09:52:19Z (GMT). No. of bitstreams: 1 201486.pdf: 496463 bytes, checksum: 55424db49c821ad081991d52c7ee8aa5 (MD5) / Esta dissertação aborda o problema de escalonamento sob restrições de recursos em Síntese de Alto Nível. Tradicionalmente, os algoritmos de escalonamento associam operações a instantes de tempo, levando em conta um número pré-fixado de unidades funcionais (somadores, ALUs, multiplicadores). Entretanto, para viabilizar a execução de uma operação em uma unidade funcional, os operandos precisam ser preliminarmente lidos de registradores e transportados, através de barramentos, até as entradas da unidade funcional. Além disso, o resultado da operação precisa também ser transportado, através de um barramento, até o registrador destino. Conseqüentemente, o escalonamento de muitas operações em paralelo pode levar à alocação de um número proibitivo de barramentos. Isto torna desejável que um algoritmo de escalonamento seja capaz de manipular também restrições impostas por um número pré-fixado de barramentos. Este trabalho estende um algoritmo de escalonamento clássico, usando a noção de transferência entre registradores (RT) ao invés da simples noção de operação. Assim, o escalonador estendido torna-se capaz de manipular, além das restrições de precedência, restrições de recursos impostas por um número limitado de recursos, sejam eles unidades funcionais e/ou barramentos. Resultados experimentais mostram o impacto do número limitado de barramentos sobre a latência.

Sistemas computacionais de tempo real são identificados como aqueles sistemas submetidos a requisitos de natureza temporal. Nestes sistemas, os resultados devem estar corretos não somente do ponto de vista lógico, mas também devem ser gerados no momento correto. Um problema básico encontrado na construção de sistemas distribuídos de tempo real é a alocação e o escalonamento das tarefas nos recursos computacionais disponíveis. Existe uma dificuldade intrínsica em compatibilizar dois objetivos fundamentais: garantir que os resultados serão produzidos no momento desejado e dotar o sistema de flexibilidade para adaptar-se a um ambiente dinâmico e, assim, aumentar sua utilidade. Uma das técnicas existentes na literatura para resolver o problema de escalonamento tempo real é a Computação Imprecisa. Nesta técnica, cada tarefa da aplicação possui uma parte obrigatória e uma parte opcional. A parte obrigatória é capaz de gerar um resultado com a qualidade mínima, necessária para manter o sistema operando de maneira segura. A parte opcional refina este resultado, até que ele alcançe a qualidade desejada. Esta técnica procura conciliar os dois objetivos fundamentais citados antes. Entretanto, não existe na literatura um estudo amplo sobre a questão de "como resolver o problema do escalonamento quando sistemas de tempo real distribuídos são construidos a partir do conceito de Computação Imprecisa". O objetivo geral desta tese é mostrar como aplicações de tempo real, construídas a partir do conceito de Computação Imprecisa, podem ser escalonadas em ambiente distribuído. Em outras palavras, mostrar que o conceito de Computação Imprecisa pode ser adaptado para um ambiente onde tarefas executam em diferentes processadores e a comunicação entre elas é implementada através de mensagens. É mostrado que o problema proposto pode ser dividido em quatro problemas específicos. São eles: - Como garantir que as partes obrigatórias das tarefas serão concluídas antes dos respectivos deadlines, em um ambiente onde tarefas podem executar em diferentes processadores e o emprego de mensagens cria relações de precedência entre elas. - Como determinar que a execução de uma parte opcional não irá comprometer a execução das partes obrigatórias, previamente garantidas. - Como escolher quais partes opcionais devem ser executadas, na medida em que o recurso "tempo de processador disponível" não permite a execução de todas elas. - Como resolver qual tarefa executa em qual processador, de forma que todas as partes obrigatórias das tarefas possam ser garantidas e que as partes opcionais estejam distribuídas de forma que sua chance de execução seja maximizada. Nesta tese são apresentadas soluções de escalonamento para estes quatro problemas específicos. Desta forma, o texto mostra que efetivamente Computação Imprecisa pode ser usada como base para a construção de aplicações distribuídas de tempo real. / Real-time computing systems are defined as those systems subjected to timing constraints. In those systems, results must be not only logically correct but they also must be generated at the right moment. A basic problem one finds when building a distributed real time system is the allocation and scheduling of tasks on the available computing resources. There is an intrinsic difficulty in simultaneously achieving two fundamental goals: to guarantee that results are generated by the desired time and to make the system flexible enough so it can adapt to a dynamic environment and, that way, increase its own utility. The Imprecise Computation technique has been proposed in the literature as an approach to the scheduling of real-time systems. When this technique is used, each task has a mandatory part and an optional part. The mandatory part is able to generate a minimal quality result that is barely good enough to keep the system in a safe operational mode. The optional part refines the result until it achieves the desired quality level. This technique tries to conciliate the two fundamental goals mentioned above. Meanwhile, there is not in the literature a broad study on "how to solve the scheduling problem when real-time distributed systems are built based on Imprecise Computation concepts. "The overall goal of this theses is to show how real-time applications, that are built upon Imprecise Computation concepts, can be scheduled in a distributed environment. We intend to show that Imprecise Computation concepts can be adapted to an environment where tasks execute in different processors and communication among them is done by sending messages. It is shown in the text that we can split this problem in the following four specific problems: - How to guarantee that mandatory parts will be finished before or at the respective task deadline, when we consider that tasks can execute in different processors and the use of messages creates precedence relations among them. - How to know that the execution of an optional part will not jeopardize the execution of previously guaranteed mandatory parts. - How to chose which optional parts should be executed when the resource "available processor time" is not enough to execute all of them. - How to decide which task runs on which processor, in a way that all mandatory parts can be guaranteed and that optional parts are evenly spread over the system so as to maximize the chance they get actually executed. This theses presents scheduling solutions for those four specific problems. In this way, the text shows that Imprecise Computation can effectively be used as the conceptual base for the construction of distributed real-time applications.

Com o aumento no uso de aglomerados e grades de computadores, cresce o interesse no estudo de comunicações entre processadores. Em um computador paralelo dedicado, ou em uma rede local homogênea, o tempo de comunicação é geralmente modelado de forma similar, independente de quais processadores estão se comunicando. Em uma rede onde os links entre os computadores são heterogêneos, computadores mais próximos tendem a apresentar menor latência e maior largura de banda do que computadores distantes. Além disso, a largura de banda agregada é diferente dependendo do número de conexões simultâneas existentes entre dois aglomerados distantes. Neste trabalho estudaremos a troca completa de mensagens de tamanhos diferentes entre aglomerados interligados por backbones. Proporemos um novo algoritmo de comunicação baseado em algoritmos conhecidos, apresentaremos simulações de escalonamentos dos algoritmos estudados para esta rede multi-aglomerado e analisaremos os resultados destas simulações. / The growth in popularity of clusters and computational grids caused an increase in the interest in studying interprocessors communications. The comunication time in a dedicated parallel computer or in a local homogeneous network is modeled in a similar way, regardless of which processors are communicating. In a network with heterogeneous links, closer computers generally have lower latency and larger bandwidth than wide area computers. Besides, the aggregated bandwidth depends on the number of simultaneous connections between two wide area clusters. In this work we study the complete exchange of messages of different sizes between interconnected clusters using a backbone. We propose a new comunication algorithm based on known algorithms, we present some scheduling simulations of the studied algorithms in this multi-cluster network and we present the results analysis of these simulations.

Sistemas computacionais de tempo real são identificados como aqueles sistemas submetidos a requisitos de natureza temporal. Nestes sistemas, os resultados devem estar corretos não somente do ponto de vista lógico, mas também devem ser gerados no momento correto. Um problema básico encontrado na construção de sistemas distribuídos de tempo real é a alocação e o escalonamento das tarefas nos recursos computacionais disponíveis. Existe uma dificuldade intrínsica em compatibilizar dois objetivos fundamentais: garantir que os resultados serão produzidos no momento desejado e dotar o sistema de flexibilidade para adaptar-se a um ambiente dinâmico e, assim, aumentar sua utilidade. Uma das técnicas existentes na literatura para resolver o problema de escalonamento tempo real é a Computação Imprecisa. Nesta técnica, cada tarefa da aplicação possui uma parte obrigatória e uma parte opcional. A parte obrigatória é capaz de gerar um resultado com a qualidade mínima, necessária para manter o sistema operando de maneira segura. A parte opcional refina este resultado, até que ele alcançe a qualidade desejada. Esta técnica procura conciliar os dois objetivos fundamentais citados antes. Entretanto, não existe na literatura um estudo amplo sobre a questão de "como resolver o problema do escalonamento quando sistemas de tempo real distribuídos são construidos a partir do conceito de Computação Imprecisa". O objetivo geral desta tese é mostrar como aplicações de tempo real, construídas a partir do conceito de Computação Imprecisa, podem ser escalonadas em ambiente distribuído. Em outras palavras, mostrar que o conceito de Computação Imprecisa pode ser adaptado para um ambiente onde tarefas executam em diferentes processadores e a comunicação entre elas é implementada através de mensagens. É mostrado que o problema proposto pode ser dividido em quatro problemas específicos. São eles: - Como garantir que as partes obrigatórias das tarefas serão concluídas antes dos respectivos deadlines, em um ambiente onde tarefas podem executar em diferentes processadores e o emprego de mensagens cria relações de precedência entre elas. - Como determinar que a execução de uma parte opcional não irá comprometer a execução das partes obrigatórias, previamente garantidas. - Como escolher quais partes opcionais devem ser executadas, na medida em que o recurso "tempo de processador disponível" não permite a execução de todas elas. - Como resolver qual tarefa executa em qual processador, de forma que todas as partes obrigatórias das tarefas possam ser garantidas e que as partes opcionais estejam distribuídas de forma que sua chance de execução seja maximizada. Nesta tese são apresentadas soluções de escalonamento para estes quatro problemas específicos. Desta forma, o texto mostra que efetivamente Computação Imprecisa pode ser usada como base para a construção de aplicações distribuídas de tempo real. / Real-time computing systems are defined as those systems subjected to timing constraints. In those systems, results must be not only logically correct but they also must be generated at the right moment. A basic problem one finds when building a distributed real time system is the allocation and scheduling of tasks on the available computing resources. There is an intrinsic difficulty in simultaneously achieving two fundamental goals: to guarantee that results are generated by the desired time and to make the system flexible enough so it can adapt to a dynamic environment and, that way, increase its own utility. The Imprecise Computation technique has been proposed in the literature as an approach to the scheduling of real-time systems. When this technique is used, each task has a mandatory part and an optional part. The mandatory part is able to generate a minimal quality result that is barely good enough to keep the system in a safe operational mode. The optional part refines the result until it achieves the desired quality level. This technique tries to conciliate the two fundamental goals mentioned above. Meanwhile, there is not in the literature a broad study on "how to solve the scheduling problem when real-time distributed systems are built based on Imprecise Computation concepts. "The overall goal of this theses is to show how real-time applications, that are built upon Imprecise Computation concepts, can be scheduled in a distributed environment. We intend to show that Imprecise Computation concepts can be adapted to an environment where tasks execute in different processors and communication among them is done by sending messages. It is shown in the text that we can split this problem in the following four specific problems: - How to guarantee that mandatory parts will be finished before or at the respective task deadline, when we consider that tasks can execute in different processors and the use of messages creates precedence relations among them. - How to know that the execution of an optional part will not jeopardize the execution of previously guaranteed mandatory parts. - How to chose which optional parts should be executed when the resource "available processor time" is not enough to execute all of them. - How to decide which task runs on which processor, in a way that all mandatory parts can be guaranteed and that optional parts are evenly spread over the system so as to maximize the chance they get actually executed. This theses presents scheduling solutions for those four specific problems. In this way, the text shows that Imprecise Computation can effectively be used as the conceptual base for the construction of distributed real-time applications.