A High-Quality and Efficient Bus-Aware Global Router

I.   Introduction

With the continuous development of technology, advanced technology nodes have entered the nanometer age, and the design complexity of chips has increased dramatically. In modern very large scale integration (VLSI) design, the proportion of the bus in the net is increasing, and the transmission bus is widely used to transfer parallel signals between function modules and macros. These signals need to arrive at the same time, so the bus routing is a decisive factor in determining the timing and power consumption in VLSI routing [1].

Timing matching is an important bus design constraint in VLSI design [2]. Each signal bit in the same bus needs to transmit the corresponding signal, and the wirelength of the signal bit is usually used as the standard of signal transmission time. If the wirelength is too long or too short, the bus deviation will cause the timing of the chip to become worse, thus greatly reducing the performance of the chip [3]. For example, the eight pin groups in Figure 1(a) represent the same group of bus net groups, where pins with the same color represent the need for interconnection. In order to facilitate timing optimization and signal synchronization, the wirelength of the same bus should be kept as consistent as possible.

Figure  1.  Bus routing process. (a) Initial bus net group; (b) 2D routing result; (c) 3D routing result.

DownLoad: Full-Size Img PowerPoint

Global routing is usually divided into two phases: 2D routing and layer assignment [4]. In the 2D routing, the multi-layer routing resources and non-bus and bus nets information are mapped to the 2D plane, and then an initial 2D routing result is obtained by completing the routing on the 2D plane. As shown in Figure 1(b), a 2D bus routing solution can be obtained. However, due to the limited routing resources, if the allocation of bus and non-bus routing resources are not balanced, and the single routing method is overly single, the wirelength of the 2D routing solution is too long or the bus timing is too poor, which will lead to the low quality of the 3D routing solution obtained by the subsequent layer assignment. Therefore, it is worth exploring the research of routing algorithms considering bus timing in 2D routing.

In the layer assignment, all edges of the 2D routing solution are assigned to the appropriate metal layer according to the specific routing direction specified by different metal layers. The final routing result in Figure 1(c) can be obtained by layer assignment based on the 2D routing solution in Figure 1(b), where the dotted line represents the vias that connect the wires of different layers, but too many vias will lead to poor timing match. It can be seen that if only considering the layer assignment method of 3D wirelength and the routing sequence selection without differentiating between non-bus and bus will lead to too many vias and too large 3D deviation in the final result.

In order to solve these problems, this paper proposes a bus-aware global routing algorithm. The main contributions are as follows:

● In the 2D routing process, the routing density map is introduced, and a bus routing model is designed by controlling the bus routing through the routing density, which can ensure the routability of non-bus and reduce the bus deviation value.

● We also propose a local ripping-up and rerouting model to optimize the bus deviation by dynamically adjusting the routing resources, which can effectively reduce the bus delay.

● A deviation-aware layer assignment algorithm is designed to significantly reduce the bus deviation of the 3D routing solution by considering the difference between bus and non-bus.

● A DFS-based algorithm is proposed to obtain multiple routing solutions, from which the routing result with the lowest deviation is selected.

The remainder of this paper is organized as follows. Section II analyzes related work. Section III introduces the problem formulation. Section IV presents the details of the algorithm. Section V is the experimental part. And Section VI gives the conclusion.

II.   Related Work

In general, the global routing process can be divided into a 2D routing phase and a layer assignment phase. 2D routing phase involves mapping multi-layer routing resources, non-bus and bus net onto a two-dimensional plane, and interconnecting each component one by one on the two-dimensional plane according to these routing information, so as to ensure certain routing quality. In recent years, there has been an increasing amount of research concerning routing issues for nanometer designs. The existing researches on 2D routing algorithms are mainly about the construction of topological structures and basic routing methods [5]–[9]. This kind of algorithm mainly studies how to minimize the wirelength by considering routing topology and routing congestion under the condition of guaranteeing the routing rate. Ripping-up and rerouting is an important step to optimize 2D routing results [10]–[14], so reference [10] reduced routing congestion by iteratively using ripping-up and rerouting methods based on forbidden routing regions. A new global router for modern design [11] used a combination of monotonic routing and adaptive multi-source and multi-sink maze routing to reroute the overflowed net, so as to obtain a good routing result. In [12], the routing congestion is eliminated by the improved ripping-up and rerouting method. Based on the algorithm in [12], reference [13] proposed two length-limited maze routing algorithms, namely the optimal length-limited maze routing algorithm and the heuristic length-limited maze routing algorithm. Reference [14] determined the order of ripping-up and rerouting through congested region identification.

As for layer assignment, some related studies have been carried out [15]–[19]. Reference [15] used a dynamic programming method to find the optimal layer assignment solution for each net for the 2D routing solution generated by [14]. Reference [16] proposed a layer assignment algorithm based on the Lagrangian relaxation method to iteratively optimize the delay of all nets. In addition, with the development of advanced process technology, reference [17] proposed an algorithm using parallel wires and wide wires to optimize the delay of critical nets. On the basis of [17], reference [18] further optimized the maximum delay and total delay of critical nets by proposing an effective congestion evaluation method and adopting non-default regular routing technology. In [19], machine learning was used to solve the layer assignment problem, which shortened the wirelength and reduced the congestion.

The existing global routing algorithms in [5]–[19] do not take into account the particularity of bus topology structure in routing problems, and cannot effectively deal with the timing constraints of the bus. For bus routing, some related studies have been carried out [20]–[34]. For timing optimization, Reference [20] proposed a placement modification method considering bus delay to minimize the number of routing vias. In [21], an algorithm was proposed to reduce the wirelength while minimizing the number of routing vias. A bus length matching algorithm for printed circuit version was proposed in [22] to ensure that the maximum and minimum length constraints are satisfied. According to the topology structure, reference [23] proposed an algorithm to regenerate the routing topology by referring to a concept of virtual net. A length-matched gridless router for general routing topologies was proposed in [24] to efficiently handle practical designs that are not constrained by topology. Reference [25] proposed a heuristic algorithm using the longest common subsequence and multi-commodity flow for the bus routing problem considering obstacles. In [26], the existence of bus and non-bus was considered simultaneously in 2D routing and a hybrid one-way monotonic routing algorithm was proposed to optimize bus 2D deviation. Based on [26], reference [27] proposed an algorithm to optimize the deviation for edge moving technique considering 2D deviation. In [28], a new bus routing framework proposed is based on maze routing and Boolean satisfiability. It produces high-quality results quickly and allows for additional optimizations. In addition, inspired by the 2018 ICCAD competition on bus routing problem [29], reference [30] proposed a bus routing algorithm based on directed acyclic graph to satisfy the specific topology of the bus. In [31], a bus routing algorithm was proposed to realize the consistent construction of topology by routing all signal bits of the bus simultaneously. Reference [32] proposed a compact topology-aware bus routing algorithm to obtain a compact topology and reduce the number of illegal constraints. Reference [33] proposed a bus routing algorithm considering track resources and obstacles to optimize the routability, wirelength and length matching. Reference [34] proposed a topology-aware track assignment method.

III.   Problem Formulation

In this paper, a grid graph $G \{{\boldsymbol{V}},{\boldsymbol{E}}\}$ is defined to represent an instance of global routing. As shown in Figure 2, the multi-layer routing area containing obstacles is divided into rectangles of the same size and defined as the routing global cells or bins (G-cell), where each vertex $v \in {\boldsymbol{V}}$ represents the routing unit G-cell in the grid, and there are pins and obstacles in each routing unit. Each $e \in {\boldsymbol{E}}$ represents the common boundary of two adjacent G-cells. Each edge $e \in {\boldsymbol{E}}$ has the capacity $c_e$ that represents the number of routable wires for that common boundary. At the same time, given the net set ${\boldsymbol{N}}= \{N_1 , N_2 , \ldots , N_m\}$, there is a set of pins $\mathit{\boldsymbol{P}}=\{p_1 , p_2 , \ldots , p_k\}$ for each net. The problem of global routing is defined as follows: given a set of nets, a grid graph, and the capacity of every grid edges, the global routing is to find the path to connect all the pins for every net under the condition of satisfying the routing constraints.

Figure  2.  Global routing grid diagram.

DownLoad: Full-Size Img PowerPoint

The constraints of edge capacity include the sum of edge capacity constraints for both bus and non-bus, and the wirelength calculation method for non-bus nets and bus nets is the same.

In order to generate a highly routable global path for each net, we stipulate that the supply $s(e)$ of an edge $e$ represents the number of available routing tracks it contains. The number of wires that utilize an edge $e$ is called the demand $d(e)$ on the edge. We define the edge capacity constraint as $s(e) \geq d(e)$. Otherwise, we refer to the edge $e$ as overflowing.

In addition, based on the traditional global routing model, the bus net is introduced into the routing net. For bus, a bus pin group is represented by a combination of multiple pins. It has $p$ bus pin groups and each pin group has $r$ pins. As shown in Figure 3, it has 3 bus pin groups and each pin group contains 4 pins.

Figure  3.  Bus routing model.

DownLoad: Full-Size Img PowerPoint

When the length of the pin interconnect between two bus pin groups wirelength ($\rm{WL}$) is inconsistent, it will lead to inconsistent signal transmission time, and then the bus deviation $D_{k}$ is generated. In addition, due to the different routing phases, the calculation methods of $\rm{WL}$ and $D_{k}$ can be divided into 2D phase and 3D phase (denoted as subscripts 2d and 3d) as follows:

where $\text{path}^{j}_{i}$ denotes the routing path from the source pin group to the $j$-th signal bit of the $i$-th sink pin group. e denotes the edge in the path that spans two adjacent G-cell. $E_{\text{cost}}$ denotes the routing cost of each edge. $V_{\text{cost}}$ denotes the via cost. $e \in e^z$ denotes whether the edge is over the layer.

where $\rm MWL$$(\text{path}_{i})$ denotes the routing cost of the path with the highest routing cost from the source pin group to the $i$-th sink pin group. ${\mathrm{PN}}-1$ denotes the number of the sink pin groups. $r$ denotes the number of signal bits.

The main objective of this paper is to minimize the total bus deviation ($\rm TD$) and achieve a high level of routability in the routing process of bus and non-bus nets at the same time. $\rm TD$ is calculated as follows:

where ${\mathrm{BN}}$ is the number of buses.

IV.   Algorithm

In this section, we present the details of the bus-aware global router. Figure 4 shows the design flow of the proposed router in this paper. In the 2D routing, the routing information is first mapped onto the 2D routing plane, followed by the fast lookup table (FLUTE) algorithm to generate a topology for the routing net in question and use it to first perform a simple L-shaped routing for the non-bus to obtain a routing density map. A heuristic search algorithm based on routing density is then proposed to effectively plan the routing paths of the bus, and the wirelength will only increase by a small amount because the number of buses is much lower than the number of non-bus. The rerouting order and the ripping-up and rerouting area are determined based on the 2D deviation of the buses with the routing density map, and a path with smaller deviation is found for the net with larger deviation while ensuring that the overflow does not increase. Then, a local ripping-up and rerouting model is used to dynamically adjust the routing resources of the bus net group with larger deviations to obtain a more balanced routing solution with better routing quality. In the layer assignment, the routing priority is first decided based on the 2D routing results, and then a single net layer is assigned to each net according to the priority to get the preliminary layer assignment results.

Figure  4.  Algorithm design process.

DownLoad: Full-Size Img PowerPoint

Each of the above mentioned phases and strategies will be described in detail in the subsequent subsections.

1   2D routing phase

Throughout the global routing process, the result of 2D routing largely determines the quality of the final routing result.

2   Routing density map generation

In the global routing process, the initial routing result determines the quality of the routing, including the CPU time, the initial net topology, and the initial 2D deviation. Therefore, considering the bus 2D deviation and the bus length, this paper proposes a bus routing algorithm that considers the non-bus routing density, and uses the routing density to guide the bus routing in the initial routing phase to effectively reduce the bus deviation in the subsequent riping-up and rerouting, and the length of the net will not increase significantly because the number of bus nets is much less than that of non-bus nets.

In the 2D routing stage, when routing is carried out using the A* algorithm [35], the routing cost of each edge is primarily determined by the routing density map. Therefore, having an accurately evaluated routing density map can greatly enhance the quality of the routing. The initial stage of topology generation and routing density map construction is explained in Figure 5. As illustrated in Figure 5(a), the pin information of multiple nets is first projected onto the 2D plane in the 2D routing, with blue and green denoting the two groups of nets in Figure 5(a). Then, the FLUTE algorithm is used to construct the topology shown Figure 5(b) for each net. L-shaped routing can not only generate a shorter routing path, but also simplify the routing process. Therefore, L-shaped routing is used to generate the initial routing results. According to the topology structure of the net, L-shaped routing is used to generate the initial routing result as shown in Figure 5(c), in which the two red and yellow wire segments represent the two possibilities of L-shaped routing. Finally, the routing density map is constructed based on the weighted records of the areas passed by the routing, as shown in Figure 5(d). The priority of the areas passed twice in the subsequent routing is greatly reduced to ensure that the subsequent bus routing will not produce too many overflows.

Figure  5.  Construct the routing density map. (a) Inital net; (b) Construct topology; (c) L-type routing; (d) Routing desity diagram.

DownLoad: Full-Size Img PowerPoint

After constructing the complete routing density map, the initial routing is carried out and the heuristic function of the A* algorithm is introduced to evaluate the nodes of path search. As shown in Figure 6, the original initial bus routing only considers L-shaped routing, which will pass through multiple overlapping routing areas, which will produce a lot of overflow after the initial routing, and bring a lot of waste of resources in the subsequent ripping-up and rerouting. Therefore, after constructing a complete routing density map, the algorithm in this paper will guide the routing based on it. As shown in Figure 6, the original bus initial routing will pass through multiple overlapping areas. Although part of the wirelength will be increased after replanning the initial routing through the routing density map, the difficulty of ripping-up and rerouting and the bus deviation will be greatly reduced in the subsequent ripping-up and rerouting.

Figure  6.  Bus routing path selection.

DownLoad: Full-Size Img PowerPoint

After that, it is necessary to rip-up and reroute the marked two-pin net to optimize the deviation and overflow. In the process of rerouting, it is found that the net with large deviation value is generally in a relatively dense routing area, so it needs to be routed preferentially. Some of the spans of the net is large, so the small impact of the routing may produce a large deviation value, the decision of the routing sequence is based on the routing deviation of the net, the span of the net, the routing pin and so on.

In the process of ripping-up and rerouting, it is also necessary to refer to the bus deviation between the routing density map of the bus and the non-bus and the initial routing, and a cost function ${\rm cost}(N_i)$ similar to the A* algorithm is introduced. The cost function is calculated as follows:

where $\alpha$ and $\beta$ are individually defined parameters. $H(v)$ is the L-shaped routing cost from current node $v$ to the destination. $T(v)$ is the actual cost of a two-point connection traversing the routing density map. The performance and convergence of the A* algorithm are closely related to the selection of parameters. In order to ensure that the A* algorithm converges to better solutions, the parameters in the cost function of this paper are chosen by randomly sampling within a parameters space. The parameters that result in the optimal routing solution are selected as the parameters for the cost function.

Heuristic function $H(v)$ in order to ensure the basic routing constraints, and $H(v)$ in the initial routing to meet the shortest wirelength constraint, in order to not affect the deviation and find the shortest wirelength path, heuristic function $H(v)$ is used to calculate the Manhattan distance of two points in this paper.

where $x_{{\mathrm{s}}}$ and $y_{{\mathrm{s}}}$ are the horizontal and vertical coordinates of the starting point coordinate $s$, respectively. $x_{{\mathrm{e}}}$ and $y_{{\mathrm{e}}}$ represent the horizontal and vertical coordinates of the end point, respectively.

The choice of $T(v)$ is to effectively determine the routing density during the bus routing so as to sacrifice part of the wirelength for the reduction of deviation. $T(v)$ is computed as follows:

where $p$ represents the routing path. $e$ denotes the edge of the routing. $d_{e}$ is the actual routing cost of edge $e$. $h_{e}$ is the cost of history.

In the proposed algorithm, $d_{e}$ is calculated as follows to distinguish bus from non-bus.

where $C$ is a parameter set to 20. $G_b$ represents the bus net group, $L$ represents the area with routing density greater than 2 (an area that multiple routes pass through), and the routing cost will increase when selecting this area in the next routing.

In addition, $h_{e}$ will become larger as the running time of the algorithm increases.

where $i$ is the number of iterations. $o(e)$ is the overflow value of edge $e$. The initial value of history cost $h_{e}$ is 0.

The termination condition of this stage is that the overflow number of all routing edges is 0 or the number of iterations reaches the user preset value. Experiments show that the algorithm can greatly reduce the bus deviation by sacrificing a small amount of wirelength.

3   Deviation optimization stage

Because the routing process is sequential, the lack of routing resources in some nets leads to large deviation values of individual bus. Therefore, in the deviation optimization stage, the net group with large bus deviation value in the routing solution is optimized to reduce the maximum deviation value in the routing. In this paper, two methods are used to optimize the deviation: 1) A local ripping-up and rerouting model is proposed to adjust the net path. 2) DFS-based multi-result algorithm is proposed to get a high quality layer assignment result.

After finding that the deviation was affected by the net difference between the longest bus net and the shortest bus net, we tried to shorten the length of the longest bus net. But it was found that because the routing order was behind, it was difficult and ineffective to shorten the length of the longest bus net first and extend the shortest bus net simultaneously. The steps of local adjustment of the net are as follows:

Step 1 Sort the bus net group according to the wirelength and the number of signal bits, and select the net group with larger deviation value to rip-up and reroute.

Step 2 Select multiple two-pin net with longer wirelength and shorter wirelength from the bus net group with larger deviation values.

Step 3 Remove the routing path of net, and at the same time, the shortest net is routed many times in different ways to obtain the routing path with appropriate wirelength.

Step 4 The rest of the net is subsequently routed. Since the shortest routing path will release several critical routing resources after choosing other routing paths, the final routing of other signal bits has a probability of having a chain reaction to reduce the wirelength of the rest of the routing net to optimize the deviation.

The properties of several routing results can be obtained according to the DFS algorithm. First select bus net group with bus deviations and remove all routing paths in the area through which it passes. Then use the DFS algorithm for a two-pin net to get $N$ routing solutions. After obtaining multiple routing paths, each routing path is traversed in turn for subsequent routing, and so on to obtain multiple final routing results. Finally, the most suitable routing solution is selected from the multiple routing results. Algorithm 1 presents the DFS algorithm to find new paths.

Figure 7 is taken as an example to illustrate the local adjustment of the net, where the numbers in the figure represent the number of nets that can pass through. Figure 7(a) shows the original bus routing result, in which the signal bits in each G-cell are signal bit 1, signal bit 2, signal bit 3, and signal bit 4 from high to low along the Y-aixs, respectively. Put into the deviation calculation formula, the original bus deviation net group can be obtained as $(5-3)+(5-3)+(11-3)=12$. After rerouting the signal bit 3, it is found that signal bit 1 has other routing ways than before. As shown in Figure 7(b), the routing path of signal bit 1 is changed, and the lack of critical routing resources will lead to the selection of shorter routing paths in subsequent routing, which will eventually become the result shown in Figure 7(b). The deviation value is $(5-5)+(5-5)+(9- 5)= 4$. Compared with before, it can greatly reduce the routing deviation value.

Figure  7.  Local adjustment of bus routing path. (a) Initial wiring path; (b) The adjusted routing path.

DownLoad: Full-Size Img PowerPoint

4   Layer assignment phase

After obtaining the 2D routing result, each edge of each net of the 2D routing result needs to be assigned to different layers. As shown in Figure 8(a), the net is first converted into the directed tree shown in Figure 8(b) and the root node and leaf node of the tree that determines Figure 8(c). Finally, as shown in Figure 8(d) and Figure 8(e), the distribution of $e_1$ to metal layer 1 or metal layer 3 will be considered.

Figure  8.  Layer assignment process. (a) 2D routing result; (b) Directed tree; (c) Pin order; (d) $e_1$ on layer 1; (e) $e_1$ on layer 3.

DownLoad: Full-Size Img PowerPoint

In the single-net layer assignment used in this work, as shown in Figure 8(a), we first select the node where the driving pin of the net $N_{i}$ is located as the root node. As shown in Figure 8(b) and Figure 8(c), we use the depth-first search (DFS) algorithm to construct a directed routing tree, and obtain the layer assignment order for each edge based on the routing tree. After obtaining the layer assignment order for each edge in $N_{i}$, as shown in Figure 8(d), we assign each edge from the bottom to up according to the assignment order and record the via cost to the corresponding node. Finally, based on the value of the root node, we backtrack all nodes to construct the layer assignment result with the minimum cost as shown in Figure 8(e). For the single net layer assignment algorithm used in this algorithm, a high quality layer assignment sequence can maximize the use of routing resources, and finally get the best routing solution. The priority of different net is calculated comprehensively for the influencing factors such as 2D wirelength, number of pins, number of bend points of routing result, 2D deviation. The larger the priority of net, the more priority the net needs to deal with so as to obtain a high-quality layer assignment routing solution.

When the wirelength of the net is longer, more resources must be consumed for layer assignment. If the routing is carried out earlier, part of the net may not be able to complete layer assignment. As a result, the number of vias will be larger, so the longer the wirelength, the lower the priority. Secondly, if the number of bend points of the net is too much, the more the number of vias, the more routing resources will be occupied, So the higher the number, the lower the priority. If the net is a bus net and its deviation is large, the priority of the net needs to be relatively higher. Different bus nets have different signal numbers. With the increase of signal bits, the difficulty of reducing the deviation value will also increase, so the net with more signal bits has a higher priority.

Priority $Q(N_{i})$ is calculated as follows:

where $\alpha$ and $\beta$ are custom parameters. $P(N_{i})$ is the number of pins of $N_{i}$. $L( N_{i})$ is the 2D net length of $N_{i}$. $B(N_{i})$ is the number of bend points of $N_{i}$. $D(N_{i})$ is the bus deviation of net $N_{i}$ (0 if not a bus). $\rm bit$ is the number of signals in the net $N_{i}$ (0 if not a bus).

5   Layer assignment optimization deviation

For each net an initial layer assignment solution is obtained according to the current state of routing resources. After the initial layer assignment solution is obtained, the 3D routing deviation of the net can be obtained. Then, the optimization of the bus deviation can be realized by reassignment layers of the bus net with poor time matching. Detailed steps are as follows:

Step 1 Rip-up all net. The purpose of ripping-up the net is to find that better layer assignment results can be obtained by reassigning the layer assignment sequence according to the 3D routing deviation.

Step 2 In order to optimize the bus deviation, the algorithm replaces the priority in function $Q(N_{i} )$ by 3D deviation obtained from the previous layer assignment to determine the layer assignment order of the net.

Step 3 Due to the DFS algorithm being commonly used for problems involving finding all solutions, it exhibits high space efficiency. Therefore, after determining the layer assignment order, the algorithm first applies DFS to the initial bus net group, obtaining multiple feasible layer assignment results. These multiple results are then simultaneously used for the layer assignment of the second bus net group, and so on. In the end, multiple layer assignment results can be obtained. DFS needs to explore the whole solution space, so the time complexity of DFS is linearly related to the problem size. And, the time complexity of DFS is $O(x+y)$, where $x$ represents the number of nodes in the routing tree and $y$ represents the number of edges in the routing tree. Since this algorithm requires considerable time and space, it is applied to bus net with fewer signal bits and larger deviation values during this step.

Step 4 After obtaining multiple layer assignment solutions, calculate the deviation and wirelength of each layer assignment solution.

Step 5 Select the optimal layer assignment solution with small 3D deviation and small increase in wirelength.

A 2D routing solution can obtain multiple layer assignment algorithms. Although part of the layer assignment solution may have poor results in this net, it may bring huge routing benefits in the subsequent routing performance. In this paper, the best 3 routing solutions are selected for the next step after traversing for many times, more routing solutions can be obtained, from which the more excellent routing results are selected.

V.   Experimental Results

The global router considering the bus presented in this paper is implemented in C/C++ in an experimental environment of a Linux server with 96 GB of memory and a 2.0 GHz Intel Xeon CPU. The benchmark circuit sets used for the experiments were provided in the global routing competition held by ISPD in 2008. Among them, the data for the bus were added by the [14]. In this paper, we compared with Min [27] and BGR [26] for bus delay deviation optimization in 2D routing phase, and compared with COLA [15] and Greedy [17] for the via minimization. The specific information of each benchmark circuit is shown in Table 1. The first column Benchmark indicates the name of the benchmark circuit, the second column BusNum shows the number of buses added to the benchmark circuit, the third column MaxBit and the fourth column MinBit indicate the maximum and minimum signal bits of the bus, the fifth column TotalNet and the sixth column Layer list the total number of nets and the number of metal layers of routing in the benchmark circuit, respectively, the last column indicates the 2D routing cell size of each benchmark circuit.

Table  1.  Baseline circuit infomation.

Benchmark	BusNum	MaxBit	MinBit	TotalNet	Layer	G-Cell
adaptec1	50	64	8	221,362	6	324×324
adaptec2	50	64	8	261,791	6	424×424
adaptec3	50	64	8	467,807	6	774×779
adaptec4	50	64	8	516,720	6	774×779
adaptec5	50	64	8	868,873	6	465×468
bigblue3	50	64	8	1,124,036	8	555×557
bigblue4	50	64	8	2,230,639	8	403×405
newblue2	50	64	8	464,925	6	557×463
newblue4	50	64	8	637,403	6	455×458
newblue5	50	64	8	1,258,937	6	637×640
newblue6	50	64	8	1,287,924	6	463×464

 | Show Table

DownLoad: CSV

The bus global router proposed in this paper is divided into a 2D routing and layer assignment. To verify the effectiveness of the three strategies proposed in 2D routing. Table 2 gives the results generated by the 2D routing strategy based on the routing density map compared with other 2D routing algorithms considering the bus, where ${\mathrm{TWL}}_{\rm 2d}$ denotes the 2D total wirelength, CPU denotes the final runtime, with the unit of measurement being minutes (min), RATIO denotes the average optimization ratio, and ${\mathrm{TD}}_{\rm 2d}$ denotes the total 2D deviation. In addition, the cases with the ${\mathrm{TD}}_{\rm 2d}$ or ${\mathrm{TD}}_{\rm 3d}$ positive optimization are selected in each table, and the total average optimization values for all cases are bolded.

Table  2.  Validity verification of 2D routing based on routing density map.

Benchmark	RDM			Min [27]			BGR [26]
	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{{\mathrm{2d}}}$	CPU (min)	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{{\mathrm{2d}}}$	CPU (min)	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{{\mathrm{2d}}}$	CPU (min)
adaptec1	63.2	89204	30.1	63.5	113538	29.2	62.7	109882	11.2
adaptec2	63.1	77165	7.1	63.9	78124	5.1	63.4	95914	2.6
adaptec3	147.3	25890	9.1	147.1	26186	7.1	146.9	42954	4.5
adaptec4	136.1	14587	6.2	135.9	16036	4.2	145.7	41776	2.1
adaptec5	168.1	59815	27.3	167.2	67146	25.3	167.0	83172	15.8
bigblue3	142.1	13841	9.4	142.7	14552	7.4	142.3	18218	3.5
bigblue4	244.1	45907	78.3	239.4	52134	76.3	241.6	49182	13.6
newblue2	85.5	11316	2.8	85.4	11863	0.8	85.2	19148	0.7
newblue4	143.5	64821	112.5	140.5	66612	110.5	140.3	62060	27.9
newblue5	247.2	65213	25.9	246.3	78980	23.9	246.0	78216	14.5
newblue6	198.4	96756	80.3	198.6	120226	78.3	197.5	185900	30.8
RATIO	1	1	1	0.99	1.14	0.99	1	1.39	0.49

 | Show Table

DownLoad: CSV

Table 2 shows that by introducing the routing density map, optimization is achieved for each benchmark circuit in terms of bus 2D deviation. It is clear that the considerable reduction of bus 2D deviation comes from newblue5 and newblue6, with the reduction values being 17% and 19%, respectively, and on average, the ${\mathrm{TD}}_{\rm 2d}$ of the algorithm in this paper is optimized by 14% and 39% compared to Min [27] and BGR [26]. These results demonstrate that our method can also achieve better optimization when faced with the larger circuit scale. This is because the routing density map can effectively evaluate the degree of congestion in the initial routing area and simplify the difficulty of ripping-up and rerouting.

Table 3 gives the results produced by using a local ripping-up and rerouting model with dynamically adjusted routing resources compared to other 2D routing algorithms considering bus, from the table it can be seen that after resource reallocation by local bus, better deviation optimization is obtained by sacrificing 2D wirelength, in which 2D wirelength is sacrificed by increasing the shortest wirelength bus in the bus group. Moreover, the release of critical resources brought by the sacrifice of wirelength contributes to the deviation optimization. On average, the ${\mathrm{TD}}_{\rm 2d}$ of the algorithm in this paper is optimized by 7% and 31% compared to [27] and [26]. Especially in newblue5, only 0.3% wirelength is sacrificed and 21% optimization of ${\mathrm{TD}} _{\rm 2d}$ is achieved.

Table  3.  Validity verification of a dynamic resource allocation ripping-up and rerouting model.

Benchmark	RRR (resource reallocation route)			Min [27]			BGR [26]
	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}} _{\rm 2d}$	CPU (min)	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}} _{\rm 2d}$	CPU (min)	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}} _{\rm 2d}$	CPU (min)
adaptec1	63.2	107652	30.2	63.5	113538	29.2	62.7	109882	11.2
adaptec2	63.7	75781	6.9	63.9	78124	5.1	63.4	95914	2.6
adaptec3	147.4	26154	9.1	147.1	26186	7.1	146.9	42954	4.5
adaptec4	136.2	13564	6.2	135.9	16036	4.2	145.7	41776	2.1
adaptec5	168.1	58572	27.3	167.2	67146	25.3	167.0	83172	15.8
bigblue3	142.5	12816	9.4	142.7	14552	7.4	142.3	18218	3.5
bigblue4	244.2	44378	78.3	239.4	52134	76.3	241.6	49182	13.6
newblue2	85.3	11876	2.8	85.4	11863	0.8	85.2	19148	0.7
newblue4	143.5	65187	112.5	140.5	66612	110.5	140.3	62060	27.9
newblue5	247.1	62134	25.9	246.3	78980	23.9	246.0	78216	14.5
newblue6	198.3	112982	80.3	198.6	120226	78.3	197.5	185900	30.8
RATIO	1	1	1	0.99	1.07	0.98	1	1.31	0.49

 | Show Table

DownLoad: CSV

Table 4 gives the results produced by using a DFS-based multi-result algorithm compared to other 2D routing algorithms considering bus, better deviation optimization is obtained by sacrificing 2D wirelength. On average, the ${\mathrm{TD}}_{\rm 2d}$ of the algorithm in this paper is optimized by 5% and 26% compared to the [27] and [26].

Table  4.  Validity verification of DFS-based multi-result algorithm.

Benchmark	DFS-based multi-result			Min [27]			BGR [26]
	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 2d}$	CPU (min)	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 2d}$	CPU (min)	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 2d}$	CPU (min)
adaptec1	63.2	102197	31.3	63.5	113538	29.2	62.7	109882	11.2
adaptec2	63.7	75421	7.2	63.9	78124	5.1	63.4	95914	2.6
adaptec3	147.4	25976	9.5	147.1	26186	7.1	146.9	42954	4.5
adaptec4	136.2	14421	6.2	135.9	16036	4.2	145.7	41776	2.1
adaptec5	168.1	62712	27.3	167.2	67146	25.3	167.0	83172	15.8
bigblue3	142.5	14513	9.5	142.7	14552	7.4	142.3	18218	3.5
bigblue4	244.2	52012	78.8	239.4	52134	76.3	241.6	49182	13.6
newblue2	85.3	11861	2.9	85.4	11863	0.8	85.2	19148	0.7
newblue4	143.5	66213	112.9	140.5	66612	110.5	140.3	62060	27.9
newblue5	247.1	75621	26.2	246.3	78980	23.9	246.0	78216	14.5
newblue6	198.3	11354	80.5	198.6	120226	78.3	197.5	185900	30.8
RATIO	1	1	1	0.99	1.05	0.97	1	1.26	0.47

 | Show Table

DownLoad: CSV

Since the three strategies are performed at different routing phases therefore their routing optimizations can be combined to some extent. Table 5 gives the final 2D routing results using the two strategies compared with the results of other 2D routing algorithms considering the bus, where TOW denotes the total overflow. From Table 5, it can be seen that by this algorithm the routing deviations are optimized by sacrificing a small amount of CPU time and the total overflow, and on average ${\mathrm{TD}}_{\rm 2d}$ of the proposed algorithm is optimized by 20% and 46% compared to [27] and [26]. The increase in CPU time is mainly due to the construction of the routing density map in this 2D routing phase and the ripping-up and re-routing of key net during the deviation optimization process. However, the increase in CPU time is acceptable relative to the optimization achieved in terms of deviation.

Table  5.  Comparison of 2D routing results.

Benchmark	Our				Min [27]				BGR [26]
	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 2d}$	CPU (min)	TOW	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 2d}$	CPU (min)	TOW	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 2d}$	CPU (min)	TOW
adaptec1	63.4	97236	31.8	0	63.5	113538	29.2	0	62.7	109882	11.2	0
adaptec2	63.8	75672	7.9	0	63.9	78124	5.1	0	63.4	95914	2.6	0
adaptec3	147.3	24905	9.8	0	147.1	26186	7.1	0	146.9	42954	4.5	0
adaptec4	136.0	15671	6.6	0	135.9	16036	4.2	0	145.7	41776	2.1	0
adaptec5	167.6	57612	27.5	0	167.2	67146	25.3	0	167.0	83172	15.8	0
bigblue3	142.6	12031	9.5	0	142.7	14552	7.4	0	142.3	18218	3.5	0
bigblue4	243.2	43907	79.8	84	239.4	52134	76.3	36	241.6	49182	13.6	138
newblue2	85.4	10381	3.1	0	85.4	11863	0.8	0	85.2	19148	0.7	0
newblue4	141.2	59213	114.5	118	140.5	66612	110.5	144	140.3	62060	27.9	180
newblue5	246.9.1	67981	26.2	0	246.3	78980	23.9	0	246.0	78216	14.5	0
newblue6	198.4	98712	80.5	0	198.6	120226	78.3	0	197.5	185900	30.8	0
RATIO	1	1	1	1	0.99	1.20	0.96	0.89	1	1.46	0.45	1.57

 | Show Table

DownLoad: CSV

In order to verify the effectiveness of the proposed layer assignment algorithm considering bus and non-bus, the results of the layer assignment algorithm run alone in this paper are compared with the algorithms of COLA [15] and Greedy [17]. The Greedy algorithm is a greedy selection-based layer assignment algorithm to optimize the timing and vias in [17]. As shown in Table 6, the layer assignment results produced by the algorithms are able to optimize an average of 47% of the 3D deviation at the expense of only 1% of the 3D wirelength compared to the algorithm of [15]. Compared with the algorithm in the [17], the algorithm in this paper is able to achieve not only 5% optimization in wirelength, but also about 20% optimization in 3D deviation. This is because the proposed layer assignment algorithm comprehensively considers non-bus and bus net, and the DFS-based algorithm is proposed to obtain multiple routing solutions, from which the routing result with the lowest deviation is selected. And then it can achieve significant deviation optimization effects at the cost of sacrificing a small amount of wirelength. In summary, the proposed layer assignment algorithm based on DFS can effectively optimize the bus deviation and obtain the high-quality routing results.

Table  6.  Comparison of layer assignment results.

Benchmark	Our		Greedy [17]		COLA [15]
	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 3d}$	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 3d}$	${\mathrm{TWL}}_{{\mathrm{2d}}}$ (×105)	${\mathrm{TD}}_{\rm 3d}$
adaptec1	64.3	184359	66.3	201156	62.7	264318
adaptec2	64.9	114260	67.0	143594	63.4	157112
adaptec3	147.3	63022	154.5	80684	146.9	117122
adaptec4	136.1	64484	142.5	81406	135.7	91294
adaptec5	169.9	90730	179.5	130868	167.0	166212
bigblue3	143.2	35364	160.4	42072	142.3	51792
bigblue4	245.2	118656	140782	241.6	183432	273.9
newblue2	86.2	51928	90.8	68792	85.2	81200
newblue4	143.3	159758	148.9	174094	140.5	201648
newblue5	248.3	94246	264.4	130226	246.0	160290
newblue6	198.5	264164	216.3	302858	197.5	355776
RATIO	1	1	1.05	1.20	0.99	1.47

 | Show Table

DownLoad: CSV

To validate the proposed algorithm, the results of the algorithm run for the complete routing process in this paper are compared with the algorithms of COLA [15] and Greedy [17]. As shown in Table 7, compared with the algorithm in [15], the final routing results produced in this paper are able to optimize the 3D deviation by 60% on average at the expense of only 1% of the 3D wirelength, and compared with the algorithm in [17], the algorithm in this paper is able to optimize not only the wirelength by 5% but also the 3D deviation by about 31%.

Table  7.  Comparison of the results of the complete routing algorithm.

Benchmark	Our		Greedy [17]		COLA [15]
	${\mathrm{TWL}}_{{\mathrm{3d}}}$ (×105)	${\mathrm{TD}}_{\rm 3d}$	${\mathrm{TWL}}_{{\mathrm{3d}}}$ (×105)	${\mathrm{TD}}_{\rm 3d}$	${\mathrm{TWL}}_{{\mathrm{3d}}}$ (×105)	${\mathrm{TD}}_{\rm 3d}$
adaptec1	64.3	186658	66.3	201156	62.7	264318
adaptec2	64.9	108060	67.0	143594	63.4	157112
adaptec3	147.3	54328	154.5	80684	146.9	117122
adaptec4	136.1	42770	142.5	81406	135.7	91294
adaptec5	169.9	81668	179.5	130868	167.0	166212
bigblue3	143.2	42616	160.4	42072	142.3	51792
bigblue4	245.2	113924	140782	241.6	183432	273.9
newblue2	86.2	51008	90.8	68792	85.2	81200
newblue4	143.3	138526	148.9	174094	140.5	201648
newblue5	248.3	96662	264.4	130226	246.0	160290
newblue6	198.5	225950	216.3	302858	197.5	355776
RATIO	0.99	1.60	1.05	1.31	1	1

 | Show Table

DownLoad: CSV

In summary, the algorithm proposed in this paper ensures the routing quality of the final routing results by proposing a variety of effective methods and strategies in the 2D routing and layer assignment, not only to achieve a large amount of optimization of bus deviation, but also to consider the difference between bus and non-bus in the complete routing process.

VI.   Conclusion

In this paper, we propose a high quality and efficient bus-aware global router, analyze the differences between bus and non-bus, and optimize the bus deviation in the complete global routing process based on these differences. Unlike previous bus routing studies, this paper proposes a bus routing algorithm based on the non-bus routing density to ensure the routability while optimizing the 2D bus deviation. In addition, a layer assignment algorithm considering both bus and non-bus is proposed to optimize the 3D deviation. The experimental results show that after considering the bus and non-bus differences in both stages, the bus deviation can be effectively reduced with only a small sacrifice of wirelength.