| As the feature size of modern large-scale integrated circuit(IC)designs continues to shrink,the circuit component and interconnect density increase,leading to frequent congestion issues in the routing regions.To address this challenge,there are two approaches: firstly,introducing a fast and high-quality global routing congestion map during the placement phase to enhance the routability of the IC,and secondly,reducing routing congestion during the global routing phase to guide the generation of legal solutions in detailed routing.However,current global routing algorithms suffer from the following issues: if they focus too much on guiding detailed routing,they require longer execution times,while if they emphasize layout guidance,they generate many congestion estimation errors.In this paper,after investigating relevant theories and algorithms in the field of global routing,we propose a congestion-aware global routing algorithm.This algorithm not only effectively reduces routing congestion and generates high-quality solutions to guide detailed routing but also greatly improves the routing speed.This algorithm accurately estimates routing congestion and serves as a guiding tool for routabilitydriven layout.The main contributions are as follows:Firstly,this paper investigates the multi-source multi-sink maze routing algorithm and designs a two-stage dual-path multi-source multi-sink maze routing algorithm,which effectively reduces the routing search space and improves routing efficiency.Subsequently,based on this,a deterministic dual-path maze routing algorithm is proposed,which satisfies deterministic requirements while ensuring routing quality,and the effectiveness of the algorithm is demonstrated.Secondly,through the study of weakly consistent parallel routing algorithms,this paper proposes a new net-level routing algorithm that not only demonstrates faster routing efficiency on machines with the same number of cores but also improves the overall convergence performance of the algorithm in multi-core devices.Next,a dynamic routing scheduling algorithm is proposed to synchronize the different stages of the routing network iteration,solving network conflicts in routing paths when utilizing the mutually exclusive routing regions in the network search space,thereby avoiding congestion that cannot converge.Finally,combined with the maze routing,routing efficiency is further improved,and routing conflicts are reduced.Lastly,this paper combines net-level routing with dynamic routing and designs a twostage routing framework.In the first stage,the algorithm performs net-level routing and then switches to the dynamic routing scheduling algorithm by controlling the parallelism using a designed parallelism reduction algorithm.This routing framework effectively controls routing congestion while improving routing efficiency.As a combinatorial optimization problem,this paper deeply investigates from basic routing algorithms to iterative routing algorithms and designs a congestion-aware global routing algorithm.In the experiments on the ISPD-08 test cases,the proposed algorithm achieves nearly optimal routing quality and significantly outperforms all other routing algorithms in terms of routing speed.This algorithm achieves low congestion and high efficiency,satisfying the requirements of guiding routabilitydriven placement and detailed routing. |
