13.5. The Three NoC Temptations
Dr. Se-Joong Lee of KAIST (Korea Advanced Institute of Science and Technology) discusses what he calls the three NoC temptations. The first such temptation is the siren song of the mesh network. With their elegant, regular architectures; good scalability; and opportunities for exploring adaptive routing algorithms, mesh networks have become the darlings of academic NoC research. However, Lee argues, mesh networks aren’t that attractive under close scrutiny. They are inefficient for global (broadcast) transactions and they are not nearly so regular and orderly as they appear in published academic articles. When actually laid out on silicon, mesh networks complicate the physical layout of the SOC and they require many network switches, each of which can often be as large as the 32-bit RISC processor it serves. Instead, says Lee, 2-level star or tree networks provide equivalent bandwidth and better latency while consuming far less silicon and much less energy. Figure 13.12 shows a 2-level, hierarchical-tree NoC and Figure 13.13 shows the ITRS MPSOC floor plan from Figure 13.3 with a tree NoC overlay added. Note that every processor within a function cluster in Figure 13.13 is on the same leaf level (connected to the same routing element, RE) as the other processors in its cluster. This design ensures that local communications stay local to the cluster.
Mesh networks provide redundant paths, which leads to the second NoC temptation: adaptive routing. At first blush, adaptive routing looks promising for NoCs. It allows for intelligent message routing that can bypass congested communication hot spots and defective switch nodes or broken links. However, adaptive routing incurs the problem of packet ordering, as shown in Figure 13.14.
Figure 13.14. Adaptive routing can cause packet reordering when passing through a network’s routing elements.
In Figure 13.14a, three packets arrive at RE 1 and need to pass on through the network to the right of RE 4. Packet 1 is routed from RE 1 to RE 2 (shown in Figure 13.14b) because RE 4 is busy. However, packet 2 is sent directly to RE 4 (shown in Figure 13.14c) because the busy condition clears. Meanwhile, packet 1 passes to RE 3 and packet 3 passes to RE 2 because packet 2 is already occupying RE 4. Eventually packets 1, 2, and 3 pass through this section of the NoC’s mesh (shown in Figure 13.14d), but the operation of the adaptive routing algorithm has reordered the packets. With adaptive routing, each network packet can take a different path, which results in different latencies for each packet. Consequently, packets can arrive out of order. Each receiver must therefore have a packet-reordering buffer, which increases the silicon overhead required by the network and also increases network latency.
NoCs with a star or tree topology cannot support adaptive routing because there is only one path through the network between each sender and receiver. All routes are pre-determined so no time is required to search for an “optimal” route for each packet. However, with only one route possible, traffic blockages or NoC “hot spots” that appear cannot be bypassed. Hot spots determine the maximum available network bandwidth, so each segment of the NoC must be designed accordingly.
The third NoC temptation is packet switching itself, which permits multiplexing of multiple messages onto one segmented communications channel. Like adaptive routing algorithms, channel segmentation adds packet buffers to the network and therefore consumes additional silicon that star and tree networks don’t need.