No / The traffic pattern has significant impact on the performance of network-on-chip. Many recent studies have shown that multimedia applications can be supported in on-chip interconnects. Driven by the motivation of evaluating on-chip interconnects in multimedia embedded systems, a new analytical model is proposed to investigate the performance of the fat-tree based on-chip interconnection network under bursty multimedia traffic and nonuniform message destinations. Extensive simulation experiments are conducted to validate the accuracy of the model, which is then adopted as a cost-efficient tool to investigate the effects of bursty multimedia traffic with nonuniform destinations on the network performance.

Sistemas Dinamicamente Reconfiguráveis (SDRs) tem sido aceitos como alternativa importante para diminuir os custos de circuitos digitais. Porém, eles adicionam novas dimensões no projeto de Sistemas sobre Silício (System-On-Chip, SoC). Apesar de novas metodologias terem sido propostas por fabricantes de FPGA para lidar com a complexidade deste tipo de circuitos, as soluções ainda são muito específicas. Considerando-se que o uso de recursos de comunicação robustos em SoCs complexos atuais é generalizado, os meios de comunicação estruturados, como rede Intrachips (Network-On-Chip, NoCs), foram incluídas em sistemas dinamicamente reconfiguráveis, gerando-se arquiteturas de SDRs baseadas em NoCs, ou de SDR-NoCs. Arquiteturas de SDR-NoCs podem ser simples ou complexas. As arquiteturas de SDR-NoCs simples são aquelas com topogias regulares e diretas e Módulos Processantes (MPs) homogêneos. As arquiteturas de SDR-NoCs complexas são aquelas com topologias irregulares e indiretas com MPs heterogêneos. O mapeamento é a fase no fluxo de projeto do SoC que visa encontrar a melhor localização das unidades de processamento da aplicação junto à topologia da NoC, de tal forma que as métricas de interesse podem ser otimizadas. O problema do posicionamento lida com a alocação otimizada de recursos (cores) dentro do dispositivo reconfigurável. No mapeamento de SDR-NoCs, a capacidade de reconfiguração no tempo acrescenta uma nova dimensão ao problema de mapeamento, uma vez que diferentes cores são atribuídos ao mesmo roteador, mas estão presentes no dispositivo em momentos distintos. Para arquiteturas de SDR-NoCs complexas, o problema de mapeamento está fortemente associado ao problema do posicionamento e convém tratá-los em conjunto. Até o presente momento, o problema de mapeamento e posicionamento para SDR-NoCs não tem sido tratados adequadamente. Neste trabalho são apresentadas soluções para o mapeamento e/ou posicionamento de MPs para arquiteturas SDR-NoCs tanto simples quanto complexas. Primeiramente, uma estratégia de mapeamento é proposta para arquiteturas simples, de uma forma que torna possível a utilização de estratégias de mapeamento clássicas anteriores (sem reconfiguração) para SDRs. Os resultados mostram a redução de até 38%, no atraso médio da NoC e de até 41% de economia de energia comparando a melhor solução com a média de soluções aleatórias. Em uma segunda fase, o problema de mapeamento e posicionamento são tratados em conjunto para arquiteturas SDR-NoCs complexas: uma formalização do problema é proposta e um algoritmo exato, semi-exaustivo, é implementado e utilizado para a a sua análise. Devido à alta complexidade do problema, um segundo algoritmo genético (Genetic Algorithm, GA) foi implementado para que casos maiores possam ser resolvidos. Vários tipos de crossover e metodologias de GAs são comparadas para se obter a melhor solução. Os resultados mostram que a melhor solução GA obteve, em média, custos de comunicação com 4% de penalidade quando comparada com a melhor solução, sendo que o algoritmo apresenta bons tempos de execução. / Dynamic Reconfigurable Systems (DRSs) have been accepted as an important alternative for lowering costs of digital circuits. However, they add new dimensions to the system-on-chip (SoC) design space. Although new methodologies have been proposed by Field Programmable Gate Arrays (FPGAs) manufacturers to deal with the increased design complexity in this class of circuits, solutions to the algorithmic and block level design are still very ad-hoc. Considering the generalized use of robust communication resources in current complex SoCs, structured communication means, as network-on-chips (NoCs), have been included in dynamic reconfigurable systems generating DRSs based on NoCs, or DRS-NoCs, under different architectures. DRS-NoC architectures can be simple or complex. Simple DRS-NoCs architectures refer to regular and direct NoC topologies, with homogeneous Processing Modules (PMs). Complex DRS-NoCs architectures refer to irregular and undirected NoC topologies, with heterogeneous MPs. Mapping is the step in the SoC design flow which aims to find the best topological location for the application processing units onto the NoC topology, such that the metrics of interest can be greatly optimized. The placement problem deals with the optimized allocation of resources (cores) inside the reconfigurable device. In DRS-NoCs mapping, the on-going reconfiguration capability adds a new dimension to the mapping problem, since different cores are assigned to the same router, but being present in the in the logic fabric in separate moments. Furthermore, in complex DRS-NoC architectures the mapping problem is strongly associated with the placement one, and they should be dealt concurrently. To the date, the mapping and placement problems have not been properly addressed for those kind of architectures. In this work solutions are presented for hardware core placement and/or mapping for both simple and complex DRS-NoC architectures. Firstly, a mapping strategy is proposed for simple architectures, in a way that makes it possible to use previous classic mapping strategies (without reconfiguration) for DRSs. Results show reductions up to 38% on the average NoC delay and up to 41% of energy saving when comparing the best solution with average random solutions. In the second phase, the mapping and placement problems are dealt concurrently for DRS-NoC complex architectures: the problem formalization is proposed and for its analysis, an exact, and semi-exaustive, algorithm is implemented and applied. Due to the high complexity associated to the problem, an Genetic Algorithm (GA) was implemented to deal with larger cases. Several GAs crossovers and methodologies are compared for obtaining the best solution. Results show that best GA solution obtained, in average, communication costs with 4% of penalty when compared with best solution. In addition, the algorithm presents low execution times.

Submitted by Caroline Xavier (caroline.xavier@pucrs.br) on 2017-06-30T13:50:31Z No. of bitstreams: 1 DIS_RAMON_COSTI_FERNANDES_COMPLETO.pdf: 4552821 bytes, checksum: 31f78eb686d2c3126cf0abf4584de386 (MD5) / Made available in DSpace on 2017-06-30T13:50:31Z (GMT). No. of bitstreams: 1 DIS_RAMON_COSTI_FERNANDES_COMPLETO.pdf: 4552821 bytes, checksum: 31f78eb686d2c3126cf0abf4584de386 (MD5) Previous issue date: 2017-03-13 / A pr?xima gera??o de sistemas multiprocessados intra-chip, do ingl?s MultiProcessor Systems-on-Chip (MPSoC), comportar? centenas de elementos de processamento num ?nico chip, com a promessa de alta vaz?o de comunica??o, baixa lat?ncia e, preferencialmente, baixo consumo de energia. Devido ? elevada demanda de comunica??o paralela de aplica??es para MPSoCs, a rede intra-chip, do ingl?s Network-on-Chip (NoC), tem sido amplamente adotada como um meio de comunica??o confi?vel e escal?vel para MPSoCs. O espa?o de projeto para NoCs deve ser explorado para atender ? demanda das aplica??es atuais. Dentre os par?metros que definem uma NoC, o algoritmo de roteamento tem sido utilizado para prover servi?os como toler?ncia ? falhas, liberdade de deadlocks e de livelocks, assim como Quality of Service (QoS). Conforme a ado??o e complexidade de Systems-on-Chip (SoC) aumenta para sistemas embarcados, a preocupa??o com a prote??o de dados tamb?m torna-se um requisito para o projeto de MPSoCs. Atualmente, MPSoCs podem ser atacados explorando vulnerabilidades em hardware ou software, sendo o ?ltimo respons?vel por 80% dos incidentes de seguran?a em sistemas embarcados. A prote??o contra vulnerabilidades de software pode acontecer em: (i) N?vel de Aplica??o, utilizando t?cnicas como a criptografia, para evitar a transmiss?o de dados desprotegidos entre os elementos de um MPSoC, conhecidos como m?dulos de propriedade intelectual, do ingl?s Intellectual Property (IP); ou (ii) N?vel de Comunica??o, inspecionando ou filtrando elementos na arquitetura de interconex?o atrav?s de monitores de comunica??o ou firewalls, respectivamente. Portanto, um algoritmo de roteamento, ciente dos requisitos de seguran?a do sistema, deve oferecer prote??o ao utilizar rotas confi?veis na NoC, evitando elementos potencialmente maliciosos em rotas porventura inseguras. A principal contribui??o deste trabalho ? uma t?cnica de prote??o para NoCs que atua em n?vel de comunica??o, adaptando os algoritmos Segment-based Routing (SBR) e Region-based Routing (RBR) para que estes considerem aspectos de seguran?a do sistema, estes caracterizados por zonas de seguran?a definidas na NoC de acordo com o mapeamento de aplica??es nos IPs. A avalia??o da t?cnica de roteamento considera aspectos como a escalabilidade das tabelas de roteamento, a quantidade de rotas seguras definidas entre os IPs, e o impacto desta t?cnica de roteamento em aplica??es do benchmark NASA Numerical Aerodynamic Simulation (NAS) Parallel Bencharm (NPB). / The next generation of MultiProcessor Systems-on-Chip (MPSoC) will encompass hundreds of integrated processing elements into a single chip, with the promise of highthroughput, low latency and, preferably, low energy utilization. Due to the high communication parallelism required by several applications targeting MPSoC architectures, the Network-on-Chip (NoC) has been widely adopted as a reliable and scalable interconnection mechanism. The NoC design space should be explored to meet the demanding requirements of current applications. Among the parameters that define a NoC configuration, the routing algorithm has been employed to provide services such as fault tolerance, deadlock and livelock freedom, as well as Quality of Service (QoS). As the adoption and complexity of System-on-Chip (SoC) increases for embedded systems, the concern for data protection appears as a new design requirement. Currently, MPSoCs can be attacked by exploiting either hardware or software vulnerabilities, with the later responsible for 80% of the security incidents in embedded systems. Protection against software vulnerabilities can occur at (i) Application Level, by using techniques such as data encryption to avoid plain data transmissions between Intellectual Property (IP) modules; or (ii) Communication Level, inspecting or filtering elements at the interconnect fabric with communication monitors or firewalls, respectively. As such, a routing algorithm aware of security requirements could also offer protection utilizing trusted communication paths in the NoC, avoiding potential malicious elements in otherwise unsafe communication paths. The main contribution of this work is a NoC protection technique at communication level by adapting Segment-based Routing (SBR) and Region-based Routing (RBR) algorithms to consider system security requirements, characterized by security zones which are defined on the NoC according to the mapping of applications on IP modules. Evaluation of the proposed routing technique considers aspects such as the scalability of routing tables, the number of secure communication paths, and the impact of this technique on applications of the NASA Numerical Aerodynamic Simulation (NAS) Parallel Benchmark (NPB).

Embedded systems have become indispensable in our life: household appliances, cars, airplanes, power plant control systems, medical equipment, telecommunication systems, space technology, they all contain digital computing systems with dedicated functionality. Most of them, if not all, are real-time systems, i.e. their responses to stimuli have timeliness constraints. The timeliness requirement has to be met despite some unpredictable, stochastic behaviour of the system. In this thesis, we address two causes of such stochastic behaviour: the application and platform-dependent stochastic task execution times, and the platform-dependent occurrence of transient faults on network links in networks-on-chip. We present three approaches to the analysis of the deadline miss ratio of applications with stochastic task execution times. Each of the three approaches fits best to a different context. The first approach is an exact one and is efficiently applicable to monoprocessor systems. The second approach is an approximate one, which allows for designer-controlled trade-off between analysis accuracy and analysis speed. It is efficiently applicable to multiprocessor systems. The third approach is less accurate but sufficiently fast in order to be placed inside optimisation loops. Based on the last approach, we propose a heuristic for task mapping and priority assignment for deadline miss ratio minimisation. Our contribution is manifold in the area of buffer and time constrained communication along unreliable on-chip links. First, we introduce the concept of communication supports, an intelligent combination between spatially and temporally redundant communication. We provide a method for constructing a sufficiently varied pool of alternative communication supports for each message. Second, we propose a heuristic for exploring the space of communication support candidates such that the task response times are minimised. The resulting time slack can be exploited by means of voltage and/or frequency scaling for communication energy reduction. Third, we introduce an algorithm for the worst-case analysis of the buffer space demand of applications implemented on networks-on-chip. Last, we propose an algorithm for communication mapping and packet timing for buffer space demand minimisation. All our contributions are supported by sets of experimental results obtained from both synthetic and real-world applications of industrial size.

Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2017-04-10T21:22:16Z No. of bitstreams: 1 AlexandroLD_DISSERT.pdf: 4478017 bytes, checksum: b25b015c0ae937a3ba2f2718697a3977 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-13T14:42:00Z (GMT) No. of bitstreams: 1 AlexandroLD_DISSERT.pdf: 4478017 bytes, checksum: b25b015c0ae937a3ba2f2718697a3977 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-13T15:00:20Z (GMT) No. of bitstreams: 1 AlexandroLD_DISSERT.pdf: 4478017 bytes, checksum: b25b015c0ae937a3ba2f2718697a3977 (MD5) / Made available in DSpace on 2017-04-13T15:07:49Z (GMT). No. of bitstreams: 1 AlexandroLD_DISSERT.pdf: 4478017 bytes, checksum: b25b015c0ae937a3ba2f2718697a3977 (MD5) Previous issue date: 2016-07-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Over the years, with the as technology advances, the search for improvements in the performance of computer systems is notable. The computer systems have evolved in both processing capacity and complexity of the implemented architectures. In such systems it is crucial to use memories since they are responsible for storing data to be processed. Considering an ideal environment, the memories should have a unlimited storage capacity, instant data access and the extremely low cost per bit. But in real systems the memories do not exhibit these characteristics. Storage capacity, speed and cost per bit are factors that increase in proportion to each other. One technique that is used to balance these factors and improve the performance of computer systems is the memory hierarchy. In the scenario of new technologies and proposals for new organizations of processors, a model that has been adopted by designers of computer systems is the use of MPSoCs (multiprocessor systems on chip), which has a higher energy and computational e ciency. In this scenario with many processing elements, networks using on-chip (NoC - networks-on-chip) is more e cient use of the buses. An NoC consists of a set of routers and interconnected channels forming a switched network. The cores are connected to network terminals and communication occurs through the exchange of packets. These NoCs have traditionally been exclusively designed for communication SoCs. However, a project of an unconventional architecture decided to integrate processing and communication in an NoC. This architecture is known for IPNoSys. The IPNoSys (Integrated Processing NoC System) architecture is an unconventional processor that uses networks on chip and implements processing units and routing to handle and process instructions. It takes advantage of the characteristics of NoC, such as scalability and parallel communication, for implement e ectively runs programs that exploit parallelism-level threads. Currently, IPNoSys architecture has four memory physically distributed at the corners of the network, but represent a unified addressing. Each memory module is associated with an access unit in charge of managing it. Given the current organization of IPNoSys memories, this work proposes to develop a new memory hierarchy system for IPNoSys and investigate the possible impact on performance and the programming model / Aolongo dos anos,coma ascensão das tecnologias, a busca por melhorias no desempenho dos sistemas computacionais é algo notável. Os sistemas computacionais evoluíram tanto em capacidade de processamento como em complexidade das arquiteturas implementadas. Nesses sistemas é crucial a utilização de memórias uma vez que elas são responsáveis pelo armazenamento de dados que serão processados. Considerando um ambiente ideal, as memórias deveriam ter uma capacidade de armazenamento ilimitado, o acesso de dados imediato e o custo por bit extremamente baixo. Porém nos sistemas reais as memórias não apresentam essas características. Capacidade de armazenamento, velocidade e custo por bit são fatores que crescem proporcionalmente entre si. Uma técnica que é utilizada para balancear esses fatores e melhorar o desempenho dos sistemas computacionais é a hierarquia de memória. No cenário de novas tecnologias e propostas de novas organizações de processadores, um modelo que vem sendo adotada pelos projetistas de sistemas computacionais é o uso de MPSoCs (sistemas multiprocessados integrados em chip), que apresenta uma maior eficiência energética e computacional. Nesse cenário com muitos elementos de processamento, a utilização de redes em chip (NoC - networks-on-chip) se mostra mais eficiente que o uso de barramentos. Uma NoC consiste em um conjunto de roteadores e canais interligados formando uma rede chaveada. Os núcleos são conectados aos terminais da rede e a comunicação ocorre pela troca de pacotes. Essas NoCs foram tradicionalmente projetadas exclusivamente para a comunicação em SoCs. Entretanto, um projeto de uma arquitetura não convencional resolveu integrar processamento e comunicação em uma NoC. Essa arquitetura é conhecida por IPNoSys. A arquitetura IPNoSys (Integrated Processing NoC System) é um processador não convencional que utiliza redes em chip e implementa unidades de processamento e roteamento para tratar e processar instruções. Aproveita as características das NoCs, como escalabilidade e comunicação paralela, para implementar de maneira eficiente execuções de programas que exploram paralelismo em nível de threads. Atualmente, a arquitetura IPNoSys possui quatro memórias fisicamente distribuidas nos cantos da rede, mas que representam um endereçamento unificado. Cada módulo de memória é associado a uma unidade de acesso que se encarregam de gerenciá-la. Diante da atual organização de memórias da IPNoSys, esse trabalho desenvolveu um novo sistema de hierarquia de memórias para o IPNoSys e investigou os possíveis impactos sobre o desempenho e o modelo de programação / 2017-04-10

Com o avanço da tecnologia de fabricação de chips o atraso em fios globais será maior que o atraso em portas lógicas. Além disso, fios globais longos são mais suscetíveis a problemas de integridade como crosstalk. Uma proposta recente de interconnecção global chamada redes intra-chip reduz essas limitações referentes a fios longos. Além dessas vantagens, redes intra-chip permitem desacoplar comunicação e computação, dividindo um sistema em sub tarefas independentes. Devido as essas vantagens é possível integrar mais lógica em um chip que usa redes intra-chip. Entretanto, o acréscimo de lógica no chip aumenta o custo de teste. Os módulos do chip precisam de mecanismos para transportar dados de teste, que são tipicamente barramentos usados exclusivamente para teste. Entretanto, como mencionado anteriormente, fios globais são caros e acrescentar barramentos de teste pode não ser possível em um futuro próximo. Por outro lado, uma rede intra-chip tem acesso a maioria dos módulos do chip. Esta rede pode ser usada para transportar dados de teste, evitando o acréscimo de barramentos dedicados ao teste. O objetivo dessa tese é estudar o uso de redes intra-chip para o transporte de dados de teste, enfatizando uma abordagem genérica que possa ser aplicada a uma dada rede. Para tanto, essa tese foi divida em três partes: modelos, projeto, e otimização. A tese propõe um modelo funcional de rede que é compatível com a maioria das recém propostas redes intra-chip. O modelo de teste, baseado no modelo funcional da rede, compreende o conjunto de informações necessárias para otimizar a arquitetura de teste. A arquitetura de teste, por sua vez, consiste de lógica para teste e algoritmo de otimização. A lógica de teste compreende lógica para ATE interface e lógica envoltória para módulos de hardware. Os algoritmos otimizam o tempo de teste e a área de lógica de teste no nível dos módulos e no nível do chip. Uma arquitetura convencional de teste de SoCs baseada em barramento de teste dedicado foi comparada com a arquitetura proposta para SoCs baseados em redes intra-chip. Os resultados apontam que o tempo de teste do SoC com a arquitetura proposta aumenta em média 5%. Os resultados também mostram que a lógica de teste da arquitetura proposta é cerca de 20% maior que na arquitetura de teste convencional. Por outro lado, o fluxo de projeto baseado na arquitetura de teste proposta é mais simples que a convencional. Além disso, a arquitetura proposta reduz o nÚmero de fios globais em torno de 20% a 50% para SoCs complexos. Estes resultados demonstram que a arquitetura proposta é melhor para sistemas complexos com um grande nÚmero de módulos. / With the advance of microchip technology, global and long wires will cost more in terms of delay than in terms of logic gates. ln addition, long wires are more susceptible to signal integrity problems such as crosstalk. A recently proposed global interconnect called network-on-chip alleviates the limitation of long wires. Moreover, on-chip networks allow decoupling communication and computation to divide a complete system into manageable and independent sub tasks. Thus, it is possible to integrate more logic into the chip using network-on-chip. However, the complexity growth of cores also increases the test costs since more logic is embedded into a single chip. These embedded cores need a test access mechanism for test data transportation, typically implemented as test-dedicated buses. As mentioned before, global wires are expensive, then, adding test buses may not be feasible in the near future. On the other hand, the on-chip network has access to most cores of the chip. This network could be used also for test data transportation, avoiding additional test-dedicated buses. The goal of this thesis is to study the reuse of on-chip networks for test data transportation, looking for a general reuse approach that can be easily used in a given network. To reach this goal, the thesis is divided in three parts: models, design, and optimization. This thesis proposes a functional model of a network, compatible with most recently proposed best-effort on-chip networks. Based on this functional model, a test model is devised. The test model comprises of a set of necessary and sufficient information required to optimize the test architecture. The test architecture consists of DfT logic and scheduling algorithm. The design of DfT logic comprises adaptation logic for the external tester and test wrappers for the modules. The optimization procedure, focused on mesh-based best-effort NoCs, schedules test data such that the chip test length and DfT silicon are a are minimized. A conventional SoC test architecture based on test-dedicated buses is compared to the proposed approach for best-effort NoCs. The experimental results show that SoC test length has increased 5% on average. The results have also shown that the are a overhead for proposed DfT is around +20% compared to the silicon area to implement the DfT of a convehtional test architecture. On the other hand, we have also presented a simpler design fiow and 20% to 50% of global wiring savings due to the use of NoC for test data transportation. The results corroborate with the conclusion that the proposed NoC reuse is a good approach for complex systems based on a large number of cores and routers.

Com o avanço da tecnologia de fabricação de chips o atraso em fios globais será maior que o atraso em portas lógicas. Além disso, fios globais longos são mais suscetíveis a problemas de integridade como crosstalk. Uma proposta recente de interconnecção global chamada redes intra-chip reduz essas limitações referentes a fios longos. Além dessas vantagens, redes intra-chip permitem desacoplar comunicação e computação, dividindo um sistema em sub tarefas independentes. Devido as essas vantagens é possível integrar mais lógica em um chip que usa redes intra-chip. Entretanto, o acréscimo de lógica no chip aumenta o custo de teste. Os módulos do chip precisam de mecanismos para transportar dados de teste, que são tipicamente barramentos usados exclusivamente para teste. Entretanto, como mencionado anteriormente, fios globais são caros e acrescentar barramentos de teste pode não ser possível em um futuro próximo. Por outro lado, uma rede intra-chip tem acesso a maioria dos módulos do chip. Esta rede pode ser usada para transportar dados de teste, evitando o acréscimo de barramentos dedicados ao teste. O objetivo dessa tese é estudar o uso de redes intra-chip para o transporte de dados de teste, enfatizando uma abordagem genérica que possa ser aplicada a uma dada rede. Para tanto, essa tese foi divida em três partes: modelos, projeto, e otimização. A tese propõe um modelo funcional de rede que é compatível com a maioria das recém propostas redes intra-chip. O modelo de teste, baseado no modelo funcional da rede, compreende o conjunto de informações necessárias para otimizar a arquitetura de teste. A arquitetura de teste, por sua vez, consiste de lógica para teste e algoritmo de otimização. A lógica de teste compreende lógica para ATE interface e lógica envoltória para módulos de hardware. Os algoritmos otimizam o tempo de teste e a área de lógica de teste no nível dos módulos e no nível do chip. Uma arquitetura convencional de teste de SoCs baseada em barramento de teste dedicado foi comparada com a arquitetura proposta para SoCs baseados em redes intra-chip. Os resultados apontam que o tempo de teste do SoC com a arquitetura proposta aumenta em média 5%. Os resultados também mostram que a lógica de teste da arquitetura proposta é cerca de 20% maior que na arquitetura de teste convencional. Por outro lado, o fluxo de projeto baseado na arquitetura de teste proposta é mais simples que a convencional. Além disso, a arquitetura proposta reduz o nÚmero de fios globais em torno de 20% a 50% para SoCs complexos. Estes resultados demonstram que a arquitetura proposta é melhor para sistemas complexos com um grande nÚmero de módulos. / With the advance of microchip technology, global and long wires will cost more in terms of delay than in terms of logic gates. ln addition, long wires are more susceptible to signal integrity problems such as crosstalk. A recently proposed global interconnect called network-on-chip alleviates the limitation of long wires. Moreover, on-chip networks allow decoupling communication and computation to divide a complete system into manageable and independent sub tasks. Thus, it is possible to integrate more logic into the chip using network-on-chip. However, the complexity growth of cores also increases the test costs since more logic is embedded into a single chip. These embedded cores need a test access mechanism for test data transportation, typically implemented as test-dedicated buses. As mentioned before, global wires are expensive, then, adding test buses may not be feasible in the near future. On the other hand, the on-chip network has access to most cores of the chip. This network could be used also for test data transportation, avoiding additional test-dedicated buses. The goal of this thesis is to study the reuse of on-chip networks for test data transportation, looking for a general reuse approach that can be easily used in a given network. To reach this goal, the thesis is divided in three parts: models, design, and optimization. This thesis proposes a functional model of a network, compatible with most recently proposed best-effort on-chip networks. Based on this functional model, a test model is devised. The test model comprises of a set of necessary and sufficient information required to optimize the test architecture. The test architecture consists of DfT logic and scheduling algorithm. The design of DfT logic comprises adaptation logic for the external tester and test wrappers for the modules. The optimization procedure, focused on mesh-based best-effort NoCs, schedules test data such that the chip test length and DfT silicon are a are minimized. A conventional SoC test architecture based on test-dedicated buses is compared to the proposed approach for best-effort NoCs. The experimental results show that SoC test length has increased 5% on average. The results have also shown that the are a overhead for proposed DfT is around +20% compared to the silicon area to implement the DfT of a convehtional test architecture. On the other hand, we have also presented a simpler design fiow and 20% to 50% of global wiring savings due to the use of NoC for test data transportation. The results corroborate with the conclusion that the proposed NoC reuse is a good approach for complex systems based on a large number of cores and routers.

Sistemas Dinamicamente Reconfiguráveis (SDRs) tem sido aceitos como alternativa importante para diminuir os custos de circuitos digitais. Porém, eles adicionam novas dimensões no projeto de Sistemas sobre Silício (System-On-Chip, SoC). Apesar de novas metodologias terem sido propostas por fabricantes de FPGA para lidar com a complexidade deste tipo de circuitos, as soluções ainda são muito específicas. Considerando-se que o uso de recursos de comunicação robustos em SoCs complexos atuais é generalizado, os meios de comunicação estruturados, como rede Intrachips (Network-On-Chip, NoCs), foram incluídas em sistemas dinamicamente reconfiguráveis, gerando-se arquiteturas de SDRs baseadas em NoCs, ou de SDR-NoCs. Arquiteturas de SDR-NoCs podem ser simples ou complexas. As arquiteturas de SDR-NoCs simples são aquelas com topogias regulares e diretas e Módulos Processantes (MPs) homogêneos. As arquiteturas de SDR-NoCs complexas são aquelas com topologias irregulares e indiretas com MPs heterogêneos. O mapeamento é a fase no fluxo de projeto do SoC que visa encontrar a melhor localização das unidades de processamento da aplicação junto à topologia da NoC, de tal forma que as métricas de interesse podem ser otimizadas. O problema do posicionamento lida com a alocação otimizada de recursos (cores) dentro do dispositivo reconfigurável. No mapeamento de SDR-NoCs, a capacidade de reconfiguração no tempo acrescenta uma nova dimensão ao problema de mapeamento, uma vez que diferentes cores são atribuídos ao mesmo roteador, mas estão presentes no dispositivo em momentos distintos. Para arquiteturas de SDR-NoCs complexas, o problema de mapeamento está fortemente associado ao problema do posicionamento e convém tratá-los em conjunto. Até o presente momento, o problema de mapeamento e posicionamento para SDR-NoCs não tem sido tratados adequadamente. Neste trabalho são apresentadas soluções para o mapeamento e/ou posicionamento de MPs para arquiteturas SDR-NoCs tanto simples quanto complexas. Primeiramente, uma estratégia de mapeamento é proposta para arquiteturas simples, de uma forma que torna possível a utilização de estratégias de mapeamento clássicas anteriores (sem reconfiguração) para SDRs. Os resultados mostram a redução de até 38%, no atraso médio da NoC e de até 41% de economia de energia comparando a melhor solução com a média de soluções aleatórias. Em uma segunda fase, o problema de mapeamento e posicionamento são tratados em conjunto para arquiteturas SDR-NoCs complexas: uma formalização do problema é proposta e um algoritmo exato, semi-exaustivo, é implementado e utilizado para a a sua análise. Devido à alta complexidade do problema, um segundo algoritmo genético (Genetic Algorithm, GA) foi implementado para que casos maiores possam ser resolvidos. Vários tipos de crossover e metodologias de GAs são comparadas para se obter a melhor solução. Os resultados mostram que a melhor solução GA obteve, em média, custos de comunicação com 4% de penalidade quando comparada com a melhor solução, sendo que o algoritmo apresenta bons tempos de execução. / Dynamic Reconfigurable Systems (DRSs) have been accepted as an important alternative for lowering costs of digital circuits. However, they add new dimensions to the system-on-chip (SoC) design space. Although new methodologies have been proposed by Field Programmable Gate Arrays (FPGAs) manufacturers to deal with the increased design complexity in this class of circuits, solutions to the algorithmic and block level design are still very ad-hoc. Considering the generalized use of robust communication resources in current complex SoCs, structured communication means, as network-on-chips (NoCs), have been included in dynamic reconfigurable systems generating DRSs based on NoCs, or DRS-NoCs, under different architectures. DRS-NoC architectures can be simple or complex. Simple DRS-NoCs architectures refer to regular and direct NoC topologies, with homogeneous Processing Modules (PMs). Complex DRS-NoCs architectures refer to irregular and undirected NoC topologies, with heterogeneous MPs. Mapping is the step in the SoC design flow which aims to find the best topological location for the application processing units onto the NoC topology, such that the metrics of interest can be greatly optimized. The placement problem deals with the optimized allocation of resources (cores) inside the reconfigurable device. In DRS-NoCs mapping, the on-going reconfiguration capability adds a new dimension to the mapping problem, since different cores are assigned to the same router, but being present in the in the logic fabric in separate moments. Furthermore, in complex DRS-NoC architectures the mapping problem is strongly associated with the placement one, and they should be dealt concurrently. To the date, the mapping and placement problems have not been properly addressed for those kind of architectures. In this work solutions are presented for hardware core placement and/or mapping for both simple and complex DRS-NoC architectures. Firstly, a mapping strategy is proposed for simple architectures, in a way that makes it possible to use previous classic mapping strategies (without reconfiguration) for DRSs. Results show reductions up to 38% on the average NoC delay and up to 41% of energy saving when comparing the best solution with average random solutions. In the second phase, the mapping and placement problems are dealt concurrently for DRS-NoC complex architectures: the problem formalization is proposed and for its analysis, an exact, and semi-exaustive, algorithm is implemented and applied. Due to the high complexity associated to the problem, an Genetic Algorithm (GA) was implemented to deal with larger cases. Several GAs crossovers and methodologies are compared for obtaining the best solution. Results show that best GA solution obtained, in average, communication costs with 4% of penalty when compared with best solution. In addition, the algorithm presents low execution times.

Com o avanço da tecnologia de fabricação de chips o atraso em fios globais será maior que o atraso em portas lógicas. Além disso, fios globais longos são mais suscetíveis a problemas de integridade como crosstalk. Uma proposta recente de interconnecção global chamada redes intra-chip reduz essas limitações referentes a fios longos. Além dessas vantagens, redes intra-chip permitem desacoplar comunicação e computação, dividindo um sistema em sub tarefas independentes. Devido as essas vantagens é possível integrar mais lógica em um chip que usa redes intra-chip. Entretanto, o acréscimo de lógica no chip aumenta o custo de teste. Os módulos do chip precisam de mecanismos para transportar dados de teste, que são tipicamente barramentos usados exclusivamente para teste. Entretanto, como mencionado anteriormente, fios globais são caros e acrescentar barramentos de teste pode não ser possível em um futuro próximo. Por outro lado, uma rede intra-chip tem acesso a maioria dos módulos do chip. Esta rede pode ser usada para transportar dados de teste, evitando o acréscimo de barramentos dedicados ao teste. O objetivo dessa tese é estudar o uso de redes intra-chip para o transporte de dados de teste, enfatizando uma abordagem genérica que possa ser aplicada a uma dada rede. Para tanto, essa tese foi divida em três partes: modelos, projeto, e otimização. A tese propõe um modelo funcional de rede que é compatível com a maioria das recém propostas redes intra-chip. O modelo de teste, baseado no modelo funcional da rede, compreende o conjunto de informações necessárias para otimizar a arquitetura de teste. A arquitetura de teste, por sua vez, consiste de lógica para teste e algoritmo de otimização. A lógica de teste compreende lógica para ATE interface e lógica envoltória para módulos de hardware. Os algoritmos otimizam o tempo de teste e a área de lógica de teste no nível dos módulos e no nível do chip. Uma arquitetura convencional de teste de SoCs baseada em barramento de teste dedicado foi comparada com a arquitetura proposta para SoCs baseados em redes intra-chip. Os resultados apontam que o tempo de teste do SoC com a arquitetura proposta aumenta em média 5%. Os resultados também mostram que a lógica de teste da arquitetura proposta é cerca de 20% maior que na arquitetura de teste convencional. Por outro lado, o fluxo de projeto baseado na arquitetura de teste proposta é mais simples que a convencional. Além disso, a arquitetura proposta reduz o nÚmero de fios globais em torno de 20% a 50% para SoCs complexos. Estes resultados demonstram que a arquitetura proposta é melhor para sistemas complexos com um grande nÚmero de módulos. / With the advance of microchip technology, global and long wires will cost more in terms of delay than in terms of logic gates. ln addition, long wires are more susceptible to signal integrity problems such as crosstalk. A recently proposed global interconnect called network-on-chip alleviates the limitation of long wires. Moreover, on-chip networks allow decoupling communication and computation to divide a complete system into manageable and independent sub tasks. Thus, it is possible to integrate more logic into the chip using network-on-chip. However, the complexity growth of cores also increases the test costs since more logic is embedded into a single chip. These embedded cores need a test access mechanism for test data transportation, typically implemented as test-dedicated buses. As mentioned before, global wires are expensive, then, adding test buses may not be feasible in the near future. On the other hand, the on-chip network has access to most cores of the chip. This network could be used also for test data transportation, avoiding additional test-dedicated buses. The goal of this thesis is to study the reuse of on-chip networks for test data transportation, looking for a general reuse approach that can be easily used in a given network. To reach this goal, the thesis is divided in three parts: models, design, and optimization. This thesis proposes a functional model of a network, compatible with most recently proposed best-effort on-chip networks. Based on this functional model, a test model is devised. The test model comprises of a set of necessary and sufficient information required to optimize the test architecture. The test architecture consists of DfT logic and scheduling algorithm. The design of DfT logic comprises adaptation logic for the external tester and test wrappers for the modules. The optimization procedure, focused on mesh-based best-effort NoCs, schedules test data such that the chip test length and DfT silicon are a are minimized. A conventional SoC test architecture based on test-dedicated buses is compared to the proposed approach for best-effort NoCs. The experimental results show that SoC test length has increased 5% on average. The results have also shown that the are a overhead for proposed DfT is around +20% compared to the silicon area to implement the DfT of a convehtional test architecture. On the other hand, we have also presented a simpler design fiow and 20% to 50% of global wiring savings due to the use of NoC for test data transportation. The results corroborate with the conclusion that the proposed NoC reuse is a good approach for complex systems based on a large number of cores and routers.

[ES] Los procesadores multinúcleo actuales cuentan con recursos compartidos entre los diferentes núcleos. Dos de estos recursos compartidos, la cache de último nivel y el ancho de banda de memoria principal, pueden convertirse en cuellos de botella para el rendimiento. Además, con el crecimiento del número de núcleos que implementan los diseños más recientes, la red dentro del chip también se convierte en un cuello de botella que puede afectar negativamente al rendimiento, ya que las redes tradicionales pueden encontrar limitaciones a su escalabilidad en el futuro cercano. Prácticamente la totalidad de los diseños actuales implementan jerarquías de memoria que se comunican mediante rápidas redes de interconexión. Esta organización es eficaz dado que permite reducir el número de accesos que se realizan a memoria principal y la latencia media de acceso a memoria. Las caches, la red de interconexión y la memoria principal, conjuntamente con otras técnicas conocidas como la prebúsqueda, permiten reducir las enormes latencias de acceso a memoria principal, limitando así el impacto negativo ocasionado por la diferencia de rendimiento existente entre los núcleos de cómputo y la memoria. Sin embargo, compartir los recursos mencionados es fuente de diferentes problemas y retos, siendo uno de los principales el manejo de la interferencia entre aplicaciones. Hacer un uso eficiente de la jerarquía de memoria y las caches, así como contar con una red de interconexión apropiada, es necesario para sostener el crecimiento del rendimiento en los diseños tanto actuales como futuros. Esta tesis analiza y estudia los principales problemas e inconvenientes observados en estos dos recursos: la cache de último nivel y la red dentro del chip. En primer lugar, se estudia la escalabilidad de las tradicionales redes dentro del chip con topología de malla, así como esta puede verse comprometida en próximos diseños que cuenten con mayor número de núcleos. Los resultados de este estudio muestran que, a mayor número de núcleos, el impacto negativo de la distancia entre núcleos en la latencia puede afectar seriamente al rendimiento del procesador. Como solución a este problema, en esta tesis proponemos una de red de interconexión óptica modelada en un entorno de simulación detallado, que supone una solución viable a los problemas de escalabilidad observados en los diseños tradicionales. A continuación, esta tesis dedica un esfuerzo importante a identificar y proponer soluciones a los principales problemas de diseño de las jerarquías de memoria actuales como son, por ejemplo, el sobredimensionado del espacio de cache privado, la existencia de réplicas de datos y rigidez e incapacidad de adaptación de las estructuras de cache. Aunque bien conocidos, estos problemas y sus efectos adversos en el rendimiento pueden ser evitados en procesadores de alto rendimiento gracias a la enorme capacidad de la cache de último nivel que este tipo de procesadores típicamente implementan. Sin embargo, en procesadores de bajo consumo, no existe la posibilidad de contar con tales capacidades y hacer un uso eficiente del espacio disponible es crítico para mantener el rendimiento. Como solución a estos problemas en procesadores de bajo consumo, proponemos una novedosa organización de jerarquía de dos niveles cache que utiliza una red de interconexión óptica. Los resultados obtenidos muestran que, comparado con diseños convencionales, el consumo de energía estática en la arquitectura propuesta es un 60% menor, pese a que los resultados de rendimiento presentan valores similares. Por último, hemos extendido la arquitectura propuesta para dar soporte tanto a aplicaciones paralelas como secuenciales. Los resultados obtenidos con la esta nueva arquitectura muestran un ahorro de hasta el 78 % de energía estática en la ejecución de aplicaciones paralelas. / [CA] Els processadors multinucli actuals compten amb recursos compartits entre els diferents nuclis. Dos d'aquests recursos compartits, la memòria d’últim nivell i l'ample de banda de memòria principal, poden convertir-se en colls d'ampolla per al rendiment. A mes, amb el creixement del nombre de nuclis que implementen els dissenys mes recents, la xarxa dins del xip també es converteix en un coll d'ampolla que pot afectar negativament el rendiment, ja que les xarxes tradicionals poden trobar limitacions a la seva escalabilitat en el futur proper. Pràcticament la totalitat dels dissenys actuals implementen jerarquies de memòria que es comuniquen mitjançant rapides xarxes d’interconnexió. Aquesta organització es eficaç ates que permet reduir el nombre d'accessos que es realitzen a memòria principal i la latència mitjana d’accés a memòria. Les caches, la xarxa d’interconnexió i la memòria principal, conjuntament amb altres tècniques conegudes com la prebúsqueda, permeten reduir les enormes latències d’accés a memòria principal, limitant així l'impacte negatiu ocasionat per la diferencia de rendiment existent entre els nuclis de còmput i la memòria. No obstant això, compartir els recursos esmentats és font de diversos problemes i reptes, sent un dels principals la gestió de la interferència entre aplicacions. Fer un us eficient de la jerarquia de memòria i les caches, així com comptar amb una xarxa d’interconnexió apropiada, es necessari per sostenir el creixement del rendiment en els dissenys tant actuals com futurs. Aquesta tesi analitza i estudia els principals problemes i inconvenients observats en aquests dos recursos: la memòria cache d’últim nivell i la xarxa dins del xip. En primer lloc, s'estudia l'escalabilitat de les xarxes tradicionals dins del xip amb topologia de malla, així com aquesta es pot veure compromesa en propers dissenys que compten amb major nombre de nuclis. Els resultats d'aquest estudi mostren que, a major nombre de nuclis, l'impacte negatiu de la distància entre nuclis en la latència pot afectar seriosament al rendiment del processador. Com a solució' a aquest problema, en aquesta tesi proposem una xarxa d’interconnexió' òptica modelada en un entorn de simulació detallat, que suposa una solució viable als problemes d'escalabilitat observats en els dissenys tradicionals. A continuació, aquesta tesi dedica un esforç important a identificar i proposar solucions als principals problemes de disseny de les jerarquies de memòria actuals com son, per exemple, el sobredimensionat de l'espai de memòria cache privat, l’existència de repliques de dades i la rigidesa i incapacitat d’adaptació' de les estructures de memòria cache. Encara que ben coneguts, aquests problemes i els seus efectes adversos en el rendiment poden ser evitats en processadors d'alt rendiment gracies a l'enorme capacitat de la memòria cache d’últim nivell que aquest tipus de processadors típicament implementen. No obstant això, en processadors de baix consum, no hi ha la possibilitat de comptar amb aquestes capacitats, i fer un us eficient de l'espai disponible es torna crític per mantenir el rendiment. Com a solució a aquests problemes en processadors de baix consum, proposem una nova organització de jerarquia de dos nivells de memòria cache que utilitza una xarxa d’interconnexió òptica. Els resultats obtinguts mostren que, comparat amb dissenys convencionals, el consum d'energia estàtica en l'arquitectura proposada és un 60% menor, malgrat que els resultats de rendiment presenten valors similars. Per últim, hem estes l'arquitectura proposada per donar suport tant a aplicacions paral·leles com seqüencials. Els resultats obtinguts amb aquesta nova arquitectura mostren un estalvi de fins al 78 % d'energia estàtica en l’execució d'aplicacions paral·leles. / [EN] Current multicores face the challenge of sharing resources among the different processor cores. Two main shared resources act as major performance bottlenecks in current designs: the off-chip main memory bandwidth and the last level cache. Additionally, as the core count grows, the network on-chip is also becoming a potential performance bottleneck, since traditional designs may find scalability issues in the near future. Memory hierarchies communicated through fast interconnects are implemented in almost every current design as they reduce the number of off-chip accesses and the overall latency, respectively. Main memory, caches, and interconnection resources, together with other widely-used techniques like prefetching, help alleviate the huge memory access latencies and limit the impact of the core-memory speed gap. However, sharing these resources brings several concerns, being one of the most challenging the management of the inter-application interference. Since almost every running application needs to access to main memory, all of them are exposed to interference from other co-runners in their way to the memory controller. For this reason, making an efficient use of the available cache space, together with achieving fast and scalable interconnects, is critical to sustain the performance in current and future designs. This dissertation analyzes and addresses the most important shortcomings of two major shared resources: the Last Level Cache (LLC) and the Network on Chip (NoC). First, we study the scalability of both electrical and optical NoCs for future multicoresand many-cores. To perform this study, we model optical interconnects in a cycle-accurate multicore simulation framework. A proper model is required; otherwise, important performance deviations may be observed otherwise in the evaluation results. The study reveals that, as the core count grows, the effect of distance on the end-to-end latency can negatively impact on the processor performance. In contrast, the study also shows that silicon nanophotonics are a viable solution to solve the mentioned latency problems. This dissertation is also motivated by important design concerns related to current memory hierarchies, like the oversizing of private cache space, data replication overheads, and lack of flexibility regarding sharing of cache structures. These issues, which can be overcome in high performance processors by virtue of huge LLCs, can compromise performance in low power processors. To address these issues we propose a more efficient cache hierarchy organization that leverages optical interconnects. The proposed architecture is conceived as an optically interconnected two-level cache hierarchy composed of multiple cache modules that can be dynamically turned on and off independently. Experimental results show that, compared to conventional designs, static energy consumption is improved by up to 60% while achieving similar performance results. Finally, we extend the proposal to support both sequential and parallel applications. This extension is required since the proposal adapts to the dynamic cache space needs of the running applications, and multithreaded applications's behaviors widely differ from those of single threaded programs. In addition, coherence management is also addressed, which is challenging since each cache module can be assigned to any core at a given time in the proposed approach. For parallel applications, the evaluation shows that the proposal achieves up to 78% static energy savings. In summary, this thesis tackles major challenges originated by the sharing of on-chip caches and communication resources in current multicores, and proposes new cache hierarchy organizations leveraging optical interconnects to address them. The proposed organizations reduce both static and dynamic energy consumption compared to conventional approaches while achieving similar performance; which results in better energy efficiency. / Puche Lara, J. (2021). Novel Cache Hierarchies with Photonic Interconnects for Chip Multiprocessors [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/165254 / TESIS