We have already established that the effect of topology on network performance is huge. I would like to quote a few sentences from Chapter 3 in [3].
A topology determines the number of hops (or routers) a message must traverse as well as the interconnect lengths between hops, thus influencing network latency significantly. As traversing routers and links incurs energy, a topology’s effect on hop count also directly affects network energy consumption. Furthermore, the topology dictates the total number of alternate paths between nodes, affecting how well the network can spread out traffic and hence support bandwidth requirements.
Bus is one of the simplest topologies which we have already discussed about. Some other common topologies are Ring, Mesh and Torus. Please see the picture below.
Let’s look at some nomenclatures related to the Topology of a NoC.
Channels - A single logical connection between routers.
Nodes – Routers. The circles in picture above are nodes.
Degree – Number of links at each node.
Diameter – Maximum distance between any two nodes.
Hop Count – Number of hops a message takes from source to destination. In mesh topology in the picture above, the hop count to reach from A to B is 4.
Throughput – Data rate in bits per second that the network can accept per input port.
Latency – Time required for a packet to traverse the network.
Path Diversity – The existence of multiple routes that can be used to reach a destination.
There are a few more terminologies that I have omitted here for the sake of simplicity. If you want to learn more, please refer [3] and [4].
Now it’s time to talk about the types of topologies. A network node may be a terminal node that acts as a source and sink for packets, a switch node that forwards packets from input ports to output ports, or both. The network types are decided on this basis. Generally speaking, there are two types of topologies – Direct and Indirect. There are Irregular and Hierarchical topologies as well, but we need not talk about them in this article. Please refer [3] if you want to learn more.
Direct Network
In a direct network, each terminal node (IPs) is associated with a router, and the nodes work as both a terminal and a switch. Some examples are ring, mesh and torus. Look at the mesh topology in the picture below.
All the IPs have at least one node, or router, connected to it, and of course all nodes are connected to each other to facilitate communication of messages from any one IP to any other IP. The IPs can be cores, cache, memory controller, PLL, almost anything we use in a SoC.
Indirect Network
Indirect network do not have router for every IP. Instead, it connects terminal nodes via one or more intermediate stages of switch nodes. One example of indirect topology is a crossbar. A crossbar connects n inputs to m outputs via nxm simple crosspoint switch nodes. Crossbar is called a non-blocking network as it can always connect a sender to a unique receiver. Butterfly network is also an example of an indirect network.
Impact of topology on Physical Design of chip
Now that we understand the impact of topology in network’s performance, it is also important to understand its impact on the physical design of a chip. First of all, the topology should be place and route friendly. Metal layers are used for physical interconnections which are limited in number, and we cannot hog up all the space in a metal later just for our network. We should be mindful in using that space. See the picture below.
In the picture below, one topology will be easier to perform layout on than the other while performing the same functionality. [6]
Wires thickness and spacing also affects the network performance. High resistance and capacitance are never good. Thicker wires with larger spacing between them can be used to lower the resistance and capacitance. Finally, if the distance between two nodes is greater such that it does not meet the timing requirements, we might have to break the timing path by using a repeater between the nodes. There are other factors that can affect the physical implementation of a network. Please check the references below for more information.
That was all about a network topology. In the next article, we will learn about routers. See you there!
References:
[1] Dally, William & Towles, Brian. (2001). Route packets, not wires: On-chip interconnection networks. Proceedings - Design Automation Conference. 684 - 689. 10.1109/DAC.2001.156225.
[2] Networks-on-Chip: From Implementations to Programming Paradigms by Sheng Ma, Libo Huang, Mingche Lai, Wei Shi, Zhiying Wang
[3] On-Chip Networks, Second Edition by Natalie Enright Jerger, Tushar Krishna, Li-Shiuan Peh
[4] Principles and Practices of Interconnection Networks by William James Dally, Brian Patrick Towles
[5] Wu, Chang & Li, Yubai & Peng, Qicong & Chai, Song & Yang, Zhongming. (2009). Construction of a multidimensional plane network-on-chip architecture based on the hypercube structure. Progress in Natural Science - PROG NAT SCI. 19. 635-641. 10.1016/j.pnsc.2008.10.003.
[7] Computer Architecture - Lecture 20: Interconnects (Fall 2022) by Onur Mutlu (Link)
[8] Computer Architecture - Lecture 21: On-Chip Networks & Efficient Router Design (Fall 2022) by Onur Mutlu (Link)
[9] W. J. Dally, "Virtual-channel flow control," in IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 2, pp. 194-205, March 1992, doi: 10.1109/71.127260.
[10] Next-Gen Computer Architecture: Till the End of Silicon by Smruti R. Sarangi
Comments