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-23T00:58:50Z (GMT). No. of bitstreams: 1 238111.pdf: 2161716 bytes, checksum: 597716c5a6074a9e93a760112ded0c97 (MD5) / A evolução dos sistemas computacionais deu origem aos systems-on-chip ou SoCs, onde diversos componentes (como memória, barramentos e processador(es)) estão presentes em um único circuito integrado. Os SoCs possivelmente contêm múltiplos processadores de diferentes tipos, portanto a exploração de seu espaço de projeto requer ferramentas redirecionáveis. O aumento da complexidade de tais sistemas, juntamente com a diminuição do time-to-market e a necessidade de iniciar-se o desenvolvimento do software embarcado o mais cedo possível, deu origem à modelagem no nível de transações ou TLM (transaction-level modeling). O projeto inicia-se com um modelo TLM atemporal, mas a posterior anotação de restrições temporais exige que o software embarcado seja revisado, sendo úteis ferramentas de análise de restrições temporais pós-compilação. Esta dissertação descreve uma técnica automaticamente redirecionável que combina análise de restrições temporais e escalonamento de código assembly. A técnica baseia se na extração de informações específicas da arquitetura-alvo através de uma descrição formal do processador e na codificação de restrições temporais e de precedência em uma representação unificada usando grafos. Resultados experimentais mostram que a técnica não somente lida eficientemente com restrições temporais, mas também as explora para guiar as otimizações. São apresentados resultados para os processadores MIPS, PowerPC e SPARC, onde acelerações na execução do código de até 1,3 vezes foram obtidas em relação ao código pré-otimizado. Este trabalho aborda ainda um estudo da viabilidade de se integrar a técnica proposta em um tradutor binário, contribuindo para que, ao se traduzir código compilado de uma arquitetura para outra, o código traduzido resulte otimizado. Resultados preliminares são apresentados como um forte indício de viabilidade.

Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores (Major Energia). Faculdade de Engenharia. Universidade do Porto. 2010

O escalonamento de veículos para múltiplas garagens é um problema clássico da Pesquisa Operacional de grande relevância à otimização da malha de transportes, de forma a buscar a melhor alocação dos recursos disponíveis. O problema é conhecido por ser do tipo NP-hard, e portanto a sua solução para grandes instâncias é realizada por heurísticas. Este trabalho aborda o desenvolvimento de uma heurística simples e eficiente para solucionar o MDVSP, buscando através da redução de possibilidades de viagens, pela retirada de viagens com baixas chances de pertencer a solução ótima reduzir a complexidade da rede. O problema reduzido, é então resolvido pela técnica de geração de colunas truncado e modificado, para resolver o problema de forma aceitável, encontrando soluções com bom compromisso entre tempo de execução e valor da função objetivo. A geração de colunas foi testada e validada através de comparações com trabalhos similares, enquanto que, cada técnica de redução de espaço de estados (de forma conjunta e individual) foram validados através da comparação com os resultados validados da geração de colunas modificada. A heurística mostrou uma melhoria considerável por meio da otimização do tempo de resolução, sem prejudicar os resultados de melhor valor, ficando com uma diferença máxima de 1% em comparação com os valores obtidos com geração de colunas. Se a redução for usada parcialmente, os tempos de solução podem ser reduzidos mais de sete vezes, com um pequeno incremento no valor da função objetivo. Pelas validações e experimentos realizados, pode-se afirmar que a heurística tem potencial para ser utilizada em problemas do mundo real, bem como servir como parte da solução de problemas correlatos mais complexos, como o crew scheduling, o disruption management e o escalonamento em tempo real. / The Multi Depot Vehicle Scheduling is a classical problem of Operations Research, with a great relevance to optimize the transportation network, as to find the best allocation of available resources. This problem is known to be NP-Hard, and therefore the solution of large instances is generally carried out by heuristics. This work proposes the development of a simple and efficient heuristic to solve the MDVSP, seeking by the reduction of travel possibilities, droping traveis with low chances to be in the best solution. The reduced problem is then solved by a modified truncated column generation technique, to solve the problem by an acceptable form, founding solutions for the MDVSP with a good compromise between time and costs. The column generation was tested and validated by the comparison of execution time and the value of objective function. The column generation was tested and comparised with similar works, whereas, each space state reduction technique (individual and joint) was validated in comparison with validated results of column generation truncated and modificated. The heuristics showed considerable improvements by the optimization of resolution time, without harm the best value results, obtaining differences lower as 1% comparing with the obtained values by the column generation solution. If the reduction is used partially, the solution times can be reduced in more then seven times, with a small increment in the objective function value. By the validations and experimenta realized, we can confirm that the heuristics has potential to be used in real world situations, as well as to serve as basis for the development of solution methods for more complex and correlated problems, as the crew scheduling problem, disruption management, and the real time assignment.

O escalonamento de veículos para múltiplas garagens é um problema clássico da Pesquisa Operacional de grande relevância à otimização da malha de transportes, de forma a buscar a melhor alocação dos recursos disponíveis. O problema é conhecido por ser do tipo NP-hard, e portanto a sua solução para grandes instâncias é realizada por heurísticas. Este trabalho aborda o desenvolvimento de uma heurística simples e eficiente para solucionar o MDVSP, buscando através da redução de possibilidades de viagens, pela retirada de viagens com baixas chances de pertencer a solução ótima reduzir a complexidade da rede. O problema reduzido, é então resolvido pela técnica de geração de colunas truncado e modificado, para resolver o problema de forma aceitável, encontrando soluções com bom compromisso entre tempo de execução e valor da função objetivo. A geração de colunas foi testada e validada através de comparações com trabalhos similares, enquanto que, cada técnica de redução de espaço de estados (de forma conjunta e individual) foram validados através da comparação com os resultados validados da geração de colunas modificada. A heurística mostrou uma melhoria considerável por meio da otimização do tempo de resolução, sem prejudicar os resultados de melhor valor, ficando com uma diferença máxima de 1% em comparação com os valores obtidos com geração de colunas. Se a redução for usada parcialmente, os tempos de solução podem ser reduzidos mais de sete vezes, com um pequeno incremento no valor da função objetivo. Pelas validações e experimentos realizados, pode-se afirmar que a heurística tem potencial para ser utilizada em problemas do mundo real, bem como servir como parte da solução de problemas correlatos mais complexos, como o crew scheduling, o disruption management e o escalonamento em tempo real. / The Multi Depot Vehicle Scheduling is a classical problem of Operations Research, with a great relevance to optimize the transportation network, as to find the best allocation of available resources. This problem is known to be NP-Hard, and therefore the solution of large instances is generally carried out by heuristics. This work proposes the development of a simple and efficient heuristic to solve the MDVSP, seeking by the reduction of travel possibilities, droping traveis with low chances to be in the best solution. The reduced problem is then solved by a modified truncated column generation technique, to solve the problem by an acceptable form, founding solutions for the MDVSP with a good compromise between time and costs. The column generation was tested and validated by the comparison of execution time and the value of objective function. The column generation was tested and comparised with similar works, whereas, each space state reduction technique (individual and joint) was validated in comparison with validated results of column generation truncated and modificated. The heuristics showed considerable improvements by the optimization of resolution time, without harm the best value results, obtaining differences lower as 1% comparing with the obtained values by the column generation solution. If the reduction is used partially, the solution times can be reduced in more then seven times, with a small increment in the objective function value. By the validations and experimenta realized, we can confirm that the heuristics has potential to be used in real world situations, as well as to serve as basis for the development of solution methods for more complex and correlated problems, as the crew scheduling problem, disruption management, and the real time assignment.

O escalonamento de veículos para múltiplas garagens é um problema clássico da Pesquisa Operacional de grande relevância à otimização da malha de transportes, de forma a buscar a melhor alocação dos recursos disponíveis. O problema é conhecido por ser do tipo NP-hard, e portanto a sua solução para grandes instâncias é realizada por heurísticas. Este trabalho aborda o desenvolvimento de uma heurística simples e eficiente para solucionar o MDVSP, buscando através da redução de possibilidades de viagens, pela retirada de viagens com baixas chances de pertencer a solução ótima reduzir a complexidade da rede. O problema reduzido, é então resolvido pela técnica de geração de colunas truncado e modificado, para resolver o problema de forma aceitável, encontrando soluções com bom compromisso entre tempo de execução e valor da função objetivo. A geração de colunas foi testada e validada através de comparações com trabalhos similares, enquanto que, cada técnica de redução de espaço de estados (de forma conjunta e individual) foram validados através da comparação com os resultados validados da geração de colunas modificada. A heurística mostrou uma melhoria considerável por meio da otimização do tempo de resolução, sem prejudicar os resultados de melhor valor, ficando com uma diferença máxima de 1% em comparação com os valores obtidos com geração de colunas. Se a redução for usada parcialmente, os tempos de solução podem ser reduzidos mais de sete vezes, com um pequeno incremento no valor da função objetivo. Pelas validações e experimentos realizados, pode-se afirmar que a heurística tem potencial para ser utilizada em problemas do mundo real, bem como servir como parte da solução de problemas correlatos mais complexos, como o crew scheduling, o disruption management e o escalonamento em tempo real. / The Multi Depot Vehicle Scheduling is a classical problem of Operations Research, with a great relevance to optimize the transportation network, as to find the best allocation of available resources. This problem is known to be NP-Hard, and therefore the solution of large instances is generally carried out by heuristics. This work proposes the development of a simple and efficient heuristic to solve the MDVSP, seeking by the reduction of travel possibilities, droping traveis with low chances to be in the best solution. The reduced problem is then solved by a modified truncated column generation technique, to solve the problem by an acceptable form, founding solutions for the MDVSP with a good compromise between time and costs. The column generation was tested and validated by the comparison of execution time and the value of objective function. The column generation was tested and comparised with similar works, whereas, each space state reduction technique (individual and joint) was validated in comparison with validated results of column generation truncated and modificated. The heuristics showed considerable improvements by the optimization of resolution time, without harm the best value results, obtaining differences lower as 1% comparing with the obtained values by the column generation solution. If the reduction is used partially, the solution times can be reduced in more then seven times, with a small increment in the objective function value. By the validations and experimenta realized, we can confirm that the heuristics has potential to be used in real world situations, as well as to serve as basis for the development of solution methods for more complex and correlated problems, as the crew scheduling problem, disruption management, and the real time assignment.

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.

Nesta dissertação convergem algumas linhas de investigação na área das meta-heurísticas que, recentemente, têm vindo a ser objecto de particular atenção: a flexibilização, ou seja, a introdução de mecanismos de modificação de componentes e estratégias elementares, o desenvolvimento de abordagens orientadas por objectos, e a adaptação a contextos multiobjectivo. Esta convergência justifica-se pelo facto de as abordagens orientadas por objectos promoverem naturalmente a flexibilização, e pela constatação da inexistência, até ao momento, de abordagens orientadas por objectos para a área das metaheurísticas multiobjectivo. Foi feita uma análise e sistematização do domínio e, em particular, das metaheurísticas multiobjectivo, com ênfase na perspectiva da flexibilização. Esta sistematização fundamenta a proposta de um template para pesquisa local multiobjectivo, e de um conjunto de estratégias genéricas de flexibilização.

Estágio realizado na Qimonda Portugal e orientado pelo Eng.º Fernando Freitas e Eng.ª Joana Pereira / Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2009

Tese de mestrado integrado. Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2009

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.