Claims:We claim:
1. A system for efficient and high throughput Network-on-Chip (NOC) architecture comprising of NoC router (1000) integrated in a manner so as to provide low or nominal latency and is area and power efficient, wherein said NOC router (1000) comprises of at least one Integrated arbitration and switching unit (1100), said integrated arbitration and switching unit (1100) comprising of
- plurality of input ports (IP0, IP1…. IPN)for receiving input data (D0, D1, D2,…DN),
- plurality of output ports (OP0, OP1, OP2, …. OPN) for obtaining desired output data,
- at least one weight generation logic unit (1110) for generating the weights (W0, W1, W2, Wi, Wj….. WN) of the corresponding input data (D0, D1, D2, Di, Dj…DN) using request vector (R) and priority vector (P) in a manner that input data (Dj) corresponding to highest weight (Wj>i) has higher priority,
- at least one MUX based- switching block (1120) comprises of
- plurality of sets of MAX units (1121) and MUX units (1122A, 1122B) being deployed in multiple stages (S1, S2.. SN) in a manner that the first stage (S1) is being connected to input ports (IP0, IP1, IP2… IPN) and said weight generation logic unit (1110) while the last stage (SN) is being connected to output ports (OP0, OP1..OPN),
wherein said n stages of said MUX-based switching block (1120) are cascaded in a manner so as to form an integrated MAX tree (1120A) and MUX tree (1120B) such that said integrated MAX tree (1120A) and MUX tree (1120B) is capable of being traversing the input data corresponding to the highest weight from input ports to the output port in power and area efficient manner.
2. The system for efficient and high throughput NoC architecture as claimed in claim 1 wherein each said MAX unit (1121) corresponding to each said stage (S1, S2, Si, Sj, SN) has at least two input lines (SR, SL) for receiving at least two weights i.e. left weight and right weight (WR, WL) of corresponding input data ((Di, Dj)) from preceding stage and generating at least one flag bit signal ( F) corresponding to highest data weight (Wi>j) and at least two output signals (MAX(0), MAX(1)) which acts as input line to the MAX unit (1121) of the next stage (Sj>i).

3. The system for efficient and high throughput NoC architecture as claimed in claim 1 and claim 2, wherein said MUX units (1122A, 1122B) of each stage (Si) comprising of at least two input data lines for capturing the subset of input data (D0, D1,D2..DN) from the preceding stage (Si-1), at least one select line (SL) for receiving at least one flag bit signal (F) from at least one MAX unit (1121), and at least one output line,
wherein said MUX unit (1122A, 1122B) is capable of traversing the input data (Di) corresponding to higher weight (Wi) from the preceding Stage (Si-1) to proceeding stage (Si+1) at said output line based on said received flag signal (F) at its select line (SL).

4. The system for efficient and high throughput NoC architecture as claimed in claim 3 wherein said select line (SL) of each said MUX unit (1122A, 1122B) of each said stage (Si) is capable of receiving the flag bit signal selected from at least one MAX unit of (1121) same stage (Si) or at least one MAX unit (1121) from preceding stage (Si-1) and at least one MAX unit (1121) of same stage (Si).

5. The system for efficient and high throughput NoC architecture as claimed in claim 1 wherein said MUX tree (1120B) in said MUX based switching block (1120) is designed using area reconstruction of MUX tree (1120B)

6. The system for efficient and high throughput NoC architecture as claimed in claim 1 wherein throughput and latency is improved in said integrated arbitration and switching unit (1100) by deploying wave pipelining technique between said stages (S1.. SN) (Fig. 4).
, Description:FIELD OF THE INVENTION
The present invention relates to a system of an efficient and high throughput Network-on-Chip (NoC) architecture. The present invention further relates to novel methods of an area and power efficient and high throughput Network-on-Chip architecture by area optimizing and wave-pipelining of integrated arbitration and switching blocks of NoC router.

BACKGROUND OF THE INVENTION
The innovation is progressing to replace planar metalcommunication structures by energy-efficient and high-performance communication technologies. The major challenges in wire-based traditional on-chip communication networks are the high latency and power consumption of their multi-hop links. The system performance can be significantly improved by inserting single-hop long range wireless links in place of multi-hop wireline communication.

Communication plays a crucial role in the design and performance of multi-core Systems-on-Chip (SoC). Networks-on-Chip (NoC) has been proposed as a promising solution to simplify and optimize SoC design. The NoC however has its own challenges. The goal in on-chip communication system design is to transmit data with low latencies and high throughput using the least possible power and resources.

Remarkable research is going on in order to harvest the potential of NoC communication, including system architecture, circuit design, device fabrication and CAD tool development.

With the number of cores of chip multiprocessors (CMPs) rapidly growing as technology scales down, connecting the different components of a CMP in a scalable and efficient way becomes increasingly challenging.

According to Daniel Sanchez, George Michelogiannakis, and Christos Kozyrakis, Stanford University, the interconnect has a large impact on performance, as it is responsible for 60% to 75% of the miss latency. Latency, and not bandwidth, is the primary performance constraint, since, even with many threads per core and workloads with high miss rates, networks with enough bandwidth can be efficiently implemented for the system scales we consider.

To connect the increasing number of cores in a scalable way, researchers are evaluating packet-switched networks-on-chip (NoC) [Dally and Towles 2001; De Micheli and Benini 2002; Owens et al. 2007]. Continuous scaling of CMOS technology makes it possible to integrate a large number of heterogeneous devices that need to communicate efficiently on a single chip. For this efficient routers are needed to communicate between these devices.

According to A.S. Kale and M.A. Gaikwad, “Design and Analysis of On-Chip Router for Network on Chip,” International Journal of Computer Trends and Technology, vol. 9, no. 6, pp. 182-186, 2011, the heart of an on-chip network is the router, which undertakes crucial task of co-ordinating the data flow. The router operation revolves around two fundamental regimes: (a) the datapath and (b) the associated control logic. It is very important that design of a NoC router should be as simple as possible because implementation cost increases with an increase in the design complexity of a router.
System on Chip (SoC) grows in complex manner with the advancement in semiconductor technology which enables to integrate dozens of cores on a chip. A sharp increase in the number of cores calls for new communication architecture. Network on Chip (NoC) has emerged as the design paradigm for design of scalable on-chip communication architectures by providing better structure and modularity.

System-on-Chip (SoC) is a VLSI device where a large number of IP cores and embedded software are integrated on a single integrated chip. As the number of cores integrated on a chip increases, the bus interconnections used in it create issues regarding the complexity, contention, power, area and delay.

The networking concept introduced in the form of Network on Chip (NoC) architectures catered to these issues to a great extent. Manycore or Multicore SoCs are able to meet reliability, performance and area requirements with the help of NoC technology.

The NoC router is the key contributor to the performance of the NoC. The NoC router implemented with IAS architecture as described in the invention disclosure results in efficient design. NoC router implemented with WPIAS architecture as described in the invention disclosure results in High performance design. Any SoC or Manycore or Multicore integrated device which uses NoC technology can use this invention to reduce area and power consumption at high frequency and improved performance. All IC design organizations and manufacturers can use this design.

OBJECTS AND SUMMARY OF THE INVENTION
The main object of the present invention is to provide a system for efficient and high throughput Network-on-Chip architecture.

Another object of the present invention is to provide novel methods of a system for efficient and high throughput Network-on-Chip architecture.

Yet another object of the present invention is to provide a method for integrating arbitration and switching blocks of NoC router to achieve an efficient and high throughput Network-on-Chip architecture.

Yet another object of the present invention is to provide an area efficient and power efficient Network-on-Chip architecture.

Yet another object of the present invention is to provide Network-on-Chip architecture with minimal or low latency and high throughput.

Accordingly, the present invention relates to an efficient and high throughput Network-on-Chip architecture. The present invention further relates to novel methods of an efficient and high throughput Network-on-Chip architecture by integrating arbitration and switching blocks of NoC router.

The NoC routers route the packets of information from one Processing Element (PE) to another processing element on a chip. The NoC router comprises of input buffer, routing computation unit, arbiter, switching block and output buffer and directs the traffic from one PE to another PE through interconnection links. In the router, the arbiter and crossbar switch can be implemented either in distributed approach (one per port) or in centralized approach (one per router).

The main blocks of a router are buffers, arbiter and the switching block. The arbiter and the switching block are integrated to reduce the area and the power consumption of the NoC router (Fig. 1). The performance of an NOC router is defined by latency and throughput and high performance NOC router aims to achieve low power consumption, high data rates, and minimal area usage.

The invention disclosure describes two novel methods of integrating arbitration and switching blocks of NoC router using distributed approach. In the first method, NoC router uses area reconstruction of MUX trees in order to minimize area and power which results in novel Integrated Arbitration and Switching (IAS) architecture. Two stages of 2:1 MUX trees are replaced by single stage 3:1 MUX tree with 2 select lines which reduces area and power. In the second method, NoC router uses wave pipelining technique in order to maximize performance which results in Wave Pipelined Integrated Arbitration and Switching (WPIAS) architecture. These methods are applicable for 2D NoC router and it is applicable for 3D NoC router structure as well.

The advantage of using IAS architecture in NoC router is low power consumption and reduced area in chip at nominal latency and throughput. The advantage of using WPIAS architecture is low latency and increased throughput at a marginal cost of area and power consumption.

BRIEF DESCRIPTION OF DRAWINGS:
Fig. 1 depicts NoC architecture
Fig. 2 depicts MAX unit.
Fig. 3 depicts Integrated Arbitration and Switching architecture (IAS)
Fig. 4 depicts Wave Pipelined Integrated and Switching architecture (WPIAS)
Fig. 5 depicts Comparative analysis of three architectures MARX, IAS and WPIAS in terms of area and latency.
Fig. 6 depicts Comparative analysis of three architectures MARX, IAS and WPIAS in terms of area and throughput
Fig. 7 depicts Comparative analysis of three architectures MARX, IAS and WPIAS in terms of power and latency
Fig. 8 depicts Comparative analysis of three architectures MARX, IAS and WPIAS in terms of power and throughput.

DETAILED DESCRIPTION OF THE INVENTION
The present invention relates to an efficient and high throughput Network-on-Chip architecture. The present invention further relates to novel methods of an area and power efficient and high throughput Network-on-Chip architecture by area optimizing and wave-pipelining of integrated arbitration and switching units (1100) of NoC router.

The most important communication backbone in NoC is the router (1000). NoC routers route the packets of information from one Processing Element (PE) to another processing element on a chip. The NoC router (1000) comprises of input buffer, routing computation unit, arbiter, switching block and output buffer. The router connects 5 input/output ports (North, South, East, West and Local) and directs the traffic from one PE to another PE through interconnection links. In the router, the arbiter and crossbar switch can be implemented either in distributed approach (one per port) or in centralized approach (one per router).
The main blocks of a router are buffers, arbiter and the switching block. The arbiter and the switching blocks are integrated to reduce the area and the power consumption of the NoC router (1000) (Fig. 1). The performance of an NOC router is defined by latency and throughput and high performance NOC router aims to achieve low power consumption, high data rates, and minimal area usage.

The invention disclosure describes two novel methods of integrating arbitration and switching units (1100) of NoC router (1000) using distributed approach. In the first method, NoC router (1000) uses area reconstruction of MUX trees in order to minimize area and power which results in novel Integrated Arbitration and Switching (IAS) architecture. In the second method, NoC router (1000) uses wave pipelining technique in order to maximize performance which results in Wave Pipelined Integrated Arbitration and Switching (WPIAS) architecture. These methods are applicable for 2D NoC router and it is applicable for 3D NoC router structure as well.

The advantage of using IAS architecture in NoC router (1000) is low power consumption and reduced area in chip at nominal latency and throughput. The advantage of using WPIAS architecture is low latency and increased throughput at a marginal cost of area and power consumption.

(1) Integrated Arbitration and Switching architecture (IAS):
The arbiter and the multiplexer blocks used in NoC router (1000) are integrated to form integrated arbitration and switching unit (1100) with reduced area and power consumption. This architecture uses round robin algorithm as a part of arbitration to avoid the conflict among the inputs.
Weight generation logic unit (1110)
The arbitration based on round robin algorithm is done by first calculating weights (W). The main parameters to be considered for calculating these weights are the request vector (R) and the priority vector (P). The weight generation logic unit (1110) generates the weights (W0, W1, W2, Wi, Wj….. WN) of the corresponding input data (D0, D1, D2, Di, Dj…DN) using request vector (R) and priority vector (P) in a manner that input data (Dj) corresponding to highest weight (Wj>i) has higher priority.

Table 1 provides an example representing the calculation of weights using request and priority vector.

Table 1:
Input ports (Dj) 7 6 5 4 3 2 1 0
Request Vector (R)
Priority Vector (P) 0 1 1 0 0 1
1 1 1 1 1 1 0 1
0 0
Weights (W) 1 3 3 1 1 3 0 2
High priority segment Low priority segment

In a request vector, a bit corresponding to a particular input port is set, only if a data is waiting in that port for transmission. In a priority vector, a bit corresponding to a particular input port is set, only if a data transmitted through that input port has priority. The weight (W) is calculated using the relation 2Ri+Pi, as shown in the Table 1. The weights are then converted into thermometer codes as shown in the Table 2. If there is no request at the input port then the weight will either 1 or 0.

Table 2: Weights and its Thermometer code
Weight Thermometer code in Bits
3 11
2 01
1 00
0 00

Arbitration logic
The arbitration is done based on the basic principle of priority based round robin policy as shown in Table 1. The search for the input port begins from the highest priority input port to the lowest priority input port and vice versa in a continuous cyclic manner. This logic is implemented in MAX tree which is present in IAS architecture.

The MUX based- switching block (1120) comprises of plurality of sets of MAX units (1121) and MUX units (1121A, 1121B) being deployed in multiple stages (S1, S2.. SN) in a manner that the first stage (S1) is connected to input ports (IP0, IP1, IP2… IPN) and said weight generation logic unit (1110) while the last stage (SN) is connected to output ports (OP0, OP1..OPN). Said n stages of said MUX-based switching block (1120) are cascaded in a manner so as to form an integrated MAX tree (1120A) and MUX tree (1120B) such that said integrated MAX tree (1120A) and MUX tree (1120B) is capable of being traversing the input data corresponding to the highest weight from input ports to the output port in power and area efficient manner.

The MAX tree (1120A) consists of MAX units (1121) (Fig. 2). The MAX units (1121) corresponding to each said stage (S1, S2, Si, Sj, SN) has at least two input lines (SR, SL) for receiving at least two weights i.e. left weight and right weight (WR, WL) of corresponding input data ((Di, Dj)) from preceding stage and generating at least one flag bit signal ( F) corresponding to highest data weight (Wi>j) and at least two output signals (MAX(0), MAX(1)) which acts as input line to the MAX unit of the next stage (Sj>i).

The thermometer code equivalent to a weight is assigned to the input lines of MAX unit. The two output lines are the highest weight and the flag bit. The flag bit indicates which input has the highest weight. If the flag bit is 1 then the left input has higher weight otherwise right input has the higher weight (Fig. 2).

The output of the flag bit is used as select line on the MUX tree (1120B). The data is traversed to the output port using a MUX tree (1120B). The MUX tree (1120B) is designed using Multiplexer Area-Minimization algorithm as shown in Fig. 3. The select line of each MUX unit (1122A, 1122B) is the flag output bit coming from the MAX unit (1121). The data coming from the higher weight side will be passed through the MUX tree (1120B) to the next layer of the architecture. After successful arbitration and switching, the desired data from the input port is obtained at the output port.

The MUX units (1122A, 1122B) of each stage (Si) comprising of at least two input data lines for capturing the subset of input data (D0, D1,D2..DN) from the preceding stage (Si-1), at least one select line (SL) for receiving at least one flag bit signal (F) from at least one MAX unit (1121), and at least one output line.
Said MUX unit (1122A, 1122B) is capable of traversing the input data (Di) corresponding to higher weight (Wi) from the preceding Stage (Si-1) to proceeding stage (Si+1) at said output line based on said received flag signal (F) at its select line (SL). The select line (SL) of each said MUX unit (1122A, 1122B) of each said stage (Si) is capable of receiving the flag bit signal selected from at least one MAX unit (1121) of same stage (Si) or at least one MAX unit (1121) from preceding stage (Si-1) and at least one MAX unit (1121) of same stage (Si).

(2) Wave Pipelined Integrated Arbitration and Switching architecture (WPIAS)
In the IAS architecture, the area and the power consumption are reduced, but the throughput and latency remains same. To improve the throughput, a slight modification is done to the IAS unit (1100) by using the wave pipelining concept.

Wave pipelining is a form of pipelining where all the intermediate registers in pipeline are eliminated and the delays are balanced. In each stage, the difference between the first output and the last is minimised. By implementing this concept in IAS architecture, a new architecture called Wave Pipelined Integrated Arbitration and Switching (WPIAS) architecture was developed as shown in Fig. 4.

The condition for generating the clock (TCK) in WPIAS architecture is
(Tmax /N) < TCK < ( Tmax /(N-1))
Where Tmax = Th + TD + TRF + Ts +?C
Th = Hold time for the registers
TD = Propagation delay for the registers
TRF = Worst-case fall or rise time in the logic
Ts = Setup time for registers
?C = Worst case clock skew
N= Number of waves in the system

Advantages and improvements over existing methods, devices or materials
Advantages and improvements over the existing Merged Arbiter and Multiplexer architecture (MARX) are
a) IAS architecture minimizes the area and power consumption by maintaining marginal latency and throughput.
b) WPIAS architecture minimizes the latency and increases the throughput at marginal cost of area and power consumption.

Potential Commercial applications
System on Chip (SoC) grows in complex manner with the advancement in semiconductor technology which enables to integrate dozens of cores on a chip. A sharp increase in the number of cores calls for new communication architecture. Network on Chip (NoC) (1000) has emerged as the design paradigm for design of scalable on-chip communication architectures by providing better structure and modularity. NoC router (1000) implemented with IAS architecture as described in the invention disclosure results in efficient design. NoC router (1000) implemented with WPIAS architecture as described in the invention disclosure results in High performance design. Any SoC or Manycore or Multicore integrated device which uses NoC technology can use this invention to reduce area and power consumption at high frequency and improved performance. All IC design organizations and manufacturers can use this design.

Experimental Results:
Architectures described in the invention disclosure are designed using Verilog HDL and synthesized using Cadence RTL compiler using 45nm technology for area and power calculations. The throughput and latency are obtained from simulation results at a clock frequency of 10MHz.The data transmitted through each input port is of 8 bits. The existing Merged Arbiter and Multiplexer architecture (MARX) is compared with the IAS and WPIAS architectures in terms of area, power, latency and throughput. Table. 3 gives the comparative analysis of MARX, IAS and WPIAS architectures in terms of area, power, latency and throughput for a 16 input to 1output implementation.

Table 3. Comparative analysis of the MARX, IAS and WP-IAS units for a 16 input to 1 output implementation

16:1

AREA
(µm2)

POWER
(nW)

LATENCY(ns)

THROUGH-
PUT(Mbps)

MARX Unit 1212 17920.817
300 24
IAS Unit 1005 10280.030
300 24
WPIAS Unit 1141 21,291.673
200 64

Fig. 5 and Fig. 6 gives the comparative analysis of MARX, IAS and WPIAS architectures for area, latency and throughput for 16 input to 1 output implementation.

Fig. 7 and Fig. 8 gives the comparative analysis of MARX, IAS and WPIAS architectures for power, latency and throughput for 16 input to 1 output implementation. NoC router(1000) with IAS architecture has reduced power and area consumption when compared to the existing MARX architecture. Also the NoC architecture with WPIAS architecture had increased throughput and reduced latency when compared to the existing MARX architecture.