NeuralSteiner: Learning Steiner Tree for Overflow-avoiding Global Routing in Chip Design
Authors: Ruizhi Liu
ZhishengZeng
Shizhe Ding
Jingyan Sui
Xingquan Li
Dongbo Bu
Venue: NeurIPS 2024 poster (2024)
Keywords: Global routing
chip design
neural network
Steiner tree
deep learning
congestion
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We propose NeuralSteiner, a learning-based method to optimize overflow and wirelength simultaneously for global routing problem in chip design.

Abstract: Global routing plays a critical role in modern chip design. The routing paths generated by global routers often form a rectilinear Steiner tree (RST). Recent advances from the machine learning community have shown the power of learning-based route generation; however, the yielded routing paths by the existing approaches often suffer from considerable overflow, thus greatly hindering their application in practice.
We propose NeuralSteiner, an accurate approach to overflow-avoiding global routing in chip design. The key idea of NeuralSteiner approach is to learn Steiner trees: we first predict the locations of highly likely Steiner points by adopting a neural network considering full-net spatial and overflow information, then select appropriate points by running a graph-based post-processing algorithm, and finally connect these points with the input pins to yield overflow-avoiding RSTs. NeuralSteiner offers two advantages over previous learning-based models. First, by using the learning scheme, NeuralSteiner ensures the connectivity of generated routes while significantly reducing congestion. Second, NeuralSteiner can effectively scale to large nets and transfer to unseen chip designs without any modifications or fine-tuning.  Extensive experiments over public large-scale benchmarks reveal that, compared with the state-of-the-art deep generative methods, NeuralSteiner achieves up to a 99.8\% reduction in overflow while speeding up the generation and maintaining a slight wirelength loss within only 1.8\%.

NeuralSteiner: Learning Steiner Tree for Overflow-avoiding Global Routing in Chip Design
Ruizhi Liu 1:24
Zhisheng Zeng 1,2,5 Xingquan Li
Shizhe Ding Dongho Bu 12,3
Jingyan Sui!2
SKLLP, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
(liuruizhi19e, dingshizhe199, suij suggingy,n88,, dbu) ac cn
2 University of Chinese Academy of Sciences, Beijing 101408, China
*Central China Artificial Intelligence Research Institute,
Henan Academy of Sciences, Zhengzhou 450046, Henan, China
"Beijing Institute of Open Source Chip, Beijing 100089, China
Peng Cheng Laboratory, Shenzhen 5 518000, Guangdong, China
{zengzheh, lixq01} http:/11@pc........m..
"School of Mathematics and Statisties, Minnan Normal University, Zhangzhou 363000, Fujian, China
Abstract
Global routing plays critical role in modern chip design. The routing paths gener- ated by global routers often form rectilinear Steiner tree (RST). Recent advances from the machine learning community have shown the power of Marning-based route generation; however, the yielded routing paths by the existing approaches often suffer from considerable overflow, thus greatly hindering their application practice. We propose NeuralSteiner, an accurate approach to overflow- global routing chip design. The key idea of NeuralSteiner approach is learn Steiner trees: we first predict the locations of highly likely Steiner points by adopt- ing neural network considering full-net spatial and overflow information, then select appropriate points by running graph-based finally connect these points with the input pins to yield wvefflow-vviiding RSTs. NeuralSteiner offers two advantages over previous learning- based models. First, by using the learning scheme, NeuralSteiner ensures the connectivity of gener- ated routes while significantly reducing congestion. Second, NeuralSteiner can effectively scale to large nets and transfer to unseen chip designs without any modifications fine-tumi fine-tuning. Extensive experiments over public large-scale bench- marks reveal that, compared with the state-of-the-as deep generative methods, Sternr achieves up 99.8% reduction in overflow while speeding up the generation and maintaining a slight wirelength loss within only 1.8%.
post-processing algorithm, and
Introduction
In the modern design flow of Very Large Scale Integration (VLSI), global routing has become one of the most complex and time-consuming steps. Given the complexity of VLSI netlist [I7 that contains millions or even billions of nets requiring routing, global routers must interconnect pins of nets, minimize the total wirelength of the routes while avoiding overflow (or congestion) a strictly limited area of chip 2 24). Overflow occurs when the number of routes in particular area of the
Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(b)
(d)
(c)
(f)
(h)
Figure 1: An illustrative example to show overflow-avoiding global routing in chip design. (a) Chip layout of a real-world net extracted from ISPDO7_ _adaptec__ (b) Two-dimensional grid graph. (c) The Hanan grid of 4-pin net. (d) The resource map and pin map (actually divided into two channels) obtained from (a) for this 4-pin net. (e) The predicted hub points (black circles) and stripe mask applied by Hubrouter [8]. (f) The routing result generated by HubRouter [8] suffers from congestion (red edges). ) (g) The candidate points (green circles) predicted by NeuralSteiner and the corresponding net augmented graph (NAG). (h) The final routing result generated by NeuralSteiner that avoids overflow.
chip exceeds the available routing resources or routes cross through impassable obstacles, which significantly impacts the subsequent design flow and functionality realization of the chip 22 22 Even the two-pin routing under design constraints or obstacles turns out to be NP-complete. When the number of pins exceeds two, the routing problem often be transformed into the construction problem of rectilinear Steiner minimum tree (RSMT) [0], which is also NP-complete and becomes more challenging when considering avoiding overflow 22
16 24 6
Traditional global routers propose various human-designer heuristics obtain near-optimal solutions for RSMT 27 13
24 or directly solve the integer programming problem for concurrent Recent advances in applying learning-basee methods to chip design problems have shown feasibility and powerful abilities and even surpassing the performance of human expert-designed algorithms, such as using deep reinforcement learning (DRL) for placement [29 18 [9] and using convolutional neural network (CNN) for predicting design rule violations (34). In global routing, DRL is firstly adopted to explore surrounding directions of current positions and achieve successful connectivity
16
routing of multiple nets 6 33
small-scale nets (20). while REST 23 decomposes multi-pin net into 2-pin pairs and explores the sequence of pin pairs through DRL to form the RST. Moreover, recent works adopt deep generative models 32 4 to perform shot generation of nets. To address the connectivity problems of generative methods, HubRouter & decomposes global routing generation into nub-generation phase and con-hub-connectin phase sequentially connect the pin-hub pairs, thereby successfully ensuring the connectivity of the routes.
However, current learning-based routing methods suffer from high overflow within their routing results, primarily due to inadequate consideration of resource availability during the routing process. Existing DRL-based approaches [20] 23 28 tend to solely focus wirelength the reward during action space exploration, while other generative methods do incorporate the current routing area't 'ss resource status in their inputs but mainly aim for connectivity wirelength optimization in their post-processing phases [4] 32 5 gj Consequently, our experimental findings indicate that routes
generated by HubRouter still exhibit significant congestion, which is illustrated in Fig. I
To address these challenges, we propose a congestion-aware learning scheme named NeuralSteiner, which consists of two main phases: i) Candidate point prediction phase: Utilizing a neural network combined with full-image spatial and overflow information aggregation to predict the accurate locations of what we call candidate points for overflow-avoidingg rectilinear Steiner tree; ii) Overflow-

---

Constructing an augmented graph of the net based on the predicted candidate points and calculating the -erfiiw-avoiding RST using a simple but effective greedy algorithm. Through this two-phase setup, NeuralSteiner successfully ensures connectivity and enables the generation of overflow-avoiding routing results for large-scale nets.
avoiding RST construction phase:
This paper has three main contributions:
We propose NeuralSteiner, a two-phase global routing scheme, which to our knowledge, is the first learning- based approach capable of optimizing both wirelength and overflow and effectively addressing the routing problem of large-scale nets.
We devise neural network architecture that integrates the deep residual network with recurrent crisscross attention mechanism learn the Steiner point locations from a carefully curated expert dataset and propose post-processing algorithm based on augmented graphs to construct routes with substantially less overflow than recent works.
We conduct extensive experiments on 14 public large-scale routing benchmarks compared with the state-of-the-ar learning-based method, where the NeuralSteiner achieves up to 99.6% reduction in total overllow with wirelength loss within 1.8%. Moreover, Neural- Steiner can generate werflowwavoiddig routes for nets with more than 1000 pins, previously challenging for recent works, which narrows the gap between learning- bbased methods and practical routing applications.
2 Preliminaries and Related Works
Global Routing, Given the complexity of VLSI routing problems, the circuit layout like la is partitioned into rectangular areas known as global cells (GCells) [6]. The global routing problem can be modeled as grid graph G(V, E), where each GCell is represented as a vertex (v V), and adjacent GCells are connected by an edge (e E E) that represents the boundary between GCells. Chip designs often contain two more metal layers for routing. Each metal layer is dedicated to either horizontal or vertical direction and the projection of these layers onto a two-dimensional grid graph is shown in Fig 1b. Global router will assign set of GCells interconnected by numerous edges to each net as its routing result to connect all pins, which often forms a Rectilinear Steiner Tree (RST) 77) The concepts of Hanan grid [T]] and escape graph 9 are often used for the generation of the shortest RSMT avoiding obstacles (22). considering the intersection points in these graphs as candidate locations for Steiner points. However, due to the complex and irregular distribution of congestion, the construction of escape graph becomes complicated, while the Hanan grid is ineffective circumventing congestion, which is shown in Fig[Ic
Overflow. Give edge e(u, v) E E is the boundary between GCell u and GCell e, the capacity c(u, v) is the routing resource of edge that can be provided to global router and demand d(u, v) is the number of routes passing through edge e. The resource r(u, v) of edge e is the part of the capacity that can still be utilized route, which is defined in Equation (1):
r(u, v) = c(u, v) d(u, v)
(1)
Overflow occurs when r(u, u) The routing results containing overflow generated by the global router will not be accepted by subsequent routing process and will trigger a tine-consuming rip-up and reroute iteration in order eliminate overflow (2]. Therefore, the global router should not only attempt to find the shortest connection for each net but also minimize the number of overflow.
Traditional Global Router. Traditional routing algorithms typically divide global routing into two main stages to address congestion: Steiner topology generation and rip-up and reroute (RRR). The former utilizes the FLUTE algorithm 77). based on lookup tables, generate Steiner trees with nearly minimal wirelength for each net. However, FLUTE is unaware of congestion. During this phase, most routers only use edge shifting partially mitigate congestion by moving some edges out of congested areas 77] while CUGR-2 [25] applies the construction of augmented graphs to build candidate paths for nets' RSTs, adjusting the position of certain Steiner points to circumvent potential congestion. In order to resolve congestion in the RSTs, traditional routers will invoke RRR, iteratively removing all initially routed nets in congested areas and employing maze routing that optimizes wirelength and congestion simultaneously. This process becomes dramatically time-consuning as the chip design's 's scale and complexity rise. Hence, accelerating congestion resolution through deep learning-baan methods can enhance the overall performance of global routing algorithm.
3

---

(+)
(b)
Paodieiinating
Charsed Pechetion
Pont
Dentreat Aagrentte Sriphh
Nodil Lagout
Rowting Tock
Caneddane
NAT RugFRintcd Dhipe
Fius POUUIINN POCUR
Figure 2: Overview of NeuralSteiner. (a) The parallel routing tasks accelerate routing by grouping the non-overlapping nets into one batch. (b) During the first phase, NeuralSteiner predicts the candidate point locations for the RST with full-image aggregation of spatial and overflow information. (c) During the second phase, NeuralSteiner constructs the net augmented graphs based on the predicted candidate points and generates overflow aoooiding RSTs.
Learning-basee RST construction. Various works explore the feasibility and advantages in wire- length and efficiency of applying deep neural networks to global routing, including generation of the pin-comnection order [23]. segments 4 32
custom hub points RST [8]. However, most of the
challenges in actual global routing come from the complexity of large-scale nets and how to avoiding overflow when routing resources are limited. Under the circumstances, detours are indispensable
to get rid of congestions, while the shortest RST like Fig. Tf generated by HubRouter [8] is not practically usable. The chip layout can be viewed as an image, where each pixel represents tile in global routing, and images of different channels represent the locations of the pins and capacity of the grid edges. The output points can also represented as a binary image. But unlike the four kinds of hub points defined in Hubrouter, Steiner points and corner points RST as candidate points to learn. Formally, we have
simplify the learning target in RST construction and select
binary image representing the RST, where each pixel Pay(1 (1 I x S m, 5 S 1) represents whether the position is occupied by a route and Poy P(m+1)y - P20 Px(x+1) The pixel pay is candidate point if and only if it satisfies:
Definition 1. Candidate point Given
{ Pay = 1, Pay 1, and P(z-1)y + P(a+1)y 1, and Pz(y-1) + Paly+1)
(day > 2)
(day 2)
where day P(--1)y + P(a+1)y + Paty-1) Pw(y-1) denotes the degree of this point in the RST.
Using Definition, the Steiner points and corner points can be recognized candidate points the pixel image of RST. The differences between hub point in [8] and candidate point are visualized in
Fig. ST
Method
3.1 Overall Pipeline
NeuralSteiner decomposes the global routing process into two main phases to optimizes wirelength and overflow of the routing result simultaneously. Before introducing the main methods, we first
propose our parallel task construction in Sec. 3.2 We then introduce the candidate point prediction
method with aggregation of full-scale spatial and overflow information in Sec. 3.3 An augmented
graph- overflow-avodding RST construction method will be proposed in Sec. 3.4 The overall
pipeline of NeuralSteiner is illustrated in Fig

---

3.2 Parallel Routing Tasks Construction.
Routing of two nets cannot be parallelized if the bounding boxes of their pins have overlap, which is defined as conflict between two nets. Inspired by (26), we scan and group the non-conflicting nets into a set t, which is called a routing task. which divides the numerous nets in the design into a set of mutually conflicting routing tasks. Nets within task I can be batched together and fed into the neural network for prediction and post-processing. significantly enhancing the parallelism of routing. Please refer to App. B.3 for the detail of our routing tasks construction algorithm.
3.3 Candidate Point Prediction
Candidate points prediction can be formulated as image segmentation task [31, which involves training a neural network model to perform pixel-level classification to recognize the locations of candidate points found in the expert RSTs data. We will first introduce the expert routes dataset optimized for both wirelength and overflow, then the network architecture incorporating the recurrent crisscross attention module to tackle the complex large-scale nets, as well as the design of our training protocol.
Expert Routing Dataset Construction. We utilize state-of- ahrt traditional global router named CUGR [24] to perform routing on public benchmarks (30) also used by [8] and extract the overflow map and pin map of every net in real-time. We adopt the logistic function in CUGR to calculate the
overflow value using resource r(u, v):
Ig(u, e) (1.0+ exp(slope x r(u, b1))
where slope (which is set to I here) is an adjustable parameter that determines the global router's sensitivity to overflow and the overflow value will increase rapidly as the resources are being used up. After that, we directly employ CUGR's maze routing algorithm to execute the rip-up and reroute process to obtain the inngesttoo-avoidingg routing results. We mark the Steiner points and corner points in the RSTs constructed by CUGR as candidate points and generate the label candidate point map for every net. Rather than clipping all images to the same scale 64 x 64, which is set in HubRouter (8, we maintain three maps of every net at the original scale of its bounding box. This preserves the precise spatial and overflow information and does not exclude any large-scale nets.
Network Architecture. In order to tackle the problem of large variation in net scale, we employ a ResNet structure as the backbone of our model and combined it with the recurrent crisscross attention mechanism
[4] to encoding full-net overflow and long-range associations in the input features. Convolutional neural networks (CNN) have been proven to be efficiently applied in chip design like predicting chip congestion distribution (35) DRV distribution 34 and thermal distribution (3.. However, due to the fixed geometric structures, CNN is inherently limited to local receptive fields that face difficulties in capturing long-range correlations. Thus, we introduce the recurrent crisscross attention mechanism (RCCA) to aggregate features from all pixels on the feature map. We insert one RCCA module with two e crisscross attention blocks in ResNet. Fig 2 illlustrates the network architecture of NeuralSteiner. We also remove the down-sampling operations to retain more spatial details of feature maps because the construction of RST requires accurate spatial location information when connecting pins that are far apart in large-scale nets. Through the computation of RCCA, the network can aggregate information of pins and congestion over the whole scale of feature maps, thereby enhancing the quality of candidate points prediction for large RSTs. This will be further demonstrated in ablation study in Sec. 4.4 The implementation details of our network and RCCA calculation are shown in App. B.I
Model Training. We adopt focal loss 21 foccl to mitigate the imbalance between positive and negative class samples in training data where the candidate points in RST only occupy minority of pixels in the entire routing area. Let pt the predicted probability for the ground truth class I, ffontt is defined as:
(4) where ag the weighting factor while 7 is the focusing parameter that reduces the loss for well- classified examples. We also adopt the dice loss Edice to measure the similarities between the predicted candidate points and the ground truth. Using Pay to represent the probability of pixel at position (Ie, y) predicted as candidate point and Jay to represent the label, Edice can be expressed as:
ffocal = aa - pp))" log(p:)
2 2E,, Ldsoe 1 En.y Pay + En.y, Ozy +
2.9 Pry9xy +
(5)
5

---

where e is a small constant added to avoid division by zero. Additionally, since the global routing problem is Nocoompee,,, even expert router may not generate the optimal routing solution for the net that achieves the shortest wirelength with the minimal overflow. Therefore, we further add an overflow loss faf to measure the congestion status predicted points. Let Oxy be the value at position (xr, y) of the overflow map, fof can be calculated by:
Ex.g PxyOsy + 6
lof Ez,,, Pay +
(6)
The inclusion of overflow loss helps the model identify potential candidate points that are not in the label set but have a lower intrinsic congestion, benefiting the post- post-processing algorithm for overflow-avoiding RST construction. Then the trainable model 0 is determined at the training stage by minimizing the loss function as follows:
(() = Cft &focat + Cai - Edice + Caf lof
where Cjt, Cdi, Cof represent weight of corresponding loss item. The parameters used in training process are provided in App. B.2
3.4 Overflow-avoiding RST Construction
To construct overflow-avoiding Rectilinear Steiner Tree (RST) based on the candidate points predicted by the neural network, we will first introduce the construction of net augmented graph that contains potential overflow-free edges and then propose a simple and effective greedy RST construction algorithm. Unlike previous works that focus solely on minimizing wirelength, the inclusion of the irregular distribution of congestion makes solving for RST more challenging.
Net Augmented Graph. We introduce the concept of the net augmented graph (NAG) based on neural network-predicted points to avoid congestion. We first merge the predicted candidate point map and pin map, then sequentially examine each point Pay 2 from the merge map according to the following two conditions: 1) if this point shares the same horizontal (X) vertical (Y) coordinates with another point g, and 2) if there is no other points on the line connecting and q. Then an edge e(p, q) will be established if the above two conditions met and the weight of e(p, 4) is set as
W(e) = wa(l<p Nzgl + 1yp Mol) + Wo
Osy
(8)
N.
where min(Fp, x.g) S x S max(1, xg),, min( 3o) S y S max (yp: My). W(e) balances the wirelength and congestion of the edge by using weights wa = 1.0 and w, = 5.0. After examining all the points, to ensure the connectivity of the net, we will check the connectivity of the current NAG and add candidate point and edge between different connected components if this NAG is disconnected. App. B.4 provides a detailed introduction to the construction algorithm.
Note that in HubRouter [8) stripe mask is introduced as filter that removes noise hub points to limit the solution space similar to the Hanan grid, which ensure that the wirelength as short as possible. However, as dipicted in Fig[Te] the addition of stripe mask in HubRouter limits its ability to generate RST avoiding congested areas. On the contrary, we here retain all candidate points predicted by the model and constructed the NAG based on them, which reduces the complexity of solving RST while preserving the solution space to avoid overflow.
Overflow-avoiding RST Construction. We convert the calculation of the overflow-avoiding RST into a greedy construction of minimal spanning tree that connects all pins. Initially, we consider all pins as separate connected components containing only one node. In each iteration, based on the NAG, we greedily select and connect the path between the two nearest connected components, then update the shortest distance (the sum of the weights of all edges on the path) of the newly formed connected component to all other connected components. This operation repeats until all pins are included in one connected component. Since this method may generate additional detours, we use a simple algorithm to detect potential feasible path reuse to shorten the wirelength. Furthermore, to accelerate the construction of RST, we parallelize the computation of the shortest distances between pins or connected components on the NAG. For the detailed algorithm and analysis of time complexity and scalability, please refer to App. B.5

---

Results and Discussion
4.1 Datasets and Experiment Setting
For training, we construct the training set from ISPDO7 30 using the method described in Sec. 3.3 Since our network's s input size is variable, we limit the nets' Half-perimeter wirelength (HPWL) in the training set to PWL L Σ 128, instead of fixing both width and height to 64. For test, Sec. 4.2 we use the same settings from HubRouter (8 to divide samples outside the training set into four groups of small-scale nets compare the connectivity and wirelength NeuralSteiner and HubRouter. For more extensive experiments, in Sec. 4.3 we select six public chip designs (ibm01-06) from ISPD98 T and cight two-layer large-scale chip designs (adaptec(01-05) 2d, newbluc(01-033) 2d) from ISPD07 (with overlap with the training set) to perform global routing all nets in these designs, comparing total overflow, wirelength and generation time. The ablation and generalization studies for NeuralSteiner are also conducted chip designs from ISPD07. We repeat 3 times under different seeds for HubRouter on the small nets test set and ISPD98, and then choose the seed with best overflow for HubRouter (GAN) to conduct the ISPD07 experiment. More details about the experimental benchmark information and hyperparameter settings can be found in App. B.2
4.2 Connectivity and Wirelength on Small Nets
We compare NeuralSteiner with three different architectures of HubRouter on the same test set from part of ISPDO7 benchmarks, which is divided into 'Route-small44" 'Route-small', "Route-large-4" and 'Route-large'. The number '4' in their names represents no more than or more than 4 pins, while 'small' and 'large' represent whether the Half-perimeter wirelength (HPWL.) of the net less or more than 16. The size of all nets' input map is fixed at 64 x 64. We do not include PRNet it shows very poor connectivity on 'large' net in previous work [ As shown in Table [S2] NeuralSteiner ensures connectivity on this small-scale net test set, while achieving wirelength rate (WLR) comparable to HubRouter. Due to the presence recurrent crisscross attention calculation, our method is slightly behind in generation time.
4.3 Global Routing on Large-scale Benchmarks
To conduct extensive experiments, first compare the proposed NeuralSteiner with three versions of HubRouter [8] and traditional global routers Boxrouter (6), GeoSteiner [15) and FLUTE + Edge Shifting 7 ibm01-06 benchmarks from ISPD98. We then conduct fully routing of 8 chip designs from ISPD07 using GeoSteiner, FLUTE + Edge Shifting, HubRouter and our method. Note that do not the randomly generated nets from previous works (20). they are relatively simple and have no overflow in the results. Moreover, it has been already studied in HubRouter that the DQN method takes excessively long time to run on even very small cases and PRNet 4 also lags behind HubRouter in terms of wirelength, time and overflow, so they are not included the comparison.
in our experiments,
Table 1: Wirelength (WL) and running time on ISPD-98 (ibm00-06). NeuralSteiner is compared with 2 traditional baselines and HubRouter with generative structures (HR- HIRRVAA,,R-DPM, HR- GAN). Optimal results of WL and time are in bold.
Metric
Model
ibm01
ibma02
3bm03
ibm04
ibmi5
Thm06
GeoSteiner
60142
165863
145678
162734
409709
275868
FLUTE4ES
61492
169251
146287
167547
411936
280477
WL
HR-VAE
64812 1: 1252
176838
6119
161032
3231
179018 1: 1791
440302 =: 4577
301035
5836
HR-DPM
66575 + 1.394
190142
2511
168550
2103
183051
+ 1946
474463
6674
320423
2958
HR GRNGAAN
60971 d: 290
167316 + 578
146893
=: 315
164084
1: 299
4 1187 = 4529
277977 d:: 514
NeuralSteiner
61735
170405
148036
166648
415684
283727
GeoSteiner
1.00
2.21
1.68
2.19
3.69
3.38
Boxroster
5.33
9.76
8.42
31.69
10:75
24.94
Time (Scc)
HR-VAE
8:41 0.03
8.47
0.06
8.59
0.04
10.85
0.04
12.4 0818
15.85 = 0.11
HR-DPM
1701.57 34.19
2589.93 19.63
2669.28 22.77
3593.04 1: 24.10
3995.17 = 19.57
4305.82 $2 132.85
0.37
NeuralStciner
27.18
34.79
46.24
50.37
75.99
770.32

---

HubRoutor
Hablouue (GAN)
Geastennor
FLITE + Edge Siitt
Noura Steinor (Durs)
Overfow
12500
10000
5000
2500
0
18902
18904
12
Broos
ISPD98
Figure 3: Overflow on ISPD98 (ibm01-06). Overflow of Geosteiner, HubRouter (VAE, DPM, GAN) and NeuralSteiner on ISPD-98 (ibm01-06) cases. Note that NeuralSteiner causes only 18 overflows on ibm05, which is annotated the figure.
Table 2: Evaluating NeuralSteiner and comparing it with state-of-the-art approaches on ISPD- 07 (a14ptec(01-05). 2d, newblue(01-03) 2d). Overflow (OF), wirelength (WL) and running time compared among traditional router GeoSteiner, FLUTE Edge Shift and HubRouter with GAN structures (HR-GAN), which achieves the best overflow and wirelength among three kinds of HubRouters ISPD98. Optimal results of overflow, wirelength and time are in bold.
Metic
Method
adaptzcO1_
adapteel12_44 2d
adapteaU1_ 24
adaptze04_. _4
adspteclIS 2d
newSlueO1 _d
newblusl22.0
uewbloelis 2d
GeuSteiner
35945
53848
142254
45050
102500
1734
1832
584761
OF
FLUTEaES
HR-GIN
32518
35441
50947
53652
137104
142131
45230
42306
957704
102108
1348
1516
1713
1857
558047
583001
NeuralStemer
728
10343
GeoSteiner
7371273
FLJITFFFS
3890007
IIR GAN
3407033
3229110
9355980
8855775
9832110
2339204
4623006
7391035
NeumiStciser
3458717
3247479
9490117
9003952
9915795
2365499
46688179
7480659
GonSteiner
83.17
111.92
320.05
267.13
261443
134.68
183.82
315.48
Time (Rec)
FLUTESES
IRN-AN
593.02
115.48
780.44
187.03
1324.81
396.5
1387.01
376.72
1384.96
360.68
849.34
169. 36
1221.16
223.55
1525.86
438,79
NeualSStenerr
1351.91
1138.66
1106.54
446.65
Routing Results on ISPD98. Table shows the total wirelength and generation time for all methods on ISPD98 benchmark. Since the total overflow the traditional router Boxrouter we depict the routing overflow of the other methods in Fig. 3 NeuralSteiner significantly reduces the total overflow compared to the state-of-the-an learning-baa -ased method HubRouter (GAN), with an average reduction of 61.1% %6 and to 95% on ibm05. In terms of wirelength, NeuralSteiner does not incur much additional loss, maintaining it within 1.8%. Furthermore, due the construction of the parallel routing tasks, NeuralSteiner achieves shorter generation time compared with HubRouter (GAN). The comparison of the actual solutions between NeuralSteiner and Hubrouter is given in Fig.
S2
Routing Results ISPD07. Based the experimental results ISPD98, we select four methods GeoSteiner, HubRouter (HR-GAN), and NeuralSteiner for comparison on the larger-scale ISPD07 chip designs. The summary ISPD07 benchmarks we use is detailed introduced in Table S1] as well as the number of predicted candidate points for ISPD07. According to Table ST] the average number of candidate points added by NeuralSteiner is not significantly more than the average number of pins, which means that for the vast majority of nets, the number of nodes in the NAG will remain at small scale and keep friendly to the calculation of the overflow-avoice avoidiig RST algorithm introduced in Sec. 3.4 The total overflow (OF), wirelength (WL) and generation time are shown in Table 2 According to Table as the sizes of chip designs and nets further increase, NeuralSteiner achieves more dramatic reduction in total overflow, with an average reduction of 97.9 97.8% across all eight designs, and up to a 99.8% reduction on design adaptec04 2d, while the increase in wirelength still remains within 1.8% compared to HubRouter.

---

4.4 Generalization and Ablation Study
Generalization. Note that the NeuralSteiner proposed by this work is trained on small-scall nets with HPWL less than 128 and is tested on 14 large-scale public benchmarks, which contain net with HPWL even larger than 2000. Its ability to generalize unseen and large-scale nets can be demonstrated. Fig. shows the remaining resource map of adaptec01 2d design after routing by HubRouter and the proposed NeuralSteiner respectively, which demonstrates that NeuralSteiner can generalize to larger chips by using routing resource more evenly and avoiding the vast majority of overflow. Moreover, to extensively examine the ability NeuralSteiner mitigate overflow in the post-routing results, we integrate our method into CUGR and compare it with the original CUGR post-detailed routing metries on ISPD 18/19 benchmarks, which are much larger than ISPD98 and ISPD07. The detailed routing is conducted by commonly used detailed router DRCU. Short and space two kinds of design rule violation caused by overflow in the detailed routing process. Table [ shows that by integrating NeuralSteiner into CUGR, we achieve 4.4% and 19. reduction average in shorts and spaces respectively, with minimal losses in wirelength and vias. This demonstrates that NeurelSteiner, pre-routing overflow mitigation method, is beneficial for reducing overflow in the post-routing results.
(a)
(b)
(c)
(d)
Figure 4: The Overflow Distribution after routing by HubRouter and NeuralSteiner. (a), (c): the horizontal and vertical overflow of HubRouter; (b), (d): the horizontal and vertical overflow of NeuralSteiner. Depth of red color indicates the number of overflow.
Table Comparison CUGR + NeuralSteiner and original CUGR on post-detailed routing metries on ISPD18/19 benchmarks. The detailed routing is conducted by DRCU. Short and space are two kinds of design rule violation caused by overflow.
Wire Length (x107)
Via (x
Short
Space
Design
CUGR
CUGR+NS
CUGR
CUGR+NS
CUGR
CUGR+NS
CUGR
CUGR+NS
ispd18 15m5
2.878
2,874
9.154
9.180
389.5
362.5
16
7
ispd18 18m5
6.653
6.671
22.466
22.452
414.6
412.8
66
65
ispd19_17
12.556
12.621
40.446
40.956
2117.6
2042.3
7084
6472
ispd19_t7ms
11.273
11.303
40.356
40.613
2368.5
2219.0
7715
6964
Average
1
1.002
1.005
0.956
0.809
Ablation Study. To study the role of recurrent crisseross attention (RCCA) module, well as our loss function, we respectively ablate the RCCA module from the network architecture and the overflow loss fof from the loss function and keep other training settings the same. The modified models are tested in comparison with the unchanged NeuralSteiner on ibm01 and adaptec05 2d. Furthermore, validate the effectiveness of our two-phase method, especially the effectiveness of predicted candidate points in reducing overflow, we ablate the output of the neural network and compare it with the unchanged NeuralSteiner. Results in Table[iindicat that, although the wirelength of three modified models are not significantly affected due to graph-based based post- pest-processing there are notable increases in overflow, especially on larger adaptec05 2d design. This implies that both RCCA module and overflow loss can help NeuralSteiner learn congestion congestion-avoidin avoiding candidate points and acquire better generalization ability to larger nets. Additionally, relying solely on the graph-based RST construction to generate RST on the Hanan grid without predicted points leads to more than x0x increase overflow on adaptec05 2d. This demonstrates that the neural network in our NeuralSteiner has learned an distribution of better candidate points for overflow- avviiiow-vooding RST under tight resource

---

constraints, We also study the role of our post-processing by replacing the REST method and the stripe mask used in the conn-einoonnettoon phase of HubRouter by our NAG-based RST construction algorithm. As shown in Table | although the congestion of this combination is still 11 larger than that of NeuralSteiner, has decreased by nearly 95% compared to the original HubRouter, which fully demonstrates the effectiveness of our post-processing method.
Table 4: Ablation study of different compo- nents in NeuralSteiner. Comparison of the com- plete NeuralSteiner learning scheme with models removing neural networks or overflow loss laf or RCCA module.
Table Ablation study of NAG-based RST construction. Comparison of original HubRouter (GAN), HubRouter (GAN) with our NAG-based RST construction without stripe mask and NeuralSteiner. Optimal results of over- flow and wirelength are in bold.
Metrie
Model
ibm01
adaptec115_2 __
Without NN
3015
1090S
Metric
adaptecU5_24
Without Eas
2258
2795
OF
Without RCCA
2189
HR-GAN
102108
NeuralSteiner
2033
431
OF
HR-Go MasKHNAG
5245
NeuralSteiner
431
Without NN
62108
9331120
Without Eaf
61965
9927082
HR-GAN
98321 10
WL
Without RCCA
62098
9930587
WL
HRwl Mask)+NAG
9952476
NeuralSteiner
61735
9915795
NeuralSteiner
9915795
5
Conclusion
In this paper, introduce NeuralSteiner, two-phase learning- based global routing scheme. By combining neural network-predicted candidate points with post-processing method based on net augmented graph, NeuralSteiner can generate wvrfflowavoidinng and connectivity aasssiiity-ssureed routing solutions for unseen large-scale nets in one shot, substantially reducing the overflow by up to 99.8% on real-world chip benchmarks, which narrows the gap between learning-basse routing method and practical chip routing applications.
The main limitation of our method is that still rely heuristic post-processing algorithms for Rectilinear Steiner Tree (RST) construction, which leads to time-consuming calculations and a slight increase in wirelength. In the future, we will explore using continuous probabilistic candidate point maps and investigate end-to-end learning with neural networks for generating overflow-avoii avoidiig RSTs. Addressing this limitation could lead to enhanced performance in routing efficiency and quality.
Acknowledgements
We would like to thank the National Key Research and Development Program of China (2000YA00907000), the National Natural Science Foundation of China (32370657, 32271297, 82130055, 62072435), and the Major Key Project of PCL (No. PCL2023A03) for providing finan- cial supports for this study and publication charges. The numerical calculations in this study were supported by ICT Computer X center, CAS Xiandao-1 I and Pengcheng Cloudbrain.
References
[1] Alpert, C. J. (1998). The ispd98 circuit benchmark suite. In Proceedings the 1998 international symposium on Physical design, pages 80-85.
[2] Chen, H.-Y. and Chang, Y.-W. (2009). Global and detailed routing. In Electronic Design Automation, pages 687-749. Elsevier
[3] Chen, T., Xiong, S., He, H., and Yu, B. (2023). Trouter: Thermal-driven peb routing via non-local crisscross attention networks. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
[4] Cheng, R., Lyu, X., Li, Y., Ye, Hao, J., and Yan, J. (2022). The policy-gradient placement and generative routing neural networks for chip design. Advances in Neural Information Processing Systems, 55:26350-26362
10

---

[5] Cheng, R. and Yan, J. (2021). On joint learning for solving placement and routing in chip design. Advances Neural Information Processing Systems, 34:16508-1657
[6] Cho, M., Lu, K., Yuan, K., and Pan, D. Z. (2007). 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. IEFE.
[7] Chu, C. and Wong, Y.-. (2005). Fast and accurate rectilinear steiner minimal tree algorithm for vlsi design. In Proceedings of the 2005 international symposium Physical design, pages 28-35.
[8] Du, X., Wang, C., Zhong, R., and Yan, J. (2023). Hubrouter: Learning global routing via hub generation and pin-hub connection. In Thirty-seventh Conference on Neural Information Processing Systems.
[9] Ganley, J. L. and Cohoon, J. P. (1994). Routing construction the presence of obstacles. In Proceedings of IEEE International Symposium on Circuits and Systems-ISCAS 99, volume 1, pages 113-116. IEEE.
critical net: Steiner tree
[10] Garey, M. R. and Johnson, S. (1977). The rectilinear steiner tree problem is np-complete. SIAM Journal on Applied Mathematics, 3244)882--34.
[11] Hanan, M. (1966). On steiner's problem with rectilinear distance. SIAM Journal on Applied mathematics, 14(2):255-265.
[12] He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778.
[13] Ho, J.MM,, Vijayan, G., and Wong, C.-K. (1990). New algorithms for the rectilinear steiner tree problem. IEEE transactions on computer-aided design of integrated circuits and systems, 9()):185-18
[14] Huang. Z., Wang, X., Huang, L., Huang, C., Wei, Y., and Liu, W. (2019). Cenet: Criss-cross attention for semantic segmentation. In Proceedings of the IEEE/CVF international conference computer vision, pages 603-612.
[15] Juhl, D., Warme, D. M., Winter, P., and Zachariasen, M. (2018). The geosteiner software package for computing steiner trees in the plane: an updated computational study. Mathematical Programming Computation, 10:487-532.
[16] Kastner, R., Bozorgzadeh. E., and Sarrafzadeh, M. (2002). Pattern routing: Use and theory for increasing predictability and avoiding coupling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21(7):777-790.
[17] Kramer, M. and Van Leeuwen, J. (1984). The complexity ofwirerouting and finding minimum area layouts for arbitrary vlsicircuits. Adv. Comput. Res, 2:129-146.
[18] Lai, Y., Liu, J., Tang, Z., Wang, B., Hao, J., and Luo, P. (2023). Chipformer: Transferable chip placement via offline decision transformer. arXiv preprini arXiv:2306. 14744.
[19] Lai, Y., Mu, Y., and Luo, (2022). Maskplace: Fast chip placement via reinforced visual representation learning. Advances in Neural Information Processing Systems, 35:24019-24030
[20] Liao, H., Zhang. W., Dong, X., Poczos, B., Shimada, K., and Burak Kara, L. (2020). A deep reinforcement learning approach for global routing. Journal of Mechanical Design, 142(6):061701.
[21] Lin. T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, (2017). Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pages 2980- 2988.
[22] Liu, C.-H., Kuo, S.-Y., Lee, D., Lin, C.-S., Weng, J.-H., and Yuan, S.-Y. (2012). Obstacle- avoiding rectilinear steiner tree construction: A steiner-point-basedd algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, (1)7): 1050-1000.
11

---

[23] Liu, J.. Chen, G., and Young, E. F. (2021). Rest: Constructing rectilinear steiner minimum tree via reinforcement learning. In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 1135-1140. IEEE.
[24] Liu, J., Pui, C.-W., Wang, F, and Young, E. F. (2020). Cugr: Detailed-routablltyy--rv 3d global routing with probabilistic resource model. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pages 1-6. IEEE.
[25] Liu, J. and Young, E. F. (2023). Edge: Efficient bas-based global routing engine. In 2023 60th ACM/IEEE Design Automation Conference (DAC), pages 1-6. IEEE.
[26] Liu, S., Pu, Y., Liao, P. Wu, H., Zhang, R., Chen, Z., Lv, W., Lin, Y., and Yu, B. (2022). Fastgr: Global routing on epu-gpu with heterogeneous task graph scheduler. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
[27] Liu, W.-H., Kao, W.-C., Li, Y.-I.,, and Chao, K.-Y. (2013). 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):00--722.
[28] Mahboubi, S., Ninomiya, H., Kamio, T., Asai, H., et al. (2021). A nesterov's accelerated quasi- method for global routing using deep reinforcement learning. Nonlinear Theory and Its Applications, IEICE, 12(3)
[29] Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J. W., Songhori, E., Wang. S., Lee, Y.-.,, Johnson, E., Pathak, O., Nazi, A., et al. (2021). A graph placement methodology for fast chip design. Nature, 594(7862):077221.
[30] Nam, G.JJ,, Yildiz, M., Pan, D. Z., and Madden, H. (2007). Ispd placement contest updates and ispd 2007 global routing contest. In Proceedings of the 2007 international symposium on Physical design, pages 167-167.
[31] Ronneberger, O., Fischer, P., and Brox, T. (2015). U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assisted Intervention-MMICA. 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part IIl 18. pages 234-24442 23.-241. Springer.
[32] Utyamishev, D. and routes ics. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pages 1-2. IEEE.
(2020). Late breaking results: A neural network that
[33] Wu, T.-H., Davoodi, A., and Linderoth, J. T. (2010). Grip: Global routing via integer pro- gramming. JEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 30(1):72-84
[34] Xie, 7., Huang, Y.-H., Fang, G.-Q., Ren, H., Fang, S.-Y., Chen, Y., and Hu, J. (2018). Routenet: Routability prediction for mixed-size designs using convolutional neural network. In 2018 IEEE/ACM International Conference Computer-Aided Design (ICCAD), pages 1-8. IEEE.
[35] Zhou, Z., Zhu, Z., Chen, J., Ma, Y., Yu, B., Ho, T.-Y., Lemieux, G., and Ivanov, A. (2019). Congestion-aware global routing using deep convolutional generative adversarial networks. In 2019 ACM/IEEE 1st Workshop Machine Learning for CAD (MLCAD), pages 1-6. IEEE.
12

---

A
Related Information
(b)
(c)
Figure S1: Differences between hub points and candidate points. (a) Routing result (white lines)
generated by traditional global router for a 12-pin (black squares) net (b) The hub points (red
squares) extracted by [8] as their label points. (c) The candidate points (green squares) labeled by NeuralSteiner as the learning targets.
Table $1: Summary predicted candidate points for ISPD07. We respectively show the scale size, number of nets, average maximum number of pins and candidate points added by NeuralSteiner.
Case
adaptec01
adaptec02 2d
aduptect12 2d
adaptec14 24
adaptec05 2d
newblue01_
newbluel2__0
newblue03,
Size
324x:224
424x424
714x 779
774x7799
465 x466
x999
557x463
973x1256
Cap.
70/70
80
110/
/80
#Nets
219794
2601.59
466295
515304
86744]
331663
463211
551667
Avg. #Pins
4.29
4,09
4.022
3.71
4.03
3.73
3.83
3,50
Max sPins
2221
1935
3713
3974
9863
12335
8069
16008
APins 10
92.9092
94.03%
95.24%
96.09%
94.94%
95,50%
96.02%
97.12%
Avg. #Cands
4,61
4.41
4.76
4.34
4.31
3.86
3.88
3.56
#Cands
2474
2145
4189
4226
10681
13109
8517
16951
B Implementation details
B.1 NeuralSteiner Network Architecture.
We employ modified ResNet-34 structure [2] as the backbone of our model and combined it with the recurrent crisscross attention mechanism (RCCA) (14). Our network accepts two channels, pin map and overflow map, input, while the output is a single-channel map indicating the positions of the predicted candidate points. To retain more accurate spatial location details of feature maps for the construction of RST, we remove the max-pooling layer from the ResNet backbone. Every two residual blocks are grouped in one pair. Thanks the 3 x convolution, the number of channels gradually increasing from 2 to 256. After 4 pairs of residual blocks, convolutional layer is applied to dimension reduction. Then, H is fed into the RCCA module to generate
obtain the feature map new feature map HO which aggregate non-local contextual information. In RCCA module, we sequentially apply two crisscross attention modules and assign different weights (attention map) to each part of the feature. After the RCCA. we concatenate the feature HO processed by RCCA with the local and dimension-reducce feature X. It is followed by another 4 pairs of residual blocks with 3 x convolution and the number of channels gradually decreasing from 256 to 1. The output feature map undergoes sigmoid operation to obtain the final predicted candidate point map.
The crisscross attention (CCA) mechanism is adopted in NeuralSteiner to capture long- Long-range de- pendencies in feature maps and aggregate full-net spatial and overflow information by computing attention along both horizontal and vertical directions for each pixel, which is shown in Fig Given an input feature map X E Cx WW H. where C' is the number of channels, W and H the width and height respectively, the CCA starts by computing queries, keys, and values using 1 x convolutions
13

---

with weight matrices Wa Ws, and We:
Q = W * X, + == v=W, xX
W
Here, * denotes the convolution operation and where {Q, K} E RC" and V RC For each pixel (i, in the input feature map X, we use k(s))) to denote the set of feature vectors extracted from K which are in the same compute the horizontal attention weights A by applying the softmax function to the dot product of the query row and the key at position (i;
column with position (i.j) and ((,)) R first
d(s)), = Q(i)) ((.))..
where d(s.)). E D is the degree of correlation between ((.5)) and ((.,), k - W + 1]. Note that D [ (/)+---)x(W HH) we compute the attention map A by applying the softmax function to D. We also use ((, to denote the collection of feature vectors extracted from which in the same row or column with position (i, j). then the crisscross spatial and overflow information can be aggregated by:
Yon Σ A + X
The output feature map Y E RC is then returned the result of the crisscross attention mechanism. As shown Fig. 3, after two CCA operations, the information positions in different rows and columns from the coordinates (i,j) also be aggregated, thus enabling learning of long-range spatial and overflow correlation.
B.2 Training details for candidate point prediction phase.
We adopt CUGR (4 to conduct routing for dataset construction, and we choose bigblue04 3d, newblue03_3ee newblue04_ and newblue07_a0 2_ddd (name of the cases in ISPD-07) as the training cases and generate 25K training samples using each case, which is more than that in HubRouter [8]. Thus, we have total of nearly 100K for training.
We use learning rate in [0.001, 0.00001] and reduce the learning rates by 0.5 if the validation loss does not decrease in epochs. The training will continue until the validation loss no longer decreases for over 10 epochs or the number of epoch reaches a maximum of 100. In the training loss, use Cyt 1.0, cas = 1.0 and Caf = 2.0 to encourage the exploration of lower-overflow candidate points. The number of ResNet blocks is before the RCCA module and 8 behind
Each experiment in this work is conducted on a system equipped with an Intel(R) Xeon(R) Gold 6230R CPU, NVIDIA A800 (80 GB) GPU, and 250 GB RAM. We repeat 3 times under different seeds for HubRouter on the small nets test set and ISPD98 and report the error bars, and then choose the seed with best overflow for HubRouter (GAN) to conduct the ISPD07 experiment.
Algorithm 1 Training in candidate point prediction phase
Require: num_iters (number of training iterations), B (minibatch size), trainingSet (training set), Ctt. Cas. Cof (loss function coefficients)
Ensure: 0 (model parameters)
1: Initialize model parameters
2: for iter 1 to num iters do
3: Sample a batch B C trainingSet with [ = B
4: Pad all pin maps. overflow maps and label point maps in B the size
5: Descend the stochastic gradient of loss:
Vo leş &focal + Cas ldice + Cof Lofl
6: end for
7: return Model with parameters 0
14

---

B.3 Parallel Routing Tasks Construction.
Algorithm 2 Parallel routing tasks construction
1: Input: A set of nets N need to route in chip design where each net has corresponding HPWL.
A set of net tasks T.
2: N {net1, heet,....,nett...
3: T + +++ O}
4: Naorted +- Sort(N, by HPWL)
Sort nets by HPWL
5: for each net, E Nsorted do
6: assigned <- False
7: for each task; E T do
8:
if net, has conflicts with all net in tasky then
9:
laskj + lask, U [ne4]
assigned True break
11:
end end for
13:
if not assigned then
15:
new ask t- 0
newTask: newTask (net;)
17:
T (newTask)
18:
end
19:
end for
20:
return
B.4 Net Augmented Graph Construction.
Algorithm Net augmented graph construction
Require: Candidate point map C' (2D map), pin map P (2D map), overflow map (2D map).
Ensure: nel AulyneeneddGrappl (Graph).
1: mergedMap &- C
2: points +- {x, y) mergedMap =M[ 2 1}
3: AA +- empty graph
4: for all p points do
5: Add p as node NAG
6: end for
7: for all (pr. Py) E pairs(points) do
8: if pr.. = -2 or pi-y = Py-y then No other points on the line between and then weight calculate_ (eibblte_weigh((p.p))
9:
11: end
Add edge (p.. Pj, weight) to netAuggentedGraahh
13:
end if end for
15:
while number_of of connected
(nuuettttnnttttteeeeeeeeaaa > 1 do
Select one point from each connected component
17: Add edges between selected points
18:
end while
19: return nel. AugrenteddCrr
15

---

B.5
Overflow-avoiding RST Construction.
Algorithm 4 Ovverllo-AAvoidnng RST Construction
Require: NAG (Graph), Pins (Set of pins)
Ensure: RST (Constructed RST)
1: Components + {p) p E Pins}
2: Parallelize computation dist(Cs; Cÿ) for Ci, C3 E Components on AG
3: while |Cmmponent|] > 1 do
4:
C2),C2) + arg mincc.C, @Components dist( C2 C₃)
5: RST RST U ((C,
6: Gnew + C2
7:
Components & (Components \ {CI, C2)
8:
Delete dist (C₁, Ck) and dist (C2, C2) for all C E Components Update dist( new: Ck) for all Cj E Components in parallel Components < Components U {Cne
9:
10:
11:
end while
12:
return RST
Time complexity and scalability of the RST construction algorithm. We use Dijkstra's algorithm search for the shortest path between every two points. Suppose the number of pin in one net is N Npin- Given that NAG is a sparse graph, and the number of edges and nodes in the NAG is (N(p)))) according to Table SI Dijkstra's algorithm with a binary heap yields a time complexity of (O log Npin)). The total time complexity is (O((Npin)) log Npin)) to calculate the shortest path for all points in the connected component. In each iteration, we connect the two components with the shortest distance and update the distances matrix. It will end with connected component containing all pins. So, in the worst case, the total time complexity of the RST construction algorithm (O((N pén) log Npin)). Table S1 shows that the pin size for most of nets in dataset no more than 10, indicating that the algorithm will be efficient.
Additionally, the algorithm can be accelerated by simple heuristic rules. When calculating the distance from one connected component to another, we compute and filter out a fixed number of node pairs with the shortest Euclidean distance, performing Dijkstra's algorithm only on these limited node pairs. This reduces the complexity of the RST construction algorithm to t (O((Npan)) log ))pn)). )). As shown in Table S3 the accelerated algorithm NeuralSteiner-I significantly improves solving efficiency while achieving similar wirelength and overflow compared to the original version.
Algorithm 5 Inference Algorithm
Require: netlist (netlist), resources (routing resources)
Ensure: roules (routing results)
1: Initialize routes <- 0
2: // Parallel routing tasks construction
Trrrreouuuttngeessssooonnniiinnn 4: for each task & in T do
3: T' +
Using Algorithm
5:
// NeuralSteiner for candidate point prediction candidatePPinnt PointMaps +- NeuralSteiner(()
6:
Predict candidate point maps
7:
// Net augmented graph construction
8:
G <
Using Algorithm
9:
II Overflow OOverllo-Avvoiding RST Construction
routingResulls &- Overflow VverfoowAvodinRRSSSCooonnnnnoo
Using Algorithm
11:
Add routing Results to routes
12: end for
13: return routes
16

---

C
Additional Results
Figure S2: Comparison of actual solutions of Hubrouter (first line) and our NeuralSteiner (second line), randomly sampled from ibm01. Pins (black hollow square), hub points (yellow circle) candidate points (green circle) and the routes (purple line) are shown in figures.
Table S2: Experiments on kinds of small nets. We train three architectures of HubRouter with default settings and test the results of three different random seeds for each HubRouter model. NeuralSteiner tested three times obtain the mean and standard deviation values of generation time. The best results are highlighted in bold.
HubRouter (VAE)
HubRouter (DPM)
HubRouter (GAN)
Metric
Case
NeuralSteiner
Route-small-4
1.000 1 0.000
1.000
0.000
1.000 + 0.000
1.000
Correctness Rate (%)
Route-small
1.000 + 0.000
1.000
0.000
1.000 = 0.000
1.000
Route-large-4
1.000 + 0.000
1.000
0.000
1.000
= 0.000
1.000
Route-large
1.000 + 0.000
0.000 1.000
1.000 + 0.000
1.000
Route-small-4
1.086 + 0.031
1.072
0.020
1.012 + 0.011
1.003
Wirelength Rate (%)
Route-small
1.051 + 0.017
1.191
0.006
1.002 + 0.001
1.003
Route-large-4
1.124 + 0.026
1.102 + 0.039
1.004 + 0.021
1.002
Route-large
1.045 + 0.023
1.264 + 0.014
1.001 + 0.002
1.002
44
5.33 1: 0.09
514.71 1: 4.42
5.14 + 0.08
6.60
Generation Time
Route-small
5.68 0.14
506.20 2.99
6,63 + 0.35
7.01
(GPU Sec)
Route-large-4
5.41 0.15
511.42 + 2.85
5.68 + 0.16
6.89
Route-large
7.17
531.98 + 3.63
7.16 = 0.21
8.77
Table S3: Comparison of NeuralSteiner with limited connected component nodes (NeuralSteiner- Ltd) and original NeuralSteiner ISPD-98 (ibm01-06).
Metric
Model
ibm01
ibm02
ibm03
ibm04
ibm05
ibm06
NeuralSteiner
61735
170405
148036
166648
415684
283727
WL NeuralSteiner-Ltt
61654
170430
148730
166160
415872
283215
NeuralSteiner
2033
3953
1754
2794
18
3042
OF
NeuralSteiner-Ltd
2042
4046
1743
2883
18
3095
NeuralSteiner
24.75
33.18
41.94
46.63
67.52
63,44
Time (Sec)
NeuralSteiner-LId
13.68
31.84
21.20
23.30
47.65
36.26
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We make sure that the main claims made in the abstract and introduction accurately reflect the paper's contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations at the end of the main paper. We also add discus- sion about time complexity analysis of the RST construction algorithm Appendix. B.5..
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer: [NA]
Justification:
We don't 't have theoretical result in this paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We has introduced the details of implementation and training protocol.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
19

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Our source code and dataset will be released at https:///itthun com/
Liuruzzhio6//euuraalteeeeis
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Policy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccppblle wwwppppgpuuiiieeeep httpc///uuidess/deeuuuubiiis SooodeSubiissi.e ssiiiiolccyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We report error bars for HubRouter method which use random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
20

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We introduce these details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps:/neuurpss... http://aaaaap..cccooaaaacaaccaaa
Answer: [Yes]
Justification:
We make sure preserve anonymity.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets used in the paper, such as datasets and models, are properly credited with clear documentation of their sources and licenses, ensuring full compliance with existing terms of use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
22

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "kQt2FpGt13", "reviewer": "Reviewer_JcjD", "summary": "This paper presents a learning-driven approach for overflow avoiding Steiner tree construction. The authors propose a two-stage framework that initially predicts the locations of potential Steiner points, followed by a post-processing algorithm that constructs the Steiner tree based on these predicted points. The effectiveness of the proposed method is then evaluated through a series of experiments.", "questions": "1. The methodology presented in this work appears to align closely with prior works, such as Hubrouter, and employs trivial techniques. Could you please elaborate on the unique technical contributions of your study?\n\n2. The primary aim of this paper is to optimize overflow during the construction of the Steiner tree, a process that occurs prior to routing. However, there tends to be a significant difference between pre-routing and post-routing overflow. Additionally, most routing tools will also take overflow reduction into account. Hence, optimizing pre-routing overflow may not yield significant benefits. Could you please shed some light on this?\n\n3. In Section 3.4, could you clarify how the congestion value O(x,y) in Eq. (8) is calculated? From which stage are the O(x,y) values extracted? How are points that do not satisfy the two conditions handled? How are the values of the weights w_d and w_o in Eq. (8) determined?\n\n4. The paper lacks clarity regarding the evaluation metrics used. Could you specify the stage from which the overflow values are extracted, for instance, is it immediately after RST construction or after global placement? Could you also share the tool used for global routing during testing and whether it considers congestion?\n\n5. It would be beneficial if the authors could provide a comprehensive description of the test flow, including the source of the inputs, how the proposed framework integrates with the routing tool, and the stage from which the evaluation metrics are extracted.\n\n6. The results in Table 3 seems wield. The data suggests that overflow loss reduces both overflow and wirelength, which is unusual as these two metrics typically have a trade-off. If overflow loss is designed to reduce overflow, it should result in an increase in wirelength. Could you provide some clarification on this?\n\n7. I'm interested to know the number of Steiner points inserted by the proposed method. This is crucial as simple methods can also reduce overflow by adding more Steiner points to circumvent congested regions. However, an increase in Steiner points could significantly limit the optimization space of the subsequent routing process. Could you please include the number of Steiner points in the results tables?\n\n8. To enhance reader comprehension, could you provide an example of an actual solution?", "limitations": "Listed in questions.", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "1. The paper is well organized.\n2. Detailed background introduction is included.", "weaknesses": "1. The idea lacks novelty.\n2. Many important experimental settings are not disclosed.\n3. The experimental results are not convincing.\n4. The writing can be difficult to follow and occasionally confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful comments. Please note our global comment with additional experimental results. Below we will address specific questions. \n\n> **W1/Q1: Novelty and contribution of the method**\n\nThank you for your valuable comments. Here, we further elaborate on the novelty and contribution of our method in comparison to the previous HubRouter approach, highlighting the differences and innovations in motivation, workflow, and neural network architecture:\n\n1.\tThe motivation of NeuralSteiner is to construct overflow-avoiding RSTs based on the deep learning method, which is crucial for practical global routing applications, rather than merely ensuring connectivity and optimizing wirelength. \n\n2.\tWe utilize a ResNet-based backbone network to learn the encoding of the overflow and pin map (lines 160-164). Additionally, we introduce the RCCA mechanism to address long-range association issues in large-scale nets (lines 165-175) and the cost loss to encourage overflow-avoiding candidate points generation.\n\n3.\tCompared with other state-of-the-art learning-based methods. NeuralSteiner achieved a significant reduction in congestion with only a minimal sacrifice in wirelength quality of RSTs, fulfilling the motivation of our method.\n\n4.\tFurther experiments on ispd18/19 indicate that NeuralSteiner when combined with traditional routing tools, can effectively reduce the number of violations after detailed routing.\n\n> **W2/Q4/Q5: Experimental settings, evaluation metrics and test flow.**\n\nWe realize the\timportance of clarifying these issues. This could be refered to in the Q2 in global responses for the detailed discussion of the different experimental setup, the metrics extraction method, and different test flows that are integrated with abstract resource model or routing tools. \n\n> **W3: The convincingness of experimental results.**\n\nSince our environment resource modeling and dataset division are the same as those in previous works, we can make a fair comparison between the NeuralSteiner and other neural network-based RST generation methods on the same routing test set. \n\nTables 1, 2, and Figure 3 in the main paper compare the RST generation results of different methods on ISPD98 and ISPD07. NeuralSteiner achieves a significant reduction in congestion while maintaining wirelength quality, and it also demonstrates higher solving efficiency. Tables 3 and 4 explore the roles of our different design modules from various perspectives. \n\nExperimental results of integrating our method with the routing tool CUGR for global routing are shown in Table 2 in the rebuttal PDF, which indicates the potential of the NeuralSteiner method to reduce overflow when combined with routing tools.\n\nW4: Thanks again for your meticulous review and we will correct the confusing parts of the writing in the revised version.\n\n> **Q2: The necessity of optimizing pre-routing overflow.**\n\nAs you mentioned, the relationship between pre-routing congestion and post-routing congestion is quite complex. However, we still believe that optimizing pre-routing congestion is of significant importance:\n\n1.\tMany global routers use rip-up and reroute to eliminate the overflow caused by initially generated RSTs without considering congestion. Introducing congestion mitigation (such as NeuralSteiner) at the RST generation stage can provide a resource-friendly initial solution for subsequent stages.\n\n2.\tTable 2 in the rebuttal PDF shows that by integrating NeuralSteiner into CUGR, we achieve a 4.4% and 19.1% reduction in shorts and spaces, respectively, in the detailed routing results, with minimal losses in wirelength and vias. This demonstrates that our pre-routing overflow mitigation method is beneficial for reducing overflow in the post-routing results.\n\n3.\tThe latest routing tool DGR [1], introduces concurrent optimization techniques in the RST generation field, optimizing wirelength, vias, and congestion simultaneously. This also leads to a significant reduction in DRV in the detailed routing results, further supporting our opinion.\n\n> **Q3: Questions about Eq.8, overflow extraction, and edge conditions.**\n\nPlease refer to the Q4 in global responses for the detailed clarification of $O(x,y)$ and the parameters $w_d$ and $w_o$. \n\nAs shown in Figure 1(a)-(d) on page 2, the overflow map of the net with black pins is extracted in real time from the environmental model. \n\nThere will be no edges between points that do not meet both conditions. If this results in a disconnected NAG, we will add turning points and edges between the disconnected components according to the 2 conditions. \n\n> **Q6: The role of cost loss.** \n\nThank you very much for pointing out this informative detail. In our loss setting, we combine focal, dice, and cost loss. The first two primarily learn candidate points from expert routing data. The inclusion of cost loss introduces candidate points not present in the expert data, thereby altering the topology of the final RST generated. \n\nAdditionally, our post-processing method constructs RSTs using a greedy algorithm, which does not guarantee the shortest wirelength. Including cost loss provides a larger solution space for RST construction, enabling optimization of both wirelength and congestion. \n\n> **Q7: Include the number of Steiner points in the results tables.**\n\nThank you very much for your important suggestion. In Table 3 of the rebuttal PDF, we have summarized the predicted candidate points for ISPD07. The average number of candidate points added by NeuralSteiner is not significantly more than the average number of pins, which means that for the vast majority of nets, the number of nodes in the NAG will remain at a small scale.\n\n> **Q8: Could you provide an example of an actual solution:**\n\nThank you for your suggestion. We have added a comparison of the actual solutions between NeuralSteiner and Hubrouter in the rebuttal PDF. \n\nReference:\n\n[1] DGR: Differentiable Global Route, DAC 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z2KWDEpnBf", "reviewer": "Reviewer_1eER", "summary": "The paper presents NeuralSteiner, a method to improve chip design routing by minimizing overflow. Using a neural network to predict Steiner points and a graph-based algorithm for selection, ensures connectivity and reduces congestion. NeuralSteiner outperforms existing methods, achieving up to a 99.8% reduction in overflow with only a 1.8% increase in wire length, and scales effectively to large nets without needing modifications for new designs.", "questions": "1. In Table 2, do you compare the Boxrouter’s routing results?\n2. In Table S2, why the correctness rate is 100%. Is it due to the small problem size?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written and the figures are very easy to understand.\n2. The experiment was very thorough, comparing the routing results of different routers, and verifying the effectiveness of the method in optimizing overlap.\n3. The Overflow-avoiding RST Construction proposed by the author is novel and effective. Meanwhile, NeuralSteiner is the first learning-based approach capable of optimizing both wirelength and overflow.", "weaknesses": "1. Typo: line 282: “enven arger”->”even larger”\n2. It is recommended that the paper should be extended to a full 9 pages.\n3. According to the results, this method still faces challenges when optimizing the wire length and running time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful comments. Please note our global responses with additional experimental results. Below we will address specific questions.\n\nW1: Thanks again for your meticulous review, and we will correct typos in the revised version.\n\n> **W2: The paper should be extended to a full 9 pages.**\n\nThank you for your comments and for affirming our method. We will expand the article based on the constructive comments in subsequent revisions.\n\n> **W3: Challenges when optimizing the wire length and running time.**\n\nWe understand the reviewers' concerns about NeuralSteiner's optimization of wirelength and its scalability to large-scale nets. \n\nFirst, wirelength is also one of our important metrics. In the construction of NAG, wirelength is considered within the weight, which allows us to achieve minimal wirelength loss while significantly optimizing congestion. \n\nWe analyze the algorithm complexity of the overflow-avoiding RST construction algorithm in Q3 of global responses and use acceleration methods to further reduce it to $(O((N_{pin})^3 \\log N_{pin}))$. \n\nAdditionally, according to our latest statistics in Table 3 of the rebuttal PDF, NeuralSteiner does not add an excessive number of extra candidate points to construct the NAG, meaning that the number of nodes remains at the scale of $(O(N_{pin}))$. Therefore, the efficiency of this method will be very high for the vast majority of nets with fewer pins. For nets with more pins, heuristic methods such as subtree division can be used to reduce the computation time.\n\n> **Q1:  In Table 2, do you compare the Boxrouter's routing results?**\n\nWe understand the reviewers' concerns regarding the comparison of NeuralSteiner and traditional routers like Boxrouter. Boxrouter is not included in the ISPD07 results in Table 2 for the following reasons:\n\n1.\tUnlike ISPD98, the ISPD07 global routing competition considers not only the consumption of routing resources but also the consumption of resources by cross-layer vias (structures to connect segments in different layers, consuming routing resources). Boxrouter's reported wirelength results also include part of the via, making it numerically incomparable with neural network-based algorithm results.\n\n2.\tNeuralSteiner inherits the abstraction of the routing environment used in Hubrouter to consider the impact of routing segments on resources. However, this abstraction does not effectively model the effect of vias, making via optimization more challenging, which is a direction for future exploration and improvement.\n\n> **Q2:  Correctness rate is 100% in Table S2. Is it due to the small problem size?**\n\nThank you very much for your meticulous reading. The correctness of the net reflects the proportion of successfully connected nets in the test set, considering only connectivity. This metric comes from Hubrouter. Our method achieves 100% net correctness because our NAG-based RST construction algorithm ensures net connectivity, irrespective of the net size. In Table S2, we mainly aim to demonstrate that our method ensures connectivity like Hubrouter. Other methods, such as PRNet, fail to ensure connectivity for smaller nets and are therefore not included in Table S2 for comparison.\n\nPlease kindly let us know if you have any follow-up questions or areas needing further clarification. Your insights are valuable to us, and we stand ready to provide any additional information that could be helpful.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n8ejMtxMWx", "reviewer": "Reviewer_4X1w", "summary": "This paper tackles the challenging task of global routing in VLSI design, with the aim of addressing the overflow limitation inherent in current learning-based methodologies. The authors introduce NeuralSteiner, a novel approach that builds upon a previous method known as HubRouter. Like HubRouter, NeuralSteiner divides the global routing process into two stages: the first predicts the locations of probable candidate points, and the second connects these points and pins with a focus on minimizing overflow. In the first stage, NeuralSteiner introduces a new concept – the Candidate point, and generates an expert routing dataset using CUGR and ISPD07. This dataset is then used to train a neural network for the point prediction task. In the second stage, NeuralSteiner employs a straightforward and heuristic construction method that avoids overflow while ensuring connectivity.\nThe paper is well-structured, with clear motivations and easy-to-follow content. NeuralSteiner effectively addresses the significant overflow issue in learning-based global routing, making it applicable. Experimental results show that NeuralSteiner significantly reduces overflow, while maintaining comparable wirelength.", "questions": "- Given that the training set is within HPWL <= 128 or the scale of 64x64, how are NeuralSteiner and HubRouter applied to ISPD07 cases with much larger scales?\n- Besides the case newblue03 which is already included in the training dataset, I note that the performance of wirelength and overflow in Table 2 is also pretty good for the case ‘newblue1’, outperforming most traditional approaches. However, the overflow for the case ‘ibm01’ is 2033 in Table 3, which is much higher than traditional methods. What are the inherent reasons for this? For instance, the overflow for ‘ibm01’ and ‘newblue1’ are 0 and 400 respectively, while the corresponding results for NeuralSteiner are 2033 and 5.\n- Based on the above question, I am curious about what the WL and overflow are for newblue01 and newblue03 when using CUGR, the approach used to generate the expert routing dataset. \n- Is the RST construction conducted by Python or C++? \n- Will the code be made available upon acceptance of the paper?", "limitations": "Yes.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ NeuralSteiner is empirically proven to be effective in reducing overflow in the global routing task. Equipped with the CNN structure, NeuralSteiner is capable of recognizing the candidate points, and the RST construction further reduces overflow significantly.\n+ A parallel technique is proposed to route the non-conflicting nets simultaneously, which can relieve the time-consuming plight.\n+ The experiments show a significant improvement in overflow. In particular, for the case of newblue01, the wirelength and overflow both surpass most traditional global routing approaches.", "weaknesses": "- The paper lacks an analysis of time complexity in the construction stage, leaving uncertainty about the scalability of the second stage.\n- In the last paragraph of Section 3, a simple post-processing algorithm is proposed to shorten the wirelength, but it lacks detail and also misses the analysis of time complexity.\n- I note that the performance of wirelength and overflow in Table 2 is pretty good for the case ‘newblue3’. This could be potentially confusing as ‘newblue03’ is part of the training dataset.\n- Typo: Line 282, enven arger. \n- Suggestion: figure 2 could be moved to the next page to better correspond with Section 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and valuable feedback. Please note our global comment with additional experimental results. Below we will address specific questions.\n\n> **W1&W2: Analysis of time complexity in the construction stage.**\n\nWe understand the reviewer's concerns regarding NeuralSteiner's optimization of wirelength and algorithm complexity. In the Q3 of global responses, we analyze the time complexity of the RST construction algorithm. The time complexity for constructing an overflow-avoiding RST is $(O((N_{pin})^4 \\log N_{pin}))$ and we further reduce it using limited component nodes acceleration to $(O((N_{pin})^3 \\log N_{pin}))$. \n\nAdditionally, according to Table 3 in the rebuttal PDF, our NeuralSteiner method does not add an excessive number of extra candidate points to the nets. This means that the number of nodes in the NAG remains small-scale for nets occupying the majority with fewer pins. Therefore, this method will be very efficient for the vast majority of nets, and for nets with more pins, heuristic methods such as subtree division can be used to reduce the computation time.\n\n> **W3:  The performance of wirelength and overflow in Table 2 is pretty good for the case 'newblue3'. This could be potentially confusing as 'newblue03' is part of the training dataset.**\n\nThank you for pointing this out. We also realize that the use of names in ISPD07 datasets has caused some confusion. In fact, our datasets for testing and training do not overlap. \n\nOur experimental setup follows the work of Hubrouter, which combines ISPD07 and ISPD08 datasets into a single dataset and re-divides the training and test sets. Specifically, the 'newblue3_3d' (with 6 routing layers) nets from ISPD08 are routed using expert routers and included in the training set, while' newblue3_2d' (with 2 routing layers) nets from ISPD07 are in the test set. The 'newblue3' presented in Table 2 is the 'newblue3_2d' from ISPD07. We realize this is not clearly stated, and we appreciate the reviewer pointing it out. We will clarify this in the revised version by correcting it to 'newblue3_2d' from the ISPD07 dataset.\n\nW4: Thanks again for your meticulous review, and we will correct typos in the revised version.\n\n> **W5: Figure 2 could be moved to the next page to better correspond with Section 3.**\n\nThank you very much for your suggestion. We will move Figure 2 to the relevant section in the revised version to improve readability.\n\n> **Q1: How are NeuralSteiner and HubRouter applied to ISPD07 cases with much larger scales?**\n\nBoth our NeuralSteiner method and the networks used in Hubrouter employ a CNN-based backbone without including structures like fully connected layers that require fixed input sizes. Therefore, the trained network weights can accept inputs of any spatial shape. However, there still exist generalization issues. To mitigate the generalization problems brought by large-scale nets (such as non-locality relations between different pins), we introduce the RCCA mechanism in Section 3.3 (lines 166-175) and App. B.1.\n\n> **Q2: Different performance on ibm01 and newblue01.**\n\nThank you very much for your detailed reading and questions. We have clarified the source of the newblue3_2d test set in response to W3. \n\nRegarding the comparison between NeuralSteiner and Boxrouter on ibm01 and newblue01_2d, it is evident from Table 6 in App. D.1 of Hubrouter and Table S1 in App. A of our paper that the ibm01 has fewer routing resources and more average pins, while is much smaller than newblue01_2d. This poses a challenge for the NeuralSteiner method. However, Boxrouter's Robust Negotiation-Based A* Search allows nets to bypass resource-constrained areas over a larger range, reflected in Boxrouter's longer wirelength (62659). \n\nIn the case of newblue01_2d, due to the ISPD07 competition setup, Boxrouter's wire length and congestion are also influenced by vias (a cross-layer connection structure), making direct comparison with NeuralSteiner impractical, which is the reason why we do not include it in Table 2 for comparison.\n\n> **Q3: Results of CUGR.**\n\nThe ISPD07 data format does not match the input format required by CUGR. We input the net information obtained through FLUTE + edge shifting and the corresponding resource distribution into CUGR, invoking its rip-up and reroute algorithm to construct congestion-free nets. The wirelengths for newblue01_2d and newblue03_2d are 2,462,361 and 7,655,784, respectively, with congestion values of 0 and 29,683.\n\n> **Q4: Is the RST construction conducted by Python or C++?**\n\nOur overflow-avoided RST construction algorithm is primarily implemented in C++.\n\n> **Q5: Will the code be made available upon acceptance of the paper?**\n\nThank you very much for your interest in our method. Yes, our code will be open-sourced.\n\nPlease kindly let us know if you have any follow-up questions or areas needing further clarification. Your insights are valuable to us, and we stand ready to provide any additional information that could be helpful.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kq5k4JOcSO", "reviewer": "Reviewer_1MAW", "summary": "This paper proposes NeuralSteiner, a two-phase global routing scheme to optimize both wirelength and overflow. It also demonstrate capability of generalization on unseen large-scale circuits. Experiments on public benchmarks show NeuralSteiner reduces 99.6 \\% in overflow with a wirelength increase of 1.8 \\%.", "questions": "1. Where is the edge weight in NAG used?\n2. How to calculate the \"distance\" mentioned in line 222 to select the two nearest connected components?\n3. In line 154, the authors mention they use CUGR to perform global routing to construct the congestion-avoid datasets. And they also propose some algorithms such as NAG, overflow-avoided RST construction algorithm. Between the datasets and algorithms, which one is the key to the overflow reduction of NeuralSteiner?", "limitations": "RST construction still relys on heuristics post-processing algorithm, but this could be leave for future work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. NeuralSteiner proposes a scheme to realize partial parallel routing tasks by group nets whose bounding boxes share no common area or overlap.\n2. NeuralSteiner is able to optimize the overflow in global routing. It utilizes SOTA global router CUGR to perform global routing stage and construct expert datasets. These routing results are congestion-avoided, assisting the candidate prediction model to learn the position of Steiner points and corner points.\n3. Besides, it also proposes NAG representation and a RST construction algorithm to reduce the overflow in global routing.", "weaknesses": "1. Typos in line 282: \"enven arger than 2000\".\n2. NeuralSteiner is not an end-to-end approach, still relying on the post-processing/greedy algorithm to construct the final routing results. But this greedy algorithm is simple and efficient, and utilizing deep learning for RST construction is leaved for future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and valuable feedback. Please note our global comment with additional experimental results. Below we will address specific questions.\n\nW1: Thanks again for your meticulous review, and we will correct typos in the revised version.\n\n> **W2: NeuralSteiner is not an end-to-end approach, still relying on the post-processing/greedy algorithm to construct the final routing results.**\n\nWe understand the reviewer's concerns about NeuralSteiner not being an end-to-end method. The complexity of obstacle-avoiding Steiner tree generation in global routing makes it very challenging for the neural network to simultaneously optimize wirelength and congestion, and ensure connectivity in an end-to-end manner. \n\nMethods like PRNet [1] and [3] have attempted to merge these tasks using a single network but faced significant connectivity issues. Hubrouter [2] addresses these two tasks with different networks, solving the problems of RST connectivity and wirelength optimization. \n\nOur NeuralSteiner method achieves optimization of wirelength and congestion simultaneously through a two-stage setup. However, since the existing candidate points still need to be processed as discrete values for subsequent RST construction, differentiable learning is difficult to apply. In the future, we will explore the efficient generation of overflow-avoiding RSTs using an end-to-end neural network.\n\n> **Q1: Where is the edge weight in NAG used?**\n\nIn Section 3.4, Eq.8 defines the weights used for edges in the NAG. \n\nThese weights consider both the wirelength and the congestion the edge passes through, with parameters $w_d$ and $w_o$ reflecting the trade-off between the two. We used $w_d = 1$ and $w_o = 2$ in all experiments. However, we realize that the usage of the symbol $O(x,y)$ causes some confusion, as it has the same meaning as $o_{ij}$ in Eq.6 of Section 3.3, representing the value of the overflow map at that location. We will clarify this ambiguity in future revisions.\n\n> **Q2: How to calculate the \"distance\" mentioned in line 222 to select the two nearest connected components?**\n\nWhen calculating the distance between two connected components, we compute the shortest path length on the NAG connecting any two points belonging to the different two components respectively (where the path length is the sum of the weights of all edges on that path). The minimum of all these shortest path lengths is taken as the distance between the two connected components. \nPlease refer to the Q3 in global responses for detailed analysis of RST construction algorithm and the acceleration methods.\n\n> **Q3: Between the datasets and algorithms, which one is the key to the overflow reduction of NeuralSteiner?**\n\nThank you for raising this question. We believe it is of significant importance to the advancement of this field. In Section 3.3, we use the expert router CUGR to solve the routing results of nets under congestion and construct an expert routing dataset. The neural network learns from this expert dataset, enabling its output to form candidate points for potential low-congestion RSTs, and provides a solution space for subsequent NAG and the overflow-avoiding RST construction algorithm.\n\nThe NAG and the corresponding RST construction algorithm use a greedy algorithm within this solution space to find the final routing result that ensures connectivity while optimizing wirelength and congestion. As shown in the ablation experiments Table 3 and Table 4 for adaptec05, even though the inclusion of NAG and the RST construction algorithm significantly reduces OF without using the candidate points generated by neural network, the addition of the neural network trained on the expert dataset further avoids 95% of the remaining challenging congestion.\n\n> **L: RST construction still relys on heuristics post-processing algorithm, but this could be leave for future work.**\n\nAs mentioned in reply to Q1 in the global responses and our response to W2, the inclusion of current heuristic post-processing is due to the multi-task nature of overflow-avoiding global routing. We hope to explore more efficient end-to-end approaches in the future to replace the existing heuristic post-processing schemes.\n\n\nPlease kindly let us know if you have any follow-up questions or areas needing further clarification. Your insights are valuable to us, and we stand ready to provide any additional information that could be helpful.\n\n\nReference:\n\n[1] The policy-gradient placement and generative routing neural networks for chip design, NIPS 2022.\n\n[2] HubRouter: Learning Global Routing via Hub Generation and Pin-hub Connection, NIPS 2023.\n\n[3] Late breaking results: A neural network that routes ics, DAC 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Area Chairs and Reviewers,

We would like to thank all reviewers for providing constructive feedback that helps us improved the paper. We are encouraged that the reviewers acknowledge the novelty (4X1w, 1MAW), effectiveness (4X1w, 1eER, 1MAW) of our approach, thoroughness of our experiments (4X1w, 1eER) and are interested in the comparison and integration with traditional routers (JcjD, 1eER). We particularly appreciate the recognition of our significant improvements in overflow over state-of-the-art learning-based methods (4X1w, 1eER, 1MAW), the affirmation of our method's generalization capabilities (1MAW), and the acknowledgment of our method's contributions to the field (4X1w, 1eER).

Beyond the positive feedback, some concerns from the reviewers are common, so we give the following global responses:

**Please see the attached PDF for a one-page PDF with a summary of added experimental results.**

> **Q1: Why not adopt an end-to-end model?**

 We understand the reviewers' concerns regarding NeuralSteiner not being an end-to-end approach. This is determined by the complexity of the global routing problem, which requires learning-based methods to 1) learn the representation of routing resource, and 2) generate routing result that ensures connectivity of all pins while minimizing wirelength and overflow. NeuralSteiner achieves the first goal by learning the expert candidate Steiner points and corner points. However, processing these candidate points as discrete values for subsequent RST construction makes differentiable learning challenging.

 Our NeuralSteiner method significantly outperforms other end-to-end methods such as PRNet [1] and two-stage methods like HubRouter [2] in terms of total time cost and overflow. In the future, we will explore using continuous probabilistic candidate point maps and investigate end-to-end learning with neural networks for generating overflow-avoiding RSTs.

> **Q2: Experimental setup and comparison with routing tools.**

 First, our environment modeling of routing resources is consistent with HubRouter [2]. Metal layers are projected onto a 2-dimensional grid graph with a horizontal and a vertical layer. The NeuralSteiner interacts with this resource model, extracting overflow map in real-time and updating the resource of corresponding edges in the model based on the routing results (Figure 2).

 Second, NeuralSteiner extracts the metrics by calculating the total wirelength and overflow in the environmental model after routing all nets. This metric extraction method is also the same as that in previous work [2].
 
 Third, we do not integrate our method with routing tools in the main experiments of the paper because they mainly evaluate the metrics above of the RSTs generated by different learning-based methods. 

Finally, the comparative experimental results of integrating our method with the routing tool CUGR for global routing are shown in Table 2 in the rebuttal PDF. In these experiments, the RSTs generated by NeuralSteiner replace the RSTs generated by FLUTE + edge shifting in CUGR, and subsequent detailed routing is performed using DRCU. The results on larger ISPD18/19 benchmarks confirm the potential of the NeuralSteiner method to reduce overflow when applied to routing tools.

> **Q3: Time complexity and scalability of the RST construction algorithm.**

 The distance between two connected components is the sum of the edge weight of the shortest path between any two points from each component. Here, we use Dijkstra's algorithm to search for the shortest path between every two points. Given that NAG is a sparse graph, and the number of edges and nodes in the NAG is $(O(N_{pin}))$ according to table 3 in the rebuttal PDF, Dijkstra's algorithm with a binary heap yields a time complexity of $(O(N_{pin} \log N_{pin}))$. The total time complexity is $(O((N_{pin})^2 \log N_{pin}))$ to calculate the shortest path for all points in the connected component. In each iteration, we connect the two components with the shortest distance and update the distances matrix. It will end with a connected component containing all pins. So, in the worst case, the total time complexity of the RST construction algorithm is $(O((N_{pin})^4 \log N_{pin}))$.

 Table 3 in the rebuttal PDF shows that the pin size for most of nets in dataset is no more than 10, indicating that the algorithm will be efficient.
 
 Additionally, the algorithm can be accelerated by simple heuristic rules. When calculating the distance from one connected component to another, we compute and filter out a fixed number of node pairs with the shortest Euclidean distance, performing Dijkstra's algorithm only on these limited node pairs. This reduces the complexity of the RST construction algorithm to $(O((N_{pin})^3 \log N_{pin}))$. As shown in Table 1 in the rebuttal PDF, the accelerated algorithm significantly improves solving efficiency while achieving similar wirelength and overflow compared to the original version.

> **Q4: Parameters used in NAG's edge weight.**

 We realize that the use of the $O(x,y)$ in Eq.8 may be misleading. It is identical in meaning to $o_{ij}$ in Eq.6 in Section 3.3, representing the value at the corresponding position on the overflow map. Eq.8 defines the weights used for edges in the NAG. These weights consider both the wirelength and the congestion that the edge traverses, with parameters $w_d$ and $w_o$ reflecting the trade-off between them. In all experiments, we use $w_d = 1$ and $w_o = 2$. We will explicitly state this in Section 3.4 and make this revision in the final version.

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

Reference:

[1] The policy-gradient placement and generative routing neural networks for chip design, NIPS 2022

[2] HubRouter: Learning Global Routing via Hub Generation and Pin-hub Connection, NIPS 2023.

Meta-review: The paper has been accepted due to its significant contributions to the field of global routing in VLSI design. The proposed method, NeuralSteiner, offers innovative techniques for addressing overflow problems and optimizing wirelength, which are well-demonstrated through rigorous experiments and detailed comparisons with existing methods. The responses to the reviewer questions have clarified the concerns effectively, reinforcing the paper's value and novelty. The decision to accept is supported by the reviewer's appreciation of the method's generalization capabilities and its potential impact on practical applications in chip design. The provision of the source code upon acceptance promises further validation and replication of the results, enhancing the paper's reproducibility and transparency.
Decision: Accept (poster)