HubRouter: Learning Global Routing via Hub Generation and Pin-hub Connection
Authors: Xingbo Du
Chonghua Wang
Ruizhe Zhong
Junchi Yan
Venue: NeurIPS 2023 poster (2023)
Keywords: global routing
generative models
TL;DR: We propose a two-phase learning scheme called HubRouter, for generative global routing in VLSI systems.

Abstract: Global Routing (GR) is a core yet time-consuming task in VLSI systems. It recently attracted efforts from the machine learning community, especially generative models, but they suffer from the non-connectivity of generated routes. We argue that the inherent non-connectivity can harm the advantage of its one-shot generation and has to be post-processed by traditional approaches. Thus, we propose a novel definition, called hub, which represents the key point in the route. Equipped with hubs, global routing is transferred from a pin-pin connection problem to a hub-pin connection problem. Specifically, to generate definitely-connected routes, this paper proposes a two-phase learning scheme named HubRouter, which includes 1) hub-generation phase: A condition-guided hub generator using deep generative models; 2) pin-hub-connection phase: An RSMT construction module that connects the hubs and pins using an actor-critic model. In the first phase, we incorporate typical generative models into a multi-task learning framework to perform hub generation and address the impact of sensitive noise points with stripe mask learning. During the second phase, HubRouter employs an actor-critic model to finish the routing, which is efficient and has very slight errors. Experiments on simulated and real-world global routing benchmarks are performed to show our approach's efficiency, particularly HubRouter outperforms the state-of-the-art generative global routing methods in wirelength, overflow, and running time. Moreover, HubRouter also shows strength in other applications, such as RSMT construction and interactive path replanning.

HubRouter: Learning Global Routing via Hub Generation and Pin-hub Connection
Xingbo Du, Chonghua Wang, Ruizhe Zhong, Junchi Yan"
Dept. of Computer Science and Engineering & MoE Key Lab of AI, Shanghai Jiao Tong University {duxingbo, philipwang, zerzerzer2271828, yanjunchi]@sjon edu. cn
Abstract
Global Routing (GR) is a core yet time-consuming task in VL.II systems. It re- cently attracted efforts from the machine learning community, especially generative models, but they suffer from the non-connettivity of generated routes. We argue that the inherent non- non-connectivity can harm the advantage its one-shot genera- tion and has to be post-processed by traditional approaches. Thus, propose novel definition, called hub, which represents the key point the route. Equipped with hubs, global routing is transferred from pin-pin connection problem to hub-pin connection problem. Specifically, to generate definitely-connecte connected routes, this paper proposes two-phase learning scheme named HubRouter, which in- cludes 1) hub-generation phase: A condition-gunl -ugided hub generator using deep generative models; 2) pin-hub-connection phase: An RSMT construction module that connects the hubs and pins using an actor-critic model. In the first phase, we incorporate typical generative models into multi-task learning framework perform hub generation and address the impact of sensitive noise points with stripe mask learning. During the second phase, HubRouter employs an actor-critic model to finish the routing, which is efficient and has very slight errors. Experiments on simulated and real-world global routing benchmarks are performed to show our approach's 's efficiency, particularly HubRouter outperforms the state-of-the- art generative global routing methods wirelength, overflow, and running time. Moreover, HubRouter also shows strength in other applications, such as RSMT construction and interactive path replanning.
Introduction
As the scale of integrated circuits (ICs) increases rapidly, the quality and efficiency of current Electronic Design Automation (EDA) technologies are being ceaselessly challenged. Among the
various tasks from logic synthesis [50] to placement and routing [7], global routing (GR) g 24 36
43.31 35
48 is one of the complex and time-consuming combinatorial problems in modern Very Large Scale Integration (VLSI) design. As posterior step of component placement, it generates routing paths to interconnect pins of IC components from a netlist, which are already placed on the physical layout (6). The objective of global routing is basically minimize total wirelength while avoiding congestion in the final layou?" However, even its simplified 'two-pin' case (see Fig. 8 in Appendix for illustration) that routes every net with only two pins under design constraints turns out to be an NP-complete problem 27
* "ooreeponddncc author. This work was partly supported by China Key Research and Development Program (2020A AA0107600), NSFC (62222607) and SITU Scientific and Technological Innovation Funds. Another routing task called detailed routing k is orthogonal to this work. To our knowledge, there is far no learning-related work problems whose scale is even much larger than global routing (see example 66).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Characteristics of global routing approaches. Classi- cal and RL-based methods generally transfer routing into 2-pin problems. In particular, B1 is highly sensitive to chip scales. The generative model PRNet can generate each route in one-shot but cannot guarantee connectivity which requires considerable post-processing for failed routes. HubRouter this paper has all the advantages of PRNet and in particular ensures connectivity.
Model
Type
Multi-pin
Connectivity
Scalability
BoxRouter g
Classical
X
X
DRL [3
RL
X
x
Figure 1: Example of an un- connected route. Up: Original route; Down: Generated route.
PRNel 6
Generative
X
A
HubRouter (ours)
Generative
Scalable for one-shot generation, but not scalable for post-processing
Traditional works 8
adopt (strong) heuristies to greedily solve global routing. However, the diversity and scale could pose new challenges to classical algorithms, which call for strategy updating and improvement by human experts on continuous basis. To mitigate the reliance on manual efforts and facilitate the overall design automation and quality, machine learning has been adopted for global routing, as one of its diverse applications in chip design ranging from logic synthesis [40] [39] to placement [32] (28) etc. Specifically, deep reinforcement learning (DRL) [3]] and generative models 48] have been adopted to tackle global routing (sometimes also along with other tasks, e.g., placement [6] in the design pipeline). However, DRL methods suffer from large state space and often need to spend enormous time on generating routes as the scale of grids increases on the test instance, i.e., the netlist, which is practically intimidating for real-world global routing. The generative approaches can be more computationally tractable due to the potential one-shot generation capability and train/test the model on different instances. In fact, the generative models have recently been adopted in different design tasks [5] (665 beyond EDA (partly) for its higher efficiency procedure, while common challenge is how to effectively incorporate the rules and constraints in the generative models. However, though generative global routing approaches [6] inject connectivity constraints into the training objective, they often degenerate to an exhaustive search in post- post-processing when the generated initial routes fail to satisfy connectivity, difficult nets have a very low average connectivity rate of less than 20%, which means that over 80% generated routes for difficult nets require cine-consuiing post- proocesccs..ng. This greatly harms the inference time and indicates a serious challenge for the routing problem.
24 36 43]
compared with the iterative RL-based pecisionnmaainn
shown in Fig. [ Our experimental results will show that the routes for
To address this intractable issue, our main idea is to propose novel definition, 'hub', which means the (virtual) key point in the route. By transferring the pin-pin connection problem to the hub-pin connection problem. situations where routes unconnected in generative approaches can be avoided.
Specifically, we propose a novel two-phase learning scheme for global routing, named HubRouter, which includes 1) hub-generation phase: A condition-guider hub generator using deep generative models under a multi-task learning framework; 2) pin-hub-connection phase: A post-processe rectilinear Steiner minimum tree (RSMT) construction module that links the hubs using an actor-critic model. In the generation phase, hubs, routes, and stripe masks (a practical module as illustrated in Sec. 3.1 are together generated under multi-task framework by generative models with optional choices, including Generative Adversarial Nets (GAN) [II, Variational Auto-Encoder (VAE) (26), and Diffusion Probabilistic Models (DPM) [6). Though only hubs are required as outputs in this phase, we find it helpful to simultancously generate routes and stripe masks together with hubs, where routes are used to obtain the local perception and stripe masks are capable of removing noise points. In the connection phase, we regard the connection of generated hubs as an RSMT construction problem, which is NP-complete [TO]. Equipped with an actor-critic model [47), this phase can be conducted in a more scalable way [3 with very slight errors. We also introduce a special case that when hubs in the first phase are correctly generated for RSMT route, its reconstruction time complexity can be reduced to (n log n), which shows the scalability potential of HubRouter.
With this two-phase learning scheme, the proposed HubRouter enforces all generated routes to be connected and save the post-processing time in generative approaches (6). Apart from the strength in global routing, HubRouter is of generality to deal with other applications. We evaluate HubRouter in
2

---

net. net
node
edge
Chip Canaas
pins
route
(a) Chip Canvas.
(b) Grid Graph.
(c) Condition.
(d) Route.
(e) Hub.
Diagrams of a) chip canvas; b) grid graph; c) condition image, with pin positions and capacity; d) route, and examples of 4 types of hubs; e) all hubs generated from d).
Figure 2:
RSMT construction and interactive path replanning. Table compares different routing methods and the highlights of this paper are:
1) We empirically show that the recent generative global routing approaches could suffer from the inherent con-connettivity of generated routes. Inspired by this observation, this paper proposes a new concept, namely hub, which means key point in the route. With hubs generated for each net, pins can be connected efficiently under connectivity assurance.
2) Equipped with the concept of hubs, we devise HubRouter, which is novel two-phase learning scheme for global routing, including (virtual) hub generation and pin-hub connection. Compared with generating routes directly, this scheme ensures the connectivity of all generated routes generating intermediate hubs and then connecting them with pins. The connectivity assurance alleviates the time-consuming post-processing.
3) In the generation phase, we introduce a condition condition-guided generative framework under the perspec- tive of multi-task learning, where routes and stripe masks are generated together with hubs to improve hubs" generation quality. In the connection phase, we adopt an actor-critic network effectively simulate the RSMT construction. Moreover, we illustrate that when hubs are correctly generated for an RSMT route, the reconstruction can be optionally performed (n log time complexity.
4) Multiple experiments on simulated and real-world datasets are performed to illustrate the effec- tiveness of HubRouter. Especially, HubRouter ensures the connectivity of generated routes and outperforms the state-of-the-art generative global routing models in wirelength, overflow, and time. We also introduce two applications other than global routing to show the generality of HubRouter.
2 Background and Preliminaries
Global Routing. In VLSI design, global routing is a stage after placement, which determines the paths for nets and interconnects the pins on a chip layout. Typically, given a physical chip and netlist, we have chip canvas and several nets (see Fig. 2(a). where each net includes some pins on the fixed positions decided by macro/standard cells routing, the chip canvas is further divided into rectangular tiles, where the tiles are formed into
previous placement process. In global
grid graph G(V,E) E) (see Fig. 2(b) Nodes V {v; | also named global routing cells (GCells), represent the tiles and we need to link all the tiles that contain pins. The nodes containing pins are dyed dark red in Fig- 2(b) Edges & represent the paths among adjacent nodes, where each edge Gij E & has its given capacity Gj and usage Waj. The main objective of global routing is to connect all the required connections and on this basis, reduce the routing wirelength (WL) and overflow (OF). The overflow here refers to o,y max(0, Uky ciz) i.e., the exceeded number of routes compared to the given capacity on a tile.
Generative Global Routing, Actually, global routing is a combinatorial problem and can be formulated as a 0-1 integer linear programming (0-1 ILP) problem 44, but is still NP-complete. Despite that various works []1 denote the layout of global routing as routing graph, generative models (6) give a novel insight that regards the layout as an image and treats route generation as independent conditional image generation. Specifically, pixels are used to represent tiles in global routing, and routing output image generated from a given condition image. The condition image contains three channels, with the first channel being the locations of pins and the other two channels

---

Hub Hlub-generation Phase
Pin-hub-connection Phase
GAN
01
Random Points
Masked
(mak)
Discriminator
Generator
Actor
Critic
VAE
Extraction
Mask
map
Point Encoder
Linear Evaluntion
Encoder
Z
Decoder
MSE
(Aub)
DPM
Baseline
Diffusion
2
Denoising
Point Decoder
Extraction
g (haih)
Condition
Guide
((r))
map
Hub Points
RES
Route
X
Connected Route
Figure 3: Pipeline the proposed two-phase scheme. 1) hub- gerb-ggeeration phase: Route, hub, and mask are fed to three optional generative models, i.e., GAN, VAE, and DPM, with condition guided. The generated hub image is further masked by a stripe mask module; 2) fii--hub-connection phase: The hubs generated in the first phase fed to actor-critic network to obtain its RSMT construction by learning Rectilinear Edge Sequence (RES), and finally the connected route obtained.
being the capacity of horizontal/vertical grid edges. The routing image is grayscale image with value of 255 representing routed and representing unrouted. Examples of condition and routing images respectively shown in Fig. and 2(d)
Hub. Fig. 2(d) also introduces hubs, the main concept proposed this paper, with 4 different types, which can be vividly represented as '+. T,,"". Formally, we have
Definition (Hub). Given a one-channel image with m x n pixels, let Pty (1 Si m, m,lijs.
denote the pixel in the i-th row and j-th column, whose value Tij 1/0 respectively represent routeal/nrouted. Auxiliary denote roj = r(m+1)s = Tso = -T((++)) = 0, then the pixel Pış is a hub if
and only if riy = 1 and it satisfies any the following condition:
(1) + ((--1) T(i+1)s ri(-1) = ri0+1) 1;
(2) : + raeey + +ig-1) + +ig+1) = 3;
(3) ((-1))) 1(++))) 1 and 1) + ri0+1) = 1; (4) 10 + T6+D5 + Tig-1) + NG+1) 1.
This means that any routed pixel hub unless has exactly two opposite routed neighbor pixels. In Fig. 2(e) we give an example of all the hubs generated from Fig. 2(d)
Difference between Hubs and Steiner Points. The intuition of hubs is similar the concept of Rectilinear Steiner Point (RSP) 21]. but we claim that there are essential differences between them. RSPs are searched for global minimum total distance, while hubs are used to determine a path. Obviously, RSPs are special cases of hubs, and hubs can generate paths of different shapes at will (not only the shortest). Furthermore, traditional approaches can obtain hubs only after accomplishing the routing, while the characteristics of machine-learning approaches naturally give them the capability of learning such hubs. We envision that HubRouter has more applications compared with RSPs. To show this, we also conduct some applications, including RSMT construction and interactive path replanning in Sec. 4.4. Related works in this work are presented in Appendix A
From Pin-Pin to Hub-Pin Connection: A Two-phase Routing Scheme
Approach Overview. We formulate global routing as a two-phase learning model. The first phase is called the hub-generation phase, where we approximate the conditional distribution po c) to the prior distribution p(x c) when given ~ Pxx and condition c. Here a latent variable from prior distribution (usually assumed Gaussian distribution) while and x are respectively condition and input images (route, extracted hubs, and stripe mask). The second phase is called the pin-hub-conmecte phase, where we link the hubs generated in the first phase to obtain the final route.

---

(a) Route Sample.
(b) Generated Hub.
(c) Bad Connected Route. (d) Stripe Mask Control.
Figure 4: Illustration of how the stripe mask alleviates the noise impact. (a) A route sample. (b) The generated hubs, where the black/blue points are respectively hubs/noises. The gray stripes are generated masks. (c) Without the stripe mask, the route will be lengthened by some wrong and redundant paths (blue). (d) Two paths with the same length scheduled by the stripe mask.
This process can be treated RSMT construction, and we follow REST
RL-based algorithm to finish the routing. We respectively introduce these two phases in See. 3.1 and Sec. 3.2 In the generation phase, we also propose multi-task learning framework improve the quality of generated hubs, especially a novel stripe mask learning method is proposed to alleviate the negative effects caused by noise points cases. The overall algorithm is in Appendix B
33
3.1 Hub-generation Phase: Multi-task Learning of Hub, Mask, and Unused Pre- Pre-RRuting
Hub generation can be formulated as image-to-image task because the prior distribution p(x[c) is given from training dataset {x., c with N samples, where N denotes the total number of nets for training. So, seems that can learn distribution Pa, (x ie) and can generate x' ~ Pay (x|c c') given a new condition out of the training dataset. However, since the results of hub generation are not unique, a generative probabilistic distribution py (x|z, e) conditioned on e can better describe the routing. The main objective of hub generation is to minimize the difference between probability distributions p(x(c) and px(x/z, c) while often differs in expression under different perspectives. With the help of the rapid development of deep generative models, various works give us optional choices address hub generation. In Appendix B we respectively introduce how to incorporate
GAN I1 37),
VAE 26 44 and DPM [16] 17 into our generative framework.
Note that PRNet [6] has similar generation model structure to ours, yet we fall into different plights. PRNet employs a bi-discriminator (54) in CGAN 37 to inject the connectivity constraints into the training objective. This constraint indeed works and increases the correctness (all pins are connected within one route) rate by over 10%, but it is almost useless for complicated cases, as will further be discussed in Sec. 4.2 Under our two- phoppase learning scheme, the connectivity can be guaranteed, but the generated noise points have more negative impact on the final results. Thus, we propose a multi-task learning framework in the following to handle this potential weakness.
We claim that hub generation is highly different from other image generation missions because subtle noises hardly affect their generation quality. When generating hubs, noise point, especially the outermost one, can largely harm the wirelength of routing. We show this challenging phenomenon in Fig. 4(b and 4c)] where noise points (blue) in Fig. leb) to much longer route in Fig. [(c) since all the generated hubs should be connected within one route in our scheme. As discussed in other special generation tasks like layout generation (5). high reconstruction accuracy is typically maintained during training to ensure the generation is suitable for its requirement. Following this setting, we further devise multi-task learning framework, whereby the input in See. 3.1 is defined
(x(b))) (rt)), x(mok)) with three components, respectively hub, route, and mask. Note that although the hub generation is the main purpose in the first phase, we still generate routes and masks for auxiliary usages. In particular, the routes (rt) are pre-routing results and are unused in the second phase, which is employed to better obtain the continuous local perception in CNN-based networks. We further propose novel mask learning module named stripe mask to focus on had cases for hub generation. Specifically, the stripe mask is defined as a matrix x (msk) E {0, 1] mm,,, where (mak) = 0. At inference means there is hub in the i-th row j-th column; otherwise Xij X,y
(msk)
5

---

time, the generated hubs are masked by a binarized stripe mask (hubb)
= xij
(lub)
Xij
(mak)
with
(mss]] =I
(mss)
(mas)
1
max
X
(I)
2
1=1
where I[|] is an indicator function yielding 1/0 if the input is correct/wrong, Eq. shows that unless the noises in vertical/horizontal lines are dense, the stripe mask will not be formed. Fig. that, with the help of the stripe mask, the blue noise points can be masked, and the generated route can be shortened by removing the redundant (blue) paths. Empirically, an appropriate stripe mask can eliminate most of these noise points. The reasons why use the stripe mask rather than other masks [46] are due to the characteristics of global routing: Compared with other generation tasks, 1) eliminate most of them; 2) the routing result is not required to be unique while the stripe mask module is capable of providing different choices of routing. As shown in Fig. [[d] two black hubs can choose arbitrary yellow point as a turning point to connect each other while the length of paths is the same.
Noise points will greatly impact the routing quality, and the stripe mask learning
3.2 Pin-hub-connection Phase: RSMT Construction
After the hub-generation phase, the hub points will be sent to the pin-hub-connection phase to link all the generated hubs and obtain the final route. In this phase, the connection process is regarded as a rectilinear Steiner minimum tree (RSMT) construction problem, which is proved to be NP- complete (10). Note that it seems be possible to directly use RSMT construction to perform global routing; however, we claim that the hub- bub-generation phase is essential because 1) Without the generated hubs, RSMT construction can only find the shortest route and fail to generate an appropriate route under restriction; 2) A good hub- -ebeeeeerrtton phase for RSMT route reconstruction can be reduced to (n log n), as stated in the following theorem:
Remark 1. [Reconstruction Bonus] Suppose then its RSMT reconstruction can be performed in On log n) time complexity.
of hubs in an RSMT route correctly generated,
We further illustrate it in Appendix C Remark | Tintroduces the optimal time complexity of the pin- hub-connection phase for the ideal cases. While without this strong assumption, we follow REST (33 to learn the Rectilinear edge sequence (RES) under an actor-critic neural network framework. Given point set P {< y1) i=1
we want to get the RES, which is sequence of [P] - index pairs [11, h1),..., [1 11)] and pair (1a, means connecting point v; and h; with rectilinear edges. RES can be modeled as a sequential decision-makinn problem, so it is advantageous in RL. Note that the validity and existence of RES for the RSMT construction are already proved in REST.
As shown in Fig. 3 the actor network is used to create RES results with given coordinate points, while the critic network sets a baseline predict the expected length of RSMT constructed by the actor network and guide the actor network to obtain better performance. According to the evaluation of the critic network. the actor network will update the policy minimize the RSMT length. Specifically, the actor network is devised via an auto-encoder to learn better representations. We draw B point sets V = (V1, V2.... VB). and construct valid RES sets (V)))) for each point set V4. The objective minimize the expected advantage of the RSMT follows:
min E
[e (V:) ((V..))))
where 6V,)), is a predicted length of RSMT by the critic network and 6(V,, r.) is the actual length evaluated in linear time. Pe (ra) is the learnable probability of generating a specific RES with regard to 5. This objective is learned with an RL-algorithm [52). Apart from the actor network, the critic one is learned simply by mean square error (MSE) with gradient descent training:
min T FV.. (lb 1.)..
At test time, in line with 33 degrees with/without swapping a and y coordinates and then choose the best solution. This trick relatively more effective when hubs are not well generated.
we apply 8 transformations that rotate the point set by [0, 90, 180, 270]

---

Table 2: Experiments on ISPD-07 with 4 kinds of cases (detailedly introduced in Appendix compare HubRouter with PRNet on three metrics. Optimal results are in bold.
D We
PRNet (GAN)
HubRouter (VAE)
HubRouter (DPM)
HubRouter (GAN)
Metric
Case
Route-small-4
0.806
1.000
1.000
1.000.00m
Correctness Rate (%)
Route-small
0.334
1.000=..000
1.000=000
1.000
louge-
0.196
1.000=s.000
1.000 00000
1.000
Route-large
0.040
1.000
1.000 1000
1.000
Route-small-4
1.001
1.099 100000
1. 1.060
1.0111000:
Wirelength Rate (%)
Route-small
1.009
1 1.022.000s
1. 1.104
1.0021000
Route-large-4
1. 1.122
1.100
1.005
Route-large
1.041 100014
1.242.0021
1.001
Route-small-4
14.99
7.14
673.2 13.00
7.16
Generation Time (GPU Sec)
Route-small
18.51
7.70...20
670.23
8,36.1035
Route-large-4
19.47
7.24
673.01 1:.18
7.
Route-large
19.22
10.65
672.8624.4
9.75
The correctness rate too low for PRNet to reasonably evaluate the wirelength rate.
4 Experiment and Analysis
We introduce datasets and setups in Sec. 4.1
To show the performance of HubRouter, in Sec. 4.3
we respectively perform global routing on three kinds of datasets with both classical and learning baselines. Ablation study is performed to evaluate key modules in HubRouter. In Sec. [4.4] we introduce two applications, including RSMT construction and interactive path replanning. Finally, analyze the time overhead and show the scalability of HubRouter. Each experiment in this section is on a machine with 19- 10920X CPU, NVIDIA RTX 3090 GPU and 128 GB RAM, and is repeated 3 times under different seeds with mean and standard deviation values in line with 6
4.1 Datasets and Setups
Datasets. For training. we construct global routing instances by adopting NCTU-GR [34] to route on ISPD-07 routing benchmarks (38), which is in line with [6]. For test, we split the samples outside the training set into 4 types of routes according to the number of pins and the distance of pins. In detail, 'Route-small-4" and sooute-small' respectively represent cases with no more than and more than 4 pins and the Half-perimeter wirelength (HPWL) of pins is less than 16. Here, HPWL [max(2;) - min(x;)) ) [ [max(y;) - min(y:) for a group of pin positions (x,, y:) "2 in a net with "p pins. -Route-large-4 and PRoute-large are similar, whose HPWL is more than 16. Moreover, we introduce ISPD-98 [1] routing benchmarks and some simulated small-scale cases used by a deep reinforcement learning (DRL) method [1] named DRL-8 and DRI-16.
Metries, On ISPD-07 routing benchmarks, we choose correctness (all pins are connected within one route) rate and wirelength ratio (WLR, the ratio of the generated route length to the ground truth route length) introduced in [6] as our metrics. In the experiments of ISPD-98 and DRL cases, wirelength (WL), overflow (OF), and routing runtime are adopted. We also investigate some common metrics for generative models like Fréchet Inception Distance (FID) [51 and Inception Score (IS) 2 42 but they not suitable for taking on the real performance global routing.
Other Implementation Details. Details of training/test datasets and other protocols, including introduction of baselines and model structures, are presented in Appendix D
4.2 Unconnected Cases in Previous Generative Global Routing Approaches
We investigate the state-of- ohetheerrt generative global routing approach 6 and show that its correctness rate (CriRR) is extremely low for cases with complex connection of pins. As declared in Table 2 the CrrtR is only 0.04 for the Route-large case. This reasonable because connectivity assured only when almost each pixel of routed path is correctly generated in the routing image, which is very strict condition for complex cases. However, under our proposed two-phase learning scheme, HubRouter guarantees the CrttR all nets with the intermediately generated hubs. Morcover, despite
7

---

Table 3: Experiments on ISPD-98 (IBM01-06) and GRL cases. Wirelength (WL) and running time are compared among baselines and HubRouter (brown) with generative structures (HR-VAL -AE, HR-DPM, HR-GAN). Optimal results of WL and time are in bold. The results of DQN [3 on ISPD-98 are out of time (OOT) within weeks, so only GRL cases are displayed.
IBM02
IBM05
Labyrinth 24
75909
201286
187345
195856
421581
341618
2376
8214
Bourouter S
63687
172504
147463
169033
410614
280177
2328
7991
[1
OOT
WL
PRNet
61950
172802
152037
170493
420274
287777
2497
B172
HR-VAE
64203g1es
1764923400
159968-99
19895
434942gmn
300248
2415an
g584
HR IR-DPM
66446x15m
19058842u7
168454-24s
183696.66
475820
316700.244
11
:246
61056--1
167545
Labyrimth 21
6.47
10.14
12.07
36.81
7.54
18.43
< second
1 second
Boxrourer
7.01
12.91
11.74
41,76
13.45
29.17
second
1 second
Time
(Sec)
PRNer
IXQN
254.31
585.22
O0T
523.34
573.19
00T
1606.00
OOF
1227.31
>.
11.54
> day
28.25
HR-VAE
9.6611
9.69
10.19.tM
12.93
14,58.20
17.28
5.83am
5.88
IR-DPM
4369.0
12146
HR-GAN
41.02
46.58
$2,04
67.31
72.28
02.02
6.31
6.38
PRNa
DQN
20000
HubRouter
PRNet
Hubitouter (DPM)
HubRouter (VAE)
Overflow
15000
HubRouter (GAN)
Overflow
HubbRouer (DPM)
HohRouter (GAN)
4
5000
IBM01
IBM02
IBM03
IBM44
IBMGS
BM06
DRL-8
DRL-18
ISPD-98
DRL
Figure 5: Initialized overflow ISPD-98 (IBM01-06) and the DRL cases.
that PRNet only counts the wirelength the connected routes, HubRouter (GAN) is competitive with it in WLR. Note that we only evaluate the inference time of generation in Table (total time is analyzed in the next part), where PRNet is efficient with its one-shot superiority, though HubRouter (VAE/GAN) are still slightly better than it. An exception comes that HubRouter (DPM) suffers from time-consuming sampling for its multiple sampling steps.
4.3
Benchmarking Global Routing and Ablation Study
We test the WL, OF, and inference time on IBM01-06 from ISPD-98 as well as DRL cases. The detailed inference time that is divided into generation time and connection time is shown Ap- pendix EE.4 As shown in Table 3 the WL of HubRouter (GAN) outperforms others on ISPD-98 cases while HubRouter (DPM) hits the optimum DRL cases. This implies that HubRouter (DPM) is more capable on small-scale cases as the model complexity is not very high that easily incurs overfitting; however, due its large inference time, we do not decide to increase model complexity, but we believe it has high potential with more support of computing power. In addition, though HubRouter (VAE) fails to reach the top in WL, is the fastest among ML-based algorithms and is competitive with classical algorithms in some cases. Since there exists the theoretical lower bound this task R, we also compare the relative error on ISPD-98 cases Appendix [E.3 to better demonstrate the performance of HubRouter. As these generative models empirically show different behaviors, we argue that when given a new dataset, the choice of generative algorithms is decided by the industrial needs. Specifically, if one needs high quality, GAN is the best. If speed is highly required, VAE is the best. If one has abundant resources, DPM can adopted. Note that PRNet is significantly more time-consuming in this experiment compared with the results in Table 2 due to its post-proct poot-processing. In line with PRNet 66) as the overflow is decreased by rerouting, we compare the initialized overflow among bLsbd algorithms. As shown in Fig. HubRouter-GAN has minimal overflow in all test cases.
Ablation study is conducted in both generation and connection phases to show the influence of the introduced modules. As depicted Table in the hub- nub-generation phase, we respectively denote the HubRouter with inputs of hubs, hubs + routers, and hubs + routers stripe masks as HubRouter-h,

---

sequentially in this task because Table 4: Ablation Study on ISPD-07 with HubRouter (using GAN as generative embodiment).
Model
HubRouter-h
HuhRouter-hr
HubRouter-hrm
Generation-phase
WLR
1.031
1.022
1.005
Model
HubRouter (T=1)
HubRouter (T=8)
Connection-phase
WLR
1.099
1.087
1.005
Original Route
Add points
Replanning
Figure 6: Samples of interactive path replanning. The first line is routes with some added points while the second line is the replanned paths.
HubRouter-hr: and HubRouter-hrm. Among all, HubRouter- hrm reaches the optimal wirelength rate and HubRouter-hr also outperforms HubRouter-h, which indicates that the multi-task learning with route and stripe mask is effective. the pin-hub-connection phase, HubRouter-RMS) is denoted the one using R-MST as the connection model. In addition, HubRouter (T=1)(T=8) respectively represent the HubRouter with/without transformations introduced in Sec. expected, HubRouter (T=8) performs the best. Details hyperparameter are in Appendix
3.2 As
4.4 Further Studies and Discussion
We envision that HubRouter can do more than just global routing. Here, we respectively perform RSMT construction and interactive path replanning reflect the generality of HubRouter. The HubRouter in this section uses GAN as the generative embodiment due to its better performance.
RSMT Construction. It is intuitive that global routing for each net without overflow constraint is to minimize the wirelength, and thus close to the problem RSMT construction. A key question whether the generated hubs can enhance the construction of the pure RSMT during the connection phase. To evaluate it, we test the average percent errors compared with GeoSteiner (51) on random point data given by REST (33] together with running time, in Table We compare baselines including R-MST BGA 233, FLUTE [53) and REST [33]. When degree is smaller than 25 REST performs the best, but HubRouter outperforms others when degree is larger than 30. In particular, an unintuitive phenomenon shows that HubRouter performs even better with a higher degree. This is due to the characteristic of hub generation since noise point in dense case has much less impact on the error wirelength than sparse case. Apart from the error, REST has the shortest running time depending large batch size. However, HubRouter has degrees are different after generating some new hubs.
Interactive Path Replanning. Path replanning [19] refers to the process of revising a given path when the environment changes. a technique used in human-machine interaction. HubRouter capable of deciding new path with user-defined hubs. Fig. ssoows samples of interactive path replanning results, where HubRouter connects new points and maintains most the previous paths.
Analysis of Scalability and Time Overhead. We claim that HubRouter is scalable in both phases. In the generation phase, for fixed scale of routing graph, similar to PRNet 66, the hub generation is one-shot. This implies that its generation speed is unrelated to the number of pins and is linear to the number of nets, as respectively shown in Fig. (eft/middle) For connection, we show in Sec. 3.2 that the RSMT construction can degrade to a O'n log n)) R-MST problem under some ideal assumptions. In addition, as depicted in Fig. 7 (right), equipped with an actor-critic network, the time overhead of HubRouter increases more slowly than pure RSMT construction.
Non End-to-End framework. HubRouter is a two-phase framework that is designed with careful analysis. It differs from PRNet 66, which is an end-to-end attempt to produce the routes directly, but

---

18
140
15
RSMT Constrction Time (Sec)
Generation (Sec)
Generation Time (Sec)
120
GenSt
16
13
1.00
11
80
40
12
HobRouter
20
HubRouter
0.8x++
10
10
20
30
40
50
11
10
20
30
40
50
#Pins
#Nets (x1e4)
Degrees
Figure 7: Generation time of HubRouter is constant number of pins (left) and is linear number of nets (middle). The RSMT construction time of HubRouter rises slower than GeoSteiner [51] (right).
Table 5: Experiments on RSMT construction. HubRouter and four baselines are compared to the RSMT solver GeoSteiner (GeoSt) and the best results on errors are in bold. Time overhead is also evaluated on GeoSt, REST, and HubRouter. Mean and variance are given with three trials.
Average Percent Errors (%)
Time (Sec)
Degree
GeoSt
R-MST
BGA
FLUTE
REST
HubRouter
GeoSt
REST
HubRouter
5
0.00
10.91
0.23
0.00
0.00
0.24
ance
11.89 2024
13.44
10
0.00
11.96
0.48
0.04
0.01
0.18
4.05
12.16
16.43=030
15
0.00
12.19
0.53
0.06
0.03
0.15
9.26
13.80104s
16.922>4
20
0.00
12.41
0.57
0.07
0.13
27.35
14.79
19.85
25
0.00
12.47
0.58
0.18
0.12
0.12
29.01 2007
16568
23.01
30
0.00
12.56
0.60
0.23
0.16
0.10
43.00
18.53
27.02=230
35
0.00
12.63
0.62
0.26
0.21
=.09
60.32+aa20
19.67 +o.s
33.11
40
0.00
12.65
0.63
0.29
0.25
0,08
78. 78.80+a0e
20.91 +0.1
39.42+335
45
0.00
12.67
0.63
0.30
0.32
0.07
102.26 o2
22.36
49.57
50
0.00
12.72
0.64
0.29
0.36
0.06
125.26-0at
23.79 20.20
61.55
faces the challenge of non-connectivity and inefficient post-processing. HubRouter addresses this by generating hubs in the middle stage and connecting them with pins to ensure connectivity. However, this two-stage framework involves a discretization process, which prevents differentiable learning and simultaneous optimization. We also pursuit the cost-effective end-to-end solver for further work.
5 Conclusion and Outlook
We have proposed HubRouter, a generative global router in VLSI with a two-phase learning scheme: the hub-generation phase and the pin-hub-connection phase. In the generation phase, HubRouter generates hubs instead of routes while the connection phase, it connects the hubs with RSMT construction. Experiments scalability. When adopting HubRouter, the potential negative impacts should be taken care: 1) The incorrect generation might lead to poor routing results; 2) Generative models computationally intensive and might consume lot resources.
real-world and simulated datasets show its effectiveness well as
This paper also has some limitations for future work: 1) The two-phase scheme is not end-to-end under a joint training scheme; 2) The supervised module for hub generation depends on large amount of training data; 3) Like SOTA generative global routing algorithms [6], the further decrease on overflow needs a reroute process; 4) Finally, it would also be compelling to integrate the learning- based methods of logic synthesis (55), with routing methodologies. including those presented in this work. This would allow for a data-driven approach to the chip design pipeline.
10

---

References
[T] C. Alpert. The ispd98 circuit benchmark suite. In Proceedings of the 1998 international symposium on Physical design, pages 80-85, 1998.
[2] A. Borji. Pros and cons of gan evaluation measures: New developments. Computer Vision and Image Understanding. 215:103329, 2022.
[3] G. Chen, C. W. Pui, H. Li, J. Chen, B. Jiang, and E. F. Young. Detailed routing by sparse grid graph and cunimum--rea-capuun path search. In Proceedings of the 24th Asia and South Pacific Design Automation Conference, 2019.
[4] H. Chen and Y.-W. Chang. Global and detailed routing, In Electronic Design Automation, pages 687-749. Elsevier, 2009.
[5] C.-Y. Cheng, Huang, Li, and Li. Play: Parametrically conditioned layout generation using latent diffusion. arXiv preprint arXiv:2301.11529 2023.
[6] R. Cheng, X. Lyu, Y. Li, J. J. J. Hao, and J. Yan. The policy- gradient placement and generative routing neural networks for chip design. In Advances in Neural Information Processing Systems, 2022.
[7] R. Cheng and J. Yan. On joint learning for solving placement and routing in chip design. In Advances in Neural Information Processing Systems, 2021.
[8] M. Cho, K. Lu, K. Yuan, and D. Z. Pan. Boxrouter 2.0: Architecture and implementation of hybrid and robust global router. In 2007 IEEE/ACM International Conference on Computer- Aided Design, pages 503-508. IEEE, 2007.
[9] J. de Vincente, J. Lanchares, and R. Hermida. Rsr: A new rectilinear steiner minimum tree approximation for fpga placement and global routing. In Proceedings. 24th EUROMICRO Conference (Cat. No. 98EX204), volume 1, pages 192-195. IEEE, 1998.
[10] M. R. Garey and D). S. Johnson. The rectilinear steiner tree problem is np-complete. SIAM Journal on Applied Mathematics, 32(4):826 -344, 1977.
[11] Goodfellow, Pouget-Abaatd Abadie, M. Mirza, Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In NIPS, 2014.
[12] W. Guo, H.-L. Zhen, X. Li, W. Luo, M. Yuan, Y. Jin, and Yan. Machine learning methods in solving the boolean satisfiability problem. Machine Intelligence Research, pages 1-16, 2023.
[13] M. Hanan. On steiner's problem with rectilinear distance. SIAM Journal Applied mathematics, 14(2):255-22 1966.
[14] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[15] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
[16] Ho, Jain, and Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
[17] J. Ho and Salimans. Classifier-frer diffusion guidance. In NewrIPS 2021 Workshop on Deep Generative Models and Downstream Applications, 2021.
[18] J.-M. Ho, G. Vijayan, and C.-K. Wong. New algorithms for the rectilinear steiner tree problem. IEEE transactions on computer-aided design of integrated circuits and systems, 182) 1990.
[19] K. Honda, R. Yonetani, M. Nishimura, and T. Kozuno. When to replan? an adaptive replan- ning strategy for autonomous navigation using deep reinforcement learning. arXiv preprint 2xXi:2334.11244 2023.

---

[20] F. K. Hwang. On steiner minimal trees with rectilinear distance. SIAM journal on Applied Mathematics, 30(1):104-11, 1976.
[21] K. Hwang. An o (n log n) algorithm for rectilinear minimal spanning trees. Journal of the ACM (JACM), 26(2):177-182, 1979.
[22] Isola, J.-Y. Zhu, Zhou, and A. A. Efros. Image-to-image translation with conditional adversarial networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1125-1134, 2017.
[23] A. B. Kahng, Mändoiu, and Z. Zelikovsky. Highly scalable algorithms for rectilinear and octilinear steiner trees. In Proceedings of the 2003 Asia and South Pacific Design Automation Conference, pages 827-833, 2003.
[24] R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh. Pattern routing: Use and theory for increasing predictability and avoiding coupling. 7CAD, 2002.
[25] D. P. Kingma and Ba. Adam: A method for stochastic optimization. arXiv preprint
1412 2014.
[26] D. P. Kingma and M. Welling. Auto-encoding variational bayes. In ICLR, 2014.
[27] M. Kramer and Van Leeuwen. The complexity of wirerouting and finding minimum area layouts for arbitrary vlsi circuits. Adv. Comput. Res, 2: 2:129-146, 1984.
[28] Y. Lai, Y. Mu, and P. Luo. Maskplace: Fast chip placement via reinforced visual representation learning. arXiv preprint arXiv:2211.13333 2022.
[29] Y. Li, J. Guo, R. Wang, and Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[30] Y. Li, L. Shi, and J. Yan. lid-gan: an iid sampling perspective for regularizing mode collapse. In E. Elkind, editor. Proceedings of the Phirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages 3929-3938. International Joint Conferences on Artificial Intelligence Organization, 2023. Main Track.
[31] H. Liao, W. Zhang, X. Dong, B. Poczos, K. Shimada, and L. Burak Kara. A deep reinforcement learning approach for global routing. Journal of Mechanical Design, 142(6), 2020.
[32] Y. Lin, S. Dhar, W. Li, H. Ren, B. Khailany, and D. Z. Pan. Dreamplace: Deep learning toolkit-enabled gpu acceleration for modern vlsi placement. In Proceedings of the 56th Annual Design Automation Conference, pages 1-6, 2019.
[33] Liu, G. Chen, and E. F. Young. Rest: Constructing rectilinear steiner minimum tree reinforcement learning. In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 1 1145- IEEE, 2021.
[34] W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao. Netu-gr 2.0: Multithreaded collision-aware global routing with bounded-length maze routing. IEEE Transactions on computer-aided design of integrated circuits and systems, 32(5):709 2013.
[35] S. Mahboubi, H. Ninomiya, T. Kamio, H. Asai, et al. A nesterov's accelerated quasi-newton method for global routing using deep reinforcement learning. Nonlinear Theory and Its Applications, IEICE, 12(3):32-335. 2021.
[36] L. McMurchie and C. Ebeling. Pathfinder: A negotiation- performance-driven router for fpgas. In Proceedings of the 1995 ACM third international symposium on Field hiedd-programmable gate arrays, pages 111-117, 1995.
[37] M. Mirza and S. Osindero. Conditional generative adversarial nets. arXiv preprint
1411 2014.
[38] G.-. Nam, M. Yildiz, D. Pan, and P. Madden. Ispd 2007 global routing contest. 2007.
12

---

[39] W. L. Neto, L. Amarú, V. Possani, P. Vuillod. J. Luo, A. Mishchenko, and P.-E. Gaillardon. Improving lut-based optimization for asics. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pages 421-426, 2022.
[40] W. L. Neto, M. T. Moreira, Y. Li, L. Amarù, C. Yu, and P.-E. Gaillardon. Slap: a supervised learning approach for priority cuts technology mapping. In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 859-864. IEEE, 2021.
[41] O. Ronneberger, P. Fischer, and T. Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Asistted Intervention-MICCA. 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part !!I 18, pages 234-241. Springer, 2015.
[42] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen. Improved techniques for training gans. Advances in neural information processing systems, 29, 2016.
[43] H. Shin and A. Senggoovann--incettee modifications: Mighty. IEEE transactions on computer-aided design of integrated circuits and systems, 6(6):942-99))) 955, 1987.
A detailed router based on incremental routing
[44] K. Sohn, H. Lee, and X. Yan. Learning structured output representation using deep conditional generative models. Advances in neural information processing systems, 28, 2015.
[45] J. Song. C. Meng, and S. Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021.
[46] L. Song, D. Gong, Z. Li, C. Liu, and W. Liu. Occlusion robust face recognition based on mask learning with pairwise differential siamese network. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 773-782, 2019.
[47] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforce- ment learning with function approximation. Advances neural information processing systems, 12, 1999.
[48] D. Utyamishev and I. Partin-Vaisbane Vaisband. Late breaking results: A neural network that routes ics. In DAC. IEEE, 2020.
[49] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and
I. Polosukhin. Attention is all you need, Advances in neural information processing systems, 30, 2017.
[50] P. Wang, A. Lu, X. Ye, L. Chen, M. Yuan, J. Hao, and J. Yan. Easymap: Improving technology mapping via exploration-enhanced heuristics and adaptive sequencing. In IEÉE/ACM International Conference on Computer-Aider Design, 2023.
[51] D. M. Warme. Spanning trees in hypergraphs with applications to Steiner trees. University of Virginia, 1998.
[52] R. J. Williams. Simple statistical learning. Reinforcement learning, pages 5-32, 1992.
algorithms for connectionist reinforremett
[53] Y.-C. Wong and C. Chu. A scalable and accurate rectilinear steiner minimal tree algorithm. In 2008 IEEÉ International Symposium on VLSI Design, Automation and Test (VLSI-DAT), pages 29-34. IEEE, 2008.
[54] X. Yu, X. Zhang, Y. Cao, and M. Xia. Vaegan: A collaborative filtering framework based on adversarial variational autoencoders. In IJCAI, pages 4212-4212,
4212, 2019.
[55] J. Yuan, P. Wang, J. Ye, M. Yuan, J. Hao, and J. Yan. Fasyso: Exploration-enhancal reinforce- ment learning for logic synthesis sequence optimization and a comprehensive rl environment. In IEEE/ACM International Conference on Computer-Aided Design, 2023.
[56] Zhang. J. Guo, S. Sun, J.-G. Lou, and D. Zhang. Layoutdiffusion: Improving graphic layout generation by discrete diffusion probabilistic models. arXiv preprint arXiv:2303.1 //589, 2023.
[57] Zhang, C. Liu, X. Li, H.-I.. Zhen, M. Yuan, Y. Li, and J. Yan. survey for solving mixed integer programming via machine learning. Neurocomputing, 519::000000n..1500022::0:000 219:205-117,22222
13

---

A Related Works
Global Routing. Traditional global routing algorithms typically start with decomposing multi-pin nets into two-pin nets by minimum spanning tree (MST) or rectilinear Steiner tree (RST) 9 [8] Then, two-pin nets routed by heuristic-based methods such pattern routing (24] and maze routing. Finally, a rip-up and reroute [43] process is adopted to refine the final result. Negotiation- based rip-up and reroute algorithms (36 g reveal their superiority by considering rerouting history. In addition to classical solutions, recent methods start to resort to learning techniques. RL-based routers with a DQN agent [I] sequentially decide every route direction in net and aim to generate a better result than A router, but they are time-consuming and currently often only applicable to small grids, rather than realistic settings. Generative models are recently introduced generate routes in a net without decomposing it into two-pin nets. 48 uses generative models to speed up global routing at the cost of reduced routability. In PRNet 6 global routing is solved by conditional generative models (specifically CGAN (7), but it still heavily depends on unscalable cost-processing due to some unconnected routes. This paper achieves connectivity by decomposing global routing into a two-phase learning scheme.
Generative Model. GAN M. VAE [26] and DPM 16 are three widely-used deep generative
models applied in the generation of different forms of data. Moreover, some works [37 44 17 incorporate conditions to make the generation under more fine-grained control, which is important
in applications like layout design [5] [5]. combinatorial optimization [29]. and chip design [6].
Generation tasks also attract the research on the distributions of real-world data [00, which show
high potentials. In this paper, we present a novel and more scalable hub generation scheme to address global routing problems.
RSMT Construction. Rectilinear Steiner minimum tree (RSMT) gives the shortest possible solution interconnect pins in net. This problem belongs to the class of combinatorial problems 12 57 that are NP-Complete [T] and challenging for machine learning researchers. Since it is computationally intractable to find an optimal solution in general, rectilinear minimum spanning tree (R-MST) 21 is widely used to approximate RSMT with time complexity of (n log n)) [21], but its length is at most 1.5x of the optimal RSMT 20). FLUTE [53] designs look-up table for small nets and decomposes larger nets into smaller nets that can be solved by the table. REST (33 introduces rectilinear edge sequence (RES) to encode RSMT and train an actor-critic neural network by reinforcement learning. Compared to existing RSMT solvers, this paper performs RSMT construction after a hub generation phase, and as such, global routing is completed by connecting the pins and generated hubs.
B
Algorithm
B.1 Deep Generative Approaches
We incorporate three prevailing generative models into our generation framework. These approaches give us different perspectives of hub generation:
GAN [II]. Conditional GAN (CGAN) (37 applies a discriminator D(-) to classify whether the input real or fake (generated), which minimizes the logistic loss function - log D& (p((cc) - log(1 (1 (x z))) with regard to Φ. It equals maximizing its negative value. Meanwhile, the generated distribution (x|c, z) is called a generator in GAN, which approximates to p(x|c) by deceiving the discriminator with regard to 0. Together optimize the above objectives, we have a min-max strategy:
min max Σ [log Dx(x,) log(1 Dx(po(x(c = C, (ooz)r(())))
We use neural networks to learn the discriminator D.(.) and the generator po (x|c, z).
VAE 26). Conditional VAE (CVAE) [4] minimizes Kullback-Leibler (KL) divergence to approx- imate simulated inference network 4s x, c) the intractable posterior distribution po (z) x, c). such that we can apply the stochastic gradient variational Bayes (SGVB) framework to optimize the variational lower bound
log po (x(e) 2 - KL [z) c) c) c)] (x/(,)) log pe (x|c, z).
(5)
①
14

---

T
S
Source Node
Target Node
S
Constraint
The simplified 2-pin problem, namely, routing the source and target node (pin) under constraints while searching for the shortest wirelength for single net. The constraints represent the obstacles derived from capacity.
Figure 8:
Note that the first term in Eq. 5 is easy to integrate since the KL divergence for Gaussian dis- tribution has closed form, and the second term is often simplified by Monte-Carlo sampling (xlxe)) log pe (x|c,,) 2) ss + log po (x(c, So, the objective of minimizing the empir- ical lower bound can be written as:
Σ log (x|c, 201)
min 0,0
KL (zo(2)x,
L
(6)
where z²)) = 9 c, e el) NN Ii is a reparameterization trick (26] and is the number of samples. Neural networks used to learn the encoder go (z/z,, c), the decoder (x(x) z). and the conditional prior network (z)
DPM [16]. DPM injects noise into the original data step by step until it turns out to be a known distribution and reverses these steps when sampling. DPM respectively defines these processes as the forward process go Xx x1) and the reverse process pe (xx:1 (x:) with t {1...., T):
9(x1:7 Xx) = [[xxx((xe1))
((x((x(1)= N(xx: / Bix:- 3cI),
1m1
(x(x))) = p(xr) po (x
where I is an identity matrix, (B.)T-1 are fixed variance schedules with ascending values, and
Oi = 1- Br. {a]][= are also fixed values. Similar to VAE, with training the variational lower bound of the marginal log likelihood and reparameterization, we finally obtain the condition-guided
DPM objective:
min E Bxcce-Nio. [lle ca(2,, c, 1)13]
(8)
Following classifier-free guidance 17
we initialize zr and denoise it by = (1 + (w) (uu))cell - (2,, c, ()
(z), t), and accelerate the sampling process with fewer sampling steps by DDIM [45).
B.2 Training and Sampling
Adam is used to train in both generation and connection phases. Specifically, Alg. and Alg.
illustrate the training processes of these two phases, while Alg. shows the sampling process.
15

---

Algorithm Training in Hub-generation Phase.
Input: Number of iterations n_ilers, minibatch size m, condition images c, real route images x(rt),
generative model mode mode {GAN, VAE, DPM), maximum time step T in DPM.
for iler from to n_ilers do
Sample minibatch of condition images {ci, C. ). real route images (x( ;... (rt)
Compute x; (bwb) and x {mas) for each (rt), and compose x; fx (hub) (rt) (mok)) (i
x; x
1. m);
if mode = GAN then
Sample minibatch of m noise images (2). ,2m) where 2, (O (i = ,...,,,,...
J.
Ascend the stochastic gradient of the discriminator in Eq.
V D==1 [log (x,) log(1 Dp
C; 2;)))]];
Sample minibatch of noise images {Zi..... am
Descend the stochastic gradient of the generator in Eq.
Vo Ei= [log(1 - D& (xo = C, 2 = 2. 2.)))]]:
else if mode = VAE then
10
Sample minibatch of noise images {EL, Em ). where e (O, (i 1,... m,):
11
Compute [Z1,-.. ... /m) using the reparameterization trick [26];
Descend the stochastic gradient of Eq. 6
Vo.0 T7 Σ (- KT. (gs (z)x Xi, c. [po c.)) + log (x/c C; z 2))]; // Let I,
14
else
if mode = DPM then
15
Sample minibatch of m noise images {EL, Em). where e, ~ N( (i = ..... ,
16
Sample minibatch of m time steps {t1, tm where to U1(1, .T} (i ,.))..m.)
17
Descend the stochastic gradient of Eq. 8
V
E Xx.. |||
co c, t)1
Output: Trained models with parameters and Φ.
Algorithm Training in Pin-huu--connetton Phase.
Input: Number of iterations n p_iters, minibatch size B. for iter from to n1_teers do
19
Sample B random point sets V .V.,... VB
Construct valid RES sets ((K)) for each point set Vi:
Sample single RES r; R(V) for each point set Vi:
22
Linearly evaluate the actual length b(V;,:;);
23
Descend the gradient in the actor network according to Eq. using reinforcement algorithm 52
A D (V:) b(V,, r:)] Ve [Pe(r:)];
24
Descend the gradient in the critic network according to Eq.
V<
B Σ (V4) 6(V,,
Output: The trained model with parameters & and Ç.
C Definition and Theorem
C.1 2-pin Problem
Fig. g gives example of the '2-pin' problem, which is the simplest version of global routing, but out to be an NP-Complete problem [27 BI.
C.2 Bonus of RSMT Reconstruction
Lemma 1. Rectilinear Steiner points hubs.
16

---

Algorithm 3 Sampling Routes.
Input:
Condition image Co, generative model mode mode {GAN, VAE, D.M), trained gen-
erative models and the RSMT connection model, DDIM 45 timesteps -/,,-.. " guide weight to in DPM.
// Hub-generation Phase.
26
mode = GAN then
Sample noise sample Zo (O,
28
Generate X (x Co. 2 = Zo);
29
else if mode = VAE then
Sample noise sample 2o (N,
31
Generate X6 (x Co, 2 20):
32
else mode = DPM then Sample noise sample Xia Eta (0,
33
for I from la 11 do
34
35
Compute previous (i and current or
36
Predict the noise: Et (1 + w) c0 (x{x ct,, {2) - w :
Predict No: Px. f (Zia / ai, Et ) v
37
Compute variance: oi (1) 1 0i 1/(1 0i (1 0z, / /
39
11 we directly set r here.
Compute the direction pointing xi,; dxi;
V --,--,11- of E
41
Compute Xi,_1² x1 V Pxp + dxy, + oi (1) -t,, where ft, (.,,I...
Finally, have Xo:
43
// Denote x = Xo, and X,j as its element in i-th row and j-th column.
Compute the binarized strip mask ((msk) according Eq. where each x ((ms)) is computed as: (mak) 1
(mak) =T max 1 Em Xi
(msk)
x
ij
11 Note that x {x(hub), x(11), (mmsk)).
(hub) (lub) 46 Compute the masked hubs: Xij
(mak)
Xij
x Xij
47 Obtain the union of hubs and pins V;;
// Pin can-hubb-coneettion Phase.
49 Obtain the RES r according to the maximum pe(ri). where r ~ R(V);
Compare 8 transformations introduced in Sec. 3.2 and pick the optimal route with the shortest length. Output: The generated route and its length.
Proof According Hanan theory [13], the rectilinear Steiner points can be restricted to the Hanan grid. The definition of hubs in this paper implics that all the routed points on the intersection of Hanan grid hubs, rectilinear Steiner points must be hubs.
Remark 1. [Reconstruction Bonus] Suppose set of hubs in an RSMT route is correctly generated, then its RSMT reconstruction can be performed in O(n log n) time complexity.
Proof According Lemma since all the rectilinear Steiner points are hubs, there is need to introduce extra rectilinear Steiner points when generating an R-MST towards all the hubs. So, the RSMT problem is degraded to an R-MST problem. which has been proved to be addressed in Onglogn) time complexity 21].
D Experimental Protocols
D.1 Dataset.
Real-world Datasets ISPD-07 38 and ISPD-98 D and the simulated dataset constructed by (we call 'DRL') employed in this work.
17

---

Table 6: Summary of the test dataset. We respectvvely show the scale size, vertical//oorizontal cttp://rrriiaaaacccccia...... number of nets, and average/maximum number of pins for each net.
CASE
IBM01
IBM02
IBM03
IBM04
IBM05
IBM06
DRL-8
DRL-16
SIZE
64x64
80x64
80x64
96x64
128x64
128
8x8
16x 16
CAP. (V H)
24/ 28
44 68
40 / 60
40/ 46
84 126
40 66
4/4
6/6
#NETS
11507
18429
21621
26163
27777
33354
20
30
AVG. #PINS
4.31
4.88
4.10
3.86
5.25
4.21
5.25
6.12
MAX #PINS
42
134
55
46
17
35
10
In line with (6, we construct training datasets by adopting B4 to route on ISPD-07 benchmarks and we declare the details unstated in [6]. We initialize the capacity given by the benchmarks and sequentially route the nets using the results of [34]. Each time the capacity is updated, condition image, consisting of the current capacity and the positions of pins to be routed in the next net, is generated. Meanwhile, ground ground-truth route image is generated and saved correspondingly. By clipping them to the same scale 64 x 64 (if possible) randomly, the image will be saved to different directories, i.e., Route-small-4, Route-small, Route-large-4, and Route-large, according the number of pins up and their HPWL. Specifically,
1) Route-ssalll small-4: npp 4 and HPWL L S 16;
2) Route-small: np > 4 and HPWL S 16;
3) Route-large-4. np 5 4 and HPWL > 16;
4) Route-large: "p and HPWL > 16.
Examples partly shown in Fig. TO This division the hand originates according to the observation from 6 that the average pin number is about most chip cases, as shown in Table 6 and on the other hand, would like to show the non-connectivity of previous generative global routing approaches under different situations. We choose bigblue4, newblue3, newblue4, and newblue7 (name the cases in ISPD-07) as the training cases and generate 15K training samples for each case's s each category. Thus, we have a total of nearly 240K (some categories cannot generate maximum 15K samples). In Table we test the cases of adaptec adaptec2, newbluel, newblue2. bigblue and bigblue2 in ISPD-07 with total 10K samples for each category.
Cases in ISPD-98 and DRL are used test data in Table and Fig. 5 however, their scales the same as the input data. So, we clip the ISPD-98 and pad the DRI. to ensure scale consistence. Very few (<0.1 1%) nets in ISPD-98 cannot satisfy the input scale due to their exceeded pin positions. For these special samples, we divide them into multiple samples and then feed them to the model. Note that there might be better solutions to deal with the scale problem, e.g., the input-size-ddapting module in [6]. but it is not the main focus of this work. Moreover, two simulated dataset DRL-8 and DRL-16, whose scales are respectively 8 and 16 16, generated using the tool introduced by B1. We randomly generate 10 cases for DRL-8 and DRL-16 16, respectively. More information about the test dataset is detailed in T
D.2 Baselines.
The baselines referred in Table introduced as follows:
1) Labyrinth [24. classical routing algorithm that discusses how the concept of pattern routing can be used to guide the router to a solution that minimizes interconnect delay without damaging the routability of the circuit;
2) BoxRouter 8 a classical global router that first employs a pre-routing strategy to identify the most congest and then performs box expansion and progressive integer linear programming((LP);
3) DQN [11, a reinforcement learning global routing algorithm with A router burn-in memory and conjoint optimization;
18

---

4) PRNer [6), a joint learning framework that together addresses the placement and routing problems, where the routing is based on generative approches.
In the RSMT construction experiment in Sec. 4.4 the referred baselines are:
1) GeoSteiner [5]], the optimal RSMT construction solver;
2) R-MST, an efficient implementation of R-MST construction with time complexity of O(n log n);
3) BGA 23
practical On log" n) sub-optimal solution of RSMT construction with heuristies.
4) FLUTE [53] a fast and accurate RSMT construction approach by using look-up table. Note that it can reach the optimal solution for nets up to 9 degrees.
5) REST 33
state-of-the-ard RL-based approach that uses actor-critic network predict the Rectilinear edge sequence (RES) for RSMT construction.
D.3 Model Setting.
In the hub-generation phase, VAE employs CNN 48 structure while GAN uses ResNet [14 22
structure. which is in line with (6), but we make some revisions. For instance, [6] utilizes a bi- discriminator (54) to inject the correctness constraint to the objectives, but our proposed HubRouter no longer requires it within the two-phase learning scheme. In addition, the model structure of DPM follows [17] due the condition guidance and uses U-Net [41 structure, but make it lightweight to achieve more rapid sampling time. Fig. details the components of the generative models in this work. In the
phase, follow REST 33] to multi-head attention encoder 49 in its auto-encoder framework.
E Experimental Analysis
E.1
Hyperparameters
We search hyperparameters on the validation dataset with the learning rate in [0.001, 0.0001] and reduce the learning rates by 0.96 after every 10 epochs until the validation loss longer decreases for over 20 epochs or the number of epochs reaches maximum of 200. In the hub-generation phase, optionally choose three generative models, including GAN, VAE, and DPM. For GAN and VAE, we use similar structures and search the number of ResNet blocks in [3, 6, 9] and the number of lownsampling/upsamping layers in [2, 4]. For DPM, we search the number of DDIM steps in [25, 50. 75], the guide weight w in [0.0, 1.5, 2.0]. and the maximum timestep in [500, 1000]. The best models are chosen by the optimal wirelength rate while keeping the generation time tolerable. Each experiment is trained with a batch size of 64 and the optimizer Adam (25] with the decay rate of first(second)-ordee experiments in Sec. [] the number of ResNet blocks and the number of wwtpssammmliggsaamaaaaan layers for GAN and VAE are respectively set as 9 and 2. For DPM, we set the number of DDIM steps as 50, the guide weight as 1.5, and the maximum timestep as 500. In the pin-hub-coonection. we 33 and employ the model with adjusted parameters.
moment estimation 0.599.9 and the L2 penalty coefficient 0.01. In the
follow REST
E.2 Correspondence between Hub and Route
The main idea of the two-phase learning scheme originates from our observation and curiosity whether the hub and the route have high correspondence. If so, we could conclude that the optimal final routes would approximately be the same for generating hubs or generating routes directly. According to the definition in Def. [ is apparent that each route can uniquely determine its hubs, but regretfully the opposite is not true. That is to say, when given group of hubs, we cannot decide uniquely what their original route is; however, we empirically find the correspondence between hubs and routes is high. To show this, we generate the hubs according to the definition for each net in ISPD-07 and then use these generated hubs and pins to construct RSMT. As shown in Table 7 the correspondence rates are respectively 99.7% and 98%18% for Route-small- and Route-large-4 and importantly these two categories occupy large proportions (totally over 80%) in ISPD-98 and ISPD-07 cases. Though the correspondence rate in Route-large is not high, the mean square error
19

---

Generator
IL updown
11 blocks
Down Sampling
Down Sampling
ResNet Block
ResNet Block
Input
updoow
Up Sampling
Up Sampling
output
Discriminator
blocks
R RsNeet
ResNet Block
input
output
Block
GAN
Generator
Discriminator
(a) Model Structure of GAN.
Encoder
updoon
blocks
Down Sampling
Down Sampling
ResNet Block
Res Block
input
output
Decoder
updown
Up Sampling
Up Sampling
input
output
VAE
Reparameter- ization
Encoder
Z
Decoder
Model Structure of VAE,
U-Net
n updoown
n updoown
ResNet Block
Down Sampling
Down Sampling
Up Sampling
Up Sampling
input
output
Transformer Encoder
Input
Norm
MLP
Norm
output
A ttention
DPM
Training
Sampling
U-Net
U-Net
Transformer
MSE
Transformer Encoder
Encoder
Xp
MLP
MLP
(c) Model Structure of DPM.
Figure 9: Model Components of a) GAN; b) VAE; DPM.
20

---

Table 7: Correspondence between hubs and routes. The correspondence rate and mean square error (MSE) are computed on ISPD-07 cases.
Category
Route-small-4
Route-small
Route-large-4
Route-large
Correspondence Rate (%)
99.7
80.31
98.18
48.75
MSE
10-6
0.0004
0.0002
0.003
Proportion in ISPD-98 (%)
65.38
4.69
15.94
13.99
Proportion in ISPD-07 (%)
66.25
9.67
14.89
9.19
Table 8: Relative error on ISPD-98 cases. The first line introduces the theoretical lower bound introduced in [7]. Optimal results are in bold.
Model
IBM01
IBM02
IBM03
IBM04
IBM05
IBM06
Lower Bound [7]
60142
163863
145678
162734
409709
275868
Labyrinth [22]
0.262
0.589
0.693
0.551
0.181
1.093
BoxRouter [7]
0.059
0.107
0.03
0.105
0.015
0.077
PRNet [6]
0.03
0.115
0.106
0.129
0.176
0.198
HR-GAN
0.015
0.028
0.023
0.026
0.036
0.039
(MSE) between the generated route and the real one is still extremely low. These observations ensure that the hub generation can be effective for global routing.
E.3 Relative Error on ISPD-98 eases
To judge the improvement of gaining on the optimal wirelength rather than the absolute value, we further compare the relative error in Table where the relative error is computed (WL- b)/b. Here, b denotes the theoretical lower bound [8] As shown in this table, the WL promotion of HubRouter notable compared with the SOTA generative global routing method (PRNet).
E.4 Generation Time and Connection Time
We present the breakdown of the inference time for each phase on ISPD-98 (IBM01-06) and GRL cases in Table From overall perspective, the connection phase has comparable time costs for the three generative models. The generation phase, however, dominates the overall time consumption. This indicates that HubRouter achieves faster performance than other generative models by reducing the time spent in the connection phase.
Table 9: Generation and connection time in the experiments on ISPD-98 (IBM01-06) and GRL cases.
Metric
Model
IBM01
IBM02
IBM03
IBM04
IBM05
IBM06
GRL-8
GRL-16
TIR-VAE
8.13
6.68
7.47
8.01
9.90
12.18
5.78
5.77
Generation Time (Sec.)
HR-DPM
1802
2841
3014
3839
4329
5110
36.76
49.55
HR-GAN
40.12
45.36
49.02
61.33
68.47
91.50
6.04
6.26
HR-VAE
1.67
3.23
2.87
5.04
0.04
Connection Time (Sec.)
HR-DPM
1.80
3.51
2.88
4.99
4.98
0.04
HR-GAN
L.72
3.30
2.84
5.00
5.04
5.11
0.04
0.11
E.5
Route Generation Results
Examples of the condition and real route images, well as the route generation results of Route- small-4, Route-small, Route-large-4, Route-large introduced in Appendix D.I are depicted in Fig.
21

---

(a) Route-small-4.
r
7
r
>
Route-small.
(c) Route-large-4.
L
E
(d) Route-large.
Condition images (first line), Real route images (second line), and the route images generated by our propose two-phase learning scheme (third line), randomly sampled in a) Route- small-4; b) Route-small; e) Route-large-4; d) Route-large.
Figure 10:
22


Reviews:
[{"review_id": "1jjS7nQVDh", "reviewer": "Reviewer_Co1X", "summary": "This paper presents a new two-phase learning approach, called HubRouter, to address the issue of unconnectivity in the generated routes of global routing (GR) tasks in VLSI systems. It has two steps. Firstly, a deep generative model generates a 'hub,' which acts as a key point in the route; then secondly, HubRouter involves an actor-critic model-based RSMT construction module to connect the hubs. This shift from a pin-pin connection to a hub-pin connection method solves the unconnectivity problem in generative approaches. The HubRouter system ensures all generated routes are connected, eliminating the need for time-consuming post-processing. Experimental results show that HubRouter outperforms other state-of-the-art generative global routing models in wirelength, overflow, and time efficiency. It also finds application in RSMT construction and interactive path replanning, demonstrating its versatility.", "questions": "Overall, this paper solves the unconnectivity problem in the generated routes of global routing (GR) tasks in VLSI systems. The experimental results are promising. The efficiency of the proposed model is verified both theoretically and experimentally. However, the reviewer has two concerns:\n\n1. The challenge of connectivity problem is unclear. It is helpful to elaborate more about the difficulty and significance of connectivity problem.\n\n2. The effectiveness of the second phase is dependent on the quality of the hubs generated in the first phase. If the generative models do not create effective hubs, the entire approach could be compromised.", "limitations": "None", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper introduces a novel approach, HubRouter, to global routing, proposing a hub generation and hub-pin connection scheme that effectively addresses the challenge of route unconnectivity.\n\nThe experimental results show HubRouter outperforming existing generative global routing models in terms of wirelength, overflow, and time efficiency.\n\nThe approach is very general. The authors show that the approach can also be applied to RSMT construction and interactive path replanning, demonstrating the versatility of their method.\n", "weaknesses": "The challenge of connectivity problem is unclear. Specifically, it introduces a novel approach to tackling the unconnectivity problem in global routing, fails to establish the significance and relevance of this problem adequately.  It is helpful to elaborate more about the difficulty and significance of connectivity problem.\n\nThe effectiveness of the second phase is dependent on the quality of the hubs generated in the first phase. If the generative models do not create effective hubs, the entire approach could be compromised.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and valuable feedback. Our replies to the questions are as follows.\n\n> **W1/Q1: The background on the challenge of connectivity is unclear.**\n\nThanks for your suggestion.\n\nExisting generative global routing methods adopt an end-to-end model and suffer from the connectivity problem. It requires a maze routing post-process procedure to connect all routes when they are not connected, which is rather time-consuming and can cause extra overflow. Our proposed approach ensures connectivity via a novel two-phase routing procedure and reduces time overhead significantly compared to the SOTA PRNet (Cheng et al, NeurIPS 2022).\n\nIn particular, Table 2 shows that PRNet suffers from severe unconnectivity. Especially for the complex case 'Route-large', PRNet only maintains a 4% correctness rate, which means that 96% of samples require the time-consuming post-process. This leads to the phenomenon that though the generation time of PRNet in Table 2 is about 2x of HubRouter, the total time (generation + post-process) in Table 3 is about 12x of HubRouter on average.\n\nWe fully agree that it would be more helpful if the statement of the difficulty and significance of the connectivity problem were put forward in the introduction part. We will make this revision in the new version. \n\n> **W2/Q2: The effectiveness of the second phase is dependent on the quality of hubs generated in the first phase, which may lead to suboptimal solutions.**\n\nWe admit that the two-phase routing model may lead to suboptimal solutions. However, global routing is such a complicated task that previous methods like PRNet, which is an end-to-end router, lead to an even worse solution compared to our HubRouter.\n\nWe also inject the stripe mask into the model to discard the wrongly generated hubs to improve the robustness. Moreover, even if some of the correct hubs are not generated, the second phase can also have the chance to connect the correct route through a rectilinear polyline. \n\nPlease also refer to the global response and let us know if you had further questions."}, {"review_id": "jcUcURjwjC", "reviewer": "Reviewer_2ZCa", "summary": "This paper investigates the issue of global routing in VLSI systems and introduces HubRouter, a method that initially generates hubs and subsequently connects them to pins. In the first phase, the authors explored different generative models. In the second phase, the authors employs an actor-critic model to generate a final routing. \n", "questions": "1. In the first phase, the authors introduced three objectives: the hub, route, and mask, with the latter two serving as auxiliary designs. Given that the goal of the route is similar to that of the second phase, it would be worth considering why the authors did not design the two phases as a loop, utilizing the second evaluation result as feedback for the first generation. Furthermore, it would be helpful to understand the differences between the results of the route and the second phase.\nBesides, the design of mask is rather hand-craft. Why the threshold is 1/2 in each row and each colum? Why the authors only evaluate the row and column, not the density of a specific rectangle area? \n\n2. In the experiments, it seems that the three generative models (VAE, DPM, and GAN) have their own advantages and disadvantages. For instance, GAN achieves the best WLs on six datasets, DPM has the best WL on the remaining two datasets, and VAE is the fastest. How should one select the model when presented with a new dataset?\n\n3. Considering the absolute value of WL, which is the primary evaluation metric, could the authors explain the real-world benefits of improving WL by 1%?\n", "limitations": "Overall, I believe that the integration of the generative model and reinforcement learning algorithm could be more elegant, potentially leading to further performance improvements.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow.\n2. The authors conducted many experiments under different baselines.\n", "weaknesses": "1. The two phases are independent, meaning that the feedback from the second phase does not influence the hub generation, potentially leading to suboptimal results.\n\n2. The authors tried three generative models (VAE, DPM and GAN) in the paper. But the paper lacks clarity on which model should be used in specific situations.\n\n3. The performance improvement achieved is marginal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and valuable feedback. According to your constructive comments, we make some replies to the questions.\n\n> **W1: The two phases are independent, potentially leading to suboptimal result./Q1: Why the authors did not design the two phases as a loop?**\n\nWe do not design an end-to-end model mainly because: 1) Some calculations in the two phases are not continuous, which make it non-trivial to incorporate the gradients computing in the backward propagation; 2) The performance of the end-to-end SOTA (PRNet) method is even worse than HubRouter, probabaly due to the complexity of the problem.\n\nWe detailedly highlight the reasons in the first question in the global response. Please refer to it for a more complete explanation. \n\n> **W2: The paper lacks clarity on which model should be used in specific situations./Q2: How should one select the model when presented with a new dataset?**\n\nThanks for your suggestions. We do have tried three generative models in our paper's experiment: VAE, GAN, and DPM. \n\nHere are our added conclusive remarks: \n\nWe empirically show that they have different behaviors. \n\nWhen given a new dataset, we argue that the choice of generative algorithms is not based on the characteristic of the dataset, but the industrial needs. Specifically, if one needs high quality, GAN is the best. If speed is highly required, VAE is the best. If one has abundant resources, DPM can be adopted.\n\n> **W3: The performance improvement achieved is marginal./Q3: Could the authors explain the real-world benefits of improving WL by 1%?**\n\nWe respectively disagree that the performance improvement is marginal. \n\nFirst, the 1% improvement of WL is significant. Actually, the absolute value of WL is a common metric in global routing since it directly shows the performance in each case. Per your comments, it seems that improvement in the absolute value of WL is marginal. However, there exists the theoretical lower bound of this task [1] and it is unfair to judge the improvement on its absolute value. To show this, we compare the relative error in Table 1 in the rebuttal PDF, where the relative error is computed as $(WL-b)/b$. Here, $b$ denotes the theoretical lower bound. As shown in this table, the WL promotion of HubRouter is notable compared with the SOTA generative global routing method (PRNet). \n\nSecond, the ensurance of routing connectivity is crucial in global routing. As can be seen in Table 2, PRNet particularly suffers from severe unconnectivity. Especially for the complex case ‘Route-large’, PRNet only maintains a 4% correctness rate, which means that 96% of samples require the time-consuming post-process. On the contrary, HubRouter can still maintain the connectivity (promote from 4% to 100% on ‘Route-large’). \n\nThird, the promotion of inference time is significant and this is a metric vital to industrial applications. As shown in Table 3, HubRouter is on average 12x faster than SOTA generative global routing method (PRNet) on ISPD-98 cases because the time-consuming post-processing to achieve connectivity is not required for HubRouter. \n\nIn conclusion, HubRouter's contribution is absolutely not just improving WL by 1%. We argue that the significant improvement on WL, correctness rate, and inference time can substantially boost the efficiency and quality of global routing, which is vital to the chip design.\n\n> **Q1: It would be helpful to understand the differences between the results of the route and the second phase.**\n\nThe first phase can generate the route but it suffers from the unconnectivity like PRNet. So, the routes generated in the first phase are only auxiliarily used to guide the hub generation by multi-task learning. In the second phase, with a connection process, the route can be ensured to be connected.\n\n> **Q1: the design of mask is rather hand-craft. Why the threshold is 1/2 in each row and each column?**\n\nWe use the majority voting algorithm [2] to determine whether a row/column is a stripe mask based on the pixel classification. This algorithm is commonly applied in machine learning, such as ensemble learning [3]. The criterion is that if more than half of the pixels are classified as 1, the row/column is considered a stripe mask. Although this is a theoretically sound threshold, we acknowledge that it may not be optimal in practice. However, we observe that the pixel ratio of any row/column that is a stripe mask is higher than 0.9, and lower than 0.1 for those that are not. This suggests that the model has learned the feature of the stripe mask well. Therefore, changing the threshold to 0.4 or 0.6 would not affect the results.\n\n\n\n> **Q1: Why the authors only evaluate the row and column, not the density of a specific rectangle area?**\n\nWe have tested several tricks to promote the generation quality and finally chose the stripe mask. Corresponding reasons are given at the end of Section 3.1.\n\n\nPlease also refer to the global response and let us know if you had further questions.\n\nReference:\n\n[1] BoxRouter 2.0: Architecture and implementation of a hybrid and robust global router, ICCAD 2007\n\n[2] A theoretical analysis of the application of majority voting to pattern recognition, ICPR 2014\n\n[3] A weighted majority voting ensemble approach for classification, ICSE 2019"}, {"review_id": "2ruAYMPLIv", "reviewer": "Reviewer_Vi96", "summary": "The paper focuses on the generative global routing tasks and mainly ensures the connectivity of generated routes via a two-stage framework. In the first phase, the approach involves a typical generative task, which exploits multi-task learning to promote the generation quality and utilizes a trick called stripe mask to decrease some redundant noise points. In the second phase, the work is formulated as an RSMT construction problem and addresses this problem by REST. The authors show that with correctly generated hubs, the RSMT construction can be solved with less time.", "questions": "- Whether the nets in ISPD98 (Table 3) are routed sequentially? If so, what’s the performance of HubRouter when nets are concurrently routed?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The structure that generates hubs first and then connects them with pins is novel and interesting, and is reasonable to guarantee the connectivity of routes in the global routing. \n+ The motivation is clear, and the authors show in Table 2 that the so-called `unconnectivity’ caused by existing generative global routing algorithms (PRNet) is severe, but I would have preferred the authors to also refer to it in the introduction part to strengthen the motivation.\n+ The proposed approach performs better than other generative global routing algorithms in several metrics, especially the connectness rate is 100% and the running time of HubRouter (GAN) is much less than PRNet (GAN).\n+ The authors also give some applications other than global routing to show the generality of the proposed approach.", "weaknesses": "- The approach is clearly divided into two different phases, but the running time shown in the experiment seems to be combined. The authors could show both generation time and connection time to display the time overhead in either phase.\n- Some possible typos: The $r_{(n+1)j}$ should be $r_{(m+1)j}$ in Definition 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and valuable feedback, as well as your positive comments and interest in our paper. According to your constructive comments, we make some replies to the questions.\n\n> **W1: Displaying time overhead in either phase.**\n\nThe time overhead of the two phases is shown in Table 2 in the rebuttal PDF. As can be seen, the connection phase has comparable time costs for the three generative models, which is reasonable. The generation phase, however, dominates the overall time consumption.\n\n> **W2: Some possible typos.**\n\nThanks again for your meticulous review and we will correct typos in the revised version.\n\n> **Q1: Whether the nets in ISPD98 (Table 3) are routed sequentially? If so, what’s the performance of HubRouter when nets are concurrently routed?**\n\nYes, the nets are routed sequentially. Such a way of routing can maintain the performance of WL and overflow, but is slower than concurrent routing. The results of concurrent routing are shown in Table 3 and Figure 1 in the rebuttal PDF. The batch size of concurrent routing is set uniformly to 20. As can be seen, the result of concurrent routing is a little worse than the one of sequential routing, but it wins in speed. \n\nPlease let us know if you had further questions."}, {"review_id": "BwNqqNZAZb", "reviewer": "Reviewer_GN8b", "summary": "This paper proposes a two-phase learning framework called HubRouter for global routing in chip design. Different from previous works that directly generate routes from chip images, which potentially cause inconnectivity, this paper proposes to generate hubs representing tiles in the first phase and then construct RMST with hubs by an actor-critic model. The experimental results show the effectiveness in terms of higher correctness, and shorter WL compared with SOTA model. ", "questions": "Q1. It is unclear how the stripe mask is generated for chips. \n\nQ2. Why not define pixels as hubs that only connect two neighbors on the same row or columns, i.e., $r_{(i-1)j}+r_{(i+1)j}+r_{i(j-1)}+r_{i(j+1)}=2$. Without points between hubs defined in the paper, how does the second phase generate the routes in the right direction?\n", "limitations": "The authors discuss the limitations of the lack of training data about hub generation, and the model is not an end-to-end model. Still, it also should discuss how the ground truth comes and the potential impact of adopting such methods when generating it. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "\n1. the paper firstly proposes hubs for the global routing task in chip design, transferring the pin-pin problem into hub-pin problems, which can passively avoid the in-connectivity problem when regarding the routing design process as image generation.\n\n2. When dealing with large chips, HubRouter is the best performer among SOTAs regarding both correctness and wire length.\n\n3. The proposed model can have good scalability with GAN or VAE as their generative model for the hub generation phase while maintaining the property of making wire length short and overflow less.\n\n4. In the hub-generation phase, besides hubs, it also generates routes and masks to avoid noises brought by the generative model itself since the noises can greatly impact the results. Especially, the stripe mask can be greatly helpful for complicated cases.\n", "weaknesses": "1.\tThe overflow still exists for those generated global routing even though the proposed model reduces overflow better than PRNet.\n2.\tEven though HubRouter can get a good performance on replicating the known facts, it does not discuss the quality of the generated routes regarding congestion, and it possibly cannot generate novel routes since it has limited knowledge of routing design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and valuable feedback, as well as your positive comments and interest in our paper. According to your constructive comments, we make some replies to the questions.\n\n> **W1:The overflow still exists for those generated global routing.**\n\nYes, overflow still exists but HubRouter achieves better overflow performance compared with the SOTA generative global routing method (PRNet). Specifically, as shown in Figure 5, HubRouter (GAN) can achieve an average overflow reduction of about 40% compared to PRNet on the ISPD-98 benchmarks.\n\n> **W2:It does not discuss the quality of the generated routes regarding congestion, and it possibly cannot generate novel routes since it has limited knowledge of routing design.**\n\nThe metric of overflow can reflect the congestion of the generated routes and we can see that HubRouter surpasses the SOTA generative global routing method (PRNet) on overflow. Since the routes are learned from the training datasets, HubRouter cannot generate novel routes when given new design rules, but it can indirectly learn the latent design knowledge from the training datasets.\n\n> **Q1:It is unclear how the stripe mask is generated for chips.**\n\nWe define the stripe mask in lines 171-172 and one can generate the stripe mask according to the definition when given a route. The corresponding sketch is shown in Figure 4(b), where gray stripes represent the stripe mask. \n\n> **Q2:Why not define pixels as hubs that only connect two neighbors on the same row or columns? Without points between hubs defined in the paper, how does the second phase generate the routes in the right direction?**\n\nHubRouter's aim is not to generate all pixels in a route but to generate the key points in the first phase, as such in the second phase, HubRouter can connect these key points with the pins. If pixels that only connect two neighbors on the same row or column are also regarded as hubs, then the hubs will be the same as all pixels in a route, which cannot correspond to our original purpose. \n\nIn the second phase, any two points can be connected under the RSMT connection perspective, and moreover, with the guidance of correctly generated key points (hubs), the routes can be generated as expected.\n\n> **Limitations: It also should discuss how the ground truth comes and the potential impact of adopting such methods when generating it.**\n\nDue to the limited length of the main text, we discussed how the ground truth comes in Appendix D.1.\n\nThe potential negative impacts include: 1) the incorrect generation might lead to poor routing results; 2) Generative models require large amounts of computing resources, which might cause a waste of resources. We will incorporate these impacts in the revised version.\n\nPlease let us know if you had further questions."}]

Author rebuttal:
Dear Area Chairs and Reviewers,

We appreciate the reviewers’ time, valuable comments, and constructive suggestions. From an overall perspective, we are happy to see that the reviewers approve of the novelty (Co1X, Vi96), originality (Co1X, GN8b), and generality（Co1X, 2ZCa, Vi96) of our approach. In particular, we are grateful for the acknowledgment of the significant improvement compared to the state-of-the-art method (Co1X, Vi96, GN8b), and the reviewers' recognition of our method's contributions to the field (Vi96, GN8b).

Apart from the positive feedback, some concerns from reviewers are in common, so we give the global responses as follows:

> **Q1: Why not adopt an end-to-end model instead of a two-phase model?**

Thanks for your question which is worth for discussion.

First, the SOTA PRNet (Cheng et al, NeurIPS 2022) is an end-to-end approach yet our method notably outperforms it regarding total time cost, wirelength, and overflow quality.

Second, to ensure the connectivity of the whole routing, we design a two-phase routing model which generate hubs and routes. The first phase in our approach includes a discretization process, turning continuous probabilities into determined hubs. These hubs are discrete values and make differentiable learning hardly applicable.

We pursuit the cost-effective end-to-end solver for further work.

> **Q2: The significance of our model.**

First, to our best knowledge, our HubRouter is the first generative model that ensures connectivity in the global routing task. We have conducted several experiments on our approach in comparison with the SOTA PRNet, a generative model that suffers from unconnectivity, which indicates the significance of connectivity in the task.

Second, one of the main contributions of HubRouter is the notable enhancement of inference speed. As shown in Table 3, HubRouter is on average 12x faster than SOTA PRNet. The decline of inference time is meaningful and crucial in the global routing task.

Third, since a theoretical lower bound of this task exists, we further compare the relative error in Table 1 in the rebuttal PDF, where the relative error is computed as $(WL-b)/b$. Here, $b$ denotes the theoretical lower bound. It turns out that the WL promotion of our approach is not marginal compared with the SOTA PRNet.

**A one-page PDF is uploaded that contains corresponding tables and figures in the response.**

In the following, we provide detailed answers. We are glad to give further response for informed evaluation.

Meta-review: Strengths:

The paper presents an innovative approach called HubRouter, designed to tackle the challenge of route unconnectivity in global routing. It introduces a hub generation and hub-pin connection scheme, effectively addressing this issue. Through rigorous experimentation, the results demonstrate HubRouter's superior performance compared to existing generative global routing models, showcasing improvements in wirelength, overflow, and time efficiency. Notably, the approach's versatility extends beyond global routing, as the authors successfully apply it to RSMT construction and interactive path replanning, underscoring its broad applicability.

Weaknesses:

Reviewer 2ZCa raised a pertinent question regarding the paper's clarity in specifying when to use the proposed model in specific situations. Although the authors responded during the rebuttal period by emphasizing the different behaviors of generative algorithms based on industrial needs rather than dataset characteristics, this critical aspect warrants further detailed evaluation and discussion in the paper.

Furthermore, the paper falls short in adequately addressing the question posed about the real-world benefits of achieving a 1% improvement in wirelength (WL). While the authors did assert the significance of this improvement and reiterated correctness rates and inference times, the revised version should directly explain the tangible real-world advantages of the 1% improvement in WL. This clarification would enhance the evaluation of the experimental section and provide a more comprehensive understanding of the practical implications.
Decision: Accept (poster)