Network-on-Chip (NoC) is emerging as a promising communication structure, which is scalable with respect to chip complexity. Meanwhile, latest chip designs are increasingly leveraging multiple voltage-frequency domains for energy-efficiency improvement. In this work, we propose a simultaneous task and voltage scheduling algorithm for energy minimization in NoC based designs. The energy-latency tradeoff is handled by Lagrangian relaxation. The core algorithm is a clustering based approach which not only assigns voltage levels and starting time to each task (or Processing Element) but also naturally finds voltage-frequency clusters. Compared to a recent previous work, which performs task scheduling and voltage assignment sequentially, our method leads to an average of 20 percent energy reduction.

As modern CMPs scale to ever increasing core counts, Networks-on-Chip (NoCs) are emerging as an interconnection fabric, enabling communication between components. While NoCs are easy to implement and provide high and scalable bandwidth, current routing algorithms, such as dimension-ordered routing, suffer from poor load balance, leading to reduced throughput and high latencies. Improving load balance, hence, is critical in future CMP designs where increased latency leads to wasted power and energy waiting for outstanding requests to resolve. Adaptive routing is a known technique to improve load balance; however, prior adaptive routing techniques either use local, myopic information or misinformed, regionally-aggregated information to form their routing decisions. This thesis proposes a new, light-weight, adaptive routing algorithm for on-chip routers based on global link state and congestion information, Global Congestion Awareness (GCA). GCA leverages unused bits in existing packet header flits to "piggyback" congestion state information around the network and uses a simple, low-complexity route calculation unit, to calculate optimal packet paths to their destination without the myopia of local decisions, nor the aggregation of unrelated status information, found in prior designs. In particular GCA outperforms local adaptive routing by up to 82%, Regional Congestion Awareness (RCA) by up to 51%, and a recent competing adaptive routing algorithm, DAR, by 8% on average on realistic workloads.

O consumo de potência em uma Rede Intra-Chip (em inglês, Network-on-Chip – NoC) cresce linearmente com a quantidade de transições de sinais nos pacotes transmitidos através da infra-estrutura de interconexão. Uma forma de minimizar o consumo de potência em um sistema baseado em NoC é reduzir a atividade de transição de sinais nas portas de entrada dos módulos que constituem a NoC. Esta redução pode ser obtida através da utilização de esquemas de codificação de dados. Vários esquemas de codificação foram propostos no final dos anos 90, porém direcionados a arquiteturas de comunicação baseadas em barramentos. Este trabalho investiga a utilização destes esquemas de codificação em sistemas baseados em Networks-on-Chip. Dentre os esquemas encontrados na literatura, quatro foram implementados e avaliados neste trabalho. Este trabalho também apresenta como contribuição original um novo esquema de codificação de dados adequado a NoCs. A estimativa do consumo de potência da NoC é calculada com base em macromodelos que reproduzem a potência consumida em cada módulo interno da NoC, de acordo com a atividade de transição de sinais no tráfego recebido. Estes macromodelos são aqui caracterizados através da simulação elétrica de cada módulo da NoC e dos esquemas de codificação. Para permitir a análise de consumo com tráfegos de aplicações reais, os macromodelos são inseridos em um modelo de mais alto nível de abstração. Este modelo é empregado para analisar o balanço entre redução de potência obtida com a redução da transição de sinais e o consumo extra do esquema de codificação. A maioria dos esquemas de codificação encontrados na literatura reduz efetivamente a atividade de transição de sinais. Porém, o impacto do consumo extra de potência para codificar e decodificar os dados não é avaliado. A avaliação conduzida neste trabalho considera o consumo da codificação/decodificação em uma NoC real, quantificando a redução de consumo obtido com cada esquema de codificação. Devido ao baixo desempenho dos esquemas de codificação existentes, quando aplicados a NoCs, foi desenvolvido um novo esquema, chamado T-Bus-Invert. Os resultados mostram um desempenho superior do T-Bus-Invert quando comparado aos demais esquemas para flits com largura de 8 e 16 bits, e um desempenho similar ao do Bus-Invert com 4 clusters para flits de 32 bits. / The power consumption in Networks-on-Chip grows linearly with the amount of signal transitions in successive data packets sent through this interconnection infrastructure. One option to decrease the power consumption in NoC-based systems is reducing the switching activity at the input ports of NoC modules. This reduction can be achieved by means of data coding schemes. Several schemes were proposed in the nineties. However, all of them address only bus-based communication architectures. This work investigates the use of such data coding schemes in NoC-based systems. Among the coding schemes found in the literature, four were implemented and evaluated in this work. This work also presents a new data coding scheme, named TBus- Invert, suitable for NoCs. Estimations of the NoC power consumption are computed here based on macromodels which reproduce the power consumption on each internal NoC module, according to the transition activity in the input traffic. Such macromodels are characterized through electrical simulations of each NoC module and coding circuits. To enable the evaluation of real applications traffic, such macromodels are inserted in a higher abstraction level model. This model is employed to analyze the trade-off between the power saving due to coding schemes versus the power consumption overhead due to the encoding and decoding modules. Most of the coding schemes proposed in the literature effectively reduce the switching activity, but the overall impact of the power consumption to encode/decode data in the system is not evaluated. The evaluation conducted in this work considers the power consumption to encode/decode data in a real NoC, quantifying the power savings for each coding scheme. Due to the insufficient performances of the existing schemes when applied to NoCs, a coding scheme, T-Bus-Invert, was developed. Results showed superior performance of the T-Bus-Invert compared to all evaluated coding schemes for 8 and 16-bit flits, and similar performance to the 4-cluster Bus-Invert for 32-bit flits.

O consumo de potência em uma Rede Intra-Chip (em inglês, Network-on-Chip – NoC) cresce linearmente com a quantidade de transições de sinais nos pacotes transmitidos através da infra-estrutura de interconexão. Uma forma de minimizar o consumo de potência em um sistema baseado em NoC é reduzir a atividade de transição de sinais nas portas de entrada dos módulos que constituem a NoC. Esta redução pode ser obtida através da utilização de esquemas de codificação de dados. Vários esquemas de codificação foram propostos no final dos anos 90, porém direcionados a arquiteturas de comunicação baseadas em barramentos. Este trabalho investiga a utilização destes esquemas de codificação em sistemas baseados em Networks-on-Chip. Dentre os esquemas encontrados na literatura, quatro foram implementados e avaliados neste trabalho. Este trabalho também apresenta como contribuição original um novo esquema de codificação de dados adequado a NoCs. A estimativa do consumo de potência da NoC é calculada com base em macromodelos que reproduzem a potência consumida em cada módulo interno da NoC, de acordo com a atividade de transição de sinais no tráfego recebido. Estes macromodelos são aqui caracterizados através da simulação elétrica de cada módulo da NoC e dos esquemas de codificação. Para permitir a análise de consumo com tráfegos de aplicações reais, os macromodelos são inseridos em um modelo de mais alto nível de abstração. Este modelo é empregado para analisar o balanço entre redução de potência obtida com a redução da transição de sinais e o consumo extra do esquema de codificação. A maioria dos esquemas de codificação encontrados na literatura reduz efetivamente a atividade de transição de sinais. Porém, o impacto do consumo extra de potência para codificar e decodificar os dados não é avaliado. A avaliação conduzida neste trabalho considera o consumo da codificação/decodificação em uma NoC real, quantificando a redução de consumo obtido com cada esquema de codificação. Devido ao baixo desempenho dos esquemas de codificação existentes, quando aplicados a NoCs, foi desenvolvido um novo esquema, chamado T-Bus-Invert. Os resultados mostram um desempenho superior do T-Bus-Invert quando comparado aos demais esquemas para flits com largura de 8 e 16 bits, e um desempenho similar ao do Bus-Invert com 4 clusters para flits de 32 bits. / The power consumption in Networks-on-Chip grows linearly with the amount of signal transitions in successive data packets sent through this interconnection infrastructure. One option to decrease the power consumption in NoC-based systems is reducing the switching activity at the input ports of NoC modules. This reduction can be achieved by means of data coding schemes. Several schemes were proposed in the nineties. However, all of them address only bus-based communication architectures. This work investigates the use of such data coding schemes in NoC-based systems. Among the coding schemes found in the literature, four were implemented and evaluated in this work. This work also presents a new data coding scheme, named TBus- Invert, suitable for NoCs. Estimations of the NoC power consumption are computed here based on macromodels which reproduce the power consumption on each internal NoC module, according to the transition activity in the input traffic. Such macromodels are characterized through electrical simulations of each NoC module and coding circuits. To enable the evaluation of real applications traffic, such macromodels are inserted in a higher abstraction level model. This model is employed to analyze the trade-off between the power saving due to coding schemes versus the power consumption overhead due to the encoding and decoding modules. Most of the coding schemes proposed in the literature effectively reduce the switching activity, but the overall impact of the power consumption to encode/decode data in the system is not evaluated. The evaluation conducted in this work considers the power consumption to encode/decode data in a real NoC, quantifying the power savings for each coding scheme. Due to the insufficient performances of the existing schemes when applied to NoCs, a coding scheme, T-Bus-Invert, was developed. Results showed superior performance of the T-Bus-Invert compared to all evaluated coding schemes for 8 and 16-bit flits, and similar performance to the 4-cluster Bus-Invert for 32-bit flits.

O consumo de potência em uma Rede Intra-Chip (em inglês, Network-on-Chip – NoC) cresce linearmente com a quantidade de transições de sinais nos pacotes transmitidos através da infra-estrutura de interconexão. Uma forma de minimizar o consumo de potência em um sistema baseado em NoC é reduzir a atividade de transição de sinais nas portas de entrada dos módulos que constituem a NoC. Esta redução pode ser obtida através da utilização de esquemas de codificação de dados. Vários esquemas de codificação foram propostos no final dos anos 90, porém direcionados a arquiteturas de comunicação baseadas em barramentos. Este trabalho investiga a utilização destes esquemas de codificação em sistemas baseados em Networks-on-Chip. Dentre os esquemas encontrados na literatura, quatro foram implementados e avaliados neste trabalho. Este trabalho também apresenta como contribuição original um novo esquema de codificação de dados adequado a NoCs. A estimativa do consumo de potência da NoC é calculada com base em macromodelos que reproduzem a potência consumida em cada módulo interno da NoC, de acordo com a atividade de transição de sinais no tráfego recebido. Estes macromodelos são aqui caracterizados através da simulação elétrica de cada módulo da NoC e dos esquemas de codificação. Para permitir a análise de consumo com tráfegos de aplicações reais, os macromodelos são inseridos em um modelo de mais alto nível de abstração. Este modelo é empregado para analisar o balanço entre redução de potência obtida com a redução da transição de sinais e o consumo extra do esquema de codificação. A maioria dos esquemas de codificação encontrados na literatura reduz efetivamente a atividade de transição de sinais. Porém, o impacto do consumo extra de potência para codificar e decodificar os dados não é avaliado. A avaliação conduzida neste trabalho considera o consumo da codificação/decodificação em uma NoC real, quantificando a redução de consumo obtido com cada esquema de codificação. Devido ao baixo desempenho dos esquemas de codificação existentes, quando aplicados a NoCs, foi desenvolvido um novo esquema, chamado T-Bus-Invert. Os resultados mostram um desempenho superior do T-Bus-Invert quando comparado aos demais esquemas para flits com largura de 8 e 16 bits, e um desempenho similar ao do Bus-Invert com 4 clusters para flits de 32 bits. / The power consumption in Networks-on-Chip grows linearly with the amount of signal transitions in successive data packets sent through this interconnection infrastructure. One option to decrease the power consumption in NoC-based systems is reducing the switching activity at the input ports of NoC modules. This reduction can be achieved by means of data coding schemes. Several schemes were proposed in the nineties. However, all of them address only bus-based communication architectures. This work investigates the use of such data coding schemes in NoC-based systems. Among the coding schemes found in the literature, four were implemented and evaluated in this work. This work also presents a new data coding scheme, named TBus- Invert, suitable for NoCs. Estimations of the NoC power consumption are computed here based on macromodels which reproduce the power consumption on each internal NoC module, according to the transition activity in the input traffic. Such macromodels are characterized through electrical simulations of each NoC module and coding circuits. To enable the evaluation of real applications traffic, such macromodels are inserted in a higher abstraction level model. This model is employed to analyze the trade-off between the power saving due to coding schemes versus the power consumption overhead due to the encoding and decoding modules. Most of the coding schemes proposed in the literature effectively reduce the switching activity, but the overall impact of the power consumption to encode/decode data in the system is not evaluated. The evaluation conducted in this work considers the power consumption to encode/decode data in a real NoC, quantifying the power savings for each coding scheme. Due to the insufficient performances of the existing schemes when applied to NoCs, a coding scheme, T-Bus-Invert, was developed. Results showed superior performance of the T-Bus-Invert compared to all evaluated coding schemes for 8 and 16-bit flits, and similar performance to the 4-cluster Bus-Invert for 32-bit flits.

No description available.

Networks-on-Chip (NoC) have been proposed to meet many challenges of modern Systems-on-Chip (SoC) design and manufacturing. At the architectural level, a clean separation of computation and communication helps integration and verification. Networking abstraction of the communication infrastructure also promotes reuse and fast development. But the benefit is most visible when it comes to circuit and physical design. Networks can be made sparse and regular and thus facilitate placement and route. It is also much easier to reach timing and power closure as NoC shield communication details away from complicating analysis. Last but not the least, networks are flexible at the design stage and adaptable post-silicon. Many techniques of tackling process variation and interconnect failure can be built upon NoC. However, when interconnects are time multiplexed in a NoC, the network’s performance will deteriorate if it is not scheduled properly. For a wide range of applications, the traffic on the network can be determined before run-time and offline scheduling offers guaranteed performance and enables simple design. We propose a synthesis flow that takes the data flow graph of the application and a network topology as inputs; and outputs an offline schedule that can be deployed directly to the NoC. We analyze the complexity of combinatorial problems that arise from this context and provide efficient heuristics when polynomial time algorithms are not available assuming P [not equal to] NP. Results on LDPC decoding and FFT designs are compared with previous ones. We further apply our findings to parallel shared memories (PSM) and formalize the PSM architecture and its scheduling problem. An efficient heuristic is derived from our algorithm for unbuffered networks. Another application exemplifies how the NoC can be reprogrammed after silicon is back from fab in order to avoid failed interconnects due to process variation. A simple statistical model is studied and the simulation result is rather interesting. We find out that high performance and yield are not always at conflict if we are able to change the network schedule based on silicon diagnosis. / text

Este trabalho tem como objetivo estudar e propor métodos de teste funcional visando a detecção e localização de falhas na infra-estrutura das redes-em-chip. Para isso, o trabalho apresenta, inicialmente, uma descrição das principais características das redes-em-chip, explicando o que elas são e para que elas servem. Em seguida são apresentados conceitos de teste de circuitos integrados, bem como trabalhos relacionados ao teste das redes-em-chip. Um método de teste visando a detecção de falhas nas interconexões de dados de uma NoC é apresentado no trabalho, sendo este método posteriormente estendido para incluir as interconexões de controle. Os circuitos de teste necessários para implementar a estratégia de teste proposta também são descritos. A partir do método de teste apresentado, é feito um estudo sobre sua capacidade de localização de falhas, onde alterações visando o aumento dessa capacidade de localização de falhas são propostas. Por fim o método de teste é estendido para detecção de falhas nos roteadores da rede. / The purpose of this work is to study and propose functional test methods that aim the detection and location of faults in the NoC’s infrastructure. In order to do so, this work presents, initially, a description of the main characteristics of networks-on-chip, explaining what are NoCs and what is their purpose. Fallowing this description, some concepts related to the test of integrated circuits are presented as well as related works on NoC testing. A method aiming the detection of data interconnect faults in a NoC is presented in this work. This method is later extended to include faults in the control interconnections as well. The circuits used to implement the proposed strategy are also described here. Based on the proposed test strategy, the method’s capability to locate faults is studied. Changes are proposed to the test method in order to increase this fault location capability. Finally, the test method is extended to include faults inside the router’s logic.

<p>There is a seemingly endless miniaturization of electronic components, which has enabled designers to build sophisticated computing structureson silicon chips. Consequently, electronic systems are continuously improving with new and more advanced functionalities. Design complexity ofthese Systems on Chip (SoC) is reduced by the use of pre-designed cores. However, several problems related to the interconnection of coresremain. Network on Chip (NoC) is a new SoC design paradigm, which targets the interconnect problems using classical network concepts. Still,SoC cores show large variance in size and functionality, whereas several NoC benefits relate to regularity and homogeneity.</p><p>This thesis studies some network aspects which are characteristic to NoC systems. One is the issue of area wastage in NoC due to cores of varioussizes. We elaborate on using oversized regions in regular mesh NoC and identify several new design possibilities. Adverse effects of regions oncommunication are outlined and evaluated by simulation.</p><p>Deadlock freedom is an important region issue, since it affects both the usability and performance of routing algorithms. The concept of faultyblocks, used in deadlock free fault-tolerant routing algorithms has similarities with rectangular regions. We have improved and adopted one suchalgorithm to provide deadlock free routing in NoC with regions. This work also offers a methodology for designing topology agnostic, deadlockfree, highly adaptive application specific routing algorithms. The methodology exploits information about communication among tasks of anapplication. This is used in the analysis of deadlock freedom, such that fewer deadlock preventing routing restrictions are required.</p><p>A comparative study of the two proposed routing algorithms shows that the application specific algorithm gives significantly higher performance.But, the fault-tolerant algorithm may be preferred for systems requiring support for general communication. Several extensions to our work areproposed, for example in areas such as core mapping and efficient routing algorithms. The region concept can be extended for supporting reuse ofa pre-designed NoC as a component in a larger hierarchical NoC.</p>

Network-on-Chip (NoC) is a developing and promising on-chip communication paradigm that improves scalability and performance of System-on-Chips. NoC design flow contains many problems from different areas, for example networking, embedded design and computer architecture. Application mapping is one of these problems, which is generally considered as a communication energy minimization problem. This dissertation approaches to this problem from a networking point of view and tries to find a mapping solution which improves the network performance in terms of the number of packets in the buffers while still minimizing the total communication energy consumption. For this purpose an on-chip network traffic model is required. Self similarity is a traffic model that is used to characterize Ethernet and/or wide area network traffic, as well as most of on-chip network traffic. In this thesis, by using an on-chip traffic characterization that contains self similarity, an application mapping problem definition that contains both energy and buffer utilization concerns is proposed. In order to solve this intractable problem a genetic algorithm based model is implemented. Execution of the algorithm on different test cases has proved that such a mapping formulation avoids high buffer utilizations while still keeping the communication energy low.