Interconnection Networks and Networks-on-Chip

Introduction and Context

Modern computer systems are increasingly parallel. A multicore processor, many-core accelerator, graphics processor, or chiplet-based system may contain hundreds or thousands of computational, storage, and control elements. The performance of such a system depends not only on the speed of individual cores but also on how efficiently they exchange data. The communication fabric that connects processors, memories, caches, accelerators, and input/output components is therefore a first-class architectural resource.

An interconnection network is a structured collection of links, switches, interfaces, and control mechanisms that transports information among system endpoints. In traditional multiprocessors, the network may connect processors to shared memory or to one another. In a system-on-chip (SoC), the same problem exists inside a single silicon die, where it is usually addressed by a network-on-chip (NoC).

NoCs replace increasingly difficult-to-scale buses and crossbars with packet-switched or circuit-switched communication structures. Their design affects latency, throughput, energy consumption, reliability, programmability, security, and physical implementation. At postgraduate level, NoCs should therefore be studied simultaneously as communication networks, microarchitectural systems, and physical VLSI structures.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Explain the architecture and terminology of interconnection networks and NoCs.
2. Compare buses, crossbars, multistage networks, direct networks, and indirect networks.
3. Analyze topology, routing, flow control, buffering, switching, and arbitration.
4. Compute basic latency, bandwidth, throughput, and offered-load relationships.
5. Evaluate NoC designs using performance, energy, area, reliability, and security criteria.
6. Apply routing and traffic-analysis principles to a realistic many-core design problem.
7. Discuss contemporary directions such as chiplet interconnects, heterogeneous NoCs, and machine-learning-assisted optimization.

1. Fundamental Concepts and Terminology

A network contains endpoints (also called nodes or processing elements), routers or switches, and physical channels. An endpoint injects a message into the network and eventually receives it. A message is commonly divided into one or more packets. A packet may be divided into flow-control units called flits. The first flit is often called the head flit, intermediate units body flits, and the final unit the tail flit.

Important terms include:

• Link: A physical connection carrying symbols between adjacent components.
• Channel: A logical or physical resource in one direction; a bidirectional link may contain two channels.
• Port: A router interface connected to a local endpoint or neighboring router.
• Hop: One router-to-router traversal.
• Path: The ordered sequence of links and routers used by a packet.
• Topology: The structural arrangement of nodes and links.
• Routing: The function that selects an output path for a packet.
• Flow control: The mechanism that prevents a sender from overrunning available buffering.
• Congestion: Competition among packets for limited network resources.
• Deadlock: A condition in which packets wait indefinitely for resources held by one another.
• Livelock: Continued movement without eventual delivery.
• Starvation: Indefinite postponement of a packet or requester despite network activity.

A useful distinction is between communication semantics and network implementation. A cache-coherence protocol may require a request, response, and invalidation message; the NoC determines how those messages are transported. Thus, network correctness includes both packet delivery and compatibility with the higher-level protocol.

2. Classification of Interconnection Networks

2.1 Shared buses

A bus is a shared medium to which multiple devices attach. Arbitration determines which device may transmit. Buses are simple and inexpensive for small systems, but bandwidth is shared and electrical loading increases with distance and device count. A bus is consequently poorly suited to large many-core systems.

2.2 Crossbars

A crossbar provides a potentially dedicated path between each input and output. For an N-input, N-output crossbar, the switching fabric has O(N²) connection points. It offers high parallelism and predictable single-stage traversal, but area, wiring, power, and arbitration complexity grow rapidly.

2.3 Multistage interconnection networks

Multistage networks use several layers of small switches. They reduce hardware relative to a full crossbar but may be blocking: a free input and free output can still be unable to communicate because intermediate switch resources are occupied. Examples include omega, butterfly, baseline, and Clos-type networks.

2.4 Direct and indirect networks

In a direct network, each router is associated with an endpoint and communicates directly with neighboring routers. Meshes, tori, rings, and hypercubes are examples. In an indirect network, endpoints connect to switching elements, but not every switch necessarily contains a processor; classic multistage networks and centralized crossbars belong to this class.

2.5 Static and dynamic networks

A static topology has fixed physical connections. A dynamic network changes logical connections through switches or configuration. Most NoCs use a fixed physical topology with dynamic packet paths.

3. Topology and Its Consequences

Topology determines possible paths, router radix, wiring length, fault tolerance, and scaling behavior. Common NoC topologies include:

For a rectangular 2D mesh with R rows and C columns, the Manhattan distance between coordinates (r₁,c₁) and (r₂,c₂) is:

Here D is the minimum number of link traversals when movement is restricted to horizontal and vertical links. The maximum distance, or diameter, is:

These expressions assume a regular mesh, unit-cost links, and no faults. In a torus, distance is the sum of the shorter wrapped and unwrapped coordinate distances; hence its diameter is lower than that of a mesh of the same dimensions.

Topology must also be evaluated physically. A mathematically attractive topology may require long global wires, excessive vias, or difficult clock and power distribution. For this reason, 2D meshes and hierarchical variants remain common even when alternatives have better graph-theoretic diameter.

Figure: A regular 4 × 4 two-dimensional mesh NoC.

4. Router Microarchitecture

A typical packet-switched router contains input buffers, route-computation logic, virtual-channel state, a switch allocator, a crossbar, and link interfaces. A packet arriving at an input is first stored or forwarded. The router computes the desired output, competes for that output, traverses the crossbar, and is transmitted over the selected link.

A router may use input buffering, output buffering, or combined buffering. Input buffering is common because it is easier to implement physically, but it can suffer from head-of-line blocking: a blocked packet at the head of an input queue prevents later packets destined for other outputs from advancing.

Virtual channels (VCs) divide one physical channel into independently managed logical channels. Each VC has its own buffer and control state. VCs can reduce head-of-line blocking and, when assigned carefully, break cyclic resource dependencies that cause deadlock. They do not automatically increase physical link bandwidth; they improve sharing and control.

The router pipeline may include route computation, virtual-channel allocation, switch allocation, switch traversal, and link traversal. A deeper pipeline can support a higher clock frequency but increases zero-load latency and may complicate flow control.

5. Switching and Flow Control

5.1 Switching techniques

In store-and-forward switching, an intermediate router receives the complete packet before forwarding it. Buffer requirements are high, and latency increases with packet length and hop count.

In virtual cut-through, forwarding begins once the output is available, but a packet may occupy substantial downstream storage if blocked.

In wormhole switching, a packet is divided into flits and only a small prefix may occupy each router. Wormhole switching reduces buffer requirements, but blocked packets can hold resources across several routers, making deadlock analysis essential.

5.2 Flow-control models

• Credit-based flow control: A receiver grants credits representing available buffer slots. The sender transmits only when it has credit.
• On/off flow control: A receiver signals whether transmission may continue. It is simpler but less precise.
• ACK/NACK or retry flow control: Data may be retransmitted after error detection; useful where links are unreliable or long.
• Elastic buffering: Queues absorb timing variation and decouple neighboring pipeline stages.

If a buffer has B flit slots and the sender has C credits, the sender may have at most C outstanding flits under a conventional credit scheme, where C should not exceed the receiver’s usable capacity. Credit-return latency must be considered: excessive round-trip delay can leave a link temporarily idle even when the receiver has space.

6. Routing Algorithms and Correctness

Routing may be deterministic, adaptive, or oblivious. Deterministic routing selects one path for a source-destination pair. Adaptive routing chooses among permitted paths based on congestion or faults. Oblivious routing may use a predetermined distribution independent of current congestion.

Dimension-order routing

In a 2D mesh, XY routing first resolves the x-coordinate and then the y-coordinate, or vice versa. It is simple, deterministic, and deadlock-free under conventional wormhole assumptions because channel dependencies are ordered: all channels in one dimension are acquired before channels in the next. Its cost is reduced path diversity.

Adaptive routing

Adaptive routing can avoid congested or faulty links. However, unrestricted adaptivity can create cyclic channel dependencies. Deadlock freedom requires a proof or a mechanism such as virtual-channel classes, turn restrictions, or an escape virtual channel using a known deadlock-free algorithm.

A routing algorithm should be judged by:

1. Correctness: Every legal packet reaches its destination.
2. Deadlock freedom: No cyclic resource dependency can persist indefinitely.
3. Livelock freedom: Packets are not diverted forever.
4. Path efficiency: Paths do not contain unnecessary hops.
5. Adaptivity: The algorithm can exploit alternate resources when safe.
6. Fault tolerance: Connectivity is maintained under specified failures.

7. Performance Analysis

7.1 Latency decomposition

A useful first-order model for a packet crossing h links is:

where T_packet is end-to-end latency; T_inj is injection and endpoint overhead; T_router is per-router processing latency; T_link is per-link traversal latency; T_serial is the time to serialize the packet; and T_queue is congestion-induced waiting. This is an approximation, not a universal law. Pipeline overlap, wormhole behavior, arbitration, and physical implementation may alter the terms.

If a packet contains L flits and a link transfers one flit per cycle, an uncontended wormhole path with h link traversals is often approximated by:

cycles, after ignoring router pipeline overhead. The first flit requires approximately h cycles to reach the destination, and the remaining L − 1 flits follow at one per cycle. This formula applies only to a fully pipelined, uncontended path with one-cycle link traversal and no extra router stages.

7.2 Bandwidth and throughput

For a link with width W bits and frequency f hertz, the raw one-direction bandwidth is:

bits per second, assuming one transfer per cycle and no encoding or protocol overhead. If each transfer carries useful payload fraction η, effective payload bandwidth is ηWf.

For a network with N nodes, average packet injection rate λ packets per node per cycle, and average packet length L flits, the offered load in flits per node per cycle is:

where ρ is dimensionless. This is offered load, not necessarily achieved throughput. Saturation occurs when demand exceeds the capacity available along one or more bottleneck resources.

Worked Example: Mesh distance and latency

Consider a 4 × 4 mesh. A packet travels from (0,1) to (3,3). Its Manhattan distance is:

Suppose the packet has 8 flits, each hop takes one cycle, and there is no queueing or additional router pipeline delay. The ideal wormhole estimate is:

If the link width is 128 bits and frequency is 1 GHz, raw link bandwidth is:

If protocol overhead leaves η = 0.75 useful payload efficiency, effective payload bandwidth is 96 Gb/s. The calculation assumes one 128-bit transfer per cycle and excludes coding, retransmission, and contention effects.

8. Traffic Patterns and Evaluation Methodology

NoC behavior depends strongly on traffic. Common synthetic patterns include:

• Uniform random: Destinations are independently and uniformly selected.
• Transpose: Coordinates are systematically exchanged, stressing particular paths.
• Hotspot: Many sources target one endpoint.
• Nearest neighbor: Communication is predominantly local.
• Bit complement: Destination bits are complements of source bits.
• Permutation traffic: Each source maps to a unique destination.

Uniform random traffic is useful for baseline comparison but may not represent cache coherence, GPU workloads, graph analytics, or AI tensor movement. A credible evaluation combines synthetic patterns with application traces.

Important metrics include average and tail latency, sustainable throughput, fairness, energy per flit, buffer occupancy, area, frequency, and reliability. The 99th-percentile latency can matter more than average latency in real-time or service-oriented systems. Simulation should report warm-up policy, injection rate, packet size, topology, routing algorithm, buffer capacity, and arbitration policy so that results are reproducible.

Analytical queueing models can provide insight, but NoCs violate many simple queueing assumptions because paths share resources, traffic may be bursty, and arbitration is discrete. Cycle-accurate simulation, RTL evaluation, FPGA prototyping, and post-layout measurement should be viewed as complementary rather than interchangeable methods.

9. Reliability, Security, and Quality of Service

As transistor dimensions shrink and systems become larger, transient faults, permanent link failures, crosstalk, timing variation, and thermal effects become important. Techniques include parity, cyclic redundancy checks, error-correcting codes, link-level retransmission, redundant paths, spare routers, and fault-aware routing. Reliability mechanisms introduce area, latency, and energy overhead, so protection should reflect application criticality.

NoCs also form a security boundary. A malicious or compromised component may inject excessive traffic, observe timing variations, exploit shared buffers, or impersonate a privileged endpoint. Defenses include traffic policing, isolation through virtual networks, access-control labels, encryption or authentication where appropriate, constant-rate or randomized scheduling for sensitive flows, and monitoring for denial-of-service behavior.

Quality of service (QoS) assigns differentiated treatment to traffic classes. Priority arbitration, bandwidth reservations, deadline-aware scheduling, and virtual networks can protect latency-sensitive traffic. Strict priority can cause starvation; weighted fair schemes improve fairness but require more state and calibration. QoS guarantees must specify the traffic model, maximum packet size, reserved capacity, and fault assumptions.

10. Design Trade-offs and Physical Implementation

NoC design is a multi-objective optimization problem. Increasing link width can reduce serialization time but increases wires, switching capacitance, and router area. More buffers can absorb bursts but consume leakage power and may increase congestion visibility delay. More virtual channels improve sharing and deadlock management but require allocation state and buffer storage.

A simplified dynamic-energy relationship is:

per switching event, where α is activity factor, C is effective switched capacitance, and V is supply voltage. This is a first-order model; leakage, short-circuit energy, clock power, and energy in repeaters are omitted. Longer global wires generally increase capacitance and may require repeaters.

Physical design must account for floorplan locality, metal-layer availability, thermal gradients, clock domains, voltage islands, and packaging. A topology that minimizes hop count may be inferior if it creates long wires. Technology scaling has also encouraged wire-aware and hierarchical NoCs, including concentrated meshes, express channels, local subnetworks, and wireless or optical research fabrics.

11. Applied Case: Illustrative AI Accelerator NoC

Background

Consider an illustrative 64-tile AI accelerator. Each tile contains a compute engine and local scratchpad. Workloads perform matrix multiplication and convolution, requiring repeated movement of activation tiles, weights, and partial sums.

Problem

A single shared bus cannot provide enough aggregate bandwidth. A full crossbar is impractical because of area and wiring. Traffic is not uniform: multicast-like weight distribution and reduction of partial sums create hotspots. Average latency is acceptable, but bursts cause high tail latency.

Analysis

A 2D mesh offers regular placement and short local wires, but ordinary unicast routing duplicates weight traffic and overloads central links. XY routing provides predictable deadlock-free behavior but lacks sufficient path flexibility. Small buffers reduce area but amplify sensitivity to burstiness.

Approach

The design adopts a concentrated 2D mesh with four compute tiles per router, separate virtual networks for requests, responses, and reductions, and a deterministic escape VC. Adaptive routing is permitted only within a deadlock-safe channel dependency scheme. Multicast packets are replicated at selected routers rather than at the source. Reduction traffic receives a reserved QoS class, while bulk weight traffic uses remaining capacity.

The evaluation uses application traces and synthetic hotspot tests. Metrics include average and 99th-percentile latency, delivered flits per cycle, energy per delivered byte, router area, and fairness among traffic classes.

Outcome

The design improves physical locality and prevents reduction traffic from being blocked indefinitely by bulk transfers. It does not eliminate congestion: multicast replication consumes router and link resources, and reserved capacity can be underutilized when reduction traffic is absent. The case demonstrates that a NoC must be co-designed with communication patterns, not selected solely from a topology catalogue.

Learning Points

1. Application traffic determines whether a theoretically scalable network is practically effective.
2. Deadlock avoidance and QoS must be designed together.
3. Tail latency and energy may reveal problems hidden by average throughput.
4. Physical placement and workload mapping are architectural decisions.

12. Contemporary Developments and Research Directions

Chiplet interconnects extend NoC principles across dies and packages. They require attention to longer links, protocol compatibility, die-to-die standards, packaging cost, and fault recovery. Heterogeneous NoCs connect CPUs, GPUs, neural accelerators, memory controllers, and security processors with different traffic and QoS requirements.

Photonic and wireless NoCs seek to reduce the cost of long-distance communication, but they face challenges in conversion energy, manufacturing variation, thermal sensitivity, and integration. Machine learning is being investigated for traffic prediction, routing, workload mapping, and dynamic voltage/frequency control. Such methods must be evaluated against overhead, explainability, stability under distribution shift, and worst-case guarantees; a predictor that improves average latency but fails under adversarial or safety-critical traffic may be unsuitable.

Research also addresses reconfigurable topologies, near-memory communication, processing in memory, approximate communication for error-tolerant workloads, and formal verification of routing and flow-control logic. The central research challenge is multi-objective: performance, energy, area, resilience, security, and programmability must be optimized under physical and workload constraints.

13. Best-Practice Design Method

A disciplined NoC design process should:

1. Characterize application communication, including packet sizes, locality, bursts, multicast, and synchronization.
2. Establish constraints for area, power, frequency, latency, throughput, reliability, and security.
3. Select candidate topologies using both graph metrics and physical floorplan analysis.
4. Define packet format, virtual networks, routing, flow control, and deadlock policy.
5. Build analytical estimates before detailed simulation.
6. Evaluate synthetic and application-driven traffic, including faults and overload.
7. Report average and tail behavior, not only peak throughput.
8. Validate control logic through assertions, formal methods, and fault injection where appropriate.
9. Reassess mapping and software communication protocols together with hardware.
10. Document assumptions so that results are reproducible.

Chapter Summary

Interconnection networks provide the communication substrate for parallel computers, while Networks-on-Chip bring these principles inside modern SoCs. Topology determines connectivity, diameter, wiring, and scalability; router microarchitecture determines buffering, arbitration, and pipeline behavior; routing determines path selection and correctness; and flow control determines how congestion and storage are managed.

Meshes, tori, rings, trees, crossbars, and multistage networks make different area, latency, bandwidth, and physical-design trade-offs. Packet, flit, wormhole, virtual-channel, credit-based, and adaptive-routing concepts are central to NoC design. Performance analysis requires distinguishing ideal latency from queueing delay and raw bandwidth from useful throughput. Reliable evaluation must include realistic traffic, tail latency, energy, area, faults, and security.

At postgraduate level, NoC design is best understood as a co-design problem involving applications, architecture, VLSI implementation, operating constraints, and verification. Emerging chiplet, heterogeneous, photonic, wireless, and learning-assisted networks broaden the design space but also introduce new correctness and governance challenges.

Key Terms

Interconnection network: A structured communication system connecting computational and storage components.

Network-on-chip: An on-chip packet communication network connecting IP blocks and endpoints.

Topology: The structural arrangement of network nodes and links.

Router: A network component that selects and forwards packet paths.

Endpoint: A processor, memory, accelerator, or other component attached to a network.

Packet: A logical unit of communication transported through the network.

Flit: A flow-control unit into which a packet may be divided.

Hop: One traversal from a router to an adjacent router.

Routing: Selection of a path for a packet.

Flow control: Regulation of transmission according to buffer and link availability.

Virtual channel: A logically separate channel sharing a physical link.

Wormhole switching: Flit-level forwarding in which a blocked packet may occupy multiple routers.

Head-of-line blocking: Blocking of later packets by a blocked packet at a queue head.

Congestion: Competition for limited network resources.

Deadlock: Indefinite mutual waiting caused by cyclic resource dependence.

Livelock: Failure to deliver despite continued packet movement.

Diameter: Maximum shortest-path distance in a network.

Quality of service: Differentiated treatment or guarantees for traffic classes.

Chiplet interconnect: Communication fabric connecting separately manufactured dies.

Tail latency: A high-percentile latency representing worst-case or near-worst-case behavior.

Review Questions

Short Answer Questions

1. Distinguish a topology from a routing algorithm.
2. What is the purpose of a virtual channel?
3. Explain head-of-line blocking.
4. State two differences between store-and-forward and wormhole switching.
5. Why can a full crossbar be difficult to scale?

Long Answer Questions

1. Compare buses, crossbars, meshes, tori, and multistage networks using area, latency, scalability, and physical-design criteria.
2. Explain the operation of a wormhole router, including input buffers, virtual-channel allocation, switch allocation, and link traversal.
3. Discuss deterministic and adaptive routing, and explain how deadlock freedom can be established.
4. Develop a methodology for evaluating a NoC using synthetic traffic and application traces.
5. Analyze the interaction among topology, buffer capacity, flow control, QoS, energy, and reliability.

Analytical / Application Questions

1. A packet travels in a 6 × 8 mesh from (1,2) to (5,7). Calculate the minimum hop count and the mesh diameter. State the assumptions behind your calculations.
2. Design a NoC for an accelerator with local-neighbor traffic, reduction traffic, and occasional multicast. Justify the topology, routing, virtual networks, and QoS policy.
3. A proposed adaptive router improves average latency but increases 99th-percentile latency and energy per flit. Explain possible causes and recommend an evaluation and design response.

Multiple Choice Questions with Answers

Question 1

Which property is most characteristic of a 2D mesh topology?

A. Regular physical layout with local horizontal and vertical links

B. A single shared electrical medium for all endpoints

C. A direct connection from every input to every output

D. A mandatory central root switch

Correct Answer: A. Regular physical layout with local horizontal and vertical links

Question 2

What is the primary purpose of virtual channels in a NoC?

A. To increase the physical width of every link

B. To provide logical separation and reduce blocking on shared physical channels

C. To eliminate the need for routing algorithms

D. To guarantee zero latency under congestion

Correct Answer: B. To provide logical separation and reduce blocking on shared physical channels

Question 3

In a regular mesh, what does Manhattan distance represent?

A. The maximum packet size

B. The number of virtual channels per router

C. The minimum number of horizontal and vertical link traversals

D. The physical wire capacitance

Correct Answer: C. The minimum number of horizontal and vertical link traversals

Question 4

Which routing method normally resolves one coordinate dimension before the other?

A. Random routing

B. XY dimension-order routing

C. Priority inversion routing

D. Store-and-forward routing

Correct Answer: B. XY dimension-order routing

Question 5

A link is 64 bits wide and operates at 500 MHz, with one transfer per cycle and no overhead. What is its raw bandwidth?

A. 32 Gb/s

B. 64 Gb/s

C. 128 Gb/s

D. 256 Gb/s

Correct Answer: A. 32 Gb/s

Question 6

For an uncontended wormhole path of h links carrying L flits, under the stated one-cycle assumptions, which estimate applies?

A. hL cycles

B. h + L − 1 cycles

C. L − h cycles

D. h² + L² cycles

Correct Answer: B. h + L − 1 cycles

Question 7

What condition is directly associated with deadlock?

A. All packets arrive earlier than expected

B. A cyclic dependency in which resources are held while waiting for one another

C. A link carrying fewer bits than its width

D. A router using deterministic routing

Correct Answer: B. A cyclic dependency in which resources are held while waiting for one another

Question 8

Which traffic pattern concentrates many packets on one destination?

A. Uniform random traffic

B. Nearest-neighbor traffic

C. Hotspot traffic

D. Bit-complement traffic

Correct Answer: C. Hotspot traffic

Question 9

If a link has width W bits and frequency f transfers per second, which expression gives ideal raw bandwidth?

A. W ÷ f

B. W + f

C. Wf

D. f − W

Correct Answer: C. Wf

Question 10

Why is average latency alone insufficient for evaluating a NoC?

A. It cannot be measured in cycles

B. It hides congestion variation and high-percentile tail behavior

C. It is always equal to throughput

D. It applies only to buses

Correct Answer: B. It hides congestion variation and high-percentile tail behavior