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.

A complexidade no projeto de sistemas eletrônicos tem aumentado devido à evolução tecnológica e permite a concepção de sistemas inteiros em um único chip (SoCs – do inglês, Systems-on-Chip). Com o objetivo de reduzir a alta complexidade de projeto, custos de projeto e o tempo de lançamento do produto no mercado, os sistemas são desenvolvidos em módulos funcionais, pré-verificados e pré-projetados, denominados de núcleos de propriedade intelectual (IP – do inglês, Intellectual Property). Esses núcleos IP podem ser reutilizados de outros projetos ou adquiridos de terceiros. Entretanto, é necessário prover uma estrutura de comunicação para interligar esses núcleos e as estruturas atuais (barramentos) são inadequadas para atender as necessidades dos futuros SoCs (compartilhamento de banda, falta de escalabilidade). As redes-em-chip (NoCs{ XE "NoCs" } – do inglês, Networks-on-Chip) vêm sendo apresentadas como uma solução para atender essas restrições. No desenvolvimento de sistemas embarcados baseados em redes-em-chip, deve-se personalizar a rede para atendimento de restrições. Essa exploração de espaço de projeto (EEP), segundo uma infinidade de trabalhos, é realizada em tempo de projeto, supondo-se que é conhecido o perfil das aplicações que devem ser executadas pelo sistema. No entanto, cada vez mais sistemas embarcados aproximam-se de dispositivos genéricos de processamento (como palmtops), onde as tarefas a serem executadas não são inteiramente conhecidas a priori. Com a mudança dinâmica da carga de trabalho de um sistema embarcado, a busca pelo atendimento de requisitos pode então ser enfrentada por mecanismos adaptativos, que implementam dinamicamente a EEP. No âmbito deste trabalho, a EEP em tempo de execução provê mecanismos adaptativos que deverão realizar suas funções para atendimento de restrições de projeto. Consequentemente, EEP em tempo de execução pode permitir resultados ainda melhores, no que diz respeito a sistemas embarcados com restrições de projetos rígidas. É possível maximizar o tempo de duração da energia da bateria que alimenta um sistema embarcado ou, até mesmo, diminuir a taxa de perda de deadlines em um sistema de tempo real soft, realocando em tempo de execução tarefas de modo a gerar menor taxa de comunicação entre os processadores, desde que o sistema seja executado em um tempo suficiente para amortizar os custos de migração. Neste trabalho, foi utilizada a combinação de heurísticas de alocação da área dos Sistemas Computacionais Distribuídos como, por exemplo, algoritmos bin-packing e linear clustering. Resultados mostraram que a realocação de tarefas, utilizando uma combinação Worst-Fit e Linear Clustering, reduziu o consumo de energia e a taxa de perda de deadlines em 17% e 37%, respectivamente, utilizando o modelo de migração por cópia. / The complexity of electronic systems design has been increasing due to the technological evolution, which now allows the inclusion of a complete system on a single chip (SoC – System-on-Chip). In order to cope with the corresponding design complexity and reduce design costs and time-to-market, systems are built by assembling pre-designed and pre-verificated functional modules, called IP (Intellectual Property) cores. IP cores can be reused from previous designs or acquired from third-party vendors. However, an adequate communication architecture is required to interconnect these IP cores. Current communication architectures (busses) are unsuitable for the communication requirements of future SoCs (sharing of bandwidth, lack of scalability). Networks-on-Chip (NoC) arise as one of the solutions to fulfill these requirements. While developing NoC-based embedded systems, the NoC customization is mandatory to fulfill design constraints. This design space exploration (DSE), according to most approaches in the literature, is achieved at compile-time (off-line DSE), assuming the profiles of the tasks that will be executed in the embedded system are known a priori. However, nowadays, embedded systems are becoming more and more similar to generic processing devices (such as palmtops), where the tasks to be executed are not completely known a priori. Due to the dynamic modification of the workload of the embedded system, the fulfillment of requirements can be accomplished by using adaptive mechanisms that implement dynamically the DSE (run-time DSE or on-line DSE). In the scope of this work, DSE is on-line. In other words, when the system is running, adaptive mechanisms will be executed to fulfill the requirements of the system. Consequently, on-line DSE can achieve better results than off-line DSE alone, especially considering embedded systems with tight constraints. It is thus possible to maximize the lifetime of the battery that feeds an embedded system, or even to decrease the deadline miss ratio in a soft real-time system, for example by relocating tasks dynamically in order to generate less communication among the processors, provided that the system runs for enough execution time in order to amortize the migration overhead.In this work, a combination of allocation heuristics from the domain of Distributed Computing Systems is applied, for instance bin-packing and linear clustering algorithms. Results shows that applying task reallocation using the Worst-Fit and Linear Clustering combination reduces the energy consumption and deadline miss ratio by 17% and 37%, respectively, using the copy task migration model.

Em relação a sistemas multiprocessados integrados em uma única pastilha (MPSoC), tanto a alocação dinâmica quanto a migração de tarefas são áreas de pesquisa recentes e abertas. Este artigo propõe uma organização de memória híbrida para sistemas com comunicação baseados em redes-em-chip, como maneira de minimizar a energia gasta durante a transferência de código decorrente de uma alocação ou migração de tarefa. É também introduzido um novo mecanismo de migração de tarefas, que, por sua vez, pode utilizar check-pointing ou outra técnica mais transparente. O aumento do uso de sistemas multiprocessados na computação embarcada torna importante a avaliação de diferentes organizações de memória. Enquanto memórias distribuídas proporcionam acessos mais rápidos, memórias compartilhadas tornam possível o compartilhamento de dados sem a interferência dos processadores. Nos experimentos realizados, foi focada a redução da energia gasta na comunicação em um contexto onde uma migração de tarefas ou uma alocação dinâmica fosse necessária. Os resultados indicam que, considerando a migração do código, a solução proposta apresenta melhor eficiência do que soluções unicamente distribuídas ou compartilhadas. Foi também verificado que, em alguns casos, a estratégia híbrida reduz os tempos de migração. Na solução apresentada, o código pode ser transferido do nó onde a tarefa era originalmente executada ou de uma memória posicionada no centro da rede. A escolha entre as duas opções é feita em tempo de execução de uma maneira intuitiva, sendo a escolha baseada na distância entre os nós envolvidos na transferência. Os resultados indicam que a organização proposta reduz a energia de transferência de código em 24% e 10% em média, se comparada, respectivamente, a soluções utilizando somente memória global ou distribuída. O modelo de migração de tarefas proposto é baseado na linguagem Java e na comunicação por troca de mensagens. Todo seu desenvolvimento se deu em software, não requerendo nenhuma modificação no sistema. O custo energético da migração foi então avaliado. Entende-se por custo energético a energia gasta nos processadores para envio e recebimento das mensagens e na estrutura de comunicação, uma rede-em-chip. Trabalhos já existentes não consideram o custo de migração, comparando apenas o arranjo inicial e final das tarefas no sistema. Este trabalho, entretanto, avalia todo o processo de migração. Através de experimentos, é estimado o tempo mínimo de execução da plataforma, como função do tamanho da tarefa e da distância entre os nós da rede, necessário para amortizar a energia gasta no processo de migração, considerando que os processadores utilizam a técnica de DVS para reduzir o consumo de acordo com suas cargas de processamento. / Regarding embedded Multi-processor Systems-on-Chip (MPSoCs), dynamic task allocation and task migration are still open research areas. This work proposes a hybrid memory organization for NoC-based systems as the way to minimize the energy spent during the code transfer when task migration or dynamic task allocation needs to be performed. It is also introduced a new flexible task migration mechanism, which can use check-pointing or a more transparent technique. The increasing use of multi-processor architectures in embedded computing makes it important to evaluate different options for memory organization. While distributed memory allows faster accesses, a global memory makes possible the sharing of data without processor interference. In the experiments, it is targeted the communication energy reduction in a context where task migration or dynamic task allocation is required. Results indicate that the proposed hybrid memory organization presents better efficiency than distributed- or global-only organizations regarding code migration. It is also noticed that, in some cases, the hybrid strategy reduces the task migration times. In the hybrid approach, the code can be transferred from the node where the task was originally running or from a memory positioned at the center of the system. The choice between the two options is done at runtime in a very intuitive way, based on the distance between the nodes involved on the transfer. Results are very encouraging and indicate that the proposed hybrid organization reduces the code transfer energy by 24% and 10% on average, as compared to global- and distributed-only memory organizations, respectively. The proposed migration model is based on the Java language and on message passing communication method. It is mainly software-based, and does not require any system modification. The energy cost of the migration process is then evaluated, i.e., the energy spent on the sending and receiving cores and on the communication structure, a wormhole-based Network-on-Chip (NoC). Previous works have compared system figures before and after task migration, while this study evaluates the whole migration process. Finally, it is derived the minimum execution time of the embedded system, as a function of the task size and of the distance between the cores on the NoC, that is required to amortize the energy spent on the migration process, considering that processors use Dynamic Voltage Scaling to reduce power consumption according to their current workloads.

A demanda por sistemas com elevado desempenho tem trazido a necessidade de aumentar o número de elementos de processamento, surgindo os chamados Sistemas em Chip Multiprocessados (MPSoCs). Além disso, com a possibilidade de redução da escala tecnológica na era submicrônica, permitindo a integração de vários dispositivos, os chips têm se tornado ainda mais complexos. No entanto, com o aumento no número de elementos de processamento, as interconexões são vistas com o principal gargalo dos sistemas-em-chip. Com isso, uma preocupação na forma como tais elementos se comunicam e estão interconectados tem sido levantada, uma vez que tais características são cruciais nos aspectos de desempenho, energia e potência, principalmente em sistemas embarcados. Essa necessidade permitiu o advento das redes-em-chip (Networks-on-Chip – NoCs) e inúmeros estudos já foram realizados para tais dispositivos. No entanto, devido ao aceleramento tecnológico atual, que traz a necessidade por sistemas ainda mais complexos, que consumam baixa energia e que permitam que as aplicações sejam constantemente atualizadas sem perder as características de desempenho, as arquiteturas de interconexão tradicionais não serão suficientes para satisfazer tais desafios. Outras alternativas de interconexão para MPSoCs precisam ser investigadas e nesse trabalho novas arquiteturas para NoCs com tais requisitos são apresentadas. As soluções propostas exploram hierarquia, adaptabilidade e interconexões em três dimensões. Esse trabalho aborda a necessidade do uso de diferentes estratégias em NoCs a fim de atingir os requisitos de desempenho e baixo consumo de potência dos atuais e futuros MPSoCs. Dessa forma, serão verificadas as diversas arquiteturas de interconexões para sistemas heterogêneos, sua escalabilidade, suas principais características e as vantagens das propostas apresentadas sobre as demais soluções. / The demand for systems with high performance has brought the need to increase the number of cores, emerging the called Multi-Processors System-on-Chip (MPSoCs). Also, with the shrinking feature size in deep-submicron era, allowing the integration of several devices, chips have become even more complex. However, with the increase in these elements, interconnections are seen as the main bottleneck in many core systemson- chip. With this, a concern about how these devices communicate and are interconnected has been raised, since these features are crucial for the performance, energy and power consumption aspects, mainly in embedded systems. This need allows the advent of the Networks-on-Chip (NoCs) and countless studies had already been done to analyze such interconnection devices. However, due to the current technological accelerating that brings the need for even more complex systems, consuming lower energy and providing constant application updates without losing performance features, traditional interconnect architectures will not be sufficient to satisfy such challenges. Other interconnecting alternatives for MPSoCs need to be investigated and in this work, novel architectures for NoCs meeting such requirements are presented. The proposed solutions explore hierarchy, adaptability and three dimensional interconnections. This work approaches the requirements in the use of different strategies for NoCs in order to reach the performance requisites and low power consumption of the current and future MPSoCs. Hence, in this approach, several interconnection architectures for heterogeneous systems, their scalability and the main features and advantages of the proposed strategies in comparison with others will be verified.

Redes Neurais têm sido um tema de pesquisas por pelo menos sessenta anos. Desde a eficácia no processamento de informações à incrível capacidade de tolerar falhas, são incontáveis os mecanismos no cérebro que nos fascinam. Assim, não é nenhuma surpresa que, na medida que tecnologias facilitadoras tornam-se disponíveis, cientistas e engenheiros têm aumentado os esforços para o compreender e simular. Em uma abordagem semelhante à do Projeto Genoma Humano, a busca por tecnologias inovadoras na área deu origem a projetos internacionais que custam bilhões de dólares, o que alguns denominam o despertar global de pesquisa da neurociência. Avanços em hardware fizeram a simulação de milhões ou até bilhões de neurônios possível. No entanto, as abordagens existentes ainda não são capazes de fornecer a densidade de conexões necessária ao enorme número de neurônios e sinapses. Neste sentido, este trabalho propõe DHyANA (Arquitetura Digital Neuromórfica Hierárquica), uma nova arquitetura em hardware para redes neurais pulsadas, a qual utiliza comunicação em rede-em-chip hierárquica. A arquitetura é otimizada para implementações de Máquinas de Estado Líquido. A arquitetura DHyANA foi exaustivamente testada em plataformas de simulação, bem como implementada em uma FPGA Stratix IV da Altera. Além disso, foi realizada a síntese lógica em tecnologia 65nm, a fim de melhor avaliar e comparar o sistema resultante com projetos similares, alcançando uma área de 0,23mm2 e potência de 147mW para uma implementação de 256 neurônios. / Neural Networks has been a subject of research for at least sixty years. From the effectiveness in processing information to the amazing ability of tolerating faults, there are countless processing mechanisms in the brain that fascinates us. Thereupon, it comes with no surprise that as enabling technologies have become available, scientists and engineers have raised the efforts to understand, simulate and mimic parts of it. In a similar approach to that of the Human Genome Project, the quest for innovative technologies within the field has given birth to billion dollar projects and global efforts, what some call a global blossom of neuroscience research. Advances in hardware have made the simulation of millions or even billions of neurons possible. However, existing approaches cannot yet provide the even more dense interconnect for the massive number of neurons and synapses required. In this regard, this work proposes DHyANA (Digital HierArchical Neuromorphic Architecture), a new hardware architecture for a spiking neural network using hierarchical network-on-chip communication. The architecture is optimized for Liquid State Machine (LSM) implementations. DHyANA was exhaustively tested in simulation platforms, as well as implemented in an Altera Stratix IV FPGA. Furthermore, a logic synthesis analysis using 65-nm CMOS technology was performed in order to evaluate and better compare the resulting system with similar designs, achieving an area of 0.23mm2 and a power dissipation of 147mW for a 256 neurons implementation.

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.

A complexidade no projeto de sistemas eletrônicos tem aumentado devido à evolução tecnológica e permite a concepção de sistemas inteiros em um único chip (SoCs – do inglês, Systems-on-Chip). Com o objetivo de reduzir a alta complexidade de projeto, custos de projeto e o tempo de lançamento do produto no mercado, os sistemas são desenvolvidos em módulos funcionais, pré-verificados e pré-projetados, denominados de núcleos de propriedade intelectual (IP – do inglês, Intellectual Property). Esses núcleos IP podem ser reutilizados de outros projetos ou adquiridos de terceiros. Entretanto, é necessário prover uma estrutura de comunicação para interligar esses núcleos e as estruturas atuais (barramentos) são inadequadas para atender as necessidades dos futuros SoCs (compartilhamento de banda, falta de escalabilidade). As redes-em-chip (NoCs{ XE "NoCs" } – do inglês, Networks-on-Chip) vêm sendo apresentadas como uma solução para atender essas restrições. No desenvolvimento de sistemas embarcados baseados em redes-em-chip, deve-se personalizar a rede para atendimento de restrições. Essa exploração de espaço de projeto (EEP), segundo uma infinidade de trabalhos, é realizada em tempo de projeto, supondo-se que é conhecido o perfil das aplicações que devem ser executadas pelo sistema. No entanto, cada vez mais sistemas embarcados aproximam-se de dispositivos genéricos de processamento (como palmtops), onde as tarefas a serem executadas não são inteiramente conhecidas a priori. Com a mudança dinâmica da carga de trabalho de um sistema embarcado, a busca pelo atendimento de requisitos pode então ser enfrentada por mecanismos adaptativos, que implementam dinamicamente a EEP. No âmbito deste trabalho, a EEP em tempo de execução provê mecanismos adaptativos que deverão realizar suas funções para atendimento de restrições de projeto. Consequentemente, EEP em tempo de execução pode permitir resultados ainda melhores, no que diz respeito a sistemas embarcados com restrições de projetos rígidas. É possível maximizar o tempo de duração da energia da bateria que alimenta um sistema embarcado ou, até mesmo, diminuir a taxa de perda de deadlines em um sistema de tempo real soft, realocando em tempo de execução tarefas de modo a gerar menor taxa de comunicação entre os processadores, desde que o sistema seja executado em um tempo suficiente para amortizar os custos de migração. Neste trabalho, foi utilizada a combinação de heurísticas de alocação da área dos Sistemas Computacionais Distribuídos como, por exemplo, algoritmos bin-packing e linear clustering. Resultados mostraram que a realocação de tarefas, utilizando uma combinação Worst-Fit e Linear Clustering, reduziu o consumo de energia e a taxa de perda de deadlines em 17% e 37%, respectivamente, utilizando o modelo de migração por cópia. / The complexity of electronic systems design has been increasing due to the technological evolution, which now allows the inclusion of a complete system on a single chip (SoC – System-on-Chip). In order to cope with the corresponding design complexity and reduce design costs and time-to-market, systems are built by assembling pre-designed and pre-verificated functional modules, called IP (Intellectual Property) cores. IP cores can be reused from previous designs or acquired from third-party vendors. However, an adequate communication architecture is required to interconnect these IP cores. Current communication architectures (busses) are unsuitable for the communication requirements of future SoCs (sharing of bandwidth, lack of scalability). Networks-on-Chip (NoC) arise as one of the solutions to fulfill these requirements. While developing NoC-based embedded systems, the NoC customization is mandatory to fulfill design constraints. This design space exploration (DSE), according to most approaches in the literature, is achieved at compile-time (off-line DSE), assuming the profiles of the tasks that will be executed in the embedded system are known a priori. However, nowadays, embedded systems are becoming more and more similar to generic processing devices (such as palmtops), where the tasks to be executed are not completely known a priori. Due to the dynamic modification of the workload of the embedded system, the fulfillment of requirements can be accomplished by using adaptive mechanisms that implement dynamically the DSE (run-time DSE or on-line DSE). In the scope of this work, DSE is on-line. In other words, when the system is running, adaptive mechanisms will be executed to fulfill the requirements of the system. Consequently, on-line DSE can achieve better results than off-line DSE alone, especially considering embedded systems with tight constraints. It is thus possible to maximize the lifetime of the battery that feeds an embedded system, or even to decrease the deadline miss ratio in a soft real-time system, for example by relocating tasks dynamically in order to generate less communication among the processors, provided that the system runs for enough execution time in order to amortize the migration overhead.In this work, a combination of allocation heuristics from the domain of Distributed Computing Systems is applied, for instance bin-packing and linear clustering algorithms. Results shows that applying task reallocation using the Worst-Fit and Linear Clustering combination reduces the energy consumption and deadline miss ratio by 17% and 37%, respectively, using the copy task migration model.

Em relação a sistemas multiprocessados integrados em uma única pastilha (MPSoC), tanto a alocação dinâmica quanto a migração de tarefas são áreas de pesquisa recentes e abertas. Este artigo propõe uma organização de memória híbrida para sistemas com comunicação baseados em redes-em-chip, como maneira de minimizar a energia gasta durante a transferência de código decorrente de uma alocação ou migração de tarefa. É também introduzido um novo mecanismo de migração de tarefas, que, por sua vez, pode utilizar check-pointing ou outra técnica mais transparente. O aumento do uso de sistemas multiprocessados na computação embarcada torna importante a avaliação de diferentes organizações de memória. Enquanto memórias distribuídas proporcionam acessos mais rápidos, memórias compartilhadas tornam possível o compartilhamento de dados sem a interferência dos processadores. Nos experimentos realizados, foi focada a redução da energia gasta na comunicação em um contexto onde uma migração de tarefas ou uma alocação dinâmica fosse necessária. Os resultados indicam que, considerando a migração do código, a solução proposta apresenta melhor eficiência do que soluções unicamente distribuídas ou compartilhadas. Foi também verificado que, em alguns casos, a estratégia híbrida reduz os tempos de migração. Na solução apresentada, o código pode ser transferido do nó onde a tarefa era originalmente executada ou de uma memória posicionada no centro da rede. A escolha entre as duas opções é feita em tempo de execução de uma maneira intuitiva, sendo a escolha baseada na distância entre os nós envolvidos na transferência. Os resultados indicam que a organização proposta reduz a energia de transferência de código em 24% e 10% em média, se comparada, respectivamente, a soluções utilizando somente memória global ou distribuída. O modelo de migração de tarefas proposto é baseado na linguagem Java e na comunicação por troca de mensagens. Todo seu desenvolvimento se deu em software, não requerendo nenhuma modificação no sistema. O custo energético da migração foi então avaliado. Entende-se por custo energético a energia gasta nos processadores para envio e recebimento das mensagens e na estrutura de comunicação, uma rede-em-chip. Trabalhos já existentes não consideram o custo de migração, comparando apenas o arranjo inicial e final das tarefas no sistema. Este trabalho, entretanto, avalia todo o processo de migração. Através de experimentos, é estimado o tempo mínimo de execução da plataforma, como função do tamanho da tarefa e da distância entre os nós da rede, necessário para amortizar a energia gasta no processo de migração, considerando que os processadores utilizam a técnica de DVS para reduzir o consumo de acordo com suas cargas de processamento. / Regarding embedded Multi-processor Systems-on-Chip (MPSoCs), dynamic task allocation and task migration are still open research areas. This work proposes a hybrid memory organization for NoC-based systems as the way to minimize the energy spent during the code transfer when task migration or dynamic task allocation needs to be performed. It is also introduced a new flexible task migration mechanism, which can use check-pointing or a more transparent technique. The increasing use of multi-processor architectures in embedded computing makes it important to evaluate different options for memory organization. While distributed memory allows faster accesses, a global memory makes possible the sharing of data without processor interference. In the experiments, it is targeted the communication energy reduction in a context where task migration or dynamic task allocation is required. Results indicate that the proposed hybrid memory organization presents better efficiency than distributed- or global-only organizations regarding code migration. It is also noticed that, in some cases, the hybrid strategy reduces the task migration times. In the hybrid approach, the code can be transferred from the node where the task was originally running or from a memory positioned at the center of the system. The choice between the two options is done at runtime in a very intuitive way, based on the distance between the nodes involved on the transfer. Results are very encouraging and indicate that the proposed hybrid organization reduces the code transfer energy by 24% and 10% on average, as compared to global- and distributed-only memory organizations, respectively. The proposed migration model is based on the Java language and on message passing communication method. It is mainly software-based, and does not require any system modification. The energy cost of the migration process is then evaluated, i.e., the energy spent on the sending and receiving cores and on the communication structure, a wormhole-based Network-on-Chip (NoC). Previous works have compared system figures before and after task migration, while this study evaluates the whole migration process. Finally, it is derived the minimum execution time of the embedded system, as a function of the task size and of the distance between the cores on the NoC, that is required to amortize the energy spent on the migration process, considering that processors use Dynamic Voltage Scaling to reduce power consumption according to their current workloads.

A Memória Transacional (TM) surgiu nos últimos anos como uma nova solução para sincronização em sistemas multiprocessados de memória compartilhada, permitindo explorar melhor o paralelismo das aplicações ao evitar limitações inerentes ao mecanismo de locks. Neste modelo, o programador define regiões de código que devem executar de forma atômica. O sistema tenta executá-las de forma concorrente, e, em caso de conflito nos acessos à memória, toma as medidas necessárias para preservar a atomicidade e isolamento das transações, na maioria das vezes abortando e reexecutando uma das transações. Um dos modelos mais aceitos de memória transacional em hardware é o LogTM, implementado neste trabalho em um MPSoC embarcado que utiliza uma NoC para interconexão. Os experimentos fazem uma comparação desta implementação com locks, levando-se em consideração performance e energia do sistema. Além disso, este trabalho mostra que o tempo que uma transação espera para reiniciar sua execução após ter abortado (chamado de backoff delay on abort) tem impactos significativos na performance e energia. Uma análise deste impacto é feita utilizando-se de três políticas de backoff. Um mecanismo baseado em um handshake entre transações, chamado Abort handshake, é proposto como solução para o problema. Os resultados dos experimentos são dependentes da aplicação e configuração do sistema e indicam ganhos da TM na maioria dos casos em relação ao mecanismo de locks. Houve redução de até 30% no tempo de execução e de até 32% na energia de aplicações de baixa demanda de sincronização. Em um segundo momento, é feita uma análise do backoff delay on abort na performance e energia de aplicações utilizando três políticas de backoff em comparação com o mecanismo Abort handshake. Os resultados mostram que o mecanismo proposto apresenta redução de até 20% no tempo de execução e de até 53% na energia comparado à melhor política de backoff dentre as analisadas. Para aplicações com alta demanda de sincronização, a TM mostra redução no tempo de execução de até 63% e redução de energia de até 71% em comparação com o mecanismo de locks. / Transactional Memory (TM) has emerged in the last years as a new solution for synchronization on shared memory multiprocessor systems, allowing a better exploration of the parallelism of the applications by avoiding inherent limitations of the lock mechanism. In this model, the programmer defines regions of code, called transactions, to execute atomically. The system tries to execute transactions concurrently, but in case of conflict on memory accesses, it takes the appropriate measures to preserve the atomicity and isolation, usually aborting and re-executing one of the transactions. One of the most accepted hardware transactional memory model is LogTM, implemented in this work in an embedded MPSoC that uses an NoC as interconnection mechanism. The experiments compare this implementation with locks, considering performance and energy. Furthermore, this work shows that the time a transaction waits to restart after abort (called backoff delay on abort) has significant impact on performance and energy. An analysis of this impact is done using three backoff policies. A novel mechanism based on handshake of transactions, called Abort handshake, is proposed as a solution to this issue. The results of the experiments depends on application and system configuration and show TM benefits in most cases in comparison to the locks mechanism, reaching reduction on the execution time up to 30% and reduction on the energy consumption up to 32% on low contention workloads. After that, an analysis of the backoff delay on abort on the performance and energy is presented, comparing to the Abort handshake mechanism. The proposed mechanism shows reduction of up to 20% on the execution time and up to 53% on the energy, when compared to the best backoff policy. For applications with a high degree of synchronization, TM shows reduction on the execution time up to 63% and energy savings up to 71% compared to locks.

Ao longo dos últimos anos, os sistemas embarcados vêm se tornando cada vez mais complexos tanto em termos de hardware quanto de software. Ultimamente têm-se adotado como solução o uso de MPSoCs (sistemas multiprocessados integrados em chip) para uma maior eficiência energética e computacional nestes sistemas. Com o uso de diversos elementos de processamento, redes-em-chip (NoC - networks-on-chip) aparecem como soluções de melhor desempenho do que barramentos. Nestes ambientes cujo desempenho depende da eficiência do modelo de comunicação, a hierarquia de memória se torna um elemento chave. Baseando-se neste cenário, este trabalho realiza uma investigação sobre o impacto da hierarquia de memória em MPSoCs baseados em NoC. Dentro deste escopo foi desenvolvida uma nova organização de memória fisicamente centralizada com diferentes espaços de endereçamentos denominada nDMA. Este trabalho também apresenta uma comparação entre a nova organização e outras três organizações bastante difundidas tais como memória distribuída, memória compartilhada e memória compartilhada distribuída. Estas duas ultimas adotam um modelo de coerência de cache baseado em diretório completamente desenvolvido em hardware. Os modelos de memória foram implementados na plataforma virtual SIMPLE (SIMPLE Multiprocessor Platform Environment). Resultados experimentais mostram uma forte dependência com relação à carga de comunicação gerada pelas aplicações. O modelo de memória distribuída apresenta melhores resultados conforme a carga de comunicação das aplicações é baixa. Por outro lado, o novo modelo de memória fisicamente compartilhado com diferentes espaços de endereçamento apresenta melhores resultados conforme a carga de comunicação das aplicações é alta. Também foram realizados experimentos objetivando analisar o desempenho dos modelos de memória em situações de alta latência de comunicação na rede. Resultados mostram melhores resultados do modelo de memória distribuída quando a carga de comunicação das aplicações é alta e, caso contrário, o modelo nDMA apresenta melhores resultados. Por fim, foram analisados os desempenhos dos modelos de memória durante o processo de migração de tarefas. Neste caso, os modelos de memória compartilhada e compartilhada distribuída apresentaram melhores resultados devido ao fato de que não se faz necessária o envio dos dados da aplicação nestes modelos e também devido ao menor tamanho de código se comparado com os outros modelos. / In the past few the years, embedded systems have become even more complex both on terms of hardware and software. Lately, the use of MPSoCs (Multi-Processor Systems-on-Chip) has been adopted on these systems for a better energetic and computational efficiency. Due to the use of several processing elements, Networks-on-Chip arise as better performance solutions than buses. Considering this scenario, this work performs an investigation on the impact of memory hierarchy in NoC-based MPSoCs. In this context, a new physically centralized and shared memory organization with different address spaces named nDMA was developed. This work also presents a comparison between the new memory organization and three different well-known memory hierarchy models such as distributed memory and shared and distributed shared memories that make use of a fully hardware cache coherence solution. The memory models were implemented in the SIMPLE (SIMPLE Multiprocessor Platform Environment) virtual platform. Experimental results shows a strong dependency on the application communication workload. The distributed memory model presents better results as the application communication workload is low. On the other hand, the new memory model (physically shared with different address spaces) presents better results as the application communication workload is high. There were also experiments aiming at observing the performance of the memory models in situations where the communication latency on the network is high. Results show better results of the distributed memory model when the application communication workload is high, and the nDMA model presents better results otherwise. Finally, the performance of the memory models during a task migration process were evaluated. In this case, the shared memory and distributed shared memory models presented better results due to the fact that in this case the data memory does not need to be transferred from one point to another and also due to the low size of the memory code in these cases if compared to other memory models.