# A Load Balancing Mechanism for 3D Network-on-Chip with Partially Vertically Connected Links

Shiva Majidzadeh

► To cite this version:

Shiva Majidzadeh. A Load Balancing Mechanism for 3D Network-on-Chip with Partially Vertically Connected Links. 14th Doctoral Conference on Computing, Electrical and Industrial Systems (Do-CEIS), Jul 2023, Monte Da Caparica, Portugal. pp.259-267, 10.1007/978-3-031-36007-7_19. hal-05473088

HAL Id: hal-05473088

https://inria.hal.science/hal-05473088v1

Submitted on 23 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
<figure><img src="image_3.png" /></figure>

# A Load Balancing Mechanism for 3D Network-on-Chip with Partially Vertically Connected Links

Shiva Majidzadeh(✉)

NOVA School of Science and Technology, UNINOVA-CTS and LASI, NOVA University
Lisbon, 2829-516 Caparica, Portugal
s.majidzadeh@campus.fct.unl.pt

**Abstract.** 3D integrated circuit was presented as a new solution to enhance the efficiency and expand the capabilities of modern integrated circuit as well. Studies have shown that in comparison with 2D NoCs, the proposed 3D NoC offers a lower power consumption, shorter delay and high performance due to the reduction of the connection length in 3D NoCs. In this article, we present a routing algorithm for heterogeneous 3D NoC which distributes the chip traffic in the whole network based on the global congestion information. This is achieved by finding the least congested minimal path between the communicating nodes. For vertical connections, we consider the Through-Silicon-Vias (TSV) and to avoid deadlock, we use two virtual channels. The results show that the proposed mechanism is superior in comparison with the Elevator-First algorithm in the similar working condition.

**Keywords:** 3D integration · Vertical Channels · Load-balancing · Latency · Thermal Distribution

## 1 Introduction

Due to power performance advantages of 3D technologies, they have been considered as a feasible solution by industry. 3D integration technology can be established with multiple silicon layers that are stacked and used TSVs [1, 2] as a vertical connection. 3D integrations can cause bandwidth widening and die area reduction by shortening the length of the connections on the chip [3–6]. Vertical links in 3D Networks-on-Chips (3D NoCs) are the shortest ones in the network which reduce both the latency and power consumption. However, the disadvantages of vertical links using TSVs are their expensive manufacturing process and low yield [7]. So, if we have a tradeoff between performance and reduction of the vertical links, we can decrease the total cost of 3D NoC and make it suitable for market [8].

So far, there are some articles about the load-balancing in 3D NoCs but only a few of them addressed the vertically partially connected networks. For routing, the local information was used where it does not reduce the possibility of dealing with congestion in the future. In this paper, we present the global load balanced (GLB) deadlock-free
distributed routing algorithm in vertically partially connected 3D NoC equipped with an
efficient load-balancing mechanism. This method checks the available load on all links
and then selects the less congested path for sending the packet from its source.

One of the major issues in 3D NoCs is thermal distribution problem. The reason for this occurrence is high power density due to the stacking structure of 3D ICs. Although in 3D ICs, power consumption is less than of 2D ICs because of reduced length of connection, reduced chip area increases power density and affects operating frequency of the chip. These factors along with other factors such as cooling problem lead high temperature. In 3D architectures, power consumption rises with growing number of stacked layers; therefore, the possibilities of overheating increase. Thermal dissipation path from silicon layers to the surroundings is provided through convection method through heat sinks is located in the lowest surface [9–11].

This paper is organized as following. After discussing the related work in Sect. 2, in
Sect. 3, we will present our global load-balancing technique in detail. The experiment
setup and results will be described and analyzed in Sect. 4, and finally, in Sect. 5, we
conclude the work.

## 2 Related Work

In [10] an oblivious routing algorithm has been presented, called Randomized Partially Minimal (RPM) which balances the network traffic in order to avoid the creation of hotspots in the network. RPM first sends packets randomly to one of layers then use XY and YX routing with equal probability. Finally, the packets will be sent to the final destination in Z dimension. RPM is not always a minimal routing and the number of hop count will be increased which can increase the latency, particularly in large networks.

To guarantee the minimal path with keeping the simplicity of routing, most of the 3D
NoCs use the conventional Dimension Ordered Routing (DOR). [13] is an extended ver-
sion of DOR for 3D networks known as Balanced Dimension Ordered Routing (BDOR).
Considering the relative position of source and destination with one another, the BDOR
routes the packets with one of the XY or YX methods to improve the balance of routes
in networks.

In [14] the problem of TSVs large-scaled dimension in 3D NoC and the necessity of
using a smaller number of TSVs to reduce the chip size have been studied. In the article,
an adaptive routing algorithm is presented which distributes the traffic on the network
by considering the limited bandwidth of vertical connections. In this method, they use
an adaptive routing with non-minimal path which distributes the traffic locally due to
the lack of global information related to the network congestion. To avoid the long path
within each router a certain weight is assigned to all directions, so based on the traffic the
priority of every direction can be calculated and then the routing can be done according
to these priorities. In this algorithm, the input buffer space of neighboring nodes with
the routers was used as the congestion status.

Elevator-First [15] is a deterministic distributed algorithm for partially vertically
connected [16] was presented where the routing selection is taken locally. This algorithm
is not only deadlock and livelock free but also independent of vertical link's location.
This algorithm includes two states:
State 1: If source and destination nodes are in the same layer, the deterministic routing algorithm will be executed and packets will be assigned randomly to one of the virtual channels $Z + \text{or } Z^-$.

State 2: If source and destination nodes are in different layers, the deterministic algorithm is responsible for routing the packets to the nearest elevator. Once the destination is on upper/lower layer of the source, packets will be assigned to $Z + /Z$-virtual channels to be routed to the upper/lower layer.

## 3 Load-Balancing Algorithm

The proposed approach is based on the Elevator-First algorithm but the routing is done adaptively and has a complete view of the congestion status of the whole network following two conditions:

* Minimal path.

* Less congested path.

In the proposed algorithm, Global Load Balance (GLB), each node calculates the number of packets traverses through output ports. Every time packets sent out from the related link, the rate of sending to that link should be added based on the rate of passing flit, so each router can record the sending rate of its output ports. If we assume the mesh network as a graph, the sending rate of each link, will be considered as the weight of each edge in the graph. So, the packets are always sent through the lower weight to keep the network balanced.

We used Dijkstra algorithm [17] for finding shortest path. Dijkstra picks the path with less congested value within the all minimal paths. This method can be used for all the destinations. In addition, since the decision is carried out in parallel with the routine activities in the network, we can ignore the algorithm overhead and hardware overhead as explained in Sect. 4.

Deadlock in the network causes system stopping due to a cyclic dependency for resources. [18] proposed a method preventing a cyclic waiting of buffer in routers and proved that the turn model is deadlock-free based on Channel Dependency Graph (CDG) [16]. CDG shows whether a network is deadlock-free or not. For providing a deadlock-free routing algorithm, channel dependency graph should contain no cycle in a network.

We analyze our algorithm based on Elevator-First algorithm for deadlock-free and consider two virtual channels per physical link in x dimension. Additionally, in y and z dimension, if the packet is sent to the ascending/descending links, the assigned virtual channel will be called $Z + /Z^-$ that is fully independent of $Z^-/Z^+$ and in x dimension can choose $Z^+$ or $Z^-$. Selection of virtual channel is done statically on the source router. Thus, its allocation never changes during routing. The proof is similar to [15, 18]. Accordingly, a cyclic dependency of input buffer usage is broken.

The GLB router microarchitecture has been shown in Fig. 1. The below components are added to a baseline adaptive router [19] in order to obtain the proper route path between two nodes which are:

1. **Traffic Map**: This can store the congestion information of the entire network links and is being updated in the traffic map router of the requester after the ACK transmitted
by router and credit receives. It keeps just the information from every hop. However, in some cases like that the source and destination are on the same layer, there is no need for traffic storage and information updates of the nodes of other layers.

2. **Local Traffic Values:** It will store the congestion rate of output links of the source router in all directions.

3. **Route Computation:** The stored values in the traffic map will be transferred to this part in order to calculate and find the most proper output port of each router. When the route computation algorithm is being executed, it will estimate the cost of the route to reach one node and will choose the best route.

4. **Best output port table:** The result from the route computation stored in this section.

<figure><img src="image_4.png" /><figcaption>Fig. 1. A GLB router microarchitecture.</figcaption></figure>

In order to find the minimum route, number of hops between source and destination is being determined and then updating process of traffic map and route computation is being done in a way that the hops between the source and destination are minimum. As an example, shown in Fig. 2, node 1 is supposed to transmit data to node 8 and the minimum distance between source and destination nodes is 3 hops, then the updating process for traffic map for node 1 is three steps.

At first, node 1 will calculate the output ports traffic in all directions and puts them in the local traffic values, then calculates the all minimal adaptive routing for one node in 2 hops from the source. It means that the source node can use nodes 3, 5 and 7 to reach the destination. And as a result, the traffic map of node 1 is being updated and then the route computation is conducting the minimum traffic to find the shortest route in the network in a way that the traffic from node 1 to 5 contains:

$$ Path1 - 2 - 5 : 2/E + 1 = 3/E \text{ and } Path1 - 4 - 5 : 3/S + 2 = 5/S. $$

And the traffic rate from node 1 to 3 contains:

$$ Path1 - 0 - 3 : 1/W + 3 = 4/W \text{ and } Path1 - 4 - 3 : 3/S + 2 = 5/S. $$
Therefore, route 1 – 2 – 5, 1 – 0 – 3 and 1 – 4 – 7 are placed in the best output port table and in the next step calculations for the nodes in 3 hops from source node are being calculated and the traffic map is being updated. Node 6 is not transferred to the route computation since it is not a destination node. So, the source node can use node 5 or 7 to reach the destination. As a result, the computation is being done in the route computation and since traffic rate from node 5 to 8 is equal to $3/E + 4 = 7/E$ and from node 7 to 8 is $3/S + 1 = 4/S$, therefore, the route of 1 – 4 – 7 – 8 being selected and placed in the best output port table.

<figure><img src="image_5.png" /><figcaption>Fig. 2. An illustration of the GLB router technique for a 3x3 2-D mesh.</figcaption></figure>

The congestion information of each link needs five bits to store in a router, in which two bits for free buffers and three bits for the directions of links. Since our link is 128 bits then the flit size is 128 as well. If we consider the size of network $8 \times 8 \times 4$, in order to store congestion values in a 7-port router, we will need maximum three buffers (12 flits). With regards to the routers with 5 and 6-ports, less buffer space is needed to store link congestion and directions information due to the reduction in the number of links (In 5-ports router, 2 bits are enough to store the directions) for this reason, they have less area overhead and power consumption.

# 4 Experimental Results

For the evaluation of the proposed algorithm in 3D NoC, the simulation tool of Access-Noxim [20] is used. We consider XYZ and Elevator-First [15] as baseline algorithms in our simulation comparisons, 10% of the vertical links are removed randomly in both synthetic and realistic traffic profiles also design parameters are shown in Table 1.

## 4.1 Performance Evaluation

The results of reduced latency and increased throughput in mesh topologies with different sizes are presented in Table 2, showing that the GLB latency has been reduced considerably before the saturation point, compared to the other two approaches.
<table><caption>**Table 1.** Design parameters.</caption><thead><tr><td>Subject</td><td>Description</td></tr></thead><tbody><tr><td>Topology</td><td>3D mesh</td></tr><tr><td>Switching mechanism</td><td>Wormhole</td></tr><tr><td>Packet size(flit)</td><td>8</td></tr><tr><td>Buffer length (flit)</td><td>4</td></tr><tr><td>Flit length (bit)</td><td>128</td></tr><tr><td>Link bandwidth (Gbps)</td><td>128</td></tr><tr><td>Number of virtual channels</td><td>2</td></tr><tr><td>Traffic pattern</td><td>Random</td></tr><tr><td>Routing algorithm</td><td>GLB, Elevator-First, XYZ</td></tr></tbody></table>

<table><caption>**Table 2.** The improvement value of GLB method.</caption><thead><tr><th rowspan="2">mesh</th><th colspan="2">Average latency</th><th colspan="2">Average throughput</th></tr><tr><th>Elevator-First</th><th>XYZ</th><th>Elevator-First</th><th>XYZ</th></tr></thead><tbody><tr><td>4x4x4</td><td>34%</td><td>7%</td><td>12%</td><td>-</td></tr><tr><td>8x8x2</td><td>42%</td><td>15%</td><td>14%</td><td>2%</td></tr><tr><td>8x8x4</td><td>46%</td><td>19%</td><td>30%</td><td>3.8%</td></tr></tbody></table>

## 4.2 Thermal Model

Top layers are farther from heat sink in 3D NoC, so thermal conductivity path lengthens and processing elements in these layers have more heating potential than bottom layers that generate new thermal hotspots, amplify available thermal hotspots and make thermal variation in different parts of the chip [21, 22].

The experiments are on an 8 × 8 × 4 with 64 tiles in each layer and the tile model is from 80-core NoC system and the ambient temperature is set to 45 °C.

In Fig. 3, the packet injection rate is set in this traffic pattern to 0.05. The thermal map shows that Elevator-First algorithm has the imbalance thermal state under random traffic pattern and each layer has different thermal characteristics with respect its distance of heat sink. The bottom layer, which is close to the heat sink, has the lowest temperature while the top layer is at the highest temperature due to the high-power density. Unbalanced traffic makes thermal hotspots in middle tiles that distribute from high to low of top layer to bottom layer and corner tiles are at a lower temperature than the middle tiles because the corner traffic is less congested under the random traffic. Using GLB algorithm leads routers to use cooler path to route the packets and reduces the peak chip temperature about 4 °C and omit thermal hotspots of middle tiles and moderate thermal distributing on each layer.
<figure><img src="image_6.png" /><figcaption>Fig. 3. Steady state temperature distribution in Random traffic patterns of 3D NoC.</figcaption></figure>

## 4.3 Area and Power Evaluation

We use DSENT (Design Space Exploration of Networks Tool) [23] to estimate the area overhead and power consumption. DSENT is an architecture-level modeling tool designed for rapid design space exploration of both electronic and emerging opto-electrical NoC. We use 45nm SOI technology for baseline and GLB routers that its electrical parameters and network configuration. We also consider two virtual channels for baseline adaptive routers in estimation. The GLB router microarchitecture comprises some additional hardware components: congestion information, route computation module, and best output port table. Compared to the baseline adaptive router, additional hardware components need extra storage to store corresponding information. The layout area and power consumption of each platform are shown in Table 3. The GLB router imposes 4% area overhead and 2% power consumption compared to baseline adaptive routers.
<table><caption>**Table 3.** The area overhead and power consumption details.</caption><thead><tr><th rowspan="2">Network platforms</th><th colspan="3">Area Overhead(mm²)</th><th colspan="3">Power Consumption (W)</th></tr><tr><th>5 port</th><th>6 port</th><th>7 port</th><th>5 port</th><th>6 port</th><th>7 port</th></tr></thead><tbody><tr><td>Baseline adaptive routers</td><td>4.30</td><td>5.04</td><td>5.80</td><td>3.46</td><td>3.79</td><td>4.11</td></tr><tr><td>GLB routers</td><td>4.51</td><td>5.26</td><td>6.03</td><td>3.54</td><td>3.87</td><td>4.19</td></tr></tbody></table>

## 5 Conclusions

So far, routing is one of the most controversial issues in 3D NoC and currently many algorithms have presented in the field of load balancing. In this regard, we presented a new routing algorithm for exploiting global traffic information on a 3D chips with partially filled TSVs in order to dynamically pick the minimal and the least congested path for every packet. As the simulation result shows, our proposed algorithm reduces the packet average latency considerably in comparison with XYZ algorithm. Considering the reduction in the number of TSVs increasing the packet latency, the improvement is sizable.

## References

1. Xu, T.C., Schley, G., Liljeberg, P., Radetzki, M., Plosila, J., Tenhunen, H.: Optimal placement of vertical connections in 3D network-on-chip. J. Syst. Architect. 59, 441–454 (2013)

2. Tanaka, N., et al.: Through-silicon via interconnection for 3D integration using room-temperature bonding. IEEE Trans. Adv. Packag. 32, 746–753 (2009)

3. Pavlidis, V.F., Friedman, E.G.: Three-Dimensional Integrated Circuit Design. Morgan Kaufmann, Burlington, MA (2009)

4. Rahmani, A.-M., Vaddina, K.R., Liljeberg, P., Plosila, J., Tenhunen, H.: Power and area optimization of 3D networks-on-chip using smart and efficient vertical channels. Integrated circuit and system design. In: Power and Timing Modeling, Optimization, and Simulation, pp. 278–287. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-11802-9

5. Liljeberg, P., Plosila, J., Tenhunen, H., Feero, B.S., Pande, P.P.: Networks-on-chip in a three-dimensional environment: a performance evaluation, IEEE Transactions on Computers, 2009, Integrated Circuit and System Design. Power and Timing Modeling, Optimization, and Simulation, pp. 278–287 (2011)

6. Pavlidis, V., Friedman, E.: 3-D topologies for networks-on-chip. In: 2006 IEEE International SOC Conference (2006)

7. Velenis, D., Stucchi, M., Marinissen, E.J., Swinnen, B., Beyne, E.: Impact of 3D design choices on manufacturing cost. In: 2009 IEEE International Conference on 3D System Integration (2009)

8. Shang, L., Peh, L., Kumar, A., Jha, N.K.: Thermal modeling, characterization and management of on-chip networks. In: 37th International Symposium on Microarchitecture (MICRO-37'04)

9. Zhu, C., Gu, Z., Shang, L., Dick, R.P., Joseph, R.: Three-dimensional chip-multiprocessor run-time thermal management. IEEE Trans. Comput.-Aid. Design Integr. Circ. Syst. 27, 1479–1492 (2008)
10. Ebrahimi, M., Daneshtalab, M.: Learning-based routing algorithms for on-chip networks. In: Palesi, M., Daneshtalab, M. (eds.) Routing Algorithms in Networks-on-Chip. Springer, New York, pp. 105–125 (2014). https://doi.org/10.1007/978-1-4614-8274-1_5

11. Ramanujam, R.S., Lin, B.: Near-optimal oblivious routing on three-dimensional mesh networks. In: 2008 IEEE International Conference on Computer Design. (2008)

12. Tyagi, S.: Extended balanced dimension ordered routing algorithm for 3D-networks. In: India International Conference on Parallel processing Workshops, pp. 499–506. Centre for Development of Advance Computing, Noida, (U.P.) (2009)

13. Zhu, M., Lee, J., Choi, K.: An adaptive routing algorithm for 3D mesh NOC with limited vertical bandwidth. In: 2012 IEEE/IFIP 20th International Conference on VLSI and System-on-Chip (VLSI-SoC). (2012)

14. Dubois, F., Sheibanyrad, A., Petrot, F., Bahmani, M.: Elevator-first: A deadlock-free distributed routing algorithm for vertically partially connected 3D-nocs. IEEE Trans. Comput. **62**, 609–615 (2013)

15. Dally, S.: Deadlock-free message routing in multiprocessor interconnection networks. IEEE Trans. Comput. **C-36**, 547–553 (1987)

16. Rosen, K.H.: Discrete Mathematics and Its Applications. Braille Jymico Inc., Charlesbourg (1993)

17. Glass, C.J., Ni, L.M.: The turn model for adaptive routing. In: Proceedings the 19th Annual International Symposium on Computer Architecture (1992)

18. Kim, J., Park, D., Theocharides, T., Vijaykrishnan, N., Das, C.R.: A low latency router supporting adaptivity for on-chip interconnects. In: Proceedings of 42nd Design Automation Conference, 2005 (2005)

19. Jheng, K.Y., Chao, C.H., Wang, H.Y., Wu, A.Y.: Traffic-thermal mutual-coupling co-simulation platform for three-dimensional network-on-chip. In: Proceedings of 2010 International Symposium on VLSI Design, Automation and Test (2010)

20. Puttaswamy, K., Loh, G.H.: Thermal herding: Microarchitecture techniques for controlling hotspots in high-performance 3D-integrated processors. In: 2007 IEEE 13th International Symposium on High Performance Computer Architecture (2007)

21. Link, G.M., Vijaykrishnan, N.: Hotspot prevention through runtime reconfiguration in Network-on-chip. In: Proceedings of the conference on Design, Automation and Test in Europe (2005)

22. Sun, C., et al.: DSENT - a tool connecting emerging photonics with electronics for optoelectronic networks-on-chip modeling. In: 2012 IEEE/ACM Sixth International Symposium on Networks-on-Chip (2012)