This project focuses on investigating energy-efficient and reconfigurable Network-on-Chips (NoCs) to address the major challenges faced by Intellectual Property (IP) integration in complex System-on-Chip (SoC) systems, including energy efficiency, reconfigurability, scalability, and signal integrity. The objectives of the proposed work include investigation of reconfigurable Recursive Diagonal Torus (RDT)-based NoC architectures, investigation of multi-path routing scheme and the prioritized wormhole switching technique and development of prototype systems. From this project, 7 journal and 6 conference publications and 2 master theses have been produced. The major results generated from this project are summarized below:

· Quartered Recursive Diagonal Torus (QRDT) Architecture (GVLSI08, ITNG08)
      The QRDT network is constructed by overlaying diagonal torus. An N-QRDT is composed of N×N nodes where N=4n and n is a positive integer, rank-0 links, and rank-1 links. Each node (x, y), where 0 <= x, y <= N-1, has 4 rank-0 links connecting to its four neighbors (mod_N(x ± 1), y) and (x, mod_N(y ± 1)) on rank-0 torus, and 4 rank-1 links connecting to its another four neighbors (mod_N(x ± n), mod_N(y ± n)) on rank-1 torus. In total, an N-QRDT has N² nodes and 4N² links. It is shown that the diameter and average distance of the N-QRDT are n+1, and (96n³+60n²-96n+6)/[3(16n²-1)], where n=N/4. From Tab. 1, one can see that QRDT has smaller diameter and average distance than the other three structures for most network sizes. A minimal routing algorithm, named Johnson coded vector routing algorithm (JCVR) is proposed for the QRDT network.
      To implement the proposed QRDT structure, a parameterized and reconfigurable router is designed. The router is designed to support up to 9 communication ports to match with the number of links connected to a node in QRDT. The main function of the router includes buffering, routing (both vector routing and JCVR), scheduling, switching (wormhole switching), and flow control. The following components are designed: input channel module, output channel module, crossbar switch, and scheduler. The synthesized results of the router design using Synopsys´s design analyzer under TSMC 0.18µm CMOS technology are reported. This router design can be reconfigured to build mesh/torus-based NoCs as the QRDT network naturally embeds the mesh/torus.

· Multi-Path Routing Scheme (IJCTA08, ITNG08)
      In NoC designs, crosstalk noise has become a serious issue which may cause the communication channel unreliable. The crosstalk problem can be mitigated by wide spacing of serial lines. However, for a fixed chip area, wider spacing of adjacent wires will reduce the number of wires between routers, thus reduce the data throughput. Consider mesh/torus networks, there exist multiple shortest paths between most pairs of source and destination nodes. In the multi-path routing (MPR) scheme, when the source node needs to send data to a destination node, it will first compute the number of the shortest paths between the source and destination nodes, then partition the message into multiple data streams and send each on one of the shortest paths.

Figure 1 MPR under FM (a) and MPR under HM (b) for 4x4 torus.

     We consider two transport models of the MPR scheme (Fig. 1): the full-wire-bank transport model (FM), and the half-wire-bank transport model (HM), which are same on the routing scheme and transport control but different on their usage of the wire bank and the buffer size. In HM, each data stream will be transmitted on half of the wires (either on odd numbered wires or even numbered wires) on each link to avoid crosstalk. Theoretical analysis shows that the MPR scheme under both FM and HM achieves improvement in data throughput when single pair of nodes are in communication. When multiple pairs of nodes are in communication, simulation results demonstrate that the MPR scheme under FM significantly improves the normalized accepted traffic and throughput as well as average message latency than the YX routing algorithm in most network loads. To ensure the deadlock-freeness of the MPR scheme, a virtual channel is also proposed. It is proved that any minimal routing algorithm using the proposed virtual channel model is deadlock-free.

· Template-Based IP Mapping Algorithm (EMCOM09, TACO10)
      In this work, we investigate the IP mapping problem that maps a given set of IP cores onto the tiles of a mesh-based NoC architecture such that the power consumption due to inter-core communications is minimized. This IP mapping problem is considered under both bandwidth and latency constraints as imposed by the applications and the on-chip network infrastructure. By examining various applications' communication characteristics extracted from their respective communication trace graphs, two distinguishable connectivity templates are realized: the graphs with tightly coupled vertices and those with distributed vertices. For these two templates, different mapping heuristics are subsequently developed to map them. In general, tightly coupled vertices are mapped onto tiles that are physically close to each other while the distributed vertices are mapped following a graph partition scheme. Experimental results on both random and multimedia benchmarks have confirmed that the proposed template-based mapping algorithm achieves an average of 15% power saving as compared with MOCA, a fast greedy-based mapping algorithm. Compared with a branch-and-bound-based mapping algorithm, which produces near optimal results but incurs an extremely high computation cost, the proposed algorithm, due to its polynomial run time complexity, can generate the results of almost the same quality with much less CPU time. As the on-chip network size increases, the superiority of the proposed algorithm becomes more evident.

· Efficient NoC Multicasting Scheme (MICPRO10, SOCC10)
      When a number of applications simultaneously running on a many-core chip multiprocessor (CMP) chip connected through network-on-chip (NoC), significant amount of on-chip traffic is one-to-many (multicast) in nature. As a matter of fact, when multiple applications are mapped onto an NoC architecture with applicable traffic isolation constraints, the corresponding sub-networks of these applications are mapped onto actually tend to be irregular. In the literature, multicasting for irregular topologies is supported through either multiple unicasting or broadcasting, which, unfortunately, results in overly high power consumption and/or long network latency. To address this problem, efficient hardware-based multicasting scheme is proposed. First, an irregular oriented multicast strategy is proposed. Literally, following this strategy, an irregular oriented multicast routing algorithm can be designed based on any regular mesh based multicast routing algorithm. Two such algorithms, namely, Alternative XY (AL+XY) based on XY routing, and Alternative Recursive Partitioning Multicasting (AL+RPM) based on RPM, which is designed for regular mesh topology originally. The basic idea of AL+XY (AL+RPM) is to find the output directions following the basic XY (RPM) routing algorithm and then decide to replicate the packets to the original output directions or the alternative output directions based on the shape of the sub-network. The experiment results show that the proposed multicast AL+XY and AL+RPM both achieve significant power saving (up to 20%) and much less network latency (up to 50%) than bLBDR (a broadcasting-based routing algorithm) and the multiple unicast scheme. To incorporate AL+XY or AL+RPM into a baseline router to support multicasting, the area overhead is fairly modest, less than 5.5%.

· PCB-Based NoC Emulation System (IJE10)
      To validate the architectures and schemes proposed in this project, a scalable and flexible NoC emulation platform implemented with multiple FPGA devices is developed. Using this emulator, NoCs built upon various types of network topologies, routing algorithms, switching protocols, and flow control schemes can be explored, compared, and validated with injected or self-generated traffic from both real-life and synthetic applications. As shown in Fig. 2, the emulation board consists of five Xilinx Virtex-5 LX110T FPGA chips that are mounted on a 22-layer, large PCB board. This emulation board is capable of emulating a complete 4x4 many-core design featuring a 32-bit, RISC core.

Figure 2 The NoC emulation system.

     The high degree of scalability and flexibility is achieved due to the FPGA design choices made at both functional and physical levels. At the functional level, an NoC system to be emulated can be partitioned into two parts: (i) the processing cores and (ii) the network. Each part is mapped onto a different FPGA so that when there is any change to be made on any one of these two parts, only the corresponding FPGA needs to be reconfigured and the rest FPGAs will be left untouched. At the physical level, two levels of interconnects are adopted to mimic NoC on-chip communications: high bandwidth and low latency parallel on-board wires, and high speed serial multigigabit transceivers available in FPGAs. The latter is particularly important as it helps the proposed NoC emulation platform scale well with the size increase of the NoCs.
      As a demonstration, the H.264 decoding application program mapped to a 2x2 mesh-based NoC is emulated on the developed emulator. The run time speedup for this application is shown to be four orders of magnitude of the software-based simulator. Experiments of NoCs with other topologies are being conducted.

· Avoidance of Request-Request Type Message-Dependent Deadlocks (JPC2013, ICCST2010)
      When an application is running on a network-on-chip (NoC)-based multiprocessor systemon- chip (MPSoC), two types of deadlocks may occur: (i) the routing-dependent deadlocks, and (ii) the message-dependent deadlocks. The former type of deadlocks can be avoided by removing any cyclic paths on the application’s channel dependency graph. The message-dependent deadlocks, caused by mutual dependency of different control and/or data messages, on the other hand, are very complicated to deal with. In this work, we have formally proved a sufficient condition that determines the minimum number of VCs actually needed for each link of a communication flow such that, request–request type message-dependent deadlocks can be completely avoided. Following this sufficient condition, we propose a path selection and minimum VC allocation (PSMV) algorithm to help determine the minimum number of non-uniform VCs for each link. The PSMV algorithm can literally be integrated with any existing application mapping algorithm to provide deadlock-free mapping results. One such deadlock-free mapping algorithm is suggested in this paper. Our experiments also show that, compared to an existing flow control based deadlock avoidance method (CTC) and a deadlock recovery method (DR), increase of buffers size in PSMV is within 5% compared to a baseline network configuration. The message latency of PSMV is the lowest among all three designs.