# Efficient Congestion Mitigation Using Congestion-Aware Steiner Trees and Network Coding Topologies

Authors: M. A. R. Chaudhry; Z. Asad; A. Sprintson; J. Hu
Journal: VLSI Design
 (2011)

---

## Abstract

In the advent of smaller devices, a significant increase in the density of on-chip components has raised congestion
and overflow as critical issues in VLSI physical design automation. In this paper, we present novel techniques for
reducing congestion and minimizing overflows. Our methods are based on ripping up nets that go through the
congested areas and replacing them withcongestion-aware topologies.
Our contributions can be summarized as follows. First, we present several efficient algorithms for finding
congestion-aware Steiner trees that is, trees that avoid congested areas of the chip. Next, we show that the novel
technique of network coding can lead to further improvements in routability, reduction of congestion, and overflow
avoidance. Finally, we present an algorithm for identifying efficient congestion-aware network coding topologies.
We evaluate the performance of the proposed algorithms through extensive simulations.


---

## Body

## 1. Introduction

In almost any VLSI design flow, global routing is an essential stage that determines the signal interconnections. Therefore, the capability of the global router may significantly affect the design turn-around time. Moreover, the results of the global routing stage impact many circuit characteristics, such as power, timing, area, and signal integrity. Global routing poses major challenges in terms of the efficient computation of quality routes. In fact, most of the global routing problems, even special cases, tend to be NP complete [1, 2].In the advent of smaller devices, a significant increase in the density of on-chip components results in a larger number of nets that need to be routed, which, together with more stringent routing constraints, results in increasing congestion and overflow. In this paper, we propose novel techniques for congestion avoidance and overflow reduction. Our methods are designed for the rip-up-and-reroute phase of the global routing stage. At this stage, all the nets have already been routed using a standard prerouting technique however some of the nets need to be rerouted due to high congestion and overflow. Our methods are based on ripping up nets that go through congested areas and replacing them with congestion-aware topologies. The proposed techniques facilitate even distribution of the routing load along the available routing areas. We propose efficient algorithms for finding congestion-aware Steiner trees that favor uncongested routes. In addition, we use the novel technique ofnetwork coding for further reduction of congestion and overflow avoidance.


### 1.1. Congestion-Aware Steiner Trees

The major goal of congestion-aware Steiner tree routing is to find a tree that connects the required set of nodes (pins of a net) while avoiding congested areas with a minimum penalty in terms of the total wirelength. In addition, the running time of the routing algorithm should scale well with the growing number of nets. These requirements pose several challenges in terms of the algorithm design. The first challenge is to select a cost function that adequately captures the local congestion conditions at the edges of the routing graph. Next, the algorithm should find a minimum cost tree within acceptable running time. Since finding a Steiner tree is an NP-complete problem, the algorithm needs to use an approximation scheme or employ a heuristic approach. Finally, the proposed algorithm should ensure that the overall performance of the rip-up-and-reroute phase is satisfactory in terms of congestion mitigation and overflow reduction. In this paper, we evaluate several cost functions which take into account various factors such as wire density, overflow, and congestion history. We propose several efficient algorithms for Steiner tree routing and compare their performance. Our algorithms are based on known approximations for the Steiner tree problem, heuristic methods, and artificial intelligence techniques.


### 1.2. Network Coding

The basic idea of thenetwork coding technique [3] is to enable the intermediate nodes to generate new signals by combining the signals arriving over their incoming wires. This is in contrast to the standard approach, in which each node can only forward or duplicate the incoming signals.For example, consider a routing instance depicted in Figure1(a). In this example, we need to route two nets, one connecting source s1 with terminals t1, t2, and t3 and the other connecting source s2 with the same set of terminals. The underlying routing graph is represented by a grid as shown in Figure 1(a). Suppose that due to congestion, each edge of this graph has a residual capacity of one unit, that is, each edge can accommodate only a single wire. It is easy to verify that using traditional Steiner tree routing, only one net can be routed without an overflow. For example, Figure 1(b) shows a possible routing of a net that connects s1 with terminals t1, t2, and t3. In contrast, Figure 1(c) shows that routing of both nets results in an overflow. In this example, two nets transmit different signals, a and b, over separate Steiner trees. Figure 1(d) shows that the network coding approach allows to route both nets without overflows. With this approach, the terminal t1 creates a new signal, a⊕b, which is delivered to terminals t2 and t3, while the signals a and b are delivered to terminals t2, and t3 directly. It is easy to verify that each terminal can decode the two original symbols a and b.(a) The underlying routing graph with two source nodess1, and s2 and three terminals t1, t2, t3. (b) A rectilinear Steiner tree that connects source s1 to all terminals. (c) Two rectilinear Steiner trees that connect sources s1 and s2 to all terminals. (d) A network coding solution.
(a)(b)(c)(d)The network coding technique offers two distinct advantages. First, it has a potential of solving difficult cases that cannot be solved using traditional routing. For example, for the routing instance shown in Figure1, the traditional routing results in an overflow of value 1, whereas with the network coding technique there are no overflows. Second, the network coding technique can decrease the total wirelength. For example, in the routing instance shown in Figure 1 the total wirelength for the traditional routing solution is 8, whereas for the network coding solution, the total wirelength is 7.


### 1.3. Previous Work

In the past decades, researchers have strived to improve the performance of global routing algorithms (see, e.g., [4–6] and references therein). To handle the complexity of large-scale global routing, multilevel routing techniques are proposed in [7, 8]. Recently proposed BoxRouter [9, 10] is based on progressive integer linear Programming (ILP) and rip-up-and-reroute techniques. A fast routing method is presented in [11]. Reference [12] proposes an approach based on the Lagrangian multiplier technique. An effective edge shifting technique is presented in [13]. Most of these previous works adopt the rip-up-and-reroute strategy. However, they usually reroute one path (i.e., a 2-pin connection) at a time. In contrast, our method reroutes entire multipin nets. We also propose to use network coding techniques to further reduce congestion and eliminate overflows.


### 1.4. Contribution

The paper makes the following contributions. First, we propose several algorithms for finding efficient congestion-aware Steiner trees. Second, we show that the novel technique of network coding can lead to further improvements in routability, reduction of congestion, and overflow minimization. Finally, we provide an algorithm for identifying efficient congestion-aware network coding topologies. We evaluate the performance of the proposed algorithms through extensive simulations.


## 1.1. Congestion-Aware Steiner Trees

The major goal of congestion-aware Steiner tree routing is to find a tree that connects the required set of nodes (pins of a net) while avoiding congested areas with a minimum penalty in terms of the total wirelength. In addition, the running time of the routing algorithm should scale well with the growing number of nets. These requirements pose several challenges in terms of the algorithm design. The first challenge is to select a cost function that adequately captures the local congestion conditions at the edges of the routing graph. Next, the algorithm should find a minimum cost tree within acceptable running time. Since finding a Steiner tree is an NP-complete problem, the algorithm needs to use an approximation scheme or employ a heuristic approach. Finally, the proposed algorithm should ensure that the overall performance of the rip-up-and-reroute phase is satisfactory in terms of congestion mitigation and overflow reduction. In this paper, we evaluate several cost functions which take into account various factors such as wire density, overflow, and congestion history. We propose several efficient algorithms for Steiner tree routing and compare their performance. Our algorithms are based on known approximations for the Steiner tree problem, heuristic methods, and artificial intelligence techniques.


## 1.2. Network Coding

The basic idea of thenetwork coding technique [3] is to enable the intermediate nodes to generate new signals by combining the signals arriving over their incoming wires. This is in contrast to the standard approach, in which each node can only forward or duplicate the incoming signals.For example, consider a routing instance depicted in Figure1(a). In this example, we need to route two nets, one connecting source s1 with terminals t1, t2, and t3 and the other connecting source s2 with the same set of terminals. The underlying routing graph is represented by a grid as shown in Figure 1(a). Suppose that due to congestion, each edge of this graph has a residual capacity of one unit, that is, each edge can accommodate only a single wire. It is easy to verify that using traditional Steiner tree routing, only one net can be routed without an overflow. For example, Figure 1(b) shows a possible routing of a net that connects s1 with terminals t1, t2, and t3. In contrast, Figure 1(c) shows that routing of both nets results in an overflow. In this example, two nets transmit different signals, a and b, over separate Steiner trees. Figure 1(d) shows that the network coding approach allows to route both nets without overflows. With this approach, the terminal t1 creates a new signal, a⊕b, which is delivered to terminals t2 and t3, while the signals a and b are delivered to terminals t2, and t3 directly. It is easy to verify that each terminal can decode the two original symbols a and b.(a) The underlying routing graph with two source nodess1, and s2 and three terminals t1, t2, t3. (b) A rectilinear Steiner tree that connects source s1 to all terminals. (c) Two rectilinear Steiner trees that connect sources s1 and s2 to all terminals. (d) A network coding solution.
(a)(b)(c)(d)The network coding technique offers two distinct advantages. First, it has a potential of solving difficult cases that cannot be solved using traditional routing. For example, for the routing instance shown in Figure1, the traditional routing results in an overflow of value 1, whereas with the network coding technique there are no overflows. Second, the network coding technique can decrease the total wirelength. For example, in the routing instance shown in Figure 1 the total wirelength for the traditional routing solution is 8, whereas for the network coding solution, the total wirelength is 7.


## 1.3. Previous Work

In the past decades, researchers have strived to improve the performance of global routing algorithms (see, e.g., [4–6] and references therein). To handle the complexity of large-scale global routing, multilevel routing techniques are proposed in [7, 8]. Recently proposed BoxRouter [9, 10] is based on progressive integer linear Programming (ILP) and rip-up-and-reroute techniques. A fast routing method is presented in [11]. Reference [12] proposes an approach based on the Lagrangian multiplier technique. An effective edge shifting technique is presented in [13]. Most of these previous works adopt the rip-up-and-reroute strategy. However, they usually reroute one path (i.e., a 2-pin connection) at a time. In contrast, our method reroutes entire multipin nets. We also propose to use network coding techniques to further reduce congestion and eliminate overflows.


## 1.4. Contribution

The paper makes the following contributions. First, we propose several algorithms for finding efficient congestion-aware Steiner trees. Second, we show that the novel technique of network coding can lead to further improvements in routability, reduction of congestion, and overflow minimization. Finally, we provide an algorithm for identifying efficient congestion-aware network coding topologies. We evaluate the performance of the proposed algorithms through extensive simulations.


## 2. Model

In this paper, we adopt the most commonly used global routing model. The routing topology is represented by a grid graphG(V,E), where each node v∈V corresponds to a global routing cell (GCell) [10, 12] and each routing edge e∈E corresponds to a boundary between two adjacent GCells. A set S={n1,n2,…,n|S|} of nets are to be routed on this graph. Each net ni∈S connects a source node si with terminal nodes Ti={t1,t2,…,t|Ti|}. If there is a wire connection between two adjacent GCells, the wire must cross their boundary and utilize the corresponding routing edge. Each routing edge e∈E has a certain routing capacity c(e) which determines the number of wires that can pass through this edge. We denote by η(e) the number of wires that are currently using edge e.


### 2.1. Global Routing Metric

The goal of a global router is to minimize congestion. Some of the important metrics for a global router are defined as follows.(i) Overflow
For each edgee∈E, the overflow ov(e) of e is defined as
(1)ov(e)={η(e)-c(e),ifη(e)>c(e),0,otherwise.
The maximum overflowovmax is defined as(2)ovmax⁡=max⁡e∈Eov(e).
Total overflowovtot is defined as(3)ovtot=∑e∈Eov(e).(ii) Wirelength
Total wirelengthwlen is defined as
(4)wlen=∑e∈Eη(e).(iii) Density
The densityd(e) of edge e∈E is defined as
(5)d(e)=η(e)c(e).


### 2.2. Cost Functions

Our algorithms associate each edgee∈E in the graph with a cost function ρ(e) which captures its congestion and overflow. The cost of the tree is defined as the sum of the costs of all of its edges. Our goal is to identify trees that go through congested areas and replace them by Steiner trees or network coding topologies that go through areas with low congestion.In this work, we consider several cost functions, described below.Polynomial Cost Function
We propose a cost assignment function, where the cost of an overflowed edge is a polynomial function of the sum of its density and overflow. Formally, our proposed cost function is defined as follows:(6)ρ(e)=(d(e)+ov(e))α,
where α is a constant which determines the relative penalty for the congested edges.Exponential Cost Function
We use the cost assignment function proposed by [12]. With this cost assignment, the cost of an edge is an exponential function of its density
(7)ρ(e)={Exp(β⋅(d(e)-1))ifd(e)>1,d(e)otherwise,
where β is a constant which determines the penalty for overflowed edges.History-Based Cost Function
This cost function assigns cost to an edge based on its congestion history [10, 12]. Specifically, each edge is associated with a parameter he that specifies the number of times the edge has been overflowed during the previous iterations of the algorithm. That is, each time the edge with an overflow is used, the parameter he is incremented by one. Then, the modified cost ρ′(e) of the edge is defined as follows:
(8)ρ′(e)=1+he⋅ρ(e).Here,ρ(e) is either the polynomial cost function (6) or exponential cost function (7). If the density of the edge is less than or equal to one, the parameter he is initially set to zero.Since we focus on the rerouting phase, we assume that for each netni∈S, there exists a Steiner tree ϕi which connects all nodes in ni. Given a set of trees {ϕ∣ni∈S}, we can determine the values of ov(e),η(e) for each edge e∈E and identify the set of congested netsS′⊆S. A net ni∈S′ is referred to as congested if its Steiner tree ϕi has at least one edge with overflow.We propose a two-phase solution for rerouting congested nets using congestion-aware topologies. In the first phase we iteratively rip up each netni∈S′ and reroute it using a congestion-aware Steiner tree with the goal of minimizing the maximum overflow ovmax and the total overflow ovtot. In second phase, we deal with the nets that remain congested at the end of the first phase and rip-up-and-reroute pairs of congested nets using congestion-aware network coding topologies to further reduce congestion and minimize the number of overflows. Note that the nets considered in phase two correspond to difficult cases, where congestion avoidance was not possible even after several attempts of ripping up and rerouting individual nets. Therefore in the second phase, we consider the pairs of congested nets for further improvement. The example given in Figure 1 shows the advantage of using network coding topologies for routing pairs of nets over using standard routing techniques that handle each net separately.


## 2.1. Global Routing Metric

The goal of a global router is to minimize congestion. Some of the important metrics for a global router are defined as follows.(i) Overflow
For each edgee∈E, the overflow ov(e) of e is defined as
(1)ov(e)={η(e)-c(e),ifη(e)>c(e),0,otherwise.
The maximum overflowovmax is defined as(2)ovmax⁡=max⁡e∈Eov(e).
Total overflowovtot is defined as(3)ovtot=∑e∈Eov(e).(ii) Wirelength
Total wirelengthwlen is defined as
(4)wlen=∑e∈Eη(e).(iii) Density
The densityd(e) of edge e∈E is defined as
(5)d(e)=η(e)c(e).


## 2.2. Cost Functions

Our algorithms associate each edgee∈E in the graph with a cost function ρ(e) which captures its congestion and overflow. The cost of the tree is defined as the sum of the costs of all of its edges. Our goal is to identify trees that go through congested areas and replace them by Steiner trees or network coding topologies that go through areas with low congestion.In this work, we consider several cost functions, described below.Polynomial Cost Function
We propose a cost assignment function, where the cost of an overflowed edge is a polynomial function of the sum of its density and overflow. Formally, our proposed cost function is defined as follows:(6)ρ(e)=(d(e)+ov(e))α,
where α is a constant which determines the relative penalty for the congested edges.Exponential Cost Function
We use the cost assignment function proposed by [12]. With this cost assignment, the cost of an edge is an exponential function of its density
(7)ρ(e)={Exp(β⋅(d(e)-1))ifd(e)>1,d(e)otherwise,
where β is a constant which determines the penalty for overflowed edges.History-Based Cost Function
This cost function assigns cost to an edge based on its congestion history [10, 12]. Specifically, each edge is associated with a parameter he that specifies the number of times the edge has been overflowed during the previous iterations of the algorithm. That is, each time the edge with an overflow is used, the parameter he is incremented by one. Then, the modified cost ρ′(e) of the edge is defined as follows:
(8)ρ′(e)=1+he⋅ρ(e).Here,ρ(e) is either the polynomial cost function (6) or exponential cost function (7). If the density of the edge is less than or equal to one, the parameter he is initially set to zero.Since we focus on the rerouting phase, we assume that for each netni∈S, there exists a Steiner tree ϕi which connects all nodes in ni. Given a set of trees {ϕ∣ni∈S}, we can determine the values of ov(e),η(e) for each edge e∈E and identify the set of congested netsS′⊆S. A net ni∈S′ is referred to as congested if its Steiner tree ϕi has at least one edge with overflow.We propose a two-phase solution for rerouting congested nets using congestion-aware topologies. In the first phase we iteratively rip up each netni∈S′ and reroute it using a congestion-aware Steiner tree with the goal of minimizing the maximum overflow ovmax and the total overflow ovtot. In second phase, we deal with the nets that remain congested at the end of the first phase and rip-up-and-reroute pairs of congested nets using congestion-aware network coding topologies to further reduce congestion and minimize the number of overflows. Note that the nets considered in phase two correspond to difficult cases, where congestion avoidance was not possible even after several attempts of ripping up and rerouting individual nets. Therefore in the second phase, we consider the pairs of congested nets for further improvement. The example given in Figure 1 shows the advantage of using network coding topologies for routing pairs of nets over using standard routing techniques that handle each net separately.


## 3. Congestion-Aware Steiner Trees

In this section, we present several techniques for finding congestion-aware Steiner trees. Our goal is to find Steiner trees that minimize congestion with a minimum penalty in terms of the overall wirelength. We would like to achieve better tradeoffs between congestion mitigation and total wirelength. These tradeoffs are useful for practical applications as in some cases, congestion mitigation is preferable to wirelength reduction, whereas in other cases, the wirelength reduction is of higher priority.


### 3.1. Previous Work on Steiner Tree Routing

The Steiner tree problem is a well-studied NP-complete problem [14]. There is a wealth of heuristic and approximate solutions that have been developed for this problem. The best-known approximation algorithm has an approximation ratio of 1.55 (i.e., the cost of the tree returned by the algorithm is less than 1.55 times the optimum) [15]. The best known approximations require significant computation time, so we focus on computationally feasible and easy to implement approximation and heuristic solution for constructing Steiner trees.


### 3.2. Algorithms for Finding Congestion-Aware Trees

As mentioned above, our goal is to rip up and reroute nets that use congested edges ofG(V,E). For each net ni∈S which has been ripped up, we need to find an alternative Steiner tree that uses uncongested routes. In this section, we describe five algorithms for finding congestion-aware Steiner trees. The first three algorithms use combinatorial techniques (see, e.g., [1, 16, 17]) while, the last two are based on the intelligent search techniques [18]. The performance of the algorithms is evaluated in Section 5.AlgorithmstTree1
This algorithm approximates a minimum cost Steiner tree by using ashortest path tree. A shortest path tree is a union of the shortest paths between source si and a set of terminals Ti. A shortest path tree can be identified by a single invocation of Dijkstra’s algorithm. However, the cost of the tree may be significantly higher than the optimum.AlgorithmstTree2
This algorithm constructs the tree in an iterative manner. We iteratively process the terminals inTi in the increasing order of their distance form si. More specifically, we first find a shortest path P1 between source si and terminal t1. Then, we assign a zero cost to all edges that belong to P1 and find a shortest path P2 between s and t2 with respect to modified costs. The idea behind this algorithm is to encourage sharing of the edges between different paths. That is, if an edge e belongs to P1, it can be used in P2 with no additional cost. In general, when finding a shortest path to terminal t, all edges that belong to paths of previously processed terminals are assigned a zero cost. This algorithm requires |T|-1 iterations of Dijkstra’s algorithm, but it typically returns a lower-cost tree than Algorithm stTree1.AlgorithmstTree3
This is a standard approximation algorithm with the approximation ratio of 2 (i.e., the cost of the tree returned by the algorithm is at most two times higher than the optimal cost). Specifically, with this algorithm, we find a shortest path between each pair of nodes in the setT¯={T∪{si}}. Then, we construct a complete graph G′ such that each node in G′ corresponds to a node in T¯. The weight of an edge e∈G′ is equal to the minimum length of the path between two corresponding nodes in T¯. The algorithm then finds a minimum spanning tree ϕ in G′. Next, each edge in ϕ is substituted by the corresponding shortest path in G, which results (after removing redundant edges) in a Steiner tree in G that connects source si with terminals in Ti.AlgorithmstTree4
AlgorithmstTree4 is an intelligent search-based algorithm. Our approach is inspired by Algorithm A*. Algorithm A* is a shortest path algorithm that uses a heuristic function λ(v) to determine the order of visiting nodes of the graph in order to improve its running time. Specifically, for each node v, we define λ(v) to be the maximum distance between node v and a terminal t∈Ti which has not yet been visited. The distance between v and t∈Ti is defined as the minimum number of hops that separate v and t in G. The Algorithm stTree4 follows the same steps as Algorithm stTree1, but it uses Algorithm A* with heuristic function λ(v) to find shortest paths.AlgorithmstTree5
AlgorithmstTree5 is also based on Algorithm A*. It follows the same steps as Algorithm stTree2, but it uses Algorithm A* with the same heuristic function λ(v) as in Algorithm stTree4.


## 3.1. Previous Work on Steiner Tree Routing

The Steiner tree problem is a well-studied NP-complete problem [14]. There is a wealth of heuristic and approximate solutions that have been developed for this problem. The best-known approximation algorithm has an approximation ratio of 1.55 (i.e., the cost of the tree returned by the algorithm is less than 1.55 times the optimum) [15]. The best known approximations require significant computation time, so we focus on computationally feasible and easy to implement approximation and heuristic solution for constructing Steiner trees.


## 3.2. Algorithms for Finding Congestion-Aware Trees

As mentioned above, our goal is to rip up and reroute nets that use congested edges ofG(V,E). For each net ni∈S which has been ripped up, we need to find an alternative Steiner tree that uses uncongested routes. In this section, we describe five algorithms for finding congestion-aware Steiner trees. The first three algorithms use combinatorial techniques (see, e.g., [1, 16, 17]) while, the last two are based on the intelligent search techniques [18]. The performance of the algorithms is evaluated in Section 5.AlgorithmstTree1
This algorithm approximates a minimum cost Steiner tree by using ashortest path tree. A shortest path tree is a union of the shortest paths between source si and a set of terminals Ti. A shortest path tree can be identified by a single invocation of Dijkstra’s algorithm. However, the cost of the tree may be significantly higher than the optimum.AlgorithmstTree2
This algorithm constructs the tree in an iterative manner. We iteratively process the terminals inTi in the increasing order of their distance form si. More specifically, we first find a shortest path P1 between source si and terminal t1. Then, we assign a zero cost to all edges that belong to P1 and find a shortest path P2 between s and t2 with respect to modified costs. The idea behind this algorithm is to encourage sharing of the edges between different paths. That is, if an edge e belongs to P1, it can be used in P2 with no additional cost. In general, when finding a shortest path to terminal t, all edges that belong to paths of previously processed terminals are assigned a zero cost. This algorithm requires |T|-1 iterations of Dijkstra’s algorithm, but it typically returns a lower-cost tree than Algorithm stTree1.AlgorithmstTree3
This is a standard approximation algorithm with the approximation ratio of 2 (i.e., the cost of the tree returned by the algorithm is at most two times higher than the optimal cost). Specifically, with this algorithm, we find a shortest path between each pair of nodes in the setT¯={T∪{si}}. Then, we construct a complete graph G′ such that each node in G′ corresponds to a node in T¯. The weight of an edge e∈G′ is equal to the minimum length of the path between two corresponding nodes in T¯. The algorithm then finds a minimum spanning tree ϕ in G′. Next, each edge in ϕ is substituted by the corresponding shortest path in G, which results (after removing redundant edges) in a Steiner tree in G that connects source si with terminals in Ti.AlgorithmstTree4
AlgorithmstTree4 is an intelligent search-based algorithm. Our approach is inspired by Algorithm A*. Algorithm A* is a shortest path algorithm that uses a heuristic function λ(v) to determine the order of visiting nodes of the graph in order to improve its running time. Specifically, for each node v, we define λ(v) to be the maximum distance between node v and a terminal t∈Ti which has not yet been visited. The distance between v and t∈Ti is defined as the minimum number of hops that separate v and t in G. The Algorithm stTree4 follows the same steps as Algorithm stTree1, but it uses Algorithm A* with heuristic function λ(v) to find shortest paths.AlgorithmstTree5
AlgorithmstTree5 is also based on Algorithm A*. It follows the same steps as Algorithm stTree2, but it uses Algorithm A* with the same heuristic function λ(v) as in Algorithm stTree4.


## 4. Network Coding Techniques

In this section, we use the network coding techniques in order to achieve further improvement in terms of minimizing congestion and reducing the number of overflows. The network coding technique enables, under certain conditions, to share edges that belong to different nets. For example, in the graph depicted in Figure1(c), there are two minimum Steiner trees one transmitting signal a from source s1 and the second transmitting signal b from source s2. These two trees clash at the middle edge (emanating from t1), resulting in an overflow. This conflict can be resolved by coding at node t1, which effectively allows two trees to share certain edges. Similarly, our algorithm will identify pairs of nets that share terminals and then apply network coding techniques to reduce overflow.


### 4.1. Previous Work on Network Coding

The problem of routing of multiple nets with shared terminals is related to the problem of establishing efficient multicast connections in communication networks. The network coding technique was proposed in a seminal paper by Ahlswede et al. [3]. It was shown in [3, 19] that the capacity of the multicast networks, that is, the number of packets that can be sent simultaneously from the source node s to all terminals, is equal to the minimum size of a cut that separates s from each terminal. Li et al. [19] proved that linear network codes are sufficient for achieving the capacity of the network. In a subsequent work, Koetter and Médard [20] developed an algebraic framework for network coding. This framework was used by Ho et al. [21] to show that linear network codes can be efficiently constructed through a randomized algorithm. Jaggi et al. [22] proposed a deterministic polynomial-time algorithm for finding feasible network codes in multicast networks. An initial study of applicability of network coding for improving the routability of VLSI designs appears in [23]. In [24], Gulati and Khatri used network coding for improving the routability of FPGAs, focusing on finding nets that are suitable for network coding. To the best of our knowledge, this is the first work that proposes efficient algorithms for finding the congestion-aware network coding topologies for VLSI circuits.


### 4.2. Network Coding Algorithm

We proceed to present the algorithm we use for constructing congestion-aware coding networks that reduce congestion and overflow.The algorithm includes the following steps. First, we identify the subsetS′ of S that includes nets that go through edges with overflow. Second, we identify pairs of nets in S′ that share at least three common terminals. Next, we check, for each such pair of nets (ni,nj), whether we can replace the Steiner trees for ni and nj by a more efficient routing topology with respect to congestion and overflow.More specifically, let(ni,nj) be a pair of nets in S′ that share at least three terminals. Let si and sj be the source nodes of these nets. We denote the set of terminals shared by ni and nj by Tij. We also denote by Ti′ the set of terminals in Ti that do not belong to Tij that is, Ti′=Ti∖Tij. Similarly, we denote by Tj′ the set of terminals in Tj that do not belong to Tij that is, Tj′=Tj∖Tij. Next, we find two congestion-aware Steiner trees ϕi and ϕj that connect si to Ti′ and sj to Tj′. These trees can be identified by one of the algorithms presented in Section 3. The parameter η(e) for each e∈G is updated after finding ϕi and ϕj.Finally, we find a congestion-aware network coding topologyϕ̂ that connects si and sj to the common set of terminals Tij in an iterative manner. First, we let ϕ̂ be a Steiner tree with source si and terminals Tij. All edges of ϕ̂ are always assigned zero cost. We then sort the terminals Tij in the increasing order of their distance (in the original graph) from sj and process them in that order. For each terminal t∈Tij, we reverse all the edges in the path Pi,t between source si and terminal t and find a shortest path Pj,t between source sj and terminal t. Then, for each link e(v,u)∈Pj,t we perform the following procedure. If there exists a link e′(u,v) in ϕ̂, we remove e′(u,v) from ϕ̂ otherwise, we add e(v,u) to ϕ̂. A sample execution of this procedure is shown in Figure 2. It is easy to verify that the algorithm produces a feasible network coding topology that is, a topology that ensures that for each terminal t∈Tij there are two-edge disjoint paths that connect si and sj with t. The formal description of algorithm for identifying the network coding topology, referred to as Algorithm NC, is given in Algorithm 1.Algorithm 1:Algorithm NC.
Algorithm NC(G,si,sj,Tij,Ti′,Tj′):(1) Find a Steiner treeϕi connects si to terminals in Ti′(2) Find a Steiner treeϕj connects sj to terminals in Tj′(3) For each linke∈Ti′∪Tj′ update η(e)(4) Find a Steiner treeϕ̂ that connects si to terminals in Tij(5) Assign zero cost to all edges inϕ̂(6) For each terminalt∈Tij let d(t) be the shortest distance between sj and t(7) For all terminalst∈Tij in the increasing order of d(t) do:(8)  LetG′(V′,E′) be a graph formed from G(V,E) by reversing all edges in Pi,t,  where Pi,t is a path from si to t in ϕ̂(9)  Find shortest pathPj,t from source sj to terminal t in G′(V′,E′)(10)   Assign zero cost to all edges ofPj,t(11)For each edge e(v,u)∈Pj,t  do(12)   If there exists an edgee′(u,v)∈ϕ̂, remove e′(u,v) from ϕ̂(13)  Otherwise, adde(v,u) to ϕ̂(14) Returnϕ̂,ϕi, and ϕjSteps for finding network coding topology using AlgorithmNC. (a) A graph G with two nets ni and nj that connect nodes si and sj to terminals T1=T2=T12={t1,t2,t3}. (b) A Steiner tree ϕ̂ connecting sj to T2. (c) Modified graph in which the costs of all edges found in ϕ̂ are set equal to zero and the edges connecting si to t1 are reversed. A shortest path from sj to t1 is shown. (d) Modified graph in which the edges connecting si to  t2 are reversed. A shortest path from sj to t2 is shown. (e) Modified graph in which the edges connecting si to t3 are reversed. A shortest path from sj to t3 is shown.
(a)(b)(c)(d)(e)After the execution of the algorithm, we determine whether the total cost ofϕ̂, ϕi, and ϕj is less than the total cost of the original Steiner trees for nets ni and nj. If there is a reduction in terms of cost, the two original Steiner trees are replaced by ϕ̂, ϕi, and ϕj.Our experimental results, presented in Section5, show that the number of coding opportunities is relatively small. However, by applying the network coding technique on a limited number of nets, we can achieve a significant reduction in the number of overflows. Also, since the network coding technique is applied to a limited number of nets, the overhead in terms of the number of additional required gates is relatively small.


## 4.1. Previous Work on Network Coding

The problem of routing of multiple nets with shared terminals is related to the problem of establishing efficient multicast connections in communication networks. The network coding technique was proposed in a seminal paper by Ahlswede et al. [3]. It was shown in [3, 19] that the capacity of the multicast networks, that is, the number of packets that can be sent simultaneously from the source node s to all terminals, is equal to the minimum size of a cut that separates s from each terminal. Li et al. [19] proved that linear network codes are sufficient for achieving the capacity of the network. In a subsequent work, Koetter and Médard [20] developed an algebraic framework for network coding. This framework was used by Ho et al. [21] to show that linear network codes can be efficiently constructed through a randomized algorithm. Jaggi et al. [22] proposed a deterministic polynomial-time algorithm for finding feasible network codes in multicast networks. An initial study of applicability of network coding for improving the routability of VLSI designs appears in [23]. In [24], Gulati and Khatri used network coding for improving the routability of FPGAs, focusing on finding nets that are suitable for network coding. To the best of our knowledge, this is the first work that proposes efficient algorithms for finding the congestion-aware network coding topologies for VLSI circuits.


## 4.2. Network Coding Algorithm

We proceed to present the algorithm we use for constructing congestion-aware coding networks that reduce congestion and overflow.The algorithm includes the following steps. First, we identify the subsetS′ of S that includes nets that go through edges with overflow. Second, we identify pairs of nets in S′ that share at least three common terminals. Next, we check, for each such pair of nets (ni,nj), whether we can replace the Steiner trees for ni and nj by a more efficient routing topology with respect to congestion and overflow.More specifically, let(ni,nj) be a pair of nets in S′ that share at least three terminals. Let si and sj be the source nodes of these nets. We denote the set of terminals shared by ni and nj by Tij. We also denote by Ti′ the set of terminals in Ti that do not belong to Tij that is, Ti′=Ti∖Tij. Similarly, we denote by Tj′ the set of terminals in Tj that do not belong to Tij that is, Tj′=Tj∖Tij. Next, we find two congestion-aware Steiner trees ϕi and ϕj that connect si to Ti′ and sj to Tj′. These trees can be identified by one of the algorithms presented in Section 3. The parameter η(e) for each e∈G is updated after finding ϕi and ϕj.Finally, we find a congestion-aware network coding topologyϕ̂ that connects si and sj to the common set of terminals Tij in an iterative manner. First, we let ϕ̂ be a Steiner tree with source si and terminals Tij. All edges of ϕ̂ are always assigned zero cost. We then sort the terminals Tij in the increasing order of their distance (in the original graph) from sj and process them in that order. For each terminal t∈Tij, we reverse all the edges in the path Pi,t between source si and terminal t and find a shortest path Pj,t between source sj and terminal t. Then, for each link e(v,u)∈Pj,t we perform the following procedure. If there exists a link e′(u,v) in ϕ̂, we remove e′(u,v) from ϕ̂ otherwise, we add e(v,u) to ϕ̂. A sample execution of this procedure is shown in Figure 2. It is easy to verify that the algorithm produces a feasible network coding topology that is, a topology that ensures that for each terminal t∈Tij there are two-edge disjoint paths that connect si and sj with t. The formal description of algorithm for identifying the network coding topology, referred to as Algorithm NC, is given in Algorithm 1.Algorithm 1:Algorithm NC.
Algorithm NC(G,si,sj,Tij,Ti′,Tj′):(1) Find a Steiner treeϕi connects si to terminals in Ti′(2) Find a Steiner treeϕj connects sj to terminals in Tj′(3) For each linke∈Ti′∪Tj′ update η(e)(4) Find a Steiner treeϕ̂ that connects si to terminals in Tij(5) Assign zero cost to all edges inϕ̂(6) For each terminalt∈Tij let d(t) be the shortest distance between sj and t(7) For all terminalst∈Tij in the increasing order of d(t) do:(8)  LetG′(V′,E′) be a graph formed from G(V,E) by reversing all edges in Pi,t,  where Pi,t is a path from si to t in ϕ̂(9)  Find shortest pathPj,t from source sj to terminal t in G′(V′,E′)(10)   Assign zero cost to all edges ofPj,t(11)For each edge e(v,u)∈Pj,t  do(12)   If there exists an edgee′(u,v)∈ϕ̂, remove e′(u,v) from ϕ̂(13)  Otherwise, adde(v,u) to ϕ̂(14) Returnϕ̂,ϕi, and ϕjSteps for finding network coding topology using AlgorithmNC. (a) A graph G with two nets ni and nj that connect nodes si and sj to terminals T1=T2=T12={t1,t2,t3}. (b) A Steiner tree ϕ̂ connecting sj to T2. (c) Modified graph in which the costs of all edges found in ϕ̂ are set equal to zero and the edges connecting si to t1 are reversed. A shortest path from sj to t1 is shown. (d) Modified graph in which the edges connecting si to  t2 are reversed. A shortest path from sj to t2 is shown. (e) Modified graph in which the edges connecting si to t3 are reversed. A shortest path from sj to t3 is shown.
(a)(b)(c)(d)(e)After the execution of the algorithm, we determine whether the total cost ofϕ̂, ϕi, and ϕj is less than the total cost of the original Steiner trees for nets ni and nj. If there is a reduction in terms of cost, the two original Steiner trees are replaced by ϕ̂, ϕi, and ϕj.Our experimental results, presented in Section5, show that the number of coding opportunities is relatively small. However, by applying the network coding technique on a limited number of nets, we can achieve a significant reduction in the number of overflows. Also, since the network coding technique is applied to a limited number of nets, the overhead in terms of the number of additional required gates is relatively small.


## 5. Performance Evaluation

We have evaluated the performance of our algorithms using the ISPD98 routing benchmarks [25]. All the experiments are performed on a 3.2 GHz Intel Xeon dual-core machine. In all experiments, we first run the Steiner tree tool Flute [26] in order to determine the initial routing of all nets in the benchmark. Next, we perform an iterative procedure, referred to as Phase 1, which processes each net with overflows and checks whether an alternative Steiner tree of lower cost and with smaller number of overflows exists, and if yes, it rips up the existing tree and replaces it with an alternative one. This phase uses one of the algorithms described in Section 3. Phase 1 terminates when four subsequent iterations yield the same cost and the number of overflows, indicating that further reduction in the number overflows is unlikely.Next, we check whether the application of the network coding technique can further reduce the number of overflows. This phase is referred to as the Phase 2. We first identify pairs of nets that have overflowed edges and share at least there terminals. We then apply AlgorithmNC, presented in Section 4, to find an alternative network coding topology and perform rip-up and reroute if such a topology is beneficial in terms of reducing congestion and eliminating overflows.The experimental results are shown in Figures3(a)–3(c). The figures present average performance over all ten benchmarks. The cost function for this set of experiments was set according to (6) with α≥10. We have observed that larger values of α yield fewer overflows but result in larger running times and increased wirelength. We also note that for Phase 1, Algorithm stTree3 shows the best performance in terms of reducing the total number of overflows as well as reducing the maximum overflow. In fact, Algorithm stTree3 eliminates all overflows in all benchmarks, except for ibm4 as given in Table 1. We also note that Algorithms stTree4 and stTree5 yield Steiner trees with a smaller total wirelength. This is due to the fact the intelligent search algorithms favor paths that have small hop count.Table 1
Performance evaluation using AlgorithmstTree3 for Phase 1 and Algorithm NC for Phase 2 on ISPD98 benchmarks with polynomial cost functions.
Phase 1Phase 2ovtotovmaxwlenovtotovmaxwlenibm1141810586180727ibm20021629900216299ibm30018839100188391ibm41252196106932195949ibm50041568100415681ibm60033610500336105ibm70046638100466381ibm80047740400477404ibm90050866100508661ibm100071120100711201Evaluation of five different algorithms for Phase 1 and AlgorithmNC for Phase 2 on ISPD98 benchmark files. In all experiments, the polynomial cost function is used. (a) Comparison of the average total overflow. (b) Comparison of the average maximum overflow. (c) Comparison of the average total wirelength. (d) Comparison of the average running time. Results present average over 10 ISPD98 benchmark files.
(a)(b)(c)(d)We observe that the network coding technique results in a considerable reduction of the total number of overflows as well as reduces the maximum overflow. Furthermore, for each pair of nets for which we perform network coding, the number of required gates is small. Moreover, in all cases that we have encountered, the network coding operations can be performed over finite fieldGF(2), that is, each encoding node can be implemented with a single XOR gate. Such gates incur minimum overhead, because they can serve as buffers for long wires. An example of how network coding can help in reducing the wirelength of two nets in the ibm1 benchmark is shown in Figure 4.A network coding topology for benchmark ibm1 for pair of netsni=66 and nj=1531 computed using Algorithm NC. There are two nets ni and nj with sources si=(60,55),andsj=(60,57) and set of common terminals Tij=(59,55),(60,54),and(57,55). Part(a) shows routing layout without network coding. Part(b) shows routing layout with network coding. Example shows that network coding has helped to reduce congestion on edges (60,54), (60,53), (59,53), and (58,53).
(a)(b)Figure3(d) compares the running times of the different Algorithms for Phase 1 and Algorithm NC for Phase 2. As expected, Algorithm stTree4 is one of the fastest algorithms, whereas Algorithm stTree1 and stTree5 have running times comparable to Algorithm stTree2. Moreover, Algorithms stTree4 and stTree5 are faster than their counterparts (Algorithms stTree1 and stTree2, resp.). This is due to the fact that intelligent search methods speed up the search by preferring nodes closer to the destination.In the second set of experiments, we evaluated the performance of three cost functions mentioned in Section2.2 on the ISPD98 benchmarks using Algorithm stTree3 for Phase 1 and Algorithm NC for Phase 2. For cost function given by (6), we used α≥10, whereas for cost function given by (7), we used β≥50, and for cost function given by (8), ρ(e) was a polynomial cost function with α≥10. The results are shown in Table 2. Polynomial cost function showed the best performance in terms of overflows.Table 2
Performance evaluation of different cost functions (using AlgorithmstTree3 for Phase 1 and Algorithm NC for Phase 2) on ISPD98 benchmarks.
Polynomial costExponential costHistory-based costovtotovmaxovtotovmaxovtotovmaxibm100117100ibm20079200ibm3000000ibm431183474394ibm5000000ibm60054200ibm70082100ibm80037100ibm90015100ibm100095300In another set of experiments, we worked on slightly modified ISPD98 benchmark files. The modification included reducing the vertical and horizontal capacity by one unit. For Phase 1, we used AlgorithmstTree3 and then applied Algorithm NC in Phase 2. Polynomial cost function given by (6) was used to check the performance on these more congested cases. The results are given in Table 3.Table 3
Performance evaluation using AlgorithmstTree3 for Phase 1 and Algorithm NC for Phase 2 on modified ISPD98 benchmarks (decreased both horizontal and vertical capacity by 1 unit) with polynomial cost function.
FlutePhase 1Phase 2Number of XOR gatesovtotovmaxwlenovtotovmaxwlenovtotovmaxwlenibm1325714602093624781611843772315ibm25678221661931812176734121773712ibm323081614577711183395001833912ibm44833151628445506193832440619313152ibm554410038004762510047326570ibm654922727601231334165113341630ibm746651536367811473743004737432ibm854001340350231476880004768640ibm98545144115241614965639149640924ibm10710320574743417135691171355318We have also conducted the same experiment on several selected benchmarks on the output of MaizeRouter [13]. In these experiments, we iteratively reduced the vertical and horizontal capacity of the ISPD98 benchmarks until we got overflows while running them through MaizeRouter. Then, we used the output of MaizeRouter as input to Phase 1 using Algorithm stTree3, and after that, we have applied Algorithm NC in Phase 2. The cost function used was polynomial with α=10. The results are shown in Table 4. The results demonstrate that Algorithms stTree3 combined with Algorithm NC perform well and can contribute to further reduction of the number of overflows.Table 4
Improvement over MaizeRouter for modified (congested) IBM benchmarks using AlgorithmstTree3 for Phase 1 and Algorithm NC for Phase 2, using polynomial cost function.
Ver. CapHor. CapMaizeRouterPhase 1 and Phase 2ovtotovmaxovtotovmaxibm11113431341ibm5213145326254515125ibm8172864996419ibm910244006939899


## 6. Conclusions

In this paper, we presented several efficient techniques for rip-up-and-reroute stage of the global routing process. Our techniques are based on ripping up nets that go through highly congested areas and rerouting them using efficient Steiner tree algorithms. We have considered several efficient Steiner tree algorithms as well as several cost functions that take into account congestion and overflow. We have also studied the application of the novel technique of network coding and showed that it can efficiently handle difficult routing cases, facilitating reduction in the number of overflows.



---

*Source: 892310-2011-04-28.xml*