Roteamento em redes embutidas utilizando otimização por colônia de formigas.

Redes embutidas (NoC, Network-on-Chip) vêm sendo adotadas como uma solução interessante para o projeto de infraestruturas de comunicação em sistemas embutidos (SoC, System-on-Chip). Estas redes são em geral parametrizadas, podendo assim ser utilizadas em vários projetos de SoCs, cada qual com diferentes quantidades de núcleos. NoCs permitem uma escalabilidade dos sistemas, ao mesmo tempo que balanceiam a comunicação entre núcleos. Projetos baseados em NoC visam a implementação de uma aplicação específica. Neste contexto, ferramentas de auxílio de projeto são essenciais. Estas ferramentas são projetadas para, a partir de uma descrição simples da aplicação, realizar sucessivos processos de otimização que irão modelar as várias características do sistema. Estes algoritmos de otimização são necessários para que a rede atenda a um conjunto de restrições, como área, consumo de energia e tempo de execução. Dentre estas etapas, pode ser incluído o roteamento estático. As rotas através da rede por onde os núcleos irão se comunicar são otimizadas, de forma a minimizar o tempo de comunicação e os atrasos na transmissão de pacotes ocasionados por congestionamentos nas chaves que compõem a NoC. Nesta dissertação, foi utilizada a otimização por colônia de formigas no cálculo dos percursos. Esta é uma meta-heurística interessante para a solução de problemas de busca em grafos, inspirada no comportamento de formigas reais. Para os algoritmos propostos, múltiplas colônias são utilizadas, cada uma encarregada pela otimização do percurso de uma mensagem. Os diferentes testes realizados mostram o roteamento baseado no Elitist Ant System obtendo resultados superiores a outros algoritmos de roteamento.

Implementação de algoritmos genéticos paralelos em uma arquitetura MPSoC.

Essa dissertação apresenta a implementação de um algoritmo genético paralelo utilizando o modelo de granularidade grossa, também conhecido como modelo das ilhas, para sistemas embutidos multiprocessados. Os sistemas embutidos multiprocessados estão tornando-se cada vez mais complexos, pressionados pela demanda por maior poder computacional requerido pelas aplicações, principalmente de multimídia, Internet e comunicações sem fio, que são executadas nesses sistemas. Algumas das referidas aplicações estão começando a utilizar algoritmos genéticos, que podem ser beneficiados pelas vantagens proporcionadas pelo processamento paralelo disponível em sistemas embutidos multiprocessados. No algoritmo genético paralelo do modelo das ilhas, cada processador do sistema embutido é responsável pela evolução de uma população de forma independente dos demais. A fim de acelerar o processo evolutivo, o operador de migração é executado em intervalos definidos para realizar a migração dos melhores indivíduos entre as ilhas. Diferentes topologias lógicas, tais como anel, vizinhança e broadcast, são analisadas na fase de migração de indivíduos. Resultados experimentais são gerados para a otimização de três funções encontradas na literatura.

Desenvolvimento de um nó de rede com diferentes interfaces de acordo com o padrão IEEE 1451 utilizando o processador nios II e o sistema operacional embarcado uclinux

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Arquitetura para publicação e universalização do acesso a transdutores inteligentes

Pós-graduação em Engenharia Elétrica - FEIS

Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.

Investigating Smart Sampling as a population initialization method for Differential Evolution in continuous problems

Recently, researches have shown that the performance of metaheuristics can be affected by population initialization. Opposition-based Differential Evolution (ODE), Quasi-Oppositional Differential Evolution (QODE), and Uniform-Quasi-Opposition Differential Evolution (UQODE) are three state-of-the-art methods that improve the performance of the Differential Evolution algorithm based on population initialization and different search strategies. In a different approach to achieve similar results, this paper presents a technique to discover promising regions in a continuous search-space of an optimization problem. Using machine-learning techniques, the algorithm named Smart Sampling (SS) finds regions with high possibility of containing a global optimum. Next, a metaheuristic can be initialized inside each region to find that optimum. SS and DE were combined (originating the SSDE algorithm) to evaluate our approach, and experiments were conducted in the same set of benchmark functions used by ODE, QODE and UQODE authors. Results have shown that the total number of function evaluations required by DE to reach the global optimum can be significantly reduced and that the success rate improves if SS is employed first. Such results are also in consonance with results from the literature, stating the importance of an adequate starting population. Moreover, SS presents better efficacy to find initial populations of superior quality when compared to the other three algorithms that employ oppositional learning. Finally and most important, the SS performance in finding promising regions is independent of the employed metaheuristic with which SS is combined, making SS suitable to improve the performance of a large variety of optimization techniques. (C) 2012 Elsevier Inc. All rights reserved.

Simple heuristics for the assembly line worker assignment and balancing problem

We propose simple heuristics for the assembly line worker assignment and balancing problem. This problem typically occurs in assembly lines in sheltered work centers for the disabled. Different from the well-known simple assembly line balancing problem, the task execution times vary according to the assigned worker. We develop a constructive heuristic framework based on task and worker priority rules defining the order in which the tasks and workers should be assigned to the workstations. We present a number of such rules and compare their performance across three possible uses: as a stand-alone method, as an initial solution generator for meta-heuristics, and as a decoder for a hybrid genetic algorithm. Our results show that the heuristics are fast, they obtain good results as a stand-alone method and are efficient when used as a initial solution generator or as a solution decoder within more elaborate approaches.

LALP: a language to program custom FPGA-based acceleration engines

Field-Programmable Gate Arrays (FPGAs) are becoming increasingly important in embedded and high-performance computing systems. They allow performance levels close to the ones obtained with Application-Specific Integrated Circuits, while still keeping design and implementation flexibility. However, to efficiently program FPGAs, one needs the expertise of hardware developers in order to master hardware description languages (HDLs) such as VHDL or Verilog. Attempts to furnish a high-level compilation flow (e.g., from C programs) still have to address open issues before broader efficient results can be obtained. Bearing in mind an FPGA available resources, it has been developed LALP (Language for Aggressive Loop Pipelining), a novel language to program FPGA-based accelerators, and its compilation framework, including mapping capabilities. The main ideas behind LALP are to provide a higher abstraction level than HDLs, to exploit the intrinsic parallelism of hardware resources, and to allow the programmer to control execution stages whenever the compiler techniques are unable to generate efficient implementations. Those features are particularly useful to implement loop pipelining, a well regarded technique used to accelerate computations in several application domains. This paper describes LALP, and shows how it can be used to achieve high-performance computing solutions.

Algoritmos evolutivos e modelo HP para predição de estruturas de proteínas

Predição de estruturas de proteínas (PSP) é um problema computacionalmente complexo. Modelos simplificados da molécula proteica (como o Modelo HP) e o uso de Algoritmos Evolutivos (AEs) estão entre as principais técnicas investigadas para PSP. Entretanto, a avaliação de uma estrutura representada pelo Modelo HP considera apenas o número de contatos hidrofóbicos, não possibilitando distinguir entre estruturas com o mesmo número de contatos hidrofóbicos. Neste trabalho, é apresentada uma nova formulação multiobjetivo para PSP em Modelo HP. Duas métricas são avaliadas: o número de contatos hidrofóbicos e a distância entre os aminoácidos hidrofóbicos, as quais são tratados pelo AE Multiobjetivo em Tabelas (AEMT). O algoritmo mostrou-se rápido e robusto.

Programmable logic design of a compact Genetic Algorithm for phasor estimation in real-time

The main objective of this work is to present an efficient method for phasor estimation based on a compact Genetic Algorithm (cGA) implemented in Field Programmable Gate Array (FPGA). To validate the proposed method, an Electrical Power System (EPS) simulated by the Alternative Transients Program (ATP) provides data to be used by the cGA. This data is as close as possible to the actual data provided by the EPS. Real life situations such as islanding, sudden load increase and permanent faults were considered. The implementation aims to take advantage of the inherent parallelism in Genetic Algorithms in a compact and optimized way, making them an attractive option for practical applications in real-time estimations concerning Phasor Measurement Units (PMUs).

Autonomic hardware manager: uma arquitetura de hardware autonômico usando a solução de repositório ativo de componentes

This Thesis main objective is to implement a supporting architecture to Autonomic Hardware systems, capable of manage the hardware running in reconfigurable devices. The proposed architecture implements manipulation, generation and communication functionalities, using the Context Oriented Active Repository approach. The solution consists in a Hardware-Software based architecture called "Autonomic Hardware Manager (AHM)" that contains an Active Repository of Hardware Components. Using the repository the architecture will be able to manage the connected systems at run time allowing the implementation of autonomic features such as self-management, self-optimization, self-description and self-configuration. The proposed architecture also contains a meta-model that allows the representation of the Operating Context for hardware systems. This meta-model will be used as basis to the context sensing modules, that are needed in the Active Repository architecture. In order to demonstrate the proposed architecture functionalities, experiments were proposed and implemented in order to proof the Thesis hypothesis and achieved objectives. Three experiments were planned and implemented: the Hardware Reconfigurable Filter, that consists of an application that implements Digital Filters using reconfigurable hardware; the Autonomic Image Segmentation Filter, that shows the project and implementation of an image processing autonomic application; finally, the Autonomic Autopilot application that consist of an auto pilot to unmanned aerial vehicles. In this work, the applications architectures were organized in modules, according their functionalities. Some modules were implemented using HDL and synthesized in hardware. Other modules were implemented kept in software. After that, applications were integrated to the AHM to allow their adaptation to different Operating Context, making them autonomic.

Reserva de recursos MSRP para o switch de tempo-real HaRTES

Os mecanismos e técnicas do domínio de Tempo-Real são utilizados quando existe a necessidade de um sistema, seja este um sistema embutido ou de grandes dimensões, possuir determinadas características que assegurem a qualidade de serviço do sistema. Os Sistemas de Tempo-Real definem-se assim como sistemas que possuem restrições temporais rigorosas, que necessitam de apresentar altos níveis de fiabilidade de forma a garantir em todas as instâncias o funcionamento atempado do sistema. Devido à crescente complexidade dos sistemas embutidos, empregam-se frequentemente arquiteturas distribuídas, onde cada módulo é normalmente responsável por uma única função. Nestes casos existe a necessidade de haver um meio de comunicação entre estes, de forma a poderem comunicar entre si e cumprir a funcionalidade desejadas. Devido à sua elevada capacidade e baixo custo a tecnologia Ethernet tem vindo a ser alvo de estudo, com o objetivo de a tornar num meio de comunicação com a qualidade de serviço característica dos sistemas de tempo-real. Como resposta a esta necessidade surgiu na Universidade de Aveiro, o Switch HaRTES, o qual possui a capacidade de gerir os seus recursos dinamicamente, de modo a fornecer à rede onde é aplicado garantias de Tempo-Real. No entanto, para uma arquitetura de rede ser capaz de fornecer aos seus nós garantias de qualidade serviço, é necessário que exista uma especificação do fluxo, um correto encaminhamento de tráfego, reserva de recursos, controlo de admissão e um escalonamento de pacotes. Infelizmente, o Switch HaRTES apesar de possuir todas estas características, não suporta protocolos standards. Neste documento é apresentado então o trabalho que foi desenvolvido para a integração do protocolo SRP no Switch HaRTES.

Operating infrastructure for an FPGA and ARM system

Advances in FPGA technology and higher processing capabilities requirements have pushed to the emerge of All Programmable Systems-on-Chip, which incorporate a hard designed processing system and a programmable logic that enable the development of specialized computer systems for a wide range of practical applications, including data and signal processing, high performance computing, embedded systems, among many others. To give place to an infrastructure that is capable of using the benefits of such a reconfigurable system, the main goal of the thesis is to implement an infrastructure composed of hardware, software and network resources, that incorporates the necessary services for the operation, management and interface of peripherals, that coompose the basic building blocks for the execution of applications. The project will be developed using a chip from the Zynq-7000 All Programmable Systems-on-Chip family.

Demonstrador para rede tempo-real HaRTES

A utilização de sistemas embutidos distribuídos em diversas áreas como a robótica, automação industrial e aviónica tem vindo a generalizar-se no decorrer dos últimos anos. Este tipo de sistemas são compostos por vários nós, geralmente designados por sistemas embutidos. Estes nós encontram-se interligados através de uma infra-estrutura de comunicação de forma a possibilitar a troca de informação entre eles de maneira a concretizar um objetivo comum. Por norma os sistemas embutidos distribuídos apresentam requisitos temporais bastante exigentes. A tecnologia Ethernet e os protocolos de comunicação, com propriedades de tempo real, desenvolvidos para esta não conseguem associar de uma forma eficaz os requisitos temporais das aplicações de tempo real aos requisitos Quality of Service (QoS) dos diferentes tipos de tráfego. O switch Hard Real-Time Ethernet Switching (HaRTES) foi desenvolvido e implementado com o objetivo de solucionar estes problemas devido às suas capacidades como a sincronização de fluxos diferentes e gestão de diferentes tipos de tráfego. Esta dissertação apresenta a adaptação de um sistemas físico de modo a possibilitar a demonstração do correto funcionamento do sistema de comunicação, que será desenvolvido e implementado, utilizando um switch HaRTES como o elemento responsável pela troca de informação na rede entre os nós. O desempenho da arquitetura de rede desenvolvida será também testada e avaliada.

Proteção passiva de estruturas e sistemas elétricos contra incêndio aplicada a uma unidade de refino de petróleo

Nesta dissertação visa-se estudar e propor alternativas de solução para a proteção de estruturas e sistemas elétricos contra fogo numa unidade de craqueamento catalítico de uma refinaria de petróleo, por meio de proteção passiva. A proteção passiva tem por finalidade garantir a integridade das estruturas sujeitas a incêndio, durante um determinado período de tempo, para possibilitar, no caso da refinaria, a realização de procedimentos de parada da unidade de forma segura e controlar o incêndio a fim de diminuir a possibilidade de propagação do fogo para outras áreas. Com base em técnicas de análise de riscos fez-se a identificação de zonas potencialmente sujeitas a cenários de acidente envolvendo jato de fogo e/ou incêndio em poça. A delimitação das áreas onde haveria necessidade de proteção passiva foi realizada com base em modelos para jatos de fogo e incêndio em poça já estabelecidos na literatura. O dimensionamento da proteção passiva de estruturas e sistemas elétricos com o uso de diversos materiais usados comercialmente para este fim foi estimado com base em equações empíricas desenvolvidas por Jeanes, 1980, Stanzak, 1973 e PABCO, 1984, e, para alguns casos particulares foi feita uma verificação por solução numérica da equação da condução do calor em meio sólido.Assim, foram determinados quais os materiais mais adequados em cada caso de aplicação e qual a espessura em que deve ser aplicado para que a temperatura no elemento estrutural ou no sistema elétrico não atinja a sua determinada temperatura crítica em um período de tempo pré-determinado. Para os casos de elementos estruturais como colunas de sustentação da unidade de seção cilíndrica, o principal material para proteção passiva é a argamassa projetada e para perfil I, é o emprego de placas de gesso. Já para o caso de sistemas elétricos, podem ser utilizadas tanto tintas intumescentes quanto as mantas reforçadas com fibras minerais, esta escolha depende da geometria do sistema em que será empregado. Da comparação entre estes dois métodos pode-se concluir que o dimensionamento da proteção passiva fazendo o uso das correlações empíricas é menos conservativo que para o caso do uso da equação da difusão do calor resolvida por método numérico. Porém, os resultados diferem dentro de um limite considerado aceitável (em torno de 15%) levando-se em consideração os erros embutidos em cada método de cálculo. É importante mencionar que as correlações empíricas são de mais simples aplicação por possuir apenas operações matemáticas básicas. Usando as correlações empíricas para os perfis cilíndricos de aço (diâmetro de 0,1524 m e espessura de parede de 0,0254 m), a espessura de revestimento estimada com o uso das correlações empíricas necessária para garantir que a temperatura na interface entre os dois materiais não atinja 550°C em duas horas seria de 13,5 mm para argamassa projetada, 19,7 mm para vermiculita com silicato de sódio e 34,5 mm para recobrimento com concreto com proteção do tipo contorno. Fazendo o mesmo cálculo pelo método numérico proposto, os resultados foram de 15,53 mm para argamassa projetada, 22,06 mm para vermiculita com silicato de sódio e 38,98 mm para recobrimento com concreto com proteção do tipo contorno. Fazendo o mesmo cálculo pelo método numérico proposto, os resultados foram de 15,53 mm para argamassa projetada, 22,06 mm para vermiculita com silicato de sódio e 38,98 mm para recobrimento com concreto com proteção do tipo contorno. Cabe ressaltar que com a realização desta dissertação busca-se uma integração entre o mestrado acadêmico e o meio empresarial com o desenvolvimento de trabalhos de natureza acadêmica que tenham aplicação direta na prática. Espera-se assim permitir que Universidade dê retorno à sociedade que a mantém e propiciar que setores da sociedade possam usufruir da capacidade disponível na academia.