A Cool Application: On-Chip Interconnection Networks and its Analogies
If you’re reading this, it is likely you are on a modern computer, with a 2-4 core processor or perhaps some even higher-performance specs. In the very near future, it is quite likely that you would be reading, perhaps not this, but some other text, on an even more complex machine running a 64-core processor, perhaps. All of this is made possible because of Networks. More specifically, On-Chip Interconnection Networks. It is one of the hottest fields in Electrical and Computer Engineering and Computer Science. It relies heavily on the ability to construct and analyze a network for flowing packets of digital information. However, the concepts involved can be expanded to other things as well, not just packets. Similar analyses may be applied to cars on a grid of roads and highways, or online with Webpages and hyperlinks (PageRank?)
This area is actually my field of research, and my primary source of information on it is “Principles and Practices of Interconnection Networks” by Dally & Towles (it’s a great book, if you’re interested http://books.google.com/books/about/Principles_and_practices_of_interconnect.html?id=uyAg3zu_DYMC)
In this book, Networks are looked at from three main areas: Topology, Routing, and Flow Control. There are other areas, less relevant to this class, such as Microarchitecture (as in a digital system) .
1. Topology
Topology is all about how nodes and edges are arranged in a Network. In the case of computer systems, a node would be a router (routes packets to processors, memories, or other routers) and an edge would be a wire or bus. The topology would be how the routers, processors, memories, and wires are arranged and placed on the chip and how they connect to each other. Analogous to other networks, the nodes would be intersections (in the case of the car) or websites in the case of the internet. The edges would then be what links them together, roads for cars or hyperlinks for websites. The following shows two sample topologies for networks:
In the above figure, the right image is of a 2-Dimensional Mesh (grid) Topology in Computer Networks, and the left image is of a possibly corresponding or analogous network of streets and locations. This image was taken from ECE 4750 lecture notes.
However, different topologies are possible such as a ring (1-dimensional mesh) or a cube (3-dimensional mesh) such as the case when analyzing the flow of electrons between atoms in a molecule via bonds. The differing topologies provide varying levels of path diversity which may be important for avoiding congestion and contention (such as cars on the road or requests to stream video from a website). It presents all the options and possibilities for proceeding through a network.
2. Routing
Routing refers to how a packet flows through a network to get from source to destination. Due to path diversity presented in the topology of a Network, there will be different ways to proceed which may be deterministically determined or optimal depending on the case.
The above images show one (of several) ways to get from a Node in the Network to another. A Routing Algorithm describes what systematic method is used to get through a Network. Many times, the shortest path is the most desirable. This type of Routing Algorithm is deterministic because the path is always known and does not change based on the traffic in the Network. However, if the shortest path is always taken, or if shortest path between several different routers involve going through the same channel (or street, or server, etc) then the Network can get clogged up and become really slow and inefficient.
In terms of contention and congestion, a numerical value or weight could be assigned to each edge in the Network to represent that channel’s load or how much is being requested of that edge to link two nodes. These values could then be use to make decisions or judgement on how to proceed through a network. It may then be useful to take alternate paths to go from a source to a destination, utilizing the way in which nodes are connected to each other. This applies to sending packets in a computer network to requesting favors of a particular person. In Computer systems, sending a packet through a heavily loaded channel will result in high latency (time it takes for the packet to arrive) which is undesirable. Analogously, it may take an hour for a professor to get to work driving through State St. and College Ave due to the popularity of such streets as opposed to cutting through Buffalo and Stewart Ave, for example.
The above example describes an Adaptive Routing Algorithm. Unlike a Deterministic Routing Algorithm, an Adaptive Routing Algorithm analyzes the current state of the Network and decides how best to proceed. In Computer Systems, Networks need to be fast because the modern age warrants high-speed transfer of data between numerous and highly connected terminals and constituents. Expanding to a more social example, let’s say it’s move-in day for new Cornell Freshmen. People need to buy stuff for their living accommodations. The Network in question is therefore the network between buyers (students and parents) and sellers (convenience stores) which sell the desired products. Minimalistic routing would dictate that all buyers go to the nearest convenience store (perhaps Walmart) and buying everything there. However, if everyone has that mindset then the traffic to get to Walmart (edge) will be highly congested. Also, the limited resource that Walmart (the node) can provide will also be limited. In this case, perhaps it is beneficial to try other outlets (like the mall), despite being further or more out-of-the-way.
3. Flow Control
Flow Control governs the natural rules, restrictions, and limitations that exist in every Network. In the case of On-Chip Networks, perhaps two processors may be wanting to access the same memory. However, memories tend to have only one port for access so it is not possible for both processors to access it so there may be a rule in place such as “Processor 0 always gets priority over Processor 1” or “Processor 0 and 1 take turns getting priority.”
The above image shows two examples of contention. Two paths to different locations share at least one common edge so there must be a rule set up for determining who goes when and how. In On-Chip Networks, different arbitration schemes such as Round Robin in which each terminal (edge-node interface) take turns having priority over the use of a particular resource. Due to physical limitations, resources are inherently limited. In On-Chip Networks, bandwidth (bits per unit time) is limited and in the cars example, roads are of finite size and can only fit so many cars. In the case with cars, there are stop signs, traffic lights, and varying rules (like the right-hand rule) so that cars do not crash into each other for trying to access a segment of the road, a lane, or an intersection simultaneously. A lack of flow control can have disastrous effects such as car accidents or in the case of Computer Systems, corrupt data.
As a social example, let’s say that person A and B (nodes) are both friends (edge) with person C. Person C owns a really cool lawn mower (resource) that decreases grass-cutting time by 10x! Both person A and B would like to borrow person C’s lawn mower, so on a Saturday afternoon they both go to ask person C. However, person C only has one lawn mower to lend, so who gets it? There has to be some Flow Control scheme in place in which person C would have some way of deciding who uses it, because simply allowing both to use it at the same time would lead to problems. Perhaps person C owes person A a favor. Perhaps person C is more friendly with person B. Whatever the way to determine allocation of the resource, it is a critical component to this social Network providing order and organization to it. If person B gets the lawn mower first, person A could always borrow it right after. Alternatively, perhaps person C is using it him or herself in which case both A and B would have to wait for it to become available.
Conclusion
Together, these three components are integral to any type of Network in one way or another. In Computer Systems, the way in which computers, processors, servers, or even networks can become faster and have higher performance are through the development of Networks and the analysis of each of these parts. To have a 64-core processor each core will have to communicate with each other, and they do so through packets. However, the more complicated a Network the more important the rules of routing, transactions, and flow are. There are, of course, many other factors that affect Networks but they can mostly be categorized into these three parts, according to Dally & Towles.
What if problems occur? What if a Network reaches deadlock? Deadlock occurs when there is a cyclic dependency between Nodes in a network. For example, perhaps Node A is waiting for B to do something, B is waiting for C to do something, but C is waiting for A to do something. In this case, the network gets locked and there have to be preventative measures or recovery procedures in place to prevent such a situation from occurring. This is a very common in Computer Networks. Another problem could be, what if a Network changes? If Nodes or Edges are added or removed, how does the rest of the Network react? These problems are studied in depth by Engineers for Computer Networks, but it can be addressed for all kinds of networks. It just goes to show how powerful a tool networks can be in different aspects of life.