EDA² | ISEDA 2024

Innovative Pathways in Routing

Abstract: In recent years, the escalating integration density of electronic devices has presented formidable challenges for Printed Circuit Boards (PCBs), with routing emerging as a particularly intricate and labor-intensive aspect. In this work, we introduce a new routing method, PCB-Router-GPT (PRG), leveraging Generative Pre-Trained Transformers (GPT) in the PCB domain.Our approach tokenizes routing patterns, transforming the rout_x0002_ing process into token encoding, facilitating database creation akin to a language model. PRG employs a fusion structure,integrating start and end position information with current flow encoding to predict flow encoding for each wire. In contrast to traditional methods relying on trial and error, PRG’s pre-training phase learns from expert human routing, summarizing routing patterns effectively. Moreover, PRG resolves wire entanglement issues encountered in traditional routing by employing a parallel routing strategy, enhancing efficiency. Utilizing a Transformer architecture enables GPU acceleration, leading to significant improvements in routing density and speed, achieving state-ofthe-art (SOTA) levels.

Abstract: Recently, chiplet-based designs, also called multi-die systems, have gained significant attention in the semiconductor industry as a promising alternative to extend the Moore’s Law in the third dimension. However, the difficulty of interoperability between chips from different vendors has posed a significant challenge for the successful design and operation of multi-die systems. Universal Chiplet Interconnect Express (UCIe) has been proposed to address this issue by standardizing die-to-die connectivity in multi-die systems, which brings new challenges to the die-to-die interconnection problem. This paper presents the first fast and efficient routing method, called LoopRoute, for die-to-die interconnections under the UCIe standard, which significantly accelerates the routing process and enhances routing scalability for large-scale multi-die systems. Compared with the integer linear programming (ILP)-based method, LoopRoute achieves a speedup of more than 200×, while the wirelength increment is less than 0.08%. LoopRoute also shows promise in routing large-scale problems with up to 100k nets efficiently.

Abstract: Escape routing is a crucial step in printed circuit board (PCB) design. In response to the issues of low wiring efficiency in large-scale pin array circuit board routing where multiple devices synchronization is not considered in the current escape algorithm, this paper proposes a simultaneous escape routing algorithm based on weighted maximum independent set. Firstly, a path conflict graph is constructed by projecting paths correlated to pin pairs, followed by obtaining layered ordering results using the weighted maximum independent set model. Subsequently, channel estimation and channel optimization are performed using depth-first search in different directions. Finally, an escape routing is conducted using a detailed grid-based wiring method. Experimental results demonstrate that the proposed algorithm achieves a near 100% successful routing rate for largescale pin array PCB cases. It outperforms the minimum cost multi-commodity flow (MMCF) algorithm and the sequential escape algorithm with estimated functions by an average improvement of 10% in wire length.

Abstract: Routing is the most time-consuming phase in the physical design of modern integrated circuits. A carefully designed global routing needs to maximize the routability for the detailed routing while minimizing the wire length and the number of vias. In this paper, we propose a gradient ascent algorithm to solve the 3D global routing ILP model. This algorithm uses the Lagrangian-based cost update method that can more accurately reflect congestion for guiding the global router to generate a solution with fewer vias and congestion. In the gradient ascent rip-up and reroute stage, we use a DAG-based multi-pattern routing strategy to handle highly congested nets with constructed multiple routing patterns. Furthermore, we propose a congestion-aware dynamic net ordering algorithm to improve the congestion convergence of the rip-up and rerouting stage. Experimental results on ICCAD'19 contest benchmarks show that, on average our global router obtains high-quality results, reducing the number of vias by over 1% and 370.6% reduction in DRVs compared to CUGR 2.0, and outperforms TritonRoute-WXL's global routing in terms of runtime consumption and the number of vias.

Abstract: In modern very large-scale integration (VLSI) design, the solution quality of the bus routing is a crucial factor that determines the timing and power of circuit, and finally affects the performance and yield of chips. Taking bus deviation as the main optimization objective, an effective multi-strategy bus deviation driven layer assignment algorithm is proposed to solve the timing-matching problem of bus routing. First, a net priority determination method that integrates multiple features is presented to determine the layer assignment order, thus obtaining a routing sequence which can weigh the wirelength and bus deviation well. Second, an effective single net layer assignment algorithm is proposed to assign each net based on dynamic programming, thus reducing the number of vias. Third, a layer shifting strategy based on the bus lookup table is designed to effectively balance total wirelength and bus deviation by sacrificing a certain number of vias. Experimental results, compared to existing work, show that the proposed algorithm can achieve significant optimization on the bus deviation and total wirelength, and finally obtain the best results in terms of the bus deviation, which is the most important optimization objective for bus routing.