Recently, network on chip (NoC) architectures are being

proposed for implementing multi-core systems for realtime

multi-media applications. The communication

traffic of those systems will be a mix of guaranteed

throughput (GT) and best effort (BE) traffic. GT traffic

not only lead to under-utilization of communication links

and routers, but also leads to degradation of QoS

parameters for BE traffic. We propose a dynamic routing

scheme for reducing jitter in the latency of BE traffic

affected by the GT traffic. Our results from modeling and

simulation indicate that a significant improvement in

jitter can be achieved.

It is possible to concurrently run multiple

applications on IP-core based SoC built using Network

on Chip (NoC) paradigm. Some applications require

predictable and guaranteed on-chip communication

performance. In this paper we propose a new approach

for using underutilized reservation of guaranteed

throughput (GT) traffic to improve the performance of

best effort (BE) traffic. We have modeled our scheme for

a mesh topology NoC on a simulation platform. The

results show that the proposed scheme leads to

significant improvement in BE performance.

Efficient routing schemes are essential if Network on

Chip (NoC) architectures are to be used for implementing

multi-core systems for real-time multi-media applications.

These systems will be characterized by internal communication

traffic which is a mix of traffic requiring guaranteed

throughput (GT) and other traffic requiring some other QoS

properties like latency and less packet drops. Communication

resources are generally reserved for providing GT

performance. In this paper we propose a dynamic scheme for

improving packet drop probability of other traffic by

intelligently utilizing the under-utilized reserved

communication resources of GT traffic. We demonstrate the

effectiveness of our scheme by simulation.

To support communication among hundreds of cores on a chip, on-chip communication must be well organized. In the embedded systems using such a chip, the communication patterns can be profiled off-line and routing can be well planned. Source routing has been shown to be suitable in such contexts. However, source routing has one serious drawback of overhead for storing the path information in header of every packet. This disadvantage becomes worse as the size of the network grows. In this paper we propose a technique, called Junction Based Routing (JBR), to remove this limitation. In the proposed technique, path information for only a few hops is stored in the packet header.

With this information, either the packet reaches the destination, or  reaches a junction from where the path information for on-ward path is picked up. There are many interesting issues related to this approach. We discuss and solve two important issues related to JBR, namely, the required number of junctions and their positions and path computation for efficient deadlock-free routing. A simulator has been developed to evaluate the performance of JBR and compare it with simple source routing. We observe that JBR has slightly worse performance as compared to pure source routing for packets with large payload. But JBR has  potential of higher performance for packets with small payloads.

Testing of high density SoCs operating at high clock speeds is an important but difficult problem. Many faults, like delay faults, in such sub-micron chips may only appear when the chip works at normal operating speed. In this paper, we propose a methodology for at-speed testing of delay faults in links connecting two distinct clock domains in a SoC. We give an analytical analysis about the efficiency of this method. We also propose a simple digital hardware structure for the receiver end of the link under test to detect delay faults. It is possible to extend our method to combine it with functional testing of the link and adapt it for online testing

Test of electronic circuits for fabrication fault is important if the circuits should have reasonable quality. To make the development of complex circuits manageable, methods and computer tools that work on a high level of abstraction are required. Development of test methodologies have however been left behind the increase of abstraction level used for the design. There is a risk that testing aspects become a bottle neck in the development of complex circuits if the test methods fail to cope up with the abstraction level for the design methods.

System on Chips is often used to implement complex systems. The methods to make test for those circuits consists of three main parts. First part is the development of test procedures for the cores, which is preferably made at high level of abstraction. This area includes fault modeling and test pattern generation at behavior level of abstraction or higher as well as design of extra logic for insertion to facilitate testing. The second part requires development of methods to test the interconnections among cores.

The third part is to develop a test access mechanism which can be used to test the cores and interconnections within a SoC. This survey is about development of fault models and test pattern for testing of cores at higher level of abstraction than logic level. A promising architecture for the interconnection is the Network on Chip architecture in which cores are interconnected through a network of packet switched switches. Testing of these switches will be identical to testing of a core.

Models of physical and fabrication faults are needed at higher levels of abstraction in order to be able to develop test patterns from functional or behavioral description of cores. Researchers have experienced that the stuck-at fault model works quite well at logic level. But no such fault model has been discovered at behavioral or higher level which is universally accepted. Several behavior level fault models have been proposed. One of the proposed models is the variable bit stuck-at fault model. This model has been derived from the logic level stuck-at fault model but it does not give adequate coverage of physical faults. Physical faults inside components, like arithmetic and logic units, cannot be modeled in this way. With the methods proposed so far, knowledge of the logic level implementation of the unit is needed to model such faults. In this survey, we describe three proposed classes of fault models - fault models derived from logic level stuck-at faults, operator mutation faults and physically induced faults.

Testing at higher level of abstraction has a lot in common with software testing. The pattern generation methods can be classified into two main categories, namely, code oriented methods and fault oriented methods. Methods can also be classified into methods that use fault simulation for test pattern generation or use algorithmic approach for test pattern generation. These two classification approaches are orthogonal leading to four different categories of methods. We have tried to put existing approaches in this category. We also survey the experimental setups developed and used by various research groups for carrying out research in high level testing. Some very interesting conclusions can be drawn about the efficacy of various categories of test pattern generation methodologies for testing various types of systems at behavioral level. An interesting conclusion is that code oriented methods are not very effective for testing data dominated circuits at behavioral level.

Approaches followed by five different research groups working in the area of high level testing is also summarized and compared. We feel that the hierarchical test pattern generation method, which works simultaneously on several levels of abstraction, to generate test patterns is the most promising of these methods. We also feel that new fault models need to be developed to make testing at higher level of abstraction achieve adequate coverage of physical faults and become practically useful.

One of the limitations of the current NOC architectures is their inability to provide efficient access mechanisms for on-chip or off-chip memories. It is expected that a large amount of memory will be required to support many cores on a NoC system. In this paper, we describe an efficient 3-level memory hierarchy suitable for NoC based systems. We also present a design of the memory network interface to connect a shared memory core to an on-chip network for block based accesses. We have developed a model of a mesh topology NoC architecture of size 5x5 with a single shared on-chip memory and buffer-less routers. The routers implement a very simple adaptive routing scheme. In the model five cores are made to concurrently access the shared memory for blocks of data. We have carried out interesting experiments to study the variation of average memory access time for different network loads, block size and width of a channel connecting two routers. As expected the average access time improves with the increase in the block size due to pipelined nature of memory accesses through the network. The results show that the average access time of the shared memory could be acceptable for block sizes larger than 100 bytes with channel widths of 64 bits even when the other traffic load is as much as 80%. However, it will be very slow to access blocks smaller than 32 bytes from a shared memory.

Network on Chip (NoC) is a new paradigm for designing large and complex systems on chips (SoCs). In this paradigm, a packet switched network is provided for on-chip communication among cores. NoC paradigm provides the required scalability and reusability to reduce design time of SoCs. A NoC simulator is an important tool required to support development of designs based on a NoC architecture. In this paper, we describe the design of such a simulator using System Description Language (SDL). Features of SDL for representing structural hierarchy using blocks, concurrent processes and dynamic generation of processes, communication channels of user defined data types and timers are useful for modelling a NoC architecture at various levels of communication protocols. We use an event driven SDL simulator to carry out interesting experiments to evaluate various architectural options like buffer size in switches, and their effect on the performance like delay and packet loss.

The idea of using on chip packet switched networks for interconnecting a large number of IP cores is very practical for designing complex SoCs since it gives possibility of not only reusing IP cores but also the interconnection infrastructure. However, the real effort and time in using these Networks on Chip (NoC) goes in developing interfaces for connecting cores to the on-chip network. Standardization of interfaces for these cores can speed up the development process. In this paper, we present our work of developing an interface for a standard bus called OPB to the on-chip network. Any cores having OPB as the wrapper can reuse this interface. The paper also describes implementation of a small NoC prototype using this idea on an FPGA platform. The performance measurements on the prototype not only demonstrate the feasibility of NoC implementation but also demonstrate that FPGA based NoC implementation will be able to meet the performance requirements in many application areas. Specifically, we show that a core can communicate 2.5 MPackets/sec to a neighboring core.

Chen and Chiu published a fault tolerant routing algorithm for mesh topology net-works which they claimed was deadlock free in the presence of multiple faults. In this paper we give a counter-example to show that their Message-Route algorithm fails to provide deadlock free routing in a 2 dimensional mesh network. We also point out certain cases where the algorithm fails to route messages to their destinations. We identify an error in the proof of the main theorem in their paper which was used for proving the property of deadlock freeness. Changes to their algorithm are proposed to make it deadlock free and complete. We also discuss a new application of fault tolerant routing algorithms for non-homogeneous 2-dimensional mesh topology networks for on-chip communication.

Mesh topology is popular for Network on Chip (NoC) architectures because it has many desirable fabrication and performance properties, due to fixed sized rectangular tiles for resources. Region concept has been proposed to handle cores with larger size than the tiles. In this paper, we present an elaboration of the region concept, pointing out new design issues and possibilities. Special routing algorithms are required for deadlock free communication to handle blockage introduced by the regions. We show that fault tolerant algorithms developed for multi-computer systems can be adapted for this purpose. By simulation, we study the introduction of rectangular regions in a 7X7 NoC. Our study shows that the position and orientation of regions have a strong influence on achieved network performance.

Selecting appropriate hardware resources corresponding to the application is an important task for design of an embedded system or a SoC. A large number of techniques have been proposed in literature to select a processor matching with the application requirements. In this report, we propose a framework called Processor Evaluation Cube (PEC) which helps in systematic classification and comparison of various processor evaluation techniques. The three axes of PEC are: Analysis, Architecture and Abstraction. The Analysis axis distinguishes methods employing static analysis or simulation; Architecture axis distinguishes methods evaluating single processor or multiprocessor computing platforms; Abstraction axis distinguishes methods employing clock true evaluation or higher level execution time estimation techniques. Our survey not only puts the existing techniques in proper perspective but also points to the weaknesses in the existing techniques which need to be removed if these techniques have to be used for design of multi-processor SoC (System on Chip) and Network on Chip (NoC) systems. We observe during our survey that the techniques for single processor evaluation are getting adapted for evaluation of multiprocessor platforms. We also note that there are no techniques developed or proposed for low level static analysis of multi-processor platforms due to complexity of such an evaluation. Although many different evaluation approaches may fall in the same category in PEC classification they have significant differences in intermediate descriptions of application, architecture and performance parameters.

The concept of hierarchical networks is useful for designing a large heterogeneous NoC by reusing predesigned small NoCs as subnets. It can also be helpful when analyzing and designing a large NoC as interconnection of subnets at a higher level of abstraction. Hierarchical deadlock-free routing is required to enable deadlock-free interconnection of sub-networks with different internal routing algorithms. In this paper we show that multi-level addressing is a cost-effective implementation option for hierarchical deadlock-free routing. We propose a two-level routing scheme, which is not only efficient, but also  enables co-existence of algorithmic and table-based implementation in one router. A hierarchical view of the network simplifies addressing of network nodes and address decoding in the router. Synthesis results show that a 2-level hierarchical router design for an 8x8 NoC, can reduce area and power requirements by  up to ~20%, as compared to a router for the flat network. This work also proposes a new possibility for increasing the number of nodes available for subnet-to-subnet interfaces, while keeping the properties of hierarchical deadlock-freedom. We evaluate and discuss the communication performance in a 2-level hierarchical network for various subnet interface set-ups and traffic situations. A cycle accurate simulator has been developed and used for this purpose.

Complexity of designing large and complex NoCs can be reduced/managed by using the concept of hierarchical networks. In this paper, we propose a methodology for design of deadlock free routing algorithms for hierarchical networks, by combining routing algorithms of component subnets. Specifically, our methodology ensures reachability and deadlock freedom for the complete network if routing algorithms for subnets are deadlock free. We evaluate and compare the performance of hierarchical routing algorithms designed using our methodology with routing algorithms for corresponding flat networks. We show that hierarchical routing, combining best routing algorithm for each subnet, has a potential for providing better performance than using any single routing algorithm. This is observed for both synthetic as well as traffic from real applications. We also demonstrate, by measuring jitter in throughput, that hierarchical routing algorithms leads to smoother flow of network traffic. A router architecture that supports scalable table-based routing is briefly outlined.

The simplicity of regular mesh topology NoC architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology can not ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.

Region concept helps to accommodate cores larger than the tile size in mesh topology NoC architectures. In addition, it offers many new opportunities for NoC design, as well as provides new design issues and challenges. The most important among these is the design of a deadlock free routing algorithm. In this paper, we present and compare two routing algorithms for mesh topology NoC with regions. The first algorithm is borrowed from the area of fault tolerant networks and is adapted for the NoC context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases.

A bridge will be required to interface a multi-core SoC, built using NoC paradigm, to the external world through Internet. In this paper we discuss and compare options for implementation of such a bridge. We have modeled one option in order to study the performance of the bridge with respect to buffer sizes and communication traffic rates. Our study shows that small buffer in the bridge is sufficient to achieve a bandwidth of at least 10 Mbits/s.

An efficient routing algorithm is important for large on-chip networks [network-on-chip (NoC)] to provide the required communication performance to applications. Implementing NoC using table-based switches provide many advantages, including possibility of changing routing algorithms and fault tolerance, due to the option of table reconfigurations. However, table-based switches have been considered unsuitable for NoCs due to their perceived high area and power consumption. In this paper, we describe the region-based routing (RBR) mechanism which groups destinations into network regions allowing an efficient implementation with logic blocks. RBR can also be viewed as a mechanism to reduce the number of entries in routing tables. RBR is general and can be used in conjunction with any adaptive routing algorithm. In particular, we have evaluated the proposed scheme in conjunction with a general routing algorithm, namely segment-based routing (SR) and an application specific routing algorithm (APSRA) using regular and irregular mesh topologies. Our study shows that the number of entries in the table is significantly reduced, especially for large networks. Evaluation results show that RBR requires only four regions to support several routing algorithms in a 2-D mesh with no performance degradation. Considering link failures, our results indicate that RBR combined with SR is able to tolerate up to 7 link failures in an 8times8 mesh. RBR also reduces area and power dissipation of an equivalent table-based implementation by factors of 8 and 10, respectively. Moreover, the degradation in performance of the network is insignificant when using APSRA combined with RBR.

Efficient on-chip communication is very important for exploiting enormous computing power available on a multi-core chip. Network on Chip (NoC) has emerged as a competitive candidate for implementing on-chip communication. Routing algorithms significantly affect the performance of a NoC. Most of the existing NoC architectural proposals advocate distributed routing algorithms for building NoC platforms. Although source routing offers many advantages, researchers avoided it due to its apparent disadvantage of larger header size requirement that results in lower bandwidth utilization. In this paper we make a strong case for the use of source routing for NoCs, especially for platforms with small sizes and regular topologies. We present a methodology to compute application specific efficient paths for communication among cores with a high degree of load balancing. The methodology first selects the most appropriate deadlock free routing algorithm, from a set of routing algorithms, based on the application’s traffic patterns. Then the selected (possibly adaptive) routing algorithm is used to compute efficient static paths with the goal of link load balancing. We demonstrate through simulation based evaluation that source routing has a potential of achieving higher performance, for example up to 28% lower latency even at medium load , as compared to distributed routing.  A simple scheme is proposed for encoding of router ports to reduce the header overhead. A generic simulator was developed for evaluation and performance comparison between source routing and distributed routing. We also designed a router to support source routing for mesh topology NoC platforms.

In this paper, we present a methodology to specialize the routing

algorithm in routing table based NoC routers. It tries to maximize the communication performance while ensuring deadlock free routing for an application. We demonstrate through analysis that routing algorithms generated by our methodology have higher adaptiveness as compared to turn-model based deadlock free routing algorithms for a mesh topology NoC architecture. Performance evaluation is carried out by using a flit-accurate simulator on traffic scenarios generated by both synthetic and real applications. Average delay is considered as performance index for comparison purposes. The routing algorithms generated by the proposed methodology outperforms deterministic and

adaptive routing algorithms. As compared to deterministic XY routing algorithm and adaptive Odd-Even routing algorithm we observe an improvement in delay close to 50% and 30% on average respectively.

In this paper we present a methodology to develop efficient and deadlock free routing algorithms for Network-on-Chip (NoC) platforms which are specialized for an application or a set of concurrent applications. The proposed methodology, called application specific routing algorithm (APSRA), exploits the application specific information regarding pairs of cores which communicate and other pairs which never communicate in the NoC platform to maximize communication adaptivity and performance. The methodology also exploits the known information regarding concurrency/non-concurrency of communication transactions among cores for the same purpose. We demonstrate, through analysis of adaptivity as well as simulation based evaluation of latency and throughput, that algorithms produced by the proposed methodology give significantly higher performance as compared to other deadlock free algorithms for both homogeneous as well as heterogeneous 2D mesh topology NoC systems. For example, for homogeneous mesh NoC, APSRA results in approximately 30% less average delay as compared to odd-even algorithm just below saturation load. Similarly the saturation load point for APSRA is significantly higher as compared to other adaptive routing algorithms for both homogeneous and non-homogeneous mesh networks.

A future NoC architecture must be general enough to allow volume production and must have features to specialize and configure to match and meet application's performance requirements. In this report, we present a methodology to specialize the routing algorithm in NoC routers to optimize its communication performance while ensuring deadlock free routing. Duato's theory of deadlock free routing is extended to incorporate application's communication requirements to

improve routing adaptiveness. We demonstrate through analysis and modeling and evaluation that routing algorithms produced by our methodology have higher adaptiveness and higher performance as compared to general purpose deadlock free routing algorithms.

Although adaptive routing algorithms promise higher communication performance, as compared to deterministic routing algorithms, they suffer from the out-of-order packet delivery problem. In the context of Network on Chip, the area and computational overhead of ordering packets at the destination is high and may reverse any gain achieved through the use of adaptivity of the routing algorithm. In this paper, we describe a novel scheme for ensuring in-order packet delivery while retaining the performance advantages of adaptive routing. The hardware architecture of a router that supports the proposed scheme is described. Although the basic idea in our proposal is topology independent we evaluate and compare the performance of our scheme with both deterministic as well as adaptive routing algorithms for 2D mesh NoC. As compared to the XY routing algorithm, our technique significantly reduces the packet delay and improves the saturation point. The impact on router area and power dissipation is also discussed. Although the power consumption of routers increase, the energy consumption per flit increases less than 2% on average, since the higher performance allows for draining more traffic during a certain time window.

General purpose routing algorithms for a network-on-chip (NoC) platform may not be able to provide sufficient performance for some communication intensive applications. This may be because of low adaptivity offered by a general purpose routing algorithm resulting in some links getting highly congested. In this study the authors demonstrate that it is possible to design highly efficient application-specific routing algorithms which distribute traffic more uniformly by using information regarding applications communication behaviour (communication topology and communication bandwidth). The authors use off-line analysis to estimate expected load on various links in the network. The result of this analysis is used along with the available routing adaptivity in each router to distribute less traffic to links and paths which are expected to be congested. The methodology for application-specific routing algorithms is extended to incorporate these features to design highly adaptive deadlock-free routing algorithms which also distribute traffic more uniformly and reduce network congestion. The authors discuss architectural implications and analyse area and power overheads of the proposed approach on the design of a table-based NoC router.

The communication infrastructure of a complex multicore system-on-a-chip is getting an increasing fraction of the overall chip area. According to the International Technology Roadmap for Semiconductors, killer defect density does not decrease over successive technology generations. For this reason, the probability that a manufacturing defect affects the communication system is predicted to increase. In this paper, we deal with manufacturing defects which affect the links in a network on-chip-based interconnection system. The goal of this paper is to show that by using effective routing functions, supported by appropriate selection policies and with a limited amount of extra logic in the router, it is easy to exploit partially faulty links to improve the performance of the system. We show that, instead of discarding partially faulty links, they can be used at reduced capacity to improve the distribution of the traffic over the network, yielding performance and power improvements. We couple an application-specific routing function with a set of selection policies which are aware of link fault distribution and evaluate them on both synthetic traffic and a real complex multimedia application. We also present an implementation of the router, augmented with the extra logic, to support both the proposed selection functions and the transmission of messages over partially faulty links. We analyze the router in terms of silicon area, timing, and power dissipation.

One way to specialize a general purpose multi-core chip built using

NoC principles is to provide a mechanism to configure an application

specific deadlock free routing algorithm in the underlying

communication network. A table in every router, implemented using a

writable memory, can provide a possibility of specializing the routing

algorithm according to the application requirements. In such an

implementation the cost (area) of the router will be proportional to

the size of the routing table. In this paper, we propose a method to

compress the routing table to reduce its size such that the resulting

routing algorithm remains deadlock free as well as has high

adaptivity. We demonstrate through simulation based evaluation that

our application specific routing algorithm gives much higher

performance, in terms of latency and throughput, as compared to

general purpose algorithms for deadlock free routing. We also show

that a table size of two entries for each output port gives

performance within 3\% of the uncompressed table.

In this paper we make a case for the use of NoC

paradigm to develop future FPGAs in which large computational

blocks (cores) are connected to each other through

a packet switched communication network. We propose a

methodology to develop efficient and deadlock free routing

algorithms for such NoC platforms which can be specialized

for an application or a set of concurrent applications.

Application specific topology of communicating cores as

well as information about their communication concurrency

over time is exploited to maximize communication adaptivity

and performance. We demonstrate, both through analysis

of adaptivity as well as simulation based evaluation

of latency and throughput, that our algorithm gives significantly

higher performance as compared to general purpose

deadlock free algorithms like XY and Odd-Even.