As semiconductor technologies develop, a System-on-Chip (SoC) that integrates all semiconductor intellectual property (IP) cores is suggested and widely used for various applications. A traditional bus interconnection does not support transmitting data between IP cores for high performance. Because of this reason, a Network-on-Chip (NoC) has been suggested to provide an efficient and scalable solution to interconnect among all IP cores. High throughput and low latency have recently become the main important factors of NoC for achieving hard guaranteed real-time systems. In order to guarantee these factors and provide real-time service (i.e., Guaranteed Service, GS), the circuit switching (CS) approach has been widely utilized. The CS approach allocates mutually exclusive paths to transmitting data between different sources and destinations using dedicated NoC resources. However, the exclusive occupancy of the allocated path reduces the efficiency of the overall use of NoC resources. In order to solve this problem, Space-Division-Multiplexing (SDM) and Time-Division-Multiplexing (TDM) techniques have been suggested. SDM implements a circuit switching technique by assigning physically different NoC-links between different connections. Path connections of the SDM technique based on spatial resources assignment do not provide high scalability. In contrast to this, using virtual time slots for a path connection, the TDM technique can share physical links between exclusively established connections, thereby improving NoC path diversity. For all of these mentioned techniques, the factor that significantly impacts the system efficiency or performance scaling is how the path is allocated. In recent years, a dynamic connection allocation approach that can cope with highly dynamic workloads has been gaining attention due to the sudden and diverse demands of applications in real-time systems. There are two groups in the dynamic connection allocation approach. One is a distributed allocation technique, and the other is a centralized allocation technique. While distributed allocation exploits additional logic integrated into the NoC-routers for path search and allocation, the centralized approach makes use of a central unit to manage the path allocation problem. There are several algorithms for the centralized allocation technique. Trellis search-based allocation approach shows the best performance among them. Many algorithms related to centralized connection allocators have been studied extensively during the past decade. However, relatively little attention was paid to methodology in analyzing and evaluating the centralized connection allocation algorithms. In order to further develop the algorithms, it is necessary to understand and evaluate the centralized connection allocator by establishing a new analysis methodology. Thus, this thesis presents a performance analysis methodology for the trellis search-based allocation approach. Firstly, this thesis proposes a system model for analysis. Secondly, performance metrics are defined. Finally, the analysis results of each performance metric related to the trellis search-based allocation approach are presented. Through this analysis, the performance of the trellis search-based allocation approach can be accurately analyzed. Although a simulation is not performed, the upper limit of performance of the trellis search-based allocation approach can also be predicted through the analysis metrics. Additionally, we introduce the general formulation of the trellis search-based path allocation algorithm. The weight values among available paths through the branch metric and path metric are proposed to enable higher performance path connection. Furthermore, according to network size, topology, TDM, interface load delivery, and router internal storage, the performance of trellis search-based path allocation algorithms is also described. In the end, the Application Specific Instruction Processor (ASIP) hardware platform customized for the trellis search-based path allocation algorithm is presented. The shortest available and lowest-cost (SALC) path search algorithm is proposed to improve the success rate of path connection in the ASIP hardware platform. We evaluate the algorithm performance and implementation synthesis results. In order to realize the dynamic connection approach, a short execution cycle of ASIP time is essential. We develop several algorithms to achieve this short execution cycle. The first one is a rectangular region of search algorithm that allows adapting the size and form of path search region according to the particular source-destination positions and considers actual operational constraints. The average execution cycles for searching an optimum path are decreased because the unnecessary region for path-search is excluded. The second one is a path-spreading search algorithm that separates between involved routers and uninvolved routers in path search. The involved routers are selected and spread out from source to destination at each intermediate trellis-search process. The path-search overhead is considerably reduced due to the router involvements. The third one is a three-directional path-spreading search algorithm that eliminates one direction movement among four spreading movements. Because of this reason, the trellis search-based path connection algorithm, which omits the back-tracing process, can be implemented in the ASIP platform. Thus, the whole algorithm execution time can be halved. The last one is a moving regional path search algorithm that significantly reduces computation complexity by selecting a constant dimensional path-search region that affects performance and moving the region from source to destination. The moving regional path search algorithm achieves a considerable decrement of computational complexity.:1 Introduction 1 1.1 NoC-interconnect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Connection allocation in a Network-on-Chip 7 2.1 Circuit Switching NoCs . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Guaranteed Service in NoCs . . . . . . . . . . . . . . . . . . . 7 2.1.2 Spatial-Division-Multiplexing technique . . . . . . . . . . . . 8 2.1.3 Time-Division-Multiplexing technique . . . . . . . . . . . . . 10 2.2 System architectures employing circuit switching NoCs . . . . . . . . 11 2.2.1 Static and dynamic connection allocation . . . . . . . . . . . 12 2.2.2 Distributed connection allocation technique . . . . . . . . . . 14 2.2.3 Centralized connection allocation technique . . . . . . . . . . 16 2.2.4 Algorithms for centralized connection allocation . . . . . . . . 17 2.2.4.1 Software based run-time path allocation approach . 18 2.2.4.2 Trellis search-based allocation approach . . . . . . . 19 3 Performance analysis methodology for a centralized connection allocator 23 3.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Performance metrics and analysis methodology . . . . . . . . . . . . 25 3.3 System simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4 Trellis search-based path allocation algorithm 45 4.1 General formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.1.1 Trellis graph structure . . . . . . . . . . . . . . . . . . . . . . 45 4.1.2 Survivor path selection criterion . . . . . . . . . . . . . . . . . 52 ix 4.1.2.1 Branch metric and path metric . . . . . . . . . . . . 52 4.1.2.2 The shortest-available and lowest-cost path selection criterion . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Algorithm Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2.1 Network topology . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2.2 Network size . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.3 Time-Division-Multiplexing . . . . . . . . . . . . . . . . . . . 61 4.2.4 NoC interface load diversity . . . . . . . . . . . . . . . . . . . 63 4.2.5 The internal storage of the router . . . . . . . . . . . . . . . . 66 5 ASIP approach for Trellis search-based connection allocation 73 5.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.1.1 Trellis search-based ASIP platform architecture . . . . . . . . 74 5.2 Algorithm for improving success rates of path connection . . . . . . . 81 5.2.1 SALC algorithm for Trellis search-based ASIP platform . . . . 81 5.2.2 Performance evaluation of the SALC algorithm . . . . . . . . 88 5.2.2.1 Simulation results . . . . . . . . . . . . . . . . . . . 88 5.2.2.2 Synthesis results . . . . . . . . . . . . . . . . . . . . 91 5.3 Algorithm for reducing path-search time . . . . . . . . . . . . . . . . 93 5.3.1 Rectangular regional path search algorithm . . . . . . . . . . 93 5.3.2 Path-spreading search algorithm . . . . . . . . . . . . . . . . 99 5.3.3 Three directional path-spreading search algorithm . . . . . . 108 5.3.4 Moving regional path search algorithm . . . . . . . . . . . . . 114 5.3.5 Performance evaluation . . . . . . . . . . . . . . . . . . . . . 123 5.3.5.1 Simulation results . . . . . . . . . . . . . . . . . . . 123 5.3.5.2 Synthesis results . . . . . . . . . . . . . . . . . . . . 126 6 Conclusion and Future work 131 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Bibliography 135

Ce mémoire traite des systèmes intégrés sur puce (System-on-Chip) à faible consommation d'énergie tels que ceux qui seront utilisés dans les équipements portables de future génération (ordinateurs de poche (PDA), téléphones mobiles). S'agissant d'équipements alimentés par des batteries, la consommation énergétique est un problème critique. Ces plateformes contiendront probablement une douzaine de coeurs de processeur et une quantité importante de mémoire embarquée. Une architecture de communication optimisée sera donc nécessaire afin de les interconnecter de manière efficace. De nombreuses architectures de communication ont été proposées dans la littérature: bus partagés, bus pontés, bus segmentés et plus récemment, les réseaux intégrés (NoC). Toutefois, à l'exception des bus, la consommation d'énergie des réseaux d'interconnexion intégrés a été largement ignorée pendant longtemps. Ce n'est que très récemment que les premières études sont apparues dans ce domaine. Cette thèse présente: - Une analyse complète de l'espace de conception des architectures de communication intégrées. Sur base de cet espace de conception et d'un état de l'art détaillé, des techniques jusqu'alors inexplorées ont pu être identifiées et investiguées. - La conception d'environnements de simulation de bas et haut niveaux permettant de réaliser des comparaisons entre différentes architectures de communication en termes de consommation énergétique et de surface. - La conception et la validation d'une architecture de communication intégrée innovante basée sur le multiplexage spatial Ce dernier point a pour ambition de démontrer qu'un réseau basé sur le multiplexage spatial (SDM) constitue une alternative intéressante aux réseaux classiques principalement basés sur le multiplexage temporel dans le contexte très spécifique des architectures de communication intégrées. Nous démontrerons la validité de la solution proposée à l'aide de campagnes de simulation de haut niveau pour divers types de trafic ainsi que des simulations de plus bas niveau. L'étude concerne successivement la conception de routers SDM, des interfaces réseau et finalement d'un réseau complet. Les avantages et inconvénients d'une telle technique seront discutés en détails.

Network-on-Chips (NoCs) have become the standard communication platform for future massively parallel systems due to their performance, flexibility and scalability advantages. However, reliability issues brought about by scaling in the sub-20nm era threaten to undermine the benefits offered by NoCs. This dissertation demonstrates design techniques that address both reliability and security issues facing modern NoC architectures. The reliability and security problem is tackled at different abstraction levels using a series of schemes that combine information from the architecture-level as well as hardware-level in order to combat aging effects and meet secure design stipulations while maintaining modest power-performance overheads.

The progress which has been made in semiconductor chip production in recent years enables a multitude of cores on a single die. However, due to further decreasing structure sizes, fault tolerance and energy consumption will represent key challenges. Furthermore, an efficient communication infrastructure is indispensable due to the high parallelism at those systems. The predominant communication system at such highly parallel systems is a Network on Chip (NoC). The focus of this thesis is on NoCs which are based on deflection routing. In this context, contributions are made to two domains, fault tolerance and dimensioning of the optimal link width. Both aspects are essential for the application of reliable, energy efficient, and deflection routing based NoCs. It is expected that future semiconductor systems have to cope with high fault probabilities. The inherently given high connectivity of most NoC topologies can be exploited to tolerate the breakdown of links and other components. In this thesis, a fault-tolerant router architecture has been developed, which stands out for the deployed interconnection architecture and the method to overcome complex fault situations. The presented simulation results show, all data packets arrive at their destination, even at high fault probabilities. In contrast to routing table based architectures, the hardware costs of the herein presented architecture are lower and, in particular, independent of the number of components in the network. Besides fault tolerance, hardware costs and energy efficiency are of great importance. The utilized link width has a decisive influence on these aspects. In particular, at deflection routing based NoCs, over- and under-sizing of the link width leads to unnecessary high hardware costs and bad performance, respectively. In the second part of this thesis, the optimal link width at deflection routing based NoCs is investigated. Additionally, a method to reduce the link width is introduced. Simulation and synthesis results show, the herein presented method allows a significant reduction of hardware costs at comparable performance. / Die Fortschritte der letzten Jahre bei der Fertigung von Halbleiterchips ermöglichen eine Vielzahl an Rechenkernen auf einem einzelnen Chip. Die in diesem Zusammenhang immer weiter sinkenden Strukturgrößen führen jedoch dazu, dass Fehlertoleranz und Energieverbrauch zentrale Herausforderungen darstellen werden. Aufgrund der hohen Parallelität in solchen Systemen, ist außerdem eine leistungsfähige Kommunikationsinfrastruktur unabdingbar. Das in diesen hochgradig parallelen Systemen überwiegend eingesetzte System zur Datenübertragung ist ein Netzwerk auf einem Chip (engl. Network on Chip (NoC)). Der Fokus dieser Dissertation liegt auf NoCs, die auf dem Prinzip des sog. Deflection Routing basieren. In diesem Kontext wurden Beiträge zu zwei Bereichen geleistet, der Fehlertoleranz und der Dimensionierung der optimalen Breite von Verbindungen. Beide Aspekte sind für den Einsatz zuverlässiger, energieeffizienter, Deflection Routing basierter NoCs essentiell. Es ist davon auszugehen, dass zukünftige Halbleiter-Systeme mit einer hohen Fehlerwahrscheinlichkeit zurecht kommen müssen. Die hohe Konnektivität, die in den meisten NoC Topologien inhärent gegeben ist, kann ausgenutzt werden, um den Ausfall von Verbindungen und anderen Komponenten zu tolerieren. Im Rahmen dieser Arbeit wurde vor diesem Hintergrund eine fehlertolerante Router-Architektur entwickelt, die sich durch das eingesetzte Verbindungsnetzwerk und das Verfahren zur Überwindung komplexer Fehlersituationen auszeichnet. Die präsentierten Simulations-Ergebnisse zeigen, dass selbst bei sehr hohen Fehlerwahrscheinlichkeiten alle Datenpakete ihr Ziel erreichen. Im Vergleich zu Router-Architekturen die auf Routing-Tabellen basieren, sind die Hardware-Kosten der hier vorgestellten Router-Architektur gering und insbesondere unabhängig von der Anzahl an Komponenten im Netzwerk, was den Einsatz in sehr großen Netzen ermöglicht. Neben der Fehlertoleranz sind die Hardware-Kosten sowie die Energieeffizienz von NoCs von großer Bedeutung. Einen entscheidenden Einfluss auf diese Aspekte hat die verwendete Breite der Verbindungen des NoCs. Insbesondere bei Deflection Routing basierten NoCs führt eine Über- bzw. Unterdimensionierung der Breite der Verbindungen zu unnötig hohen Hardware-Kosten bzw. schlechter Performanz. Im zweiten Teil dieser Arbeit wird die optimale Breite der Verbindungen eines Deflection Routing basierten NoCs untersucht. Außerdem wird ein Verfahren zur Reduzierung der Breite dieser Verbindungen vorgestellt. Simulations- und Synthese-Ergebnisse zeigen, dass dieses Verfahren eine erhebliche Reduzierung der Hardware-Kosten bei ähnlicher Performanz ermöglicht.

<p>The computer engineering group at Linköping University has parts of their research dedicated to networks-on-chip and components used in network components and terminals. This research has among others resulted in the SoCBUS NOC and a flow based network protocol processor. The main objective of this project was to integrate these components into an IP router with two or more Gigabit Ethernet interfaces.</p><p>A working system has been designed and found working. It consists of three main components, the input module, the output module and a packet buffer. Due to the time constraint and the size of the project the packet buffer could not be designed to be as efficient as possible, thus reducing the overall performance. The SoCBUS also has negative impact on performance, although this could probably be reduced with a revised system design. If such a project is carried out it could use the input and output modules from this project, which connect to SoCBUS and can easily be integrated with other packet buffers and system designs.</p>

Due to the interplay between increasing chip capacity and complex applications, System-on-Chip (SoC) development is confronted by severe challenges, such as managing deep submicron effects, scaling communication architectures and bridging the productivity gap. Network-on-Chip (NoC) has been a rapidly developed concept in recent years to tackle the crisis with focus on network-based communication. NoC problems spread in the whole SoC spectrum ranging from specification, design, implementation to validation, from design methodology to tool support. In the thesis, we formulate and address problems in three key NoC areas, namely, on-chip network architectures, NoC network performance analysis, and NoC communication refinement. Quality and cost are major constraints for micro-electronic products, particularly, in high-volume application domains. We have developed a number of techniques to facilitate the design of systems with low area, high and predictable performance. From flit admission and ejection perspective, we investigate the area optimization for a classical wormhole architecture. The proposals are simple but effective. Not only offering unicast services, on-chip networks should also provide effective support for multicast. We suggest a connection-oriented multicasting protocol which can dynamically establish multicast groups with quality-of-service awareness. Based on the concept of a logical network, we develop theorems to guide the construction of contention-free virtual circuits, and employ a back-tracking algorithm to systematically search for feasible solutions. Network performance analysis plays a central role in the design of NoC communication architectures. Within a layered NoC simulation framework, we develop and integrate traffic generation methods in order to simulate network performance and evaluate network architectures. Using these methods, traffic patterns may be adjusted with locality parameters and be configured per pair of tasks. We propose also an algorithm-based analysis method to estimate whether a wormhole-switched network can satisfy the timing constraints of real-time messages. This method is built on traffic assumptions and based on a contention tree model that captures direct and indirect network contentions and concurrent link usage. In addition to NoC platform design, application design targeting such a platform is an open issue. Following the trends in SoC design, we use an abstract and formal specification as a starting point in our design flow. Based on the synchronous model of computation, we propose a top-down communication refinement approach. This approach decouples the tight global synchronization into process local synchronization, and utilizes synchronizers to achieve process synchronization consistency during refinement. Meanwhile, protocol refinement can be incorporated to satisfy design constraints such as reliability and throughput. The thesis summarizes the major research results on the three topics. / QC 20100525

The increased demand for on-chip communication bandwidth as a result of the multi-core trend has made packet-switched networks-on-chip (NoCs) a more compelling choice for the communication backbone in next-generation systems. NoC designs are sensitive to many design parameters—hence the study of new NoCs can be time-intensive. We propose DART, a fast and flexible FPGA-based NoC simulation architecture. Rather than laying the NoC out directly on the FPGA like previous approaches, DART virtualizes the NoC by mapping its components to a generic NoC simulation engine. This approach has two main advantages: (i) since it is virtualized it can simulate any NoC; and (ii) any NoC can be mapped to the engine without the time-consuming process of rebuilding the FPGA design. We demonstrate that an implementation of DART on a Virtex-II Pro FPGA achieves over 100x speedup over the cycle-based software simulator Booksim, while maintaining the same level of simulation accuracy.

The increased demand for on-chip communication bandwidth as a result of the multi-core trend has made packet-switched networks-on-chip (NoCs) a more compelling choice for the communication backbone in next-generation systems. NoC designs are sensitive to many design parameters—hence the study of new NoCs can be time-intensive. We propose DART, a fast and flexible FPGA-based NoC simulation architecture. Rather than laying the NoC out directly on the FPGA like previous approaches, DART virtualizes the NoC by mapping its components to a generic NoC simulation engine. This approach has two main advantages: (i) since it is virtualized it can simulate any NoC; and (ii) any NoC can be mapped to the engine without the time-consuming process of rebuilding the FPGA design. We demonstrate that an implementation of DART on a Virtex-II Pro FPGA achieves over 100x speedup over the cycle-based software simulator Booksim, while maintaining the same level of simulation accuracy.

This thesis proposes a synthesis methodology which is capable of fault-tolerance and deadlock-free for constructing a custom NoC topology in 3D ICs. In this thesis, the processors and their communications can be synthesized simultaneously in the system-level floorplanning with fault tolerant consideration, called 3D-NoC-FT. Experimental results show that the pro-posed 3D-NoC-FT produces custom 3D NoCs with lower power dissipation than previous works. This method is also more scalable, which makes it ideal for complicated 3D NoC de-signs. Compared with the previous 3D NoC work (3D-SAL-FP) without link fault tolerance, our fault tolerant method outperforms on the average the power dissipation by 1.67X with rela-tively small overhead of latency by 17% and the number of TSV by 35%, respectively.

The emergence of networks-on-chip (NoC) as the communication infrastructure solution for complex multi-core SoCs presents communication synthesis challenges. This dissertation addresses the design and run-time management aspects of communication synthesis. Design reuse and the infeasibility of Intellectual Property (IP) core interface redesign, requires the development of a Core-Network Interface (CNI) which allows them to communicate over the on-chip network. The absence of intelligence amongst the NoC components, entails the introduction of a CNI capable of not only providing basic packetization and depacketization, but also other essential services such as reliability, power management, reconguration and test support. A generic CNI architecture providing these services for NoCs is proposed and evaluated in this dissertation. Rising on-chip communication power costs and reliability concerns due to these, motivate the development of a peak power management technique that is both scalable to dierent NoCs and adaptable to varying trac congurations. A scalable and adaptable peak power management technique - SAPP - is proposed and demonstrated. Latency and throughput improvements observed with SAPP demonstrate its superiority over existing techniques. Increasing design complexity make prediction of design lifetimes dicult. Post SoC deployment, an on-line health monitoring scheme, is essential to maintain con- dence in the correct operation of on-chip cores. The rising design complexity and IP core test costs makes non-concurrent testing of the IP cores infeasible. An on-line scheme capable of managing IP core test in the presence of executing applications is essential. Such a scheme ensures application performance and system power budgets are eciently managed. This dissertation proposes Concurrent On-Line Test (COLT) for NoC-based systems and demonstrates how a robust implementation of COLT using a Test Infrastructure-IP (TI-IP) can be used to maintain condence in the correct operation of the SoC.