Variações ambientais e de processo representam um grande desafio a ser vencido pelas redes de distribuição de relógio. O efeito das variações nos atrasos da rede de distribuição de relógio não pode ser previsto com precisão e portanto não podem ser diretamente considerados no projeto das redes de distribuição de relógio. Estruturas baseadas em clock meshes (i.e. clock mesh, clock spines e crosslinks) são a maneira mais eficiente de proteger a rede de relógio do efeito das variações nos atrasos. Clock meshes tem sido utilizados por bastante tempo no projeto de microprocessadores e recentemente foram incluídos no fluxo de síntese de ASICs. Embora o uso de clock meshes esteja aumentando há uma grande necessidade por métodos de analise e otimização dos mesmos. Essa tese propõe soluções para ambos os problemas. Uma metodologia para permitir a simulação elétrica de clock meshes grandes é proposta. O método proposto permite que a simulação dos clock meshes seja paralelizada com um erro menor que 1%. Duas metodologias de otimização também são propostas nessa tese. A primeira consiste em um algoritmo para dimensionamento para os mesh buffers. Esse algoritmo permite que o clock skew e o consumo de potência sejam reduzidos ao custo de aumentar o clock slew. O segundo método de otimização proposto consiste em um novo projeto para os mesh buffers. O novo mesh buffer é capaz de reduzir o clock skew em 22% e o consumo de potencia em 59%. / Process and environmental variations are a great challenge to clock network designers. Variations effect on the clock network delays can not be predicted, hence it can not be directly accounted in the design stage. Clock mesh-based structures (i.e. clock mesh, clock spines and crosslinks) are the most effective way to tolerate variation effects on delays. Clock meshes have been used for a long time in microprocessor designs and recently became supported by commercial tools in the ASIC design flow. Although clock meshes have been known for some time and its use in ASIC design is increasing, there is a lack of good analysis and optimization strategies for clock meshes. This thesis tackles both problems. Chapter 1 presents a basic introduction to clock distribution and important definitions. A review of existent clock dsitribution design strategies is presented in chapter 2. A study about the clock distribution architecture used in several microprocessor and a comparison between mesh-based and pure tree clock distribution architectures is shown in chapter 3.2. A methodology for enabling and speeding up the simulation of large clock meshes is presented in chapter 4. The proposed analysis methodology was shown to enable the parallel evaluation of large clock meshes with an error smaller than 1%. Chapter 5 presents two optimization strategies, a new mesh buffer design and a mesh buffer sizing algorithm. The new mesh buffer design was proposed improving clock skew by 22% and clock power by 59%. The mesh buffer sizing algorithm can reduce clock skew by 33%, power consumption by 20% with at the cost of a 26% slew increase. At last conclusions are presented on chapter 6.

O objetivo deste trabalho é propor técnicas de alocação dinâmica de tarefas periódicas em MPSoCs homogêneos, com processadores interligados por uma rede emchip do tipo malha, visando redução do consumo de energia do sistema. O foco principal é a definição de uma heurística de alocação, não se considerando protocolos de escalonamento distribuído, uma vez que este ainda é um primeiro estudo para o desenvolvimento de um alocador dinâmico. Na arquitetura alvo utilizada, cada nodo do sistema é dado como autônomo, possuindo seu próprio escalonador EDF. Além disso, são aplicadas técnicas de voltage scaling e power managmenent para redução do consumo de energia durante o escalonamento. Durante a pesquisa do estado da arte, não foram encontradas técnicas de alocação dinâmica em NoCs com restrições temporais e minimização do consumo de energia. Por isso, esse trabalho se concentra em avaliar técnicas de alocação convencionais, como bin-packing e técnicas baseadas em teoria de grafos, no contexto de sistemas embarcados. Dessa forma, o modelo de estimativas do consumo de energia de alocações é baseado no escalonamento de grafos de tarefas, e foi utilizado para implementar a ferramenta Serpens com este propósito. Os grafos de tarefas utilizados nos experimentos são tirados do benchmark E3S – Embedded System Synthesis Benchmark Suite, composto por um conjunto de grafos de tarefas gerados aleatoriamente com a ferramenta TGFF – Task Graph for Free, a partir de dados de aplicações comuns em sistemas embarcados obtidos no EEMBC – Embedded Microprocessor Benchmark Consortium. Entre as heurísticas de bin-packing, Best-Fit, First-Fit e Next-Fit geram alocações com concentração de carga, enquanto a heurística Worst-Fit faz balanceamento de carga. O balanceamento de carga favorece a aplicação de voltage scaling enquanto a concentração favorece o power management. Como o bin-packing não contempla comunicação e dependência entre tarefas em seu modelo, o mesmo foi reformulado para atender esta necessidade. Nos experimentos, a alocação inicial com bin-packing original apresentou perdas de deadlines de até 84 % para a heurística Worst-Fit, passando para perdas em torno de 16% na alocação final, praticamente com o mesmo consumo de energia, após a reformulação do modelo. / The goal of this work is to offer dynamic allocation techniques of periodic tasks in mesh networks-on-chip, aiming to reduce the system power consumption. The main focus is the definition of an allocation heuristic, which does not consider distributed scheduling protocols, since this is the beginning of a study for the development of a dynamic partitioning tool. In the target architecture, each system node is self-contained, that is, the nodes contain their own EDF scheduler. Besides, voltage-scaling and power management techniques are applied for reducing power consumption during the scheduling. To the best of our knowledge, this is the first research effort considering both temporal constraints and power consumption minimization on the dynamic allocation of tasks in a mesh NoC. This way, our concentrates in the evaluation of dynamic allocation techniques, which are generally used in distributed systems, in the embedded systems context, as bin-packing and graph theory based techniques. Therefore, the estimation model for power consumption is based on task graph scheduling, and it was used for implementing the Serpens tool with this purpose. The task graphs used in the experiments were obtained from the E3S benchmark (Embedded System Synthesis Benchmark Suite), which is composed by a set of task graphs randomly generated with the TGFF tool (Task Graph for Free), from common application data obtained from the EEMBC (Embedded Microprocessor Benchmark Consortium). Among the bin-packing heuristics, Best-Fit, First-Fit, and Next-Fit generate allocations with load concentration, while the Worst-Fit heuristics works with load balancing. Load balancing favors the application of voltage scaling, while load concentration favors the utilization of power management. Since the bin-packing model does not consider inter-task communication and dependency, it has been modified to fulfill this need. In the experiments, the initial allocation using the original bin-packing model presented deadline losses of up to 84% for the Worst-Fit heuristic, changing for losses around 16% in the final allocation, after modification of the model, maintaining almost the same power consumption.

Dissertação apresentada para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores (Área de especialização de Sistemas Digitais e Informática Industrial), na Faculdade de Engenharia da Universidade do Porto, sob a orientação do professor Doutor Augusto Oliveira da Silva Gomes

Dissertação apresentada para obtenção do grau de Doutor em Engenharia Electrotécnica e de Computadores, na Faculdade de Engenharia da Universidade do Porto

Dissertação apresentada para obtenção do grau de Doutor em Engenharia Electrotécnica e de Computadores, na Faculdade de Engenharia da Universidade do Porto, sob a orientação do Prof. Dr. José Manuel Martins Ferreira

Esta dissertação apresenta duas implementações de algoritmos para gerência dinâmica de memória em software, as quais foram desenvolvidas utilizando como alvo uma plataforma embarcada Java. Uma vez que a plataforma utilizada pertence a uma metodologia para geração semi-automática de hardware e software para sistemas embarcados, os dois algoritmos implementados foram projetados para serem integrados ao contexto desta mesma metodologia. Como forma de estabelecer comparações detalhadas entre as duas implementações desenvolvidas, foram realizadas diversas estimativas em desempenho, uso de memória, potência e energia para cada implementação, utilizando para isto duas versões existentes da plataforma adotada. Através da análise dos resultados obtidos, observou-se que um dos algoritmos desenvolvidos obteve um desempenho melhor para realização da gerência dinâmica da memória. Em contrapartida, o outro algoritmo possui características de projeto que possibilitam sua utilização com aplicações de tempo-real. De um modo geral, os custos adicionais resultantes da utilização do algoritmo de tempo-real, em relação ao outro algoritmo também implementado, são de aproximadamente 2% para a potência média dissipada, 16% para o número de ciclos executados, 18% para a energia consumida e 10% sobre a quantidade de total memória utilizada. Isto mostra que o custo extra necessário para utilização do algoritmo de tempo real é razoavelmente baixo se comparado aos benefícios proporcionados pela sua utilização. Como impactos finais produzidos por este trabalho, obteve-se um acréscimo de 35% sobre o número total de instruções suportadas pela arquitetura utilizada. Adicionalmente, 12% das instruções que já existiam no conjunto desta arquitetura foram modificadas para se adaptarem aos novos mecanismos implementados. Com isto, o conjunto atual da arquitetura passa a corresponder a 44% do total de instruções existentes na arquitetura da máquina virtual Java. Por último, além das estimativas desenvolvidas, foram também realizadas algumas sugestões para melhoria global dos algoritmos implementados. Em síntese, alguns pontos cobertos por estas sugestões incluem: a migração de elementos do processamento do escopo dinâmico para o estático, o desenvolvimento de mecanismos escaláveis para compactação de memória em tempo-real, a integração de escalonadores ao processo de gerência de memória e a extensão do processo de geração semi-automática de software e hardware para sistemas embarcados.

Objetivando implementar um sistema embarcado baseado principalmente em software, duas abordagens ortogonais estão sendo propostas: Desenvolvimento Baseado em Plataformas, que maximiza o reuso; Desenvolvimento Baseado em Modelos, que aumenta o nível de abstração utilizando conceitos de orientação a objetos e UML para modelar uma aplicação. Porém, com o aumento do nível de abstração, engenheiros de software não possuem a idéia exata do impacto de suas decisões de modelagem em questões importantes, como desempenho, e consumo de energia e de memória para uma plataforma embarcada específica. Neste trabalho, propõe-se estimar a memória de dados e de programa, o desempenho e o consumo de energia, diretamente de especificações em UML, como intuito de realizar a exploração do espaço de projeto já nos estágios iniciais do processo de desenvolvimento. Resultados experimentais apresentam erros reduzidos, quando componentes da plataforma são reutilizados e seus custos já são conhecidos para uma plataforma alvo. Aplicações reais foram modeladas de diferentes formas e demonstram a eficiência da abordagem de estimativa para o estagio inicial de exploração do espaço de projeto, permitindo ao desenvolvedor avaliar e comparar diferentes soluções de modelagem. Os valores estimados utilizados na exploração do espaço de projeto podem alcançar taxas de erros inferiores a 5%. / In order to quickly implement an embedded system that is mainly based on software, two orthogonal approaches have been proposed: Platform-based Design, which maximizes the reuse of components; and Model Driven Development, which rises the abstraction level by using object-oriented concepts and UML for modeling an application. However, with this increasing of the abstraction level, software engineers do not have an exact idea of the impact of their modeling decisions on important issues such as performance, energy, and memory footprint for a given embedded platform. This work proposes to estimate data and program memory, performance, and energy directly from UML model specifications to explore the design space in the early steps of development process. Experimental results show a very small estimation error when platform components are reused and their costs on the target platform are already known. Real-life applications are modeled in different ways and demonstrate the effectiveness of the estimates in an early design space exploration, allowing the designer to evaluate and compare different modeling solutions. The estimated values used in the design space exploration can achieve errors as low as 5%.

O trabalho apresenta os recursos oferecidos ao usuario do ambiente de projeto AMPLO para o controle e gerencia do processo de simulação de sistemas digitais. O ambiente de simulação proposto a constituído por diversas ferramentas baseadas em recursos gráficos- interativos. As ferramentas do ambiente permitem executar funções como : construir modelos de simulação a partir das descrições de sistemas armazenadas na base de dados, gerar estados iniciais para os modelos de simulação através de estratégias de inicialização pré-definidas, criar estímulos a serem aplicados aos modelos de simulação utilizando linguagens gráficas e textuais dedicadas, vincular estímulos as entradas primarias dos modelos de simulação, controlar a simulação através dos comandos de simulação disponíveis na sessão de simulação, analisar os resultados das simulações já, realizadas através de recursos gráficos de visualização e criar uma sequência de comandos que devem ser executados dentro de uma sessão de simulação. O ambiente de simulação integra todos os dados gerados durante o processo de simulação em uma base de dados única. Para isto, os objetos manipulados pelas diversas ferramentas do ambiente e as relações existentes entre eles foram definidos de acordo com um modelo de dados uniforme que e a base para a implementação de uma base de dados íntegra e não redundante. A interface de acesso a esta base de dados a constituída por funções primitivas que realizam o acesso a cada um dos objetos. Estas primitivas de acesso a base de dados permitem a criação, alteração e remoção dos objetos mantendo a consistência geral dos mesmos, bem como vários tipos de consultas. O processo de simulação propriamente dito a controlado por um conjunto de funções próprias para a simulação disponíveis na sessão de simulação. A sessão de simulação apresenta uma linguagem de comandos que através de recursos de visualização gráfico-interativos permite ao usuário, entre outros recursos, alterar e monitorar valores de sinais do modelo de simulação e controlar o avanço do tempo de simulação. A sessão de simulação realiza a comunicação com os simuladores através de um sistema de troca de mensagens onde para cada comando fornecido durante a sessão de simulação, uma mensagem é acrescentada ao conjunto de mensagens enviadas ao simulador. / This work describes the facilities that are available to the user of the AMPLO design environment for controlling and managing the process of digital systems simulation. The proposed simulation environment is composed by several tools that are of graphical-interactive nature. These tools support tasks like: building simulation models from system descriptions stored in the data base, generating initial states for the models according to various initialization strategies, creating stimuli to be applied to the models by using dedicated graphical and textual languages, associating stimuli to the primary inputs of the models, controlling the simulation run through a specialized command language, and analyzing results of already executed simulation runs. The environment integrates all data that is generated during the simulation process in a unique data base. Therefore, objects that are manipulated by the several tools of the environment, as well as relationships between them, have been defined according to a uniform data model which is the basis for the implementation of a consistent and non-redundant data base. The access interface to this data base is composed by primitive functions that implement the access to the objects. These functions allow the creation, modification, and removal of objects, while maintaining their overall consistency, as well as several queries. The process of simulation itself is controlled by a command language. These commands are available during the simulation session, which integrates the environment with the AMPLO simulators through a message system. The command language, through graphical-interactive visualization facilities, allow the user to modify and monitor signals values of the model and to control the simulation time advancement. Each command issue adds a new message to a message queue to be sent to the simulator.

Este trabalho visa propor uma metodologia de análise da variabilidade do tempo de atraso de propagação no FPGA. Para alcançar esse objetivo são utilizados três circuitos diferentes: o circuito 1 mede a diferença de atrasos de dois circuitos, o circuito 2 identifica o atraso menor de dois circuitos e, por fim, o terceiro circuito que consiste do oscilador em anel. Cada circuito foi avaliado individualmente numa estrutura BIST, implementada nos FPGA XC3S200-FT256 e EP2C35F672C6. Os métodos utilizados para análise dos dados foram a média móvel, o plano de mínimos quadrados e o teste t-student. A metodologia permitiu mostrar a variabilidade within-die e suas componentes sistêmica e randômica. / This work aims to propose a methodology of analysis of variability of propagation-delay time in FPGA. To achieve this goal three different circuits are implemented: the circuit 1 measures the delay difference of two logic paths, the circuit 2 identifies smallest delay of two logic paths, and finally the third circuit consists of a ring oscillator. Each circuit has been assessed individually in a BIST structure, implemented in FPGAs XC3S200-FT256 and EP2C35F672C6. The methods used for data analysis were the moving average, least-squares plane and the t-student test. The methodology has allowed to evaluate the within-die variability and its systemic and random components.

A codificação de vídeo digital depende de uma série de etapas para ser alcançada a compressão de dados necessária para, então, o vídeo ser enviado ou armazenado em um meio. Existe uma série de padrões que se propõe a isso e dentre eles, o que apresenta o melhor desempenho em termos de compressão de dados e qualidade de vídeo até o presente momento é o H.264/AVC. Considerando então o padrão H.264/AVC, uma das etapas do seu processamento é a codificação de entropia, sendo que um dos algoritmos usados para esse fim é o CAVLC (Context-Based Adaptive Variable Length Coding). Esta técnica faz uso de uma série de características onde o código gerado pela seqüência de vídeo processada tende a assumir, para, então, gerar códigos menores para padrões do vídeo que tendem a aparecer mais freqüentemente em detrimento a padrões que são mais raros, fazendo para isso uso de código de comprimento variável que depende do contexto atual em que cada porção do código está sendo processada. Baseado nisso, este trabalho apresenta uma arquitetura para o algoritmo CAVLC segundo o padrão H.264/AVC, onde foi inserida uma nova técnica para diminuir o gargalo na etapa inicial do algoritmo, além de usar técnicas já conhecidas na literatura para diminuir os ciclos necessários para o processamento do componente, fazendo com que a arquitetura aqui apresentada tenha um ganho em relação aos demais trabalhos da literatura encontrados e comparados. Esse trabalho está inserido no esforço do grupo de TV Digital da UFRGS e pretende-se que, no futuro, esse módulo seja integrado aos demais módulos desenvolvidos no grupo para formar um codificador H.264/AVC completo. / The digital video encoding depends on different phases to reach the necessary data compression, so the video can be transmitted through or stored in the medium. There are a variety of compression standards that are designed to that purpose and, among them, the one that has the best performance currently is the H.264/AVC. Considering the H.264/AVC standard, one of the processing stages is the entropy encoding. CAVLC (Context-Based Adaptive Variable Length Coding) is one of the algorithms that can be used for that end. It can use many of the code particularities, generated by the video sequence being processed. This way, CAVLC can generate codes with less bits for portions of the video sequence that occur more often, and codes with more bits for rarer patterns of the video sequence, using variable code lengths that depend on the current context for each portion of the code being processed. Based on this, the present work presents a VLSI hardware architecture for the CAVLC algorithm, according to the H.264/AVC standard. The architecture introduces a new technique to decrease the bottleneck at the initial stage of the algorithm and, furthermore, well-known techniques already tested in works found in the literature, were also implemented, to save processing cycles at the other stages of the component. The present architecture is then able to achieve gains compared to the other works found in the literature. This work is inserted into the effort of the Digital TV Group at UFRGS and it is intended to be integrated with the others developed by the group to make a complete H.264/AVC encoder.