HubRouter: Learning Global Routing via Hub Generation and Pin-hub Connection

Global Routing (GR) is a core yet time-consuming task in VLSI systems. It recently attracted efforts from the machine learning community, especially generative models, but they suffer from the non-connectivity of generated routes. We argue that the inherent non-connectivity can harm the advantage of its one-shot generation and has to be post-processed by traditional approaches. Thus, we propose a novel definition, called hub, which represents the key point in the route. Equipped with hubs, global routing is transferred from a pin-pin connection problem to a hub-pin connection problem. Specifically, to generate definitely-connected routes, this paper proposes a two-phase learning scheme named HubRouter, which includes 1) hub-generation phase: A condition-guided hub generator using deep generative models; 2) pin-hub-connection phase: An RSMT construction module that connects the hubs and pins using an actor-critic model. In the first phase, we incorporate typical generative models into a multi-task learning framework to perform hub generation and address the impact of sensitive noise points with stripe mask learning. During the second phase, HubRouter employs an actor-critic model to finish the routing, which is efficient and has very slight errors. Experiments on simulated and real-world global routing benchmarks are performed to show our approach's efficiency, particularly HubRouter outperforms the state-of-theart generative global routing methods in wirelength, overflow, and running time. Moreover, HubRouter also shows strength in other applications, such as RSMT construction and interactive path replanning. * Correspondence author. This work was partly supported by China Key Research and Development Program (2020AAA0107600), NSFC (62222607) and SJTU Scientific and Technological Innovation Funds. 2 Another routing task called detailed routing [3] is orthogonal to this work. To our knowledge, there is so far no learning-related work on problems whose scale is even much larger than global routing (see example in [6] ). 37th Conference on Neural Information Processing Systems (NeurIPS 2023). Model Type Multi-pin Connectivity Scalability Generative ∆ * HubRouter (ours) Generative * Scalable for one-shot generation, but not scalable for post-processing. Traditional works [8, 24, 36, 43] adopt (strong) heuristics to greedily solve global routing. However, the diversity and scale could pose new challenges to classical algorithms, which call for strategy updating and improvement by human experts on a continuous basis. To mitigate the reliance on manual efforts and facilitate the overall design automation and quality, machine learning has been adopted for global routing, as one of its diverse applications in chip design ranging from logic synthesis [40, 39] to placement [32, 28] , etc. Specifically, deep reinforcement learning (DRL) [31, 35] and generative models [48] have been adopted to tackle global routing (sometimes also along with other tasks, e.g., placement [6] in the design pipeline). However, DRL methods suffer from large state space and often need to spend enormous time on generating routes as the scale of grids increases on the test instance, i.e., the netlist, which is practically intimidating for real-world global routing. The generative approaches can be more computationally tractable due to the potential one-shot generation capability and train/test the model on different instances. In fact, the generative models have recently been adopted in different design tasks [5, 56] beyond EDA (partly) for its higher efficiency compared with the iterative RL-based decision-making procedure, while a common challenge is how to effectively incorporate the rules and constraints in the generative models. However, though generative global routing approaches [6] inject connectivity constraints into the training objective, they often degenerate to an exhaustive search in post-processing when the generated initial routes fail to satisfy connectivity, as shown in Fig. 1 . Our experimental results will show that the routes for difficult nets have a very low average connectivity rate of less than 20%, which means that over 80% generated routes for difficult nets require time-consuming post-processing. This greatly harms the inference time and indicates a serious challenge for the routing problem.