NeuralSteiner: Learning Steiner Tree for Overflow-avoiding Global Routing in Chip Design

Thank you for your detailed review and valuable feedback. Please note our global comment with additional experimental results. Below we will address specific questions.

W1: Thanks again for your meticulous review, and we will correct typos in the revised version.

W2: NeuralSteiner is not an end-to-end approach, still relying on the post-processing/greedy algorithm to construct the final routing results.

We 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.

Methods 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.

Our 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.

Q1: Where is the edge weight in NAG used?

In Section 3.4, Eq.8 defines the weights used for edges in the NAG.

These 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.

Q2: How to calculate the "distance" mentioned in line 222 to select the two nearest connected components?

When 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. Please refer to the Q3 in global responses for detailed analysis of RST construction algorithm and the acceleration methods.

Q3: Between the datasets and algorithms, which one is the key to the overflow reduction of NeuralSteiner?

Thank 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.

The 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.

L: RST construction still relys on heuristics post-processing algorithm, but this could be leave for future work.

As 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.

Please 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.

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.

[3] Late breaking results: A neural network that routes ics, DAC 2020.

Thank you for your detailed review and thoughtful comments. Please note our global responses with additional experimental results. Below we will address specific questions.

W1: Thanks again for your meticulous review, and we will correct typos in the revised version.

W2: The paper should be extended to a full 9 pages.

Thank you for your comments and for affirming our method. We will expand the article based on the constructive comments in subsequent revisions.

W3: Challenges when optimizing the wire length and running time.

We understand the reviewers' concerns about NeuralSteiner's optimization of wirelength and its scalability to large-scale nets.

First, 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.

We 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}))$.

Additionally, 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.

Q1: In Table 2, do you compare the Boxrouter's routing results?

We 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:

1. Unlike 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.

2. NeuralSteiner 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.

Q2: Correctness rate is 100% in Table S2. Is it due to the small problem size?

Thank 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.

Please 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.

Thank you for your detailed review and valuable feedback. Please note our global comment with additional experimental results. Below we will address specific questions.

W1&W2: Analysis of time complexity in the construction stage.

We 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}))$.

Additionally, 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.

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.

Thank 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.

Our 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.

W4: Thanks again for your meticulous review, and we will correct typos in the revised version.

W5: Figure 2 could be moved to the next page to better correspond with Section 3.

Thank you very much for your suggestion. We will move Figure 2 to the relevant section in the revised version to improve readability.

Q1: How are NeuralSteiner and HubRouter applied to ISPD07 cases with much larger scales?

Both 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.

Q2: Different performance on ibm01 and newblue01.

Thank you very much for your detailed reading and questions. We have clarified the source of the newblue3_2d test set in response to W3.

Regarding 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).

In 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.

Q3: Results of CUGR.

The 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.

Q4: Is the RST construction conducted by Python or C++?

Our overflow-avoided RST construction algorithm is primarily implemented in C++.

Q5: Will the code be made available upon acceptance of the paper?

Thank you very much for your interest in our method. Yes, our code will be open-sourced.

Please 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.

Thank you for your detailed review and thoughtful comments. Please note our global comment with additional experimental results. Below we will address specific questions.

W1/Q1: Novelty and contribution of the method

Thank 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:

1. The 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.

2. We 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.

3. Compared 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.

4. Further experiments on ispd18/19 indicate that NeuralSteiner when combined with traditional routing tools, can effectively reduce the number of violations after detailed routing.

W2/Q4/Q5: Experimental settings, evaluation metrics and test flow.

We realize the importance 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.

W3: The convincingness of experimental results.

Since 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.

Tables 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.

Experimental 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.

W4: Thanks again for your meticulous review and we will correct the confusing parts of the writing in the revised version.

Q2: The necessity of optimizing pre-routing overflow.

As 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:

1. Many 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.

2. Table 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.

3. The 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.

Q3: Questions about Eq.8, overflow extraction, and edge conditions.

Please refer to the Q4 in global responses for the detailed clarification of $O(x,y)$ and the parameters $w_d$ and $w_o$.

As 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.

There 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.

Q6: The role of cost loss.

Thank 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.

Additionally, 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.

Q7: Include the number of Steiner points in the results tables.

Thank 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.

Q8: Could you provide an example of an actual solution:

Thank you for your suggestion. We have added a comparison of the actual solutions between NeuralSteiner and Hubrouter in the rebuttal PDF.

Reference:

[1] DGR: Differentiable Global Route, DAC 2024